Computer Science and Automation, IISc, Bangalore, Prof. Dr. D. P.

Patil E0 219 Linear Algebra and Applications / August-December 2011

E0 219 Linear Algebra and Applications / August-December 2011

(ME, MSc. Ph. D. Programmes)
Download from : http://www.math.iisc.ernet.in/patil/courses/courses/Current Courses/...
Tel : +91-(0)80-2293 2239/(Maths Dept. 3212) E-mails : dppatil@csa.iisc.ernet.in / patil@math.iisc.ernet.in
Lectures : Monday and Wednesday ; 11:30–13:00 Venue: CSA, Lecture Hall (Room No. 117)

Corrections by : Jasine Babu (jasinekb@gmail.com) / Nitin Singh (nitin@math.iisc.ernet.in) /

Amulya Ratna Swain (amulya@csa.iisc.ernet.in) / Meghana Mande (meghanamande@gmail.com) /
Achintya Kundu (achintya.ece@gmail.com)
1-st Midterm : Saturday, September 17, 2011; 10:30 -12:30 2-nd Midterm : Saturday, October 22, 2011; 10:30 -12:30
Final Examination : December ??, 2011, 10:00 -13:00

Evaluation Weightage : Assignments : 20% Midterms (Two) : 30% Final Examination : 50%

4. Dimension of vector spaces

Submit a solution of the ∗-Exercise ONLY
Due Date : Monday, 05-09-2011 (Before the Class)
Let K be arbitrary field and let K denote either the field R or the field C.
4.1 Let ω ∈ R× + be a fixed positive real number. For a ∈ R and ϕ ∈ R, let f a , ϕ : R → R be the
function defined by t 7→ a sin (ω t + ϕ) and let W := { fa , ϕ | a, ϕ ∈ R}. Then W is a R-subspace
of the R-vector space RR of all R-valued functions on R.
(a) Find a R-basis of the R-subspace W . What is the dimension DimRW ? (Hint : The functions
t 7→ sin ω t and t 7→ cos ω t = sin(ω t + π/2) form a basis of W . — Remark: Elements of W are called
h a r m o n i c o s c i l l a t i o n s with the c i r c u l a r f r e q u e n c y ω.)
(b) Show that every f 6= 0 function in W has a unique representation
f (t) = a sin (ω t + ϕ) , a>0 and 0 ≤ ϕ < 2π .
(Remark : This unique a is called the a m p l i t u d e and ϕ is called the p h a s e a n g l e of f . The zero
function has the amplitude 0 and an arbitrary phase angle.)
(c) From the amplitudes and the phase angles of two harmonic oscillations f and g, compute the
amplitudes and the phase angles of the functions f ± g.
4.2 Let V be a K-vector space of dimension n ∈ N.
(a) If H1 , . . . , Hr are hyper-planes in V , then show that DimK (H1 ∩ · · · ∩ Hr ) ≥ n − r .
(b) If U ⊆ V is a subspace of codimension r, then show that there exist r hyper-planes H1 , . . . , Hr
in V such that U = H1 ∩ · · · ∩ Hr .
∗ 4.3 Let x1 = (a11 , . . . , a1n ) , . . . , xn = (an1 , . . . , ann ) be elements of Kn with
n
|aii | > ∑ |a ji | for all i = 1, . . . , n.
j=1, j6=i
Show that x1 , . . . , xn is a basis of Kn . (Hint : It is enough to show the linear independence of x1 , . . . , xn .
For this, suppose that b1 x1 + · · · + bn xn = 0 with |bi | ≤ 1 for all i and bi0 = 1 for some i0 . This already
contradicts the give condition for i0 .)
4.4 Let x1 , . . . , xn ∈ Zn be arbitrary vectors with integer components. For every λ ∈ Q \ Z, the
vectors x1 +λ e1 , . . . , xn +λ en form a basis of Qn . (Hint : Suppose a1 (x1 +λ e1 )+· · ·+an (xn +λ en ) = 0
with a1 , . . . , an ∈ Z and gcd(a1 , . . . , an ) = 1 and lead to contradict the condition gcd(a1 , . . . , an ) = 1.)
4.5 Let K be a field with at least n elements (n ∈ N∗ ) and let V be a finite dimensional K-vector
space. Let U1 , . . . ,Un be subspaces of V of equal dimension r and let u1i , . . . , uir be a basis of Ui
for i = 1, . . . , r . Show that there exists DimK V − r vectors in V such that which simultaneously
extend the given bases of Ui to a basis of V . (Hint : Use Exercise 2.2.)
On the other side one can see auxiliary results and (simple) test-exercises.

D. P. Patil/IISc e0-219-laa11-ex04.tex September 7, 2011 ; 10:43 a.m. 1/5

Page 2 E0 219 Linear Algebra and Applications / August-December 2011 Exercise Set 4

Auxiliary Results/Test-Exercises
To understand and appreciate the Test-Exercises which are marked with the symbol † one may possibly
require more mathematical maturity than one has! These are steps towards applications to various other
branches of mathematics, especially to analysis, number theory and Affine and Projective Geometry.
T4.1 Compute the dimension of U,W,U + W and U ∩ W for the following subspaces U,W of the given
vector space V .
(a) V := R3 , U := (x1 , x2 , x3 ) ∈ R3 | x1 + x2 = 0, −x2 + x3 = 0 ,


W := (x1 , x2 , x3 ) ∈ R3 | x1 + x3 = 0, x1 − x2 − x3 = 0 .
(b) V := R4 , U := (x1 , x2 , x3 , x4 ) ∈ R4 | x1 − x2 + x3 = 0, x1 + x2 − x4 = 0 ,


W := (x1 , x2 , x3 , x4 ) ∈ R4 | x1 + x2 − 3x3 = 0, x1 + 2x3 − x4 = 0 .

(c) V := R5 , U := Rx1 + Rx2 + Rx3 , W := Ry1 + Ry2 mit x1 := (1, 1, 0, 1, 0) , x2 := (0, 1, 1, 0, 1) , x3 :=
(0, 1, 1, 0, 0) , y1 := (0, 0, 1, 1, 0) , y2 := (1, 1, −1, 0, −1) .
T4.2 Let n ∈ N, n ≥ 2. Determine whether or not the vectors (1, 1, 1, . . . , 1) , (1, 2, 1, . . . , 1) , . . . , (1, . . . , 1, n)
form a basis of Rn .
T4.3 (a) Let W ⊆ R4 be the subspace generated by y1 := (1, 2, 3, 4) , y2 := (4, 3, 2, 1) , y3 := (−1, 0, 1, 2) , y4 :=
(0, 1, 0, 1) , y5 := (1, 3, −2, 0). List all bases of W which are the subsequences of y1 , . . . , y5 .
(b) Let U ⊆ R4 be the subspace generated by the vectors x1 := (0, 12, −3, 10) , x2 := (1, 7, −3, 2) , x3 :=
(−1, 5, 0, 7) , x4 := (1, 3, −2, −1) and let W ⊆ R4 be the subspace as in the part (a).
(1) From x1 , . . . , x4 choose a basis of U and extend it to a basis of U +W by using the vectors y1 , . . . , y5 .
(2) Give a basis of U ∩W .
T4.4 Compute the co-ordinates of the vectors
(a) (i, 0), (1+i, −2+3i), (0, 1) with respect to the basis v1 = (1+i, i), v2 = (1, 1+i) of the C-vector space C2 .
(b) (1, 0, −5i), (2 + i, 1, 0) with respect to the basis v1 = (1, 0, 1 − i), v2 = (2 + i, −1, −i), v3 = (0, 1 + i, 2 − i)
of the C-vector space C3 .
T4.5 Let K be a field. For which (a, b) ∈ K 2 , the vectors (a, b), (b, a) for a basis of K 2 .
T4.6 Show that the elements x1 , . . . , xn of the K-vector space V are linearly independent if and only if the
subspace U := Kx1 + · · · + Kxn has dimension n.
T4.7 Let xi , i ∈ I, be a family of vectors in a K-vector space V and let U be a subspace of V generated
by xi , i ∈ I. Show that U is finite dimensional if and only if there exists a natural number n ∈ N such that
every n + 1 vectors among xi , i ∈ I, are linearly dependent. Moreover, if this condition is satisfied then the
dimension DimK U is the minimum of the n ∈ N with this property.
T4.8 Let K be a finite field with q elements. Show that a K-vector space of dimension n ∈ N has exactly qn
elements.
T4.9 Let K be a finite field with q elements.
(a) The multiples m · 1K , m ∈ Z, form a subfield K 0 of K.
(b) There exists a smallest positive natural number p such that p · 1K = 0. Moreover, it is prime (and is called
the C h a r a c t e r i s t i c of K, The subfield K 0 ⊆ K contains exactly p distinct elements 0, 1K , . . . , (p − 1)1K .
(c) Show that q = pn with n := DimK 0 K .
(Remark : Therefore the number of elements is a finite field is a power of a prime number. Conversely, (we shall prove
later that) for a given prime-power q there exists (essentially unique) field with q elements.)
T4.10 Let V be a finite dimensional K-vector space and let U be a subspace of V . Let u1 , . . . , um be a basis
of U and let u1 , . . . , um , um+1 , . . . , un be an extended basis of V . Show that
x = a1 u1 + · · · + am um + bm+1 um+1 + · · · + bn un ∈ V

is an element of U if and only if the coordinates bm+1 = um+1 ∗ (x) , . . . , b = u∗ (x) of x with respect to the basis
n n
u1 , . . . , un of V are zero. (Remark : This is the most common method of characterizing the elements of a subspace.)

D. P. Patil/IISc e0-219-laa11-ex04.tex September 7, 2011 ; 10:43 a.m. 2/5

Exercise Set 4 E0 219 Linear Algebra and Applications / August-December 2011 Page 3

T4.11 Let V be a C-vector space of dimension n ∈ N∗ and let H be a real hyperplane in V (i. e. a real
subspace of dimension 2n − 1). Then show that H ∩ iH is a complex hyper-plane in V (i. e. a complex
subspace of dimension n − 1), where we put iH := {ix | x ∈ H}.

of a K-vector space V with Ui ∩U j = 0 for i 6= j. Show

T4.12 Let U1 ,U2 ,U3 be
finite dimensional subspaces
that Dim (U1 +U2 ) ∩U3 = Dim (U1 ∩ (U2 +U3 ) = DimU1 + DimU2 + DimU3 − Dim (U1 +U2 +U3 ) .
T4.13 Let V be a K-vector space with a countably infinite basis. Show that for every subspace U of V
there exists a countable basis. (Hint : Let xi , i ∈ N, be a basis of V and let Vn := Kx0 + · · · + Kxn . Then
U= ∞ n=0 (U ∩Vn ).)
S

T4.14 Let U be the subspace generated by the following functions in a space of a;; real-valued functions on
R. Compute the dimension of U, by choosing a basis from the given generating system and expressing other
functions in this generating system as the linear combinations of the basis chosen.
(a) t 2 , (t + 1)2 , (t + 2)2 , (t + 3)2 . (b) sinh 3t, cosh 3t, e3t , e−3t .
(c) 1, sint, sin 2t, sin2t, cost, cos 2t, cos2t. (d) 1, sinht, sinh 2t, sinh2t, cosht, cosh 2t, cosh2t.

T4.15 Let n ∈ N∗ and let a0 , . . . , an be real numbers with a0 < a1 < · · · < an .
(a) Let U be the R-vector space of continuous piecewise linear 1 real valued functions os the closed interval
[a0 , an ] in R with partition points a1 , . . . an−1 . Show that the functions |t − a0 | , . . . , |t − an | is a R-basis of U.
In particular, DimK U = n + 1.
(b) Let V be the R-vector space of the continuous piecewise linear functions R → R with partition points
a0 , . . . , an . Show that the functions (a0 − t)+ , |t − a0 | , . . . , |t − an | , (t − an )+ is a basis of V , where f+ :=
Max ( f , 0) denote the positive part of a real valued function f . In particular, DimK V = n + 3.
(c) Let W be the R-vector space of the continuous piecewise linear functions [a0 , an ] → R with partitions
points a1 , . . . , an−1 , and which vanish at both the end points a0 and an . Show that there exist functions
f1 , . . . , fn−1 ∈ W and the functions g1 , . . . , gn−1 ∈ W which form bases of W such that the graphs of fi and
gi are:

(d) Let k, m ∈ N with k < m. The set of k-times continuously differentiable R-valued functions on the closed
interval [a0 , an ] , which are polynomial functions of degree ≤ m on every subinterval [ai , ai+1 ], is a R-vector
space of dimension (m − k)n + k + 1 with basis

k+1
m
k+1
m
1, (t − a0 ) , . . . , (t − a0 )m , (t − a1 )+ , . . . , (t − a1 )+ , . . . , (t − an−1 )+ , . . . , (t − an−1 )+ .
(Remark : The elements of this vector space are called s p l i n e f u n c t i o n s of type (m, k) on [a0 , an ] with partition
points a1 , . . . , an−1 .)
T4.16 For pairwise distinct elements λ0 , . . . , λn of a field K, in which the multiples m · 1K , m ∈ N∗ , are all
6= 0, 2 show that the polynomial functions (t − λ0 )n , . . . , (t − λn )n form a basis of the space K[t]n+1 of all poly-
nomial functions of degree ≤ n on K. (Hint : It is enough to prove the linear independence, do this by using binomial
formula and Test-Exercise T3.6. – More generally, if f (t) = ∑nj=0 b j t j is an arbitrary polynomial function of degree n
over K, then (under the given hypotheses on K and on λ0 , . . . , λn ) the polynomial functions f (t − λ0 ) , . . . , f (t − λn ) are
linearly independent. Note that the k-th derivative f (k) (t) = ∑nj=k j( j − 1) · · · ( j − k + 1)b j t j−k is a polynomial function
of degree n − k for every k = 0, . . . , n (This also holds for arbitrary field K of characteristic 0 or > n, if one use the

1 Let n ∈ N∗ and let a0 , . . . , an be real numbers with a0 < a1 < · · · < an . A continuous  real valued function
f : [a0 , an ] → R is called p i e c e w i s e l i n e a r w i t h p a r t i t i o n p o i n t s a0 , . . . , an if f [ai , ai+1 ] → R is linear
(see below) for every i = 1, . . . , n − 1. A real valued function f : [a, b] → R defined on the closed interval [a, b] ⊆ R is
called l i n e a r if there exist λ , µ ∈ R such that f (t) = λt + µ for every t ∈ [a, b].
2 In this one also says that K has the c h a r a c t e r i s t i c 0 .

D. P. Patil/IISc e0-219-laa11-ex04.tex September 7, 2011 ; 10:43 a.m. 3/5

 Page 4 E0 219 Linear Algebra and Applications / August-December 2011 Exercise Set 4

formal derivatives)3 In particular, by Exercise 3.3-(a), the polynomial functions f = f (0) , f (1) , . . . , f (n) = n!bn form
a basis of K[t]n+1 and hence by using binomial formula and interchanging the summations, we get the well-known
T a y l o r - F o r m u l a for f at λ ∈ K:
n n j   n n n
j j j−k t j−k f (k) (t)
f (t−λ )= ∑ b j (t−λ ) = ∑ b j ∑ t (−λ )k = ∑ (−1)k λ k ∑ j( j−1) · · · ( j−k +1) b j = ∑ (−1)k λ k .
j=0 j=0 k=0 k k=0 =k k! k=0 k!
Now, to prove linear independence, consider 0 = ∑ni=0 ai f (t − λi ) with
! coefficients ai ∈ K. From this it follows that
n n n (k) n k n
f (t) (−1)
0 = ∑ ai f (t − λi ) = ∑ ai ∑ (−1)k λik
k!
=∑ ∑ ai λik f (k) (t) and hence by the linear independence
i=0 i=0 k=0 i=0 k! i=0
of f = f (0) , f (1) , . . . , f (n) we have ∑ni=0 ai λik = 0 for all k = 0, . . . , n. Now, use the Test-Exercise T3.6 to conclude that
a0 = · · · = an = 0.)

† T4.17 Let n ∈ N∗ . Show that there exist a representation in Q[t] of the form
n
ak
t= (t + k)n ,
∑ ak ∈ Z, b ∈ N∗ .
k=0 b
Use this to deduce that there exists a natural number γ(n) such that every natural number is a sum of γ(n)
integers of the form ±mn , m ∈ N. (Hint : For a representation use the above Test-Exercise T4.16. For multiples of
b the assertion directly follows from the above formula, otherwise apply division with remainder. – Remarks: Further,
one can choose γ(n) ≤ |a0 | + · · · + |an | + [b/2]. In particular, one can even have γ(2) = 3 and γ(3) = 5, where it is still
unknown whether or not γ(3) = 4. Since 6 and 14 can not be written in the form m21 ± m22 , the equality γ(2) = 2 is not
enough. – The Two-Square Theorem (Fermat-Euler) describes exactly those natural numbers m ∈ N which can not
be expressed in the form m21 ± m22 . Since 4 and 5 can not be expressed in the form m31 ± m32 ± m33 , as one sees this by
computing modulo 9, it follows that the equality γ(3) = 3 is not enough. – Moreover, it is conjectured by E. Waring4
(and von D. Hilbert proved it, even sharper) that: There exists a natural number g(n) such that every natural number is
sum of g(n) natural numbers of the form mn , m ∈ N. In other words: To determine , for a given positive natural number
n, there is a natural number g(n) such that the equation a = x1n + · · · xg(n)
n has a solution in Ng(n) for every a ∈ N. This
is known as the W a r i n g ’ s P r o b l e m . Previous writers had proved its existence when n = 3, 4, 5, 6, 7, 8 and 10, but
its value g(n) is determined only for n = 3. The value g(n) is now known for all n. For example, g(2) = 4, g(3) = 9,
g(4) = 19, g(5) = 37. Except for g(2) and g(3), the known proofs of these results involve much more complicated
methods and use heavily the theory of functions of complex variable.)
T4.18 Let K be a field and let c0 , . . . , cn−1 ∈ K elements in K. Show that the subset V ⊆ K N of all sequences
(ak ) from K N , which satisfy the recursion-relation
ak+n = c0 ak + c1 ak+1 + · · · + cn−1 ak+n−1 ,
k ∈ N, is a subspace of KN of the dimension n. (Hint: If K = C and if
1 − cn−1 x − · · · − c0 xn = (1 − β1 x)n1 · · · (1 − βr x)nr
holds in C[x] with pairwise distinct β1 , . . . , βr ∈ C, then the sequences
(β1k ) , . . . , (kn1 −1 β1k ) , . . . , (βrk ) , . . . , (knr −1 βrk )
form a C-Basis of V . It is easy to see that these sequences belong to V and are linearly independent.)

† T4.19 (a) Let U ⊆ K n be a subspace of dimension m. Then there exists uniquely determined basis of U of
the form
v1 = (∗ , . . . , ∗ , 1, 0, . . . , 0) ∈ K n ,

3 Formal derivatives Let K be a field. For a polynomial F = ∑n∈N an X n ∈ K[X], we define the (f o r m a l)
d e r i v a t i v e of F by F 0 := ∑n∈N nan X n−1 ∈ K[X]. This formal derivative satisfies usual p r o d u c t and q u o -
 0
F GF 0 − G0 F
t i e n t r u l e s: (FG)0 = F 0 G + FG0 for all F, G ∈ K[X] and = for all F, G ∈ K[X], G 6= 0.
G G2
4 An English mathematician E. Waring stated without proof that every number is the sum of 4 squares, of 9 cubes, of

19 biquadrates, and so on in Meditationes algebraicae (1770), 204-205 and Lagrange proved that g(2) = 4 (Lagrange’s
four-square theorem) later in the same year. It is very improbable that Waring had any sufficient grounds for his assertion
and it was until more than 100 years later that Hilbert first proved (even sharper assertion) that it is true. Hilbert’s
proof of the existence of g(n) for every n was published in Göttinger Nachrichten (1909), 17-36 and Math.Annalen, 67
(1909), 281-305.

D. P. Patil/IISc e0-219-laa11-ex04.tex September 7, 2011 ; 10:43 a.m. 4/5

Exercise Set 4 E0 219 Linear Algebra and Applications / August-December 2011 Page 5

v2 = (∗, . . . , ∗ , 0, ∗ , . . . , ∗ , 1, 0, . . . , 0) ∈ K n ,
················································
vm = (∗ , . . . , ∗ , 0, ∗ , . . . , ∗ , 0, ∗ , . . . , ∗ , 0, . . . , 1, 0, . . . , 0) ∈ K n ,
where at the position of ∗ there are elements in K which are uniquely determined by U and the positions d j
where there is 1 in the vectors v j are uniquely determined by U, 1 ≤ d1 < d2 < · · · < dm ≤ n. In the vectors
v j there are 0s at the positions d1 , . . . , d j−1 , d j + 1, . . . , n. (Remarks: The set of all m-dimensional subspaces of
K n is called the G r a s s m a n n - M a n n i f o l d GK (m, n) of the type (m, n) over K. This Exercise gives a partition  of

n
GK (m, n) into subsets σ (d1 , . . . , dm ), where (d1 , . . . , dm ) runs through the subsets of {1, 2, . . . , n} of cardinality
m
with 1 ≤ d1 < · · · < dm ≤ n. The subspace corresponding to σ := σ (d1 , . . . , dm ) is then parameterized by the tuple in
K kσ where m
m+1
 
kσ := (d1 − 1) + · · · + (dm − m) = ∑ d j − .
j=1
2
σ (d1 , . . . , dm ) is called a S c h u b e r t - c e l l of the dimension
m
m+1
 
kσ = ∑ d j −
j=1
2
in GK (m, n) . Further, σ (1, . . . , m) respectively, σ (n −m +1, . . . , n) are the only Schubert-cells of the minimal dimension
0 respectively, the maximal dimension m`, ` := n − m. – The definition of the Schubert-cells and their notation is
not uniform in the literature. If we put δ j := d j − j, j = 1, . . . , m, then a sequence 0 ≤ δ1 ≤ · · · ≤ δm ≤ ` and the
corresponding cell has the dimension δ1 + · · · + δm . For a given k ∈ N, the number of Schubert-cells of dimension k is
therefore equal to the number p(k; m, `) of partitions of the number k with at most m positive natural numbers ≤ `. For
example, if K is a finite field with q elements, then
m`
Card GK (m, n) = ∑ p(k; m, `)qk .
k=0
[n] [n]
Moreover, this sum is equal to the value Gm (q) of the Gauss-polynomial Gm at the place q. One can use this result
and the Identity-Theorem for polynomials to give a combinatorial proof of the following equality of polynomials:
m`
[n] (T n − 1) · · · (T n−m+1 − 1)
Gm (T ) = ∑ p(k; m, `)T k = (T m − 1) · · · (T − 1)
, ` = n−m.)
k=0

(b) Compute the bases described in part a) for the subspaces U and for W given in the Test-Exercise T4.3-(b)
and T4.3-(a), respectively.
T4.20 Which numbers can occur as the dimensions of the intersections of a p-dimensional and a q-
dimensional subspaces in a K-vector space of dimension n in Question?
T4.21 Let V = Kx1 + · · · + Kxn + Kxn+1 be a K-vector space, W be a K-subspace of V with W 6⊆ V 0 :=
Kx1 + · · · + Kxn and let y be an arbitrary vector in W \V 0 . Then show that
W = W ∩V 0 + Ky .
By induction on n it follows directly that every subspace of a K-vector space which a generating system
consisting of n vectors, itself has a generating system consisting of at most n vectors.
T4.22 Let v1 , . . . , vn be a basis of the n-dimensional K-vector space V , n ≥ 1, and let H be a hyperplane in
V . Show that there exist an index i0 , 1 ≤ i0 ≤ n, and elements ai ∈ K, i 6= i0 such that vi − ai vi0 , i 6= i0 is a
basis of H. In which case for every i0 ∈ {1, . . . , n} there are such elements ai ∈ K?
T4.23 Let K be a field„ V be a n-dimensional K-vector space and
V0 ⊆ V1 ⊆ · · · ⊆ Vn ⊆ V
be a sequence of K-subspaces with DimK Vi ≤ i for i = 0, . . . , n. Then show that there is a flag
0 = W0 ⊂ W1 ⊂ · · · ⊂ Wn = V
in V with Vi ⊆ Wi for all i = 1, . . . , n.
T4.24 Let V be a finite dimensional K-vector space and m ∈ N. If Vi , i ∈ I, are subspaces of V with
\
CodimK Vi = m ,
i∈I
then show that there exists a finite subset J ⊆ I with |J| ≤ m and
T T
=
i∈J Vi . (Remark : See also
i∈I Vi
Exercise 4.2. – This statement also hold even if V is not finite dimensional, if we put CodimK U := DimK V /U, where
V /U denote the quotient space of V by U.)

D. P. Patil/IISc e0-219-laa11-ex04.tex September 7, 2011 ; 10:43 a.m. 5/5