Math 110 - Fall 05 - Lectures notes # 6 - Sep 12 (Monday)Homework due Thursday, Sep 15:(1) Sec 1.5: 1 (justify) (postponed from last time)2bd, 8, 9,12 (postponed from last time)13, 17(2) Recall that that the set of symmetric nxn matrices form a subspaceW of M_{n x n}(F). Find a basis of W. What is the dimension of W?(3) Sec 1.6: 1 (justify), 5 (justify), 11, 12, 13, 29, 31Goal for the day: Understand bases and dimension:Express space V in simplist possible way:where every vector in V is a unique linearcombination of a set of linear independentvectors called a basisShow that if W has a finite basis, then allbases have the same number of vectors, andthis number is called the dimension of VDef: If V = span(S), and S is linearly independent, we callS a basis of VEx: V = F^n, then S = {(1,0,...,0), (0,1,0,...,0), ... , (0,...,0,1)}is called the standard basisASK & WAIT: Why is this a basis?Ex: M_{m x n}(F): S = {E^{11}, E^{12},..., E^{ij}, ... , E^{mn} }where E^{ij} is a matrix where entry ij is 1 and rest 0;S is also called standard basis, for same reason as last exampleEx: V = F^2, S = {(1,0), (1,1)} is a basis, but not standardASK & WAIT: why is this a basis?Ex: P_n(F) = {polynomials of degree <= n over F}S = {1,x,x^2,...,x^n} is standard basisEx: P(F) = {all polynomials over F}S = {1,x,x^2,...} is a basis (not finite!)Recall Thm 1 from last time: Let V be a vector space over F, S a subsetThen any v in span(S) can be written as a unique linear combination1of vectors in S if and only if S is linearly independentCorollary: a subset S of V is a basis for V if and only ifeach v in V can be written as a unique linear combination ofvectors in SProof: If S is a basis for V, then by definition V = span(S) andS is linearly independent. By Thm 1, this implies that eachv in V can be written as a unique linear combination of S.If each v in V is a unique linear combination of S, thenV = span(S) and by the Thm 1, S is linearly independent, sothat S is a basis.Now we move on to constructing bases, and showing, if finite, theyall have to have the same number of vectors (the dimension)Thm 2: If V = span(S) and S is finite, then S contains a finitebasis S1 of V.Proof: If S already independent, nothing to show, so assume S dependent.The idea of the proof is simply to start picking vectors out ofS to put in S1, continuing as long as S1 is independent.As soon as putting any other vector from S into S1 wouldmake S1 dependent, we will show that S1 is a basis.We can pick vectors out of S in any order we like, and this willproduce a basis (not always the same one!)Formally, to do an induction,pick any nonzero s in S,set S1 = {s}; S1 is independent (why?)remove s from S: S2 = S - {s} (so we can’t pick it again)repeatif there exists some t in S2 such thatS1 U {t} is independent, thenadd t to S1: S1 = S1 U {t}remove t from S2: S2 = S2 - {t}until we can’t find any such tClaim 1: This algorithm for building S1 eventually stopsProof: Since S is finite, there are only finitely2many t to pick, and since S is dependent,we know we will eventuallyrun out of t’s to add.Claim 2: When we stop, S1 is independentProof: by construction, S1 is independent at every stepClaim 3: When we stop, V = span(S1)Proof: at every step of the algorithm S = S1 U S2.When we stop S2 is in Span(S1), sospan(S1) = span(S1 U S2) = span(S) = VThe next Theorem will be the main tool for show that all baseshave the same dimensionThm 3 (Replacement Thm): Let V be a vector space over F,V generated by G, G contains n vectors. Let L be any otherlinearly independent subset of V, and suppose it containsm vectors. Then m <= n, and there is a subset H of G containingm-n vectors such that the n vectors in L U H also span V.We defer the proof briefly to presentCorollary 1: Let V be a vector space over F with a finite generating set.Then every basis of V has the same number of vectors.Proof of Corollary 1: If V has a finite generating set, then it hasa finite basis, call it G, by Thm 2. Let n be the number ofvectors in G. Let L be any other finite basis of V, containingm vectors. By Thm 3, m <= n. Reversing the roles of G and L,we get n <= m. So m=n.Def: A vector space V is called finite dimensional if it has a finitebasis. The number of vectors in the basis is called thedimension of V, written dim(V) .(By the corollary, this number does not dependon the choice of basis, so the definition makes sense).If V does not have a finite basis, it is calledinfinite-dimensionalEx: dim(F^n) = n, dim(F) = 13ASK & WAIT: if V = C, F = R, what is dim(V)?Ex: dim(M_{m x n}(F)) = mnEx: P(F) is infinite dimensionalEx: we say dim({0}) = 0Proof of Replacement Theorem:We use induction on m. When m=0, so L is the null_set, then m=0 <= n,and we can simply choose H = G to get the spanning set G = G U null_setwith n vectors.Now assume the Thm is true for m; we need to prove it for m+1.This means that we assume there is a linearly independent subset Lof V, where L contains m+1 vectors, and have to prove 2 things:(1) that m+1 <= n(2) we can find a set H of n-(m+1) vectors in G such that span(L U H)=VWrite L = {v_1,v_2,...,v_{m+1}}. Then L’ = {v_1,...,v_m} hasjust m vectors, is linearly independent too (why?), so by theinduction hypothesis, we can apply the Thm to L’, conclude thatm <= n, and pick n-m vectors out of G to get H’ = {u_1,...,u_{n-m}}where L’ U H’ span V. Thus v_{m+1} is in span(L’ U H’) = V, so wecan write v_{m+1} as a linear combination(*) v_{m+1} = a_1*v_1 + ... + a_m*v_m + b_1*u_1 + ... + b_{n-m}*u_{n-m}Not all the b_i can be zero, because then we would havev_{m+1} in span(v_1,..,v_m), contradicting the fact theL is independent (why?). In particular, this meansn-m>0, or m < n, or m+1 <= n, proving the first part of the induction.For the second part, finding n-(m+1) = n-m-1 vectors H so thatL U H span V, we suppose, by renumbering the u’s if necessary,that b_1 is nonzero. Then we can solve (*) for u_1 to get(**) u_1 = (-a_1/b_1)*v_1 + ... + (-a_m/b_1)*v_m + (1/b_1)*v_{m+1}+ (-b_2/b_1)*u_1 + ... + (-b_{n-m}/b_1)*u_{n-m}i.e. u_1 is in span({v_1,...,v_{m+1},u_2,...,u_{n-m})Now let H = {u_2,...,u_{n-m}} contain n-m-1 vectors. We have just shown thatspan(L U H) = span(L U H U {u_1}) since u_1 is in span L U H= span(L U H’) since H’ = H U {u_1}= span(L’ U {v_{m+1}} U H’) since L = L’ U {v_{m+1}}contains span(L’ U H’) since we removed v_{m+1}= …