chapter1

Chapter 1 Vectors and Vector Spaces 1.1 Vector Spaces Underlying every vector space (to be de fined shortly) is a scalar fieldF. Examples of scalar fields are the real and the complex numbers R:= real numbers C:= complex numbers. These are the only fields we use here. Definition 1.1.1. Avector space Vis a collection of objects with a (vector) addition and scalar multiplication de fined that closed under both operations and which in addition satis fies the following axioms: (i) (α+β)x=αx+βxfor all x∈Vandα,β∈F (ii)α(βx)=(αβ)x (iii)x+y=y+xfor all x, y∈V (iv)x+(y+z)=(x+y)+zfor all x, y, z∈V (v)α(x+y)=αx+αy (vi)∃O∈Vz0+x=x; 0 is usually called the origin (vii) 0 x=0 (viii) ex=xwhere eis the multiplicative unit in F. 7 8 CHAPTER 1. VECTORS AND VECTOR SPACES The “closed” property mentioned above means that for all α,β∈Fand x, y∈V αx+βy∈V (i.e. you can’t leave Vusing vector addition and scalar multiplication). Also, when we write for α,β∈Fandx∈V (α+β)x the ‘+’ is in the field, whereas when we write x+yforx, y∈V,t h e‘ + ’i s in the vector space. There is a multiple usage of this symbol. Examples. (1)R2={(a1,a2)|a1,a2∈R}two dimensional space. (2)Rn={(a1,a2,... ,a n)|a1,a2,... ,a n∈R},n dimensional space. (a1,a2,... ,a n)i sc a l l e da n n-tuple. (3)C2andCnrespectively to R2andRnwhere the underlying field isC, the complex numbers. (4)Pn=l n j=0ajxj|a0,a1,... ,a n∈RM is called the polynomial space of all polynomials of degree n. Note this includes not just the polynomials of exactly degree nbut also those of lesser degree. (5)fp={(ai,...)|ai∈R,Σ|ai|p<∞}. This space is comprised of vectors in the form of in finite-tuples of numbers. Properly we would write fp(R)o rfp(C) to designate the field. (6)TN=FN n=1ansinnπx|a1,... ,a n∈Rk , trigonometric polynomials. Standard vectors in Rn e1=( 1,0,... , 0) e2=( 0,1,0,... , 0) e3=( 0,0,1,0,... , 0) ... en=( 0,0,... , 0,1)These are the unit∗vec- tors whichpoint in thenorthogonal ∗ directions. 1.1. VECTOR SPACES 9 ∗Precise de finitions will be given later. ForR2, the standard vectors are 10 CHAPTER 1. VECTORS AND VECTOR SPACES e1=( 1,0) e2=( 0,1) (1,0)(0,1) (0,0)12 e Graphical representa- tion of e1ande2in the usual two dimensional plane. Recall the usual vector addition in the plane uses the parallelogram rule yx+y ForR3, the standard vectors are e1=( 1,0,0) e2=( 0,1,0) e3=( 0,0,1)(0,0,1) (1,0,0)ee e(0,1,0)23 1 Graphical representa- tion of e1,e2,a n d e3in the usual Linear algebra is the mathematics of v ector spaces and their subspaces. We will see that many questions about vector spaces can be reformulated asquestions about arrays of numbers. 1.1.1 Subspaces LetVbe a vector space and U⊂V.W e w i l l c a l l Uasubspace ofVifU is closed under vector addition, scalar multiplication and satis fies all of the vector space axioms. We also use the term linear subspace synonymously. 1.1. VECTOR SPACES 11 Examples. Proofs will be given later letV=R3={(a, b, c )|a, b, c∈R} (1.1) U={(a, b,0)|a, b∈R}. Clearly U⊂Vand also Uis a subspace of V. let v1,v2∈R3(1.2) W={av1+bv2|a, b∈R} Wis a subspace of R3. In this case we say Wis “spanned” by {v1,v2}. In general, let S⊂V,a vector space, have the form S={v1,v2,... ,v k}. Thespan ofSis the set U=  k3 j=1ajvj|a1,... ,a k∈R  . We will use the notion S(v1,v2,... ,v k) for the span of a set of vectors. Definition 1.1.2. We say that u=a1v1+···+akvk is alinear combination of the vectors v1,v2,... ,v k. Theorem 1.1.1. LetVbe a vector space and U⊂V.I fUis closed under vector addition and scalar multiplication, then Uis a subspace of V. Proof. We remark that this result provides a “short cut” to proving that a particular subset of a vector space is in fact a subspace. The actual proofof this result is simple. To show (i), note that if x∈Uthen x∈Vand so (ab)x=ax+bx. Nowax, bx, ax +bxand ( a+b)xareallinUby the closure hypothesis. The equality is due to vector space properties of V.T h u s( i )h o l d sf o r U.E a c h of the other axioms is proved similarly. 12 CHAPTER 1. VECTORS AND VECTOR SPACES A very important corollary follows about spans. Corollary 1.1.1. LetVbe a vector space and S={v1,v2,... ,v k}⊂V. ThenS(v1,... ,v k)is a linear subspace of V. Proof. We merely observe that S(v1,... ,v k)=lk3 1ajvj|a1,... ,a k∈RorCM . This means that the closure is built right into the de finition of span. Thus, if v=a1v1+···+akvk w=b1v1+···+bkvk then both v+w=(a1+b1)v1+···+(ak+bk)vk and cv=ca1v+ca2v+···+cakv are in U.T h u s Uis closed under both operations; therefore Uis a subspace ofV. Example 1.1.1. (Product spaces.) Let VandWbe vector spaces de fined over the same field. We de fine the new vector space Z=V×Wby Z={(v, w)|u∈V, w∈W} We de fine vector addition as ( v1,w1)+(v2,w2)=( v1+v2,w1+w2)a n d scalar multiplication by α(v, w)=(αv,αw). With these operations, Zis a vector space, sometimes called the product ofVandW. Example 1.1.2. Using set-builder notation, de fineV13={(a,0,b)|a, b,∈ R}.Then Uis a subspace of R3.It can also be realized as the subspace of the standard vectors e1=( 1,0,0) and e3=( 0,0,1), that is to say V13= S(e1,e3). 1.2. LINEAR INDEPENDENCE AND LINEAR DEPENDENCE 13 Example 1.1.3. More subspaces of R3.There are two other important methods to construct subspaces of R3. Besides the set builder notation used above, we have just considered the method of spanning sets. Forexample, let S={v 1,v2}⊂R3.ThenS(S) is a subspace of R3.Simi- larly, if T={v1}⊂R3.ThenS(T) is a subspace of R3.At h i r dw a y to construct subspaces is by using inner products. Let x, w∈R3.Ex- p r e s s e di nc o o r d i n a t e s x=(x1,x2,x3)a n d w=(w1,w2,w3).Define the inrner product of xandwbyx·w=x1w1+x2w2+x3w3.Then Uw={x∈R3|x·w=0}is a subpace of R3. To prove this it is neces- sary to prove closure under vector addition and scalar multiplication. Thelatter is easy to see because the inner product is homogeneous in α,that is, (αx)·w=αx 1w1+αx2w2+αx3w3=α(x·w).Therefore if x·w=0s o also is (αx)·w.The additivity is also straightforward. Let x, y∈U.T h e n the sum (x+y)·w=(x1+y1)w1+(x2+y2)w2+(x3+y3)w3 =(x1w1+x2w2+x3w3)+(y1w1+y2w2+y3w3) =0 + 0 = 0 However, by choosing two vectors v,w,∈R3we can de fineUv,w={x∈ R3|x·y=0a n d x·w=0}.E s t a b l i s h i n g Uv,wis a subspace of R3is proved similarly. In fact, what is that both these sets of subspaces, those formedby spanning sets and those formed from the inner products are the same set of subspaces. For example, referring to the previous example, it follows that V 13=S(e1,e3)=Ue2. Can you see how to correspond the others? 1.2 Linear independence and linear dependence One of the most important problems in vector spaces is to determine if a given subspace is the span of a collection of vectors and if so, to deter- mine a spanning set. Given the importance of spanning sets, we intend to examine the notion in more detail. In particular, we consider the conceptof uniqueness of representation. LetS={v 1,... ,v k}⊂V, a vector space, and let U=S(v1,... ,v k)( o r S(S) for simpler notation). Certainly we know that any vector v∈Uhas the representation v=a1v1+···+akvk for some set of scalars a1,... ,a k. Is this representation unique? Or,c a nw e 14 CHAPTER 1. VECTORS AND VECTOR SPACES find another set of scalars b1,... ,b kn o ta l lt h es a m ea s a1,... ,a krespec- tively for which v=b1v1+···+bkvk. We need more information about Sto answer this question either way. Definition 1.2.1. LetS={v1,... ,v k}⊂V, a vector space. We say that Sislinearly dependent (l.d.) if there are scalars a1,... ,a knot all zero for which a1v1+a2v2+···+akvk=0. (T) O t h e r w i s ew es a y Sislinearly independent (l.i.). Note. If we allow all the scalars to be zero we can always arrange for ( T) to hold, making the concept vacuous. Proposition 1.2.1. IfS={v1,... ,v k}⊂V, a vector space, is linearly dependent, then one member of this set can be expressed as a linear combi- nation of the others. Proof. We know that there are scalars a1,... ,a ksuch that a1v1+a2v2+···+akvk=0 Since not all of the coe fficients are zero, we can solve for one of the vectors as a linear combination of the other vectors. Remark 1.2.1. Actually we have shown that there is novector with a unique representation in S(S). Corollary 1.2.1. If0∈S={v1,... ,v k},t h e n Sis linearly dependent. Proof. Trivial. Corollary 1.2.2. IfS={v1,... ,v k}is linearly independent then every subset of Sis linearly independent. 1.3. BASES 15 1.3 Bases The idea of a basis is that of finding a minimal generating set for a vector space. Through basis, unicity of representation and a number of other usefulproperties, both theoretical and com putational, can be concluded. Thinking of the concept in operations research ideas, a basis will be a redundancy freeand complete generating set for a vector space Definition 1.3.1. LetVbe a vector space and S={v 1,... ,v k}⊂V.W e callSaspanning set for the subspace U=S(S). Suppose that Vis a vector space, and S={v1,... ,v k}is a linearly independent spanning set for V.T h e n Sis called a basis ofV.M o d i f yt h i s definition correspondingly for subspaces. Proposition 1.3.1. IfSis a basis of V, then every vector has a unique representation. Proof. LetS={v1,... ,v k}andv∈V.T h e n v=a1v1+···+akvk for some choice of scalars. If there is a second choice of scalars b1,... ,b k not all the same, respectively, as a1,... ,a k,w eh a v e v=b1v1+···+bkvk and 0=(a1−b1)v1+···+(ak−bk)vk. Since not all of the di fferences a1−b1,... ,a k−bkare zero we must have thatSis linearly dependent. This is a contradiction to our hypothesis, and the result is proved. Example. LetV=R3andS={e1,e2,e3}.T h e n Sis a basis for V. Proof. Clearly Vis spanned by S. Now suppose that 0=a1e1+a2e2+a3e3 or (0,0,0) =a1(1,0,0) +a2(0,1,0) +a3(0,0,1) =(a1,a2,a3). Hence a1=a2=a3=0 . T h u st h es e t {e1,e2,e3}is linearly independent. 16 CHAPTER 1. VECTORS AND VECTOR SPACES Remark 1.3.1. Note how we resolved the linearly dependent/linearly in- dependent issue by converting a vector problem to a numbers problem. Thisis at the heart of linear algebra. Exercise. LetS={v 1,v2}={(1,0,1),(1,−1,0)}⊂R3. Show that Sis linearly independent and therefore a basis of S(S). 1.4 Extension to a basis In this section, we show that given a linearly independent set of vectors from a vector space with a finite spanning set, it is possible add to this set more vectors until it becomes a basis. Thus any set of linearly independent vectors can be a part (subset) of a basis. Theorem 1.4.1 (Extension to a basis). Assume that the given vector space Vhas a finite spanning set S1, i.e. V=S(S1).L e t S0={x1,... ,x f}be a linearly independent subset of Vso that S(S0)V. Then, there is a subset SI 1ofS1,s u c ht h a t S0∪SIis a basis for V. Proof. Our intention is to add vectors to S0keeping it linearly independent and eventually becoming a basis. There are a couple of steps.Steps. 1. Since S(S 1)SS(S0), there is a vector y1∈S1such that S0,1= {S0,y1}is linearly independent and thus S(S0,1)SS(S0). 2. Continue this process generating sets S0,1={S0,y1} S0,2={S0,1,y2} ... S0,j={S0,j−1,yj−1} ... At each step S0,1,S0,2,... are linearly independent sets. Since S1is finite we must eventually have that S(S0,m)=S(S1)=V. 3. Since S0,mis linearly independent and spans V, it must be a basis. 1.5. DIMENSION 17 Remark 1.4.1. In the proof it was important to begin with anyspanning set for Vand to extract vectors from it as we did. Assuming merely that there exists a finite spanning set and extracting vectors directly from V leads to a problem of terminus. That is, when can we say that the new linearly independent set being generated in Step 2 above is a spanning set forV? What we would need is a theorem that says something to the e ffect that if Vhas a finite basis, then every linearly independent set having the same number of vectors is also a basis. This result is the content of the nextsection. However, to prove it we need the Extension theorem. Corollary 1.4.1. IfS={v 1,... ,v k}is linearly dependent then the repre- sentation of vectors in S(S)isnotunique. Proof. We know there are scalars a1,... ,a knot all zero, for which a1v1+···+akvk=0 letv∈S(S) have the representation v=b1v1+b2v2+···+bkvk. Then we also have the representation v=(a1+b1)v1+(a2+b2)v2+···+(ak+bk)vk establishing the result. Remark 1.4.2. The upshot of this construction is that we can always con- struct a basis from a spanning set. In actual practice this process may bequite difficult to carry out. In fact, we will spend some time achieving this goal. The main tool will be matrix theory. 1.5 Dimension One of the most remarkable features of vector spaces is the notion of dimension. We need one simple result that makes this happen, the basis theorem. Theorem 1.5.1 (Basis Theorem). LetS={v1,... ,v k}⊂Vbe a basis forV. Then every basis of Vhaskelements. 18 CHAPTER 1. VECTORS AND VECTOR SPACES Proof. We proceed by induction. Suppose S={v1}andT={w1,w2}are both bases of V.T h e ns i n c e Sis a basis w1=α1v1w2=α2v1 and therefore 1 α1w1−1 α2w2=0 which implies that Tis linearly dependent (we tacitly assumed that both α1andα2were nonzero. Why can we do this?) The next step is to assume the result holds for bases having up to k elements. Suppose that S={v1,... ,v k+1}andT={w1,... ,w k+2}are both bases of V. Now consider SI={v1,... ,v k}. We know that S(SI) S(S)=S(T)=V. By our extension of bases result, there is a vector wf1∈Tsuch that SI 1={v1,... ,v k,wf1} is linearly independent and S(SI 1)⊂S(S)=V.I fS(SI 1)V, our extension result applies again to give a vector vf1such that SI 11={v1,... ,v k,wf1,vf1} is linearly independent The only possible selection is vf1=vk+1. But in this casewfiwill depend on v1,... ,v k,vk+1, and that is a contradiction. Hence S(v1,... ,v k,wf1)=V. The next step is to remove the vector vkfrom SI 1and apply the extension to conclude that the span of the set SI 2={v1,... ,v k−1,wf1,wf2} isV. We continue in this way eventually concluding that SI k+1={wf1,wf2,... ,w fk+1} has span V.B u t SI k+1T, whence Tis linearly dependent. Proposition 1.5.1 (Reduced spanning sets). (a) Suppose that S= {v1,... ,v k}spans Vandvjdepends (linearly) on Sj={v1,... ,v j−1,vj+1...v k}. Then Sjalso spans V. 1.5. DIMENSION 19 ( b )I fa tl e a s to n ev e c t o ri n Sis nonzero (that is VW={0}, the smallest vector space), then there is a subset S0⊂Sthat is linearly independent and spans V. Proof. (Left to reader.) Definition 1.5.1. Thedimension of a vector space Vis the (unique) num- b e ro fv e c t o r si nab a s i so f V.W ew r i t ed i m ( V) for the dimension. Remark 1.5.1. This de finition make sense possible only because of our basis theorem from which we are assured all every linearly independentspanning sets of V, that is all bases, have the same number of elements. Examples. (1) dim( R n)=n, (2) dim( Pn)=n+1 . Exercise. LetM= all rectangular arrays of two rows and three columns with real entries. Find a basis for M,a n d find the dimension of M.N o t e M=F}abc def]eeeea, b, c, d, e, f ∈Rk Example 1.5.1. P n={anxn+an−1xn−1+···+a1x+a0=0 }is the vector space of polynomials of degree n. We claim that the powers, x0=1 , x, x2,... ,xnare linearly independent, and since Pn=S(1,x ,... ,xn) they form a basis of Pn. Proof. There are several ways we can prove this fact. Here is the most direct and it requires essentially no machinery. Suppose they are linearly dependent, which means that there are coe fficients a0,a1,... ,a nso that anxn+an−1xn−1+···+a1x+a0=0, (T) the function . (This functional view is critically important because every polynomial has roots.) There must be a coe fficient which is nonzero and which corresponds to the highest power. Let us assume that anW=0 ,f o r convenience, and with no loss in generality. 20 CHAPTER 1. VECTORS AND VECTOR SPACES Solve for xnto get xn=−an−1 anxn−1+···+−a1 anx−a0 an(TT) Now compute the ratio of this expression divided by xnon both sides, and letx→∞ . The left side of course will be 1. Again for convenience we take n= 2. So, condensing terms we will have b1x+b0 x2=b1w1 xW +b0w1 x2W =1 where bj=−aj/a2.B u t a s x→∞ the expression b1D1 xi +b0D1 x2i →0. This is a contradiction. It cannot be that the functions 1 ,x,a n d x2are linearly dependent. In the general case for nwe have bn−1w1 xW +bn−2w1 x2W +···+b0w1 xnW =1, where bj=−aj/an. Apply the same limiting argument to obtain the con- tradiction. Thus T={1,x ,... ,xn} is a basis of Pn. A calculus proof is available. It is also based on the fact that if the powers are linearly independent and ( T) holds, then we can assume that the same relation ( TT)i st r u e . N o wt a k et h e nthderivative of both sides. We obtain n!=0 a contraction, and the result if proved Finally, one more technique used to prove this result is by using the Fundamental Theorem of Algebra. Theorem 1.5.2. Every polynomial ( T)o f exactly nthdegree (i.e. with anW=0) has exactly nroots counted with mu ltiplicity (i.e. if q(x)=qnxn+ qn−1xn−1+···+q1x+q0∈Pn(C),qnW=0 t h e nt h en u m b e ro fs o l u t i o n so f q(x)=0 is exactly n). From (T) above we have an nthdegree polynomial that is zero for every x. Thus the polynomial is zero, and this means allthe coefficients are zero. This is a contradiction to the hypothesis, and therefore the theorem is proved. 1.5. DIMENSION 21 Remark 1.5.2. P0P1P2···Pn···. On the other hand this is not true for the Euclidean spaces R1,R2,... . However, we may say that there is a subspace of R3which is “like” R2in every possible way. Do you see this? We have R2={(a, b)|a, b∈R} R3={(a, b, c )|a, b, c∈R}. No element in R2, an ordered pair,c a nb ei n R3, a set of ordered triples. However U={(a, b,0)|a, b∈R} is “like” R2is just about every way. Later on we will give a precise mathe- matical meaning to this comparison. Example 1.5.2. Find a basis for the subspace V0ofR3of all solutions to x1+x2+x3=0 ( T) where x=(x1,x2,x3)∈R3. Solution. First show that the set V0={(x1,x2,x3)∈R3|x1+x2+x3=0} is in fact a subspace of R3. Clearly if x=(x1,x2,x3)∈V0andy= (y1,y2,y3)∈V0then x+y=(x1+y1,x2+y2,x3+y3)∈V0,p r o v i n g closure under vector addition. Similarly V0is closed under scalar multi- plication. Next, we seek a collection of vectors v1,v2,... ,v k∈V0so that S(v1,... ,v k)=V0.L e t x3=αandx2=βbe free parameters. Then x1=−(α+β). Hence all solutions of ( T)h a v et h ef o r m x=(−(α+β),β,α) x=α(−1,0,1) +β(−1,1,0). Obviously the vectors v1=(−1,0,1) and v2=(−1,1,0) are linearly inde- pendent, and xis expressed as being in the span of them. So, V0=S(v1,v2). V0has dimension 2. 22 CHAPTER 1. VECTORS AND VECTOR SPACES Theorem 1.5.3 (Uniqueness). LetS={v1,... ,v k}be a basis of V. Then each vector v∈Vhas a unique representation with respect to S. Proof. SinceS(S)=Vwe have that v=a1v1+a2v2+···+akvk for some coe fficients a1,a2,... ,a kin the given field. (This is the represen- tation of vwith respect to S.) If it is notunique there is another v=b1v1+b2v2+···+bkvk. So, subtracting we have (a1−b1)v1+(a2−b2)v2+···+(ak−bk)vk=0 where the di fferences aj−bjare not all zero. This implies that Sis a linearly dependent set. Theorem 1.5.4. Suppose that S={v1,... ,v k}is a basis of the vector space V. Suppose that T={w1,... ,w m}is a linearly independent subset ofV.T h e n m≤k. Proof. We know that Sis a linearly independent spanning set. This means that every linearly independent set of kvectors is also a spanning set. There- fore,m>k renders a contradiction as T0={w1,... ,w k}is a spanning set andwk+1∈S(T0). Definition 1.5.2. IfAis any set we de fine |A|:= cardinality of A, that is to say |A|is the number of elements of A. Example 1.5.3. LetT={1,x ,x2,x3}.T h e n |T|=4 . Theorem 1.5.5. Both RkandCkarek-dimensional and Sk={e1,e2,... ,e k} is a basis of both. Proof. It is easy to see that e1,... ,e kare linearly independent, and any vector xinRkhas the form x=a1e1+a2e2+···+akek fora1,... ,a k∈R.T h u s Skis a linearly independent spanning set and hence a basis of Rk. 1.6. NORMS 23 Question: What single change to the proof above gives the theorem for Ck? The following results follow easily from previous results. Theorem 1.5.6. LetVbe ak-dimensional vector space. (i) Every set Twith |T|>k is linearly dependent. (ii) If D={v1,... ,v j}is linearly independent and j<k , then there are vectors vf1,... ,v fk−j∈Vsuch that D∪{vf1,... ,v fk−j} is a basis of V. (iii) If D⊂V,|D|=k,a n d Dis either a spanning set for Vor linearly independent, then Dis a basis for V. 1.6 Norms Norms are a way of putting a measure of distance on vector spaces. The purpose is for the re fined analysis of vector spaces from the viewpoint of many applications. It is also to all the comparison of various vectors on the basis of their length. Ultimately , we wish to discuss vector spaces as representatives of points. Naturally, we are all accustomed to the “shortestdistance” distance from the Pythagorean theorem. This is an example of anorm, but we shall consider them as real valued functions with very special properties. Definition 1.6.1. Norms on vector spaces over C,orR.L e t Vbe a vec- tor space and suppose that ,·,:V→R +is a function from Vto the nonnegative reals for which (i),x,≥0 for all x∈Vand ,x,=0i fa n do n l yi f x=0 (ii),αx,=|α|,x,for allα∈C,Randx∈V (iii),x+y,≤, x,+,y,for all x, y∈V “The Triangle inequality”. Then,·,is called a norm onV. The second condition is often termed the (positive) homogeneity property. Remark 1.6.1. The notation is a substitute function notation. The ex- pression ,·,, without the vector, is just the way a norm is expressed. 24 CHAPTER 1. VECTORS AND VECTOR SPACES Examples. LetV=Rn(orCn). De fine for x=(x1,... ,x n) (i),x,2=(|x1|2+|x2|2+···+|xn|2)1/2Euclidean norm (ii),x,1=(|x1|+|x2|+···+|xn|)f1norm (iii),x,∞=m a x 1≤i≤n|xi|f∞norm Norm (ii) is read as: ell one norm. Norm (iii) is read as: ell in finity norm. Proof that (ii) is a norm. Clearly (i) holds. Next ,αx,1=(|αx1|+|αx2|+···+|αxn|) =(|α||x1|+|α||x2|+···+|α||xn|) =|α|(|x1|+|x2|+···+|xn|)=|α|,x,1 which is what we needed to prove. Also, ,x+y,1=(|x1+y1|+|x2+y2|+···+|xn+yn|) ≤(|x1|+|y1|+|x2|+|y2|+···+|xn|+|yn|) =(|x1|+|x2|+···+|xn|)+( |y1|+|y2|+···+|yn|) =,x,1+,y,1. Here we used the fact that |α+β|≤|α|+|β|for numbers. To prove that (i) is a norm we need a very famous inequality. Lemma 1.6.1 (Cauchy—Schwartz). Given that a1,... ,a nandb1,... ,b n are in C.T h e n n3 1|aibi|≤Xn3 1a2 i~1/2Xn3 1b2 i~1/2 . (T) Proof. We consider for the variable t Σ(ai+tbi)2=Σa2 i+2tΣaibi+t2Σb2 i. Note that ( T) is obvious ifn 1aibi=0 . I fn o tt a k e t=−n 1a2 i n 1aibi. 1.6. NORMS 25 Then Σ(ai+tbi)2=Σa2 i−2Σa2 i ΣaibiΣaibi+D Σa2 ii2 (Σaibi)2Σb2 i =−Σa2 i+D Σa2 ii2Σb2 i (Σaibi)2 =D Σa2 iiw −1+Σa2 iΣb2 i (Σaibi)2W . Since the left side is ≥0 and since Σa2 i≥0, we must have that w −1+Σa2 iΣb2 i (Σaibi)2W ≥0. Solving this inequality we have (Σaibi)2≤Σa2 iΣb2 i. Now that square roots to get the result. To prove that (i) is a norm, we note that conditions (i) and (ii) are straightforward. The truth of condition (iii) is a consequence of anotherfamous result. Theorem 1.6.1 (Minkowski). ,x+y, 2≤,x,2+,y,2. Proof. Σ(ai+bi)2=Σa2 i+2Σaibi+Σb2 i ≤Σa2 i+2D Σa2 ii1/2D Σb2 ii1/2+Σb2 i =pD Σa2 ii1/2+D Σb2 ii1/2Q2 . Taking square roots gives the result. Continuity and Equivalence of Norms Lemma 1.6.2. Every vector norm on Cnis continuous in the vector com- ponents. 26 CHAPTER 1. VECTORS AND VECTOR SPACES Proof. Letx∈Cnand,·,some norm on Cn. We need to show that if the vectorδ→0, in components, then ,x+δ,→, x,. First, by the triangle inequality ,x+δ,≤, x,+,δ,or ,x+δ,−,x,≤,δ, Similarly ,x,≤, x+δ−δ, ≤,x+δ,+,δ,or −,δ,≤, x+δ,−,x, Therefore |,x+δ,−,x,|≤,δ, Now expressing δin components and standard bases vectors, we write δ= δ1e1+···+δnenand ,δ,≤ |δ1|,e1,+···+|δn|,en, ≤max 1≤i≤n|δi|(,e1,+···+,en,) ≤Mmax 1≤i≤n|δi| where M=,e1,+···+,en,.We know that if δ→0i nc o m p o n e n t s ,t h e n max 1≤i≤n|δi|→0.Therefore |,x+δ,−,x,|→0, as well. Definition 1.6.2. Let,·,aand,·,bbe two vector norms on Cn.We say that these norms are equivalent if there are postive constants m, M such that for all x∈Cn m,x,a≤,x,b≤M,x,a The remarkable fact about vector norms on Cnis that they are allequiv- alent. The only tool we need to prove this is the following result: Every continuous function on a compact set of Cnassumes its maximum (and minimum) on that set. The term “compact” refers to a particular kind of setK, one which is both bounded and closed. Bounded means that for max x∈K,x,≤B<∞a n dc l o s e dm e a n st h a ti fl i m n→∞xn=x,t h e n x∈K. 1.6. NORMS 27 Theorem 1.6.2. All norms on Cnare equivalent. Proof. Since equivalence of norms is an equivalence condition, we can take one of the norms to be the in finity norm ,·,∞.Denote the other norm by ,·,.N o w d e fineK={x|,x,∞=1 }.This set, called the unit ball in the infinity norm, is compact. Now we de fine m=m i n x∈K,x,and M=m a x x∈K,x, Since,·,is a continuous function on K(from the lemma above) and since Kis compact, we have that both the minimum and maximum are attained by speci fic vectors in K. Since these vectors are nonzero (they’re in K)a n d because ,x,is positive for nonzero vectors, it must follow that 0 <m< M<∞. Hence, on K,t h er e l a t i o n m,x,≤, x,∞≤M,x, holds true. For any vector x∈Cnwe can write x=wx ,x,∞W ,x,∞and x ,x,∞∈K.Thus mEEEEx ,x,∞EEEE≤EEEEx ,x,∞EEEE ∞≤MEEEEx ,x,∞EEEE mEEEEx ,x,∞EEEE,x, ∞≤EEEEx ,x,∞EEEE ∞,x,∞≤MEEEEx ,x,∞EEEE,x, ∞ m,x,≤, x,∞≤M,x, and the theorem is proved. Example 1.6.1. Example. Find the estimates for the equivalence of ,·,2 and,·,∞ Solution. Letx∈Cn. Then, because we know for any finite sequences 28 CHAPTER 1. VECTORS AND VECTOR SPACES thatn i=1|aibi|≤max 1≤i≤n|ai|n i=1|bi| ,x,2=Xn3 i=1|xi|2~1 2 ≤Xn3 i=11·|xi|2~1 2 ≤w max 1≤i≤n|xi|2W1/2Xn3 i=11~1 2 =n1 2,x,∞ On the other hand, by the Cauchy-Schwartz inequality ,x,∞=m a x 1≤i≤n|xi| ≤n3 i=1|xi| ≤Xn3 i=11~1 2Xn3 i=1|xi|2~1/2 =n1 2,x,2 Putting these inequalities together we have n−1 2,x,2≤,x,∞≤n1 2,x,2 This makes m=n−1/2andM=n1 2. Remark 1.6.2. Note that the constants mandMdepend on the dimension of the vector space. Though not the rule in all cases, it is mostly thesituation. Norms on polynomial spaces Polynomial spaces, as we have considered earlier, can be given norms as well.Since they are function spaces, our norms usually need to consider all the values of the independent variable. In many, though not all, cases we need 1.6. NORMS 29 to restrict the domains of the polynomials. With that in mind we introduce the notation Pk(a, b)=Pkwith domain restricted to the interval [ a, b] We now de fine the function versions of the same three norms we have just studied. For functions p(x)i nPk(a, b)w ed e fine 1.,p(x),2=D$b a|p(x)|2dxi1 2 2.,p(x),1=$b a|p(x)|dx 3.,p(x),∞=m a x a≤x≤b|p(x)| The positivity and homogeneity properties are fairly easy to prove. The triangle property is a little more involved. However, it has essentially beenproved for the earlier norms. In the present case, one merely “integrates” over the inequality. Sometimes ,·, 2is called the energy norm. T h ei n t e g r a ln o r m sa r er e a l l yt h e norm for polynomial spaces. Alternate norms use pointwise evaluation or even derivatives depending on the appli-cation. Here is a common type of norm that features the first derivative. Forp∈P n(a, b)d efine ,p,=m a x a≤x≤b|p(x)|+m a x a≤x≤beepI(x)ee As is evident this norm becomes large not only when the polynomial is large but also when its derivative is large. If we remove the term max a≤x≤b|p(x)| from the norm above and de fine N(p)= m a x a≤x≤beepI(x)ee This function satis fies all the norm properties except one and thus is not a norm. (See the exercises.) Point evaluation-type norms take us too far a field of our goals partly because making poi nt evaluations into norms requires some knowledge of interpolation and related topics. Leave it said that the obvious point evaluation functions such as p(a)a n dt h el i k ew i l ln o tp r o v i d e us with norms. 30 CHAPTER 1. VECTORS AND VECTOR SPACES 1.7 Ordered Bases Given a vector space Vwith a basis S={v1,v2,... ,v k}we now know that every vector v∈Vhas a representation with respect to the basis v=a1v1+a2v2+···+akvk. But no order is implied. For example, for R2we have S={e1,e2}={e2,e1} shows us that there is no particular order convey through the de finition of a basis. When we place an order on a basis we will notice an underlyingalgebraic structure of all k-dimensional vector spaces. Definition 1.7.1. LetVbe a k-dimensional vector space with basis S= {v 1;v2;...;vk}is speci fied with a fixed and well de fined order as indicated by their relevant positions. Then Sis called an ordered basis. With or- dered bases we obtain coordinates .L e t Vbe a vector space of dimension kwith ordered basis S, and suppose v∈V.F o r 1 ≤i≤k,w ed e fine theithcoordinate ofvwith respect to Sto be the ithcoefficient aiin the representation v=a1v1+a2v2+···+aivi+···+akvk. In this way we can associate each v∈Vwith a k-tuple of numbers (a1,a2,... ,a k)∈Rkthat are the coe fficients of vwith respect to S.T h e k-tuple is unique, owing to the fixed ordering of S. Conversely, for each ordered k-tuple ( a1,a2,... ,a k)∈Rkthere is associated a unique vector v∈Vgiven by v=a1v1+a2v2+···+aivi+···+akvk. We will express this association as v∼(a1,a2,... ,a k) The following properties are each simple propositions: •Ifv∼(a1,a2,... ,a k)a n d w∼(b1,b2,... ,b k)t h e n v+w∼(a1+b1,a2+b2,... ,a k+bk) •Ifv∼(a1,a2,... ,a k)a n dα∈R(orC), then αv∼α(a1,a2,... ,a k)=(αa1,αa2,... ,αak) •Ifv∼(a1,a2,... ,a k)=( 0 ,0,...0), then v=0 . 1.7. ORDERED BASES 31 We now de fine a special type of linear function from one linear space to another. The special condition is linearity of the map. Definition 1.7.2. LetVandWbe two vector spaces. We say that Vand Warehomomorphic if there is a mapping Φbetween VandWfor which (1.) For vandwinV Φ(v+w)=Φ(v)+Φ(w) (2.) For vandα∈R(orC) Φ(αv)=αΦ(v) In this case we call Φahomomorphism from VtoW.F u r t h e r m o r e ,w es a y thatVandWare isomorphic if they are homomorphic and if (3.) For each w∈Wthere exists a unique v∈Vsuch that Φ(v)=w In this case we call Φaisomorphism from VtoW. We put all this together to show that finite dimensional vector spaces over the reals (resp. complex numers) and the standard Euclidean spaces Rk(resp. Ck) are very, very closely related. Indeed from the point of view of isometry, they are identical. Theorem 1.7.1. IfVis ak-dimensional vector space over R(respC), then Vis isomorphic to Rk(resp. Ck). This constitutes the beginning of the su fficiency of matrix theory as a tool to study finite dimentsional vector spaces. Definition 1.7.3. The mapping cs:V→Rkdefined by cs(v)=(a1,a2,... ,a k) where v∼(a1,a2,... ,a k)i st h es o - c a l l e d coordinate map. Example 1.7.1. We have shown that in R3the solutions to the equation x1+x2+x3=0f o r x=(x1,x2,x3)∈R3is a subspace V0with basis S={v1,v2}={(−1,0,1),(−1,1,0)}. With respect to this basis v0∈V0if there are constants α0,β0so that v0=α0(−1,0,1) +β0(−1,1,0) With respect to this basis the coordinate map has the form cs(v0)=(α0,β0) Therefore, we have established that V0is isomorphic to R2. 32 CHAPTER 1. VECTORS AND VECTOR SPACES 1.8 Exercises. 1. Show that {(a, b,0)|a, b∈R}is a subspace of R3by proving that it is spanned by vectors in R3. Find at least two sets of spanning sets. 2. Show that {(a, b,1)|a, b∈R}cannot be a subspace of R3. 3. Show that {(a−b,2b−a, a−b)|a, b∈R}is a subspace of R3by proving that it is spanned by vectors in R3. 4. For any w∈R3, show that Uw={x∈R3|x·w=dW=0}isnot subpace of R3. 5. Find a set of vectors in R3that spans the subspace Uw={x∈R3|x· w=0},w h e r e w=( 1,1,1). 6. Why can {(a−b, a2,a b)|a, b∈R}never be a subspace of R3? 7. Let Q={x1,...,x k}be a set of distinct points on the real line with k<n . Show that the subset PQof the polynomial space Pnof polynomials zero on the set Qis in fact a subspace of Pn. Characterize PQifk>n andk=n. 8. In the product space de fined above prove that de finitions given the result is a vector space. 9. What is the product space R2×R3? 10. Find a basis for Q={ax+bx3|a, b∈R}. 11. Let T⊂Pnbe those polynomials of exactly degree n. Show that Tis not a subspace of Pn. 12. What is the dimension of Q={ax+ax2+bx3|a, b∈Q}. What is a basis for Q? 13. Given that S={x1,x2, ..., x 2k}andT={y1,y2, ..., y 2k}are both bases of a vector space V.(Note, the space Vhas dimension 2 k.) Consider the set of any kintegers L={l1,..., l k}⊂{1,2,..., 2k}.(i) Show that associated with P={xl1,xl2, ..., x lk}there are exactly kvectors from T,s a yQ={ym1,ym2,. . . ,y mk}so that P∪Qis also ab a s i sf o r V.(ii) Is the set of vectors from Tunique? Why or why not? 1.8. EXERCISES. 33 14. Given Pn.D efineZn={pI(x)|p(x)∈Pn}.( T h e n o t a t i o n pI(x)i st h e standard notation for the derivative of the function p(x)w i t hr e s p e c t to the variable x.) What is another way to express Znin terms of previously de fined spaces? 15. Show that ,x,∞is a norm. (Hint. The condition (iii) should be the focal point of your e ffort.) 16. Let S={x1,x2,. . . , x n}⊂Rn.F o r e a c h j=1,2,...,n suppose xj∈Shas the property that its firstj−1 entries equal zero and the jthentry is nonzero. Show that Sis a basis of Rn. 17. Let w=(w1,w2,w3)∈R3,where all the components of ware strictly positive. De fine,·,wonR3by,x,w=p w1|x1|2+w2|x3|2+w2|x3|2Q1/2 . Show that ,·,wis a norm on R3. 18. Show that equivalence of norms is an equivalence relation.19. De fine for p∈P n(a, b) the function N(p)=m a x a≤x≤b|pI(x)|.Show that this is not a norm on Pn(a, b). 20. For p∈Pn(a, b)d efine,p,=m a x a≤x≤b|p(x)|+m a x a≤x≤b|pII(x)|. Show this is a norm on Pn(a, b). 21. Suppose that Vis a vector space with dimension k. Find two (linearly independent) spanning sets S={v1,v2,...,v k}andW={w1,w2,...,w k} ofVsuch that if any m<k vectors are chosen from Sand any k−m vectors are chosen from T,the resulting set will be a basis for V. 22. For p∈Pn(a, b)d e fineN(p)=eepDa+b 2iee.Show this is not a norm onPn(a, b). 23. Find the estimates for the equivalence of ,·,1and,·,∞. 24. Find the estimates for the equivalence of ,·,1and,·,2. 25. Show that Pndefined over the reals is isomorphic to Rn+1. 26. Show that Tn, the space of trigonometric polynomials, de fined over the reals is isomorphic to Rn. 27. Show that the product space Ck×Cmis isomorphic to Ck+m. 28. What is the relation between the product space Pn×PnandP2n? Find the polynomial space that is isomorphic to Pn×Pn. 34 CHAPTER 1. VECTORS AND VECTOR SPACES Terms. Field Vector space scalar multiplication Closed spaceOriginPolynomial spaceSubspace, linear subspaceSpan Spanning set RepresentationUniqueness of representationlinear dependencelinear independencelinear combination Basis Extension to a basisDimensionNormf 2norm;f1norm;f2∞norm Cauchy-Schwartz inequality Fundamental Theorem of AlgebraCardinalityTriangle inquality