Linear Algebra Examples, Subspaces, Basis and Dimension PDF

198 Chapter 3 Matrices parallel to the plane but are not parallel to each other. In algebraic parlance, two such vectors span the plane and are linearly independent. Fewer than two vectors will not wo...

198 Chapter 3 Matrices parallel to the plane but are not parallel to each other. In algebraic parlance, two such vectors span the plane and are linearly independent. Fewer than two vectors will not work; more than two vectors is not necessary. This is the essence of a basis for a subspace. Definition A basis for a subspace S of ll r is a set of vectors in S that 1. spans S and 2. is linearly independent. Exa m p l e 3. 4 2 In Section 2.3, we saw that the standard unit vectors e1, e2 ,... e n in !R n are linearly independent and span !R n. Therefore, they form a basis for !R n , called the standard 4 basis. Exa m p l e 3. 4 3 In Example 2. 1 9, we showed that IR 2 = span ([ _ , ] [ ] ) [ ] [ ]. Since _ and are also linearly independent (as they are not multiples), they form a basis for IR 2. 4 { [ l [ ] } { [ l [ ] } A subspace can (and will) have more than one basis. For example, we have just seen that IR 2 has the standard basis and the basis _. How- ever, we will prove shortly that the number of vectors in a basis for a given subspace will always be the same. Exa m p l e 3. 4 4 Find a basis for S = span (u, v, w) , where Solution The vectors u, v, and w already span S, so they will be a basis for S if they are also linearly independent. It is easy to determine that they are not; indeed, w = 2u - 3v. Therefore, we can ignore w, since any linear combinations involving u, v, and w can be rewritten to involve u and v alone. (Also see Exercise 47 in Section 2.3.) This implies that S = span (u, v , w) = span ( u, v) , and since u and v are certainly linearly independent (why?), they form a basis for S. (Geometrically, this means that u, v, and w all lie in the same plane and u and v can serve as a set of direction vectors 4 for this plane.)  Section 3. 5 Subspaces, Basis, Dimension, and Rank 199 Exa m p l e 3. 4 5 Find a basis for the row space of [ -! 3 -1 0 A= 2 1 -2 1 6 Solution The reduced row echelon form of A is 0 1 0 1 2 0 0 0 1 0 0 0 By Theorem 3.20, row(A) = row(R), so it is enough to find a basis for the row space of R. But row(R) is clearly spanned by its nonzero rows, and it is easy to check that the staircase pattern forces the first three rows of R to be linearly independent. (This is a general fact, one that you will need to establish to prove Exercise 33.) Therefore, a basis for the row space of A is {[1 0 0 - 1 ] , [0 1 2 0 3 ] , [0 0 0 4]} We can use the method of Example 3.45 to find a basis for the subspace spanned by a given set of vectors. Exa m p l e 3. 4 6 Rework Example 3.44 using the method from Example 3.45. Solution We transpose u, v, and w to get row vectors and then form a matrix with these vectors as its rows: [ !> ] Proceeding as in Example 3.45, we reduce B to its reduced row echelon form -! 1 0 and use the nonzero row vectors as a basis for the row space. Since we started with column vectors, we must transpose again. Thus, a basis for span (u, v, w) is { [ H Ul l R e m arks In fact, we do not need to go all the way to reduced row echelon form-row ech­ elon form is far enough. If U is a row echelon form of A, then the nonzero row vectors 200 Chapter 3 Matrices of U will form a basis for row(A) (see Exercise 33). This approach has the advantage of (often) allowing us to avoid fractions. In Example 3.46, B can be reduced to which gives us the basis for span (u, v, w). \HH - rn Observe that the methods used in Example 3.44, Example 3.46, and the Remark above will generally produce different bases. We now turn to the problem of finding a basis for the column space of a matrix A. One method is simply to transpose the matrix. The column vectors of A become the row vectors of A T' and we can apply the method of Example 3.45 to find a basis for row(A T ). Transposing these vectors then gives us a basis for col (A). (You are asked to do this in Exercises 2 1 -24.) This approach, however, requires performing a new set of row operations on A T. Instead, we prefer to take an approach that allows us to use the row reduced form of A that we have already computed. Recall that a product Ax of a matrix and a vec­ tor corresponds to a linear combination of the columns of A with the entries of x as coefficients. Thus, a nontrivial solution to Ax = 0 represents a dependence relation among the columns of A. Since elementary row operations do not affect the solution set, if A is row equivalent to R, the columns of A have the same dependence relation­ ships as the columns of R. This important observation is the basis (no pun intended!) for the technique we now use to find a basis for col (A). Exa m p l e 3. 4 1 Find a basis for the column space of the matrix from Example 3.45, 1 3 1 [- -:i -1 0 1 A= 2 -2 6 1 Solution Let a; denote a column vector of A and let r; denote a column vector of the [ reduced echelon form -il 0 1 0 1 2 0 R 0 0 1 0 0 0 We can quickly see by inspection that r3 = r 1 + 2r2 and rs = - r 1 + 3r2 + 4r4 (Check that, as predicted, the corresponding column vectors of A satisfy the same depen­ dence relations.) Thus, r3 and rs contribute nothing to col (R). The remaining column  Section 3. 5 Subspaces, Basis, Dimension, and Rank 201 vectors, r 1 , r2 , and r4 , are linearly independent, since they are just standard unit vec­ tors. The corresponding statements are therefore true of the column vectors of A. Thus, among the column vectors ofA, we eliminate the dependent ones ( a3 and a5 ) , and the remaining ones will be linearly independent and hence form a basis for col(A). What is the fastest way to find this basis? Use the columns of A that correspond to the columns of R containing the leading ls. A basis for col(A) is r....,.., } { [ - ;H - H - m Warning Elementary row operations change the column space! In our example, col (A) * col (R), since every vector in col (R) has its fourth component equal to 0 but this is certainly not true of col (A). So we must go back to the original matrix A to get the column vectors for a basis of col (A). To be specific, in Example 3.47, r 1 , r2 , and r4 do not form a basis for the column space of A. Exa m p l e 3. 4 8 Find a basis for the null space of matrix A from Example 3.47. Solution There is really nothing new here except the terminology. We simply have to find and describe the solutions of the homogeneous system Ax = 0. We have al­ ready computed the reduced row echelon form R of A, so all that remains to be done in Gauss-Jordan elimination is to solve for the leading variables in terms of the free variables. The final augmented matrix is 0 1 0 2 0 0 0 1 0 0 0 If then the leading l s are in columns 1 , 2, and 4, so we solve for x 1 , x2 , and x4 in terms of the free variables x3 and x5 We get x 1 = - x3 + x5 , x2 = - 2x3 - 3x5, and x4 = - 4x5. Setting x3 = s and x5 = t, we obtain X1 -s + t -1 1 X2 - 2s - 3t -2 -3 x = X3 s = s 1 + t 0 = su + tv X4 -4t 0 -4 X5 0 Thus, u and v span null(A ), and since they are linearly independent, they form a basis for null(A). 4 202 Chapter 3 Matrices Following is a summary of the most effective procedure to use to find bases for the row space, the column space, and the null space of a matrix A. 1. Find the reduced row echelon form R of A. 2. Use the nonzero row vectors of R (containing the leading l s) to form a basis for row(A). 3. Use the column vectors o fA that correspond t o the columns o f R containing the leading ls (the pivot columns) to form a basis for col (A). 4. Solve fo r the leading variables o f Rx = 0 i n terms o f the free variables, set the free variables equal to parameters, substitute back into x, and write the result as a linear combination off vectors (where f is the number of free variables). These f vectors form a basis for null (A). I f we d o not need t o find the null space, then it i s faster t o simply reduce A t o row echelon form to find bases for the row and column spaces. Steps 2 and 3 above remain valid (with the substitution of the word "pivots" for "leading l s"). Dimension and Rank We have observed that although a subspace will have different bases, each basis has the same number of vectors. This fundamental fact will be of vital importance from here on in this book. Theorem 3. 2 3 The Basis Theorem Let S be a subspace of !R n. Then any two bases for S have the same number of vectors. Proof Let B = {u 1 , u2 ,... , u,.} and C = {v1 , v2 ,. , v, } be bases for S. We need to prove that r = s. We do so by showing that neither of the other two possibilities, r < s Sherlock Holmes noted, "When or r > s, can occur. you have eliminated the impos­ Suppose that r < s. We will show that this forces C to be a linearly dependent set sible, whatever remains, however of vectors. To this end, let improbable, must be the truth" (from The Sign of Four by Sir (1) Arthur Conan Doyle). Since B i s a basis for S , we can write each a s a linear combination o f the elements "f V; V1 = a 1 1 u, + a 12 u2 + · · · + a , rur Vz = a 1 1 u , + a z 2U2 + · · · + a zrUr (2) Substituting the Equations (2) into Equation ( 1 ) , we obtain  Section 3. 5 Subspaces, Basis, Dimension, and Rank 203 Regrouping, we have ( c 1 a ll + C2 a2 1 +... + c, as1 ) U1 + ( c 1 a 1 2 + C2 a22 +... + cs asz ) Uz ·+ + ( c 1 a 1r + c2a2 r + + c, a ) u, = 0 · · · · · Now, since B is a basis, the u/s are linearly independent. So each of the expressions in parentheses must be zero: c 1 a 11 + c2a2 1 + + c, a, 1 = 0 · · · C 1 a 1 2 + C2 a22 +... + csas 2 = 0 This is a homogeneous system of r linear equations in the s variables c 1 c 2 ,, c5 (The ,.. fact that the variables appear to the left of the coefficients makes no difference.) Since r < s, we know from Theorem 2.3 that there are infinitely many solutions. In particu­ lar, there is a nontrivial solution, giving a nontrivial dependence relation in Equa­ tion ( 1 ). Thus, C is a linearly dependent set of vectors. But this finding contradicts the fact that C was given to be a basis and hence linearly independent. We conclude that r < s is not possible. Similarly (interchanging the roles of B and C), we find that r > s leads to a contradiction. Hence, we must have r = s, as desired. Since all bases for a given subspace must have the same number of vectors, we can attach a name to this number. Definition If S is a subspace of !R n , then the number of vectors in a basis for S is called the dimension of S, denoted dim S. Remark The zero vector 0 by itself is always a subspace of !R n. (Why?) Yet any set containing the zero vector (and, in particular, { 0}) is linearly dependent, so { 0} cannot have a basis. We define dim {O} to be 0. Exa m p l e 3. 4 9 Since the standard basis for !R n has n vectors, dim !R n = n. (Note that this result agrees with our intuitive understanding of dimension for n :s 3.) Exa m p l e 3. 5 0 In Examples 3.45 through 3.48, we found that row(A) has a basis with three vectors, col (A) has a basis with three vectors, and null (A) has a basis with two vectors. Hence, dim(row(A)) = 3, dim(col (A)) = 3, and dim(null (A)) = 2. A single example is not enough on which to speculate, but the fact that the row and column spaces in Example 3.50 have the same dimension is no accident. Nor is the fact that the sum of dim(col (A)) and dim(null (A)) is 5, the number of columns of A. We now prove that these relationships are true in general. 204 Chapter 3 Matrices Theorem 3. 2 4 The row and column spaces of a matrix A have the same dimension. Proof Let R be the reduced row echelon form of A. By Theorem 3.20, row(A) = row(R), so dim(row (A)) = dim(row(R)) = number of nonzero rows of R = number of leading l s of R Let this number be called r. Now col (A) * col (R), but the columns of A and R have the same dependence relationships. Therefore, dim(col (A)) = dim(col (R)). Since there are r leading ls, R has r columns that are standard unit vectors, e1, e2 ,... , er. (These will be vectors in !R m if A and R are m X n matrices.) These r vectors are linearly independent, and the remaining columns of R are linear combinations of them. Thus, dim(col (R)) = r. It follows that dim(row(A)) = r = dim(col (A)), as we wished to prove. 1878 The rank o f a matrix was first de­ (1849-1917), fined in by Georg Frobenius although he defined Definition The rank of a matrix A is the dimension of its row and column spaces and is denoted by rank(A). have done here. (See Chapter Frobenius was a German 4.) it using determinants and not as we For Example 3.50, we can thus write rank(A) = 3. mathematician who received his doctorate from and later taught R e m a rks at the University of Berlin. Best The preceding definition agrees with the more informal definition of rank that known for his contributions to was introduced in Chapter 2. The advantage of our new definition is that it is much group theory, Frobenius used more flexible. matrices in his work on group The rank of a matrix simultaneously gives us information about linear representations. dependence among the row vectors of the matrix and among its column vectors. In particular, it tells us the number of rows and columns that are linearly independent (and this number is the same in each case!). Since the row vectors of A are the column vectors of A r, Theorem 3.24 has the following immediate corollary. Theorem 3. 2 5 For any matrix A, rank (A T) = rank (A ) Proof We have rank (A T) = dim ( col (A T)) = dim ( row (A )) = rank (A ) Definition The nullity of a matrix A is the dimension of its null space and is denoted by nullity(A).  Section 3. 5 Subspaces, Basis, Dimension, and Rank 205 In other words, nullity(A) is the dimension of the solution space of Ax = 0, which is the same as the number of free variables in the solution. We can now revisit the Rank Theorem (Theorem 2.2), rephrasing it in terms of our new definitions. Theorem 3. 2 6 The Rank Theorem If A is an m X n matrix, then rank (A ) + nullity (A ) = n Proof - - Let R be the reduced row echelon form of A, and suppose that rank(A) = r. Then R has r leading ls, so there are r leading variables and n r free variables in the - solution to Ax = 0. Since dim(null (A)) = n r, we have rank (A ) + nullity (A ) = r + (n r) = n Often, when we need to know the nullity of a matrix, we do not need to know the actual solution of Ax = 0. The Rank Theorem is extremely useful in such situations, as the following example illustrates. Exa m p l e 3. 5 1 Find the nullity of each of the following matrices: M= [I : and N [ 1 4 7 -2 -3 -1 : Solution Since the two columns of M are clearly linearly independent, rank(M ) = 2. Thus, by the Rank Theorem, nullity(M ) = 2 - rank(M ) = 2 - 2 = 0. There is no obvious dependence among the rows or columns of N, so we apply row operations to reduce it to [: - ] -2 2 1 0 0 We have reduced the matrix far enough (we do not need reduced row echelon form - - here, since we are not looking for a basis for the null space). We see that there are only two nonzero rows, so rank(N) = 2. Hence, nullity(N) = 4 rank(N) = 4 2 = 2. 4 The results of this section allow us to extend the Fundamental Theorem of Invertible Matrices (Theorem 3. 1 2 ). 206 Chapter 3 Matrices Theorem 3. 2 1 The Fundamental Theorem of Invertible Matrices: Version 2 Let A be an n X n matrix. The following statements are equivalent: a. A is invertible. b. Ax = b has a unique solution for every b in ll r. c. Ax = 0 has only the trivial solution. d. The reduced row echelon form of A is In - e. A is a product of elementary matrices. f. rank(A) = n g. nullity(A) = 0 h. The column vectors of A are linearly independent. i. The column vectors of A span ll r. j. The column vectors of A form a basis for ll r. k. The row vectors of A are linearly independent. 1. The row vectors of A span !R n. m. The row vectors of A form a basis for !R n. The 1884nullbyityJames in(1814-1887), of a matrix Joseph wasSyldefined vesterin who -propertieswas i nterested of certain matrices Proof We have already established the equivalence of (a) through (e). It remains to be shown that statements (f) to (m) are equivalent to the first five statements. that do invariants types not change of transformations.under Bornthe (f) (g) Since rank(A) + nullity(A) = n when A is an n X n matrix, it follows from the Rank Theorem that rank(A) = n if and only if nullity(A) = 0. insecond England, Sylv ester presidentSociety. became of theInLondon (f) ==> (d) ==> ( c) ==> (h) If rank(A) = n , then the reduced row echelon form of A has Mathematical whi l e teaching at Johns 1878, Hopkins n leading ls and so is I - From (d) ==> (c) we know that Ax = 0 has only the trivial n solution, which implies that the column vectors of A are linearly independent, since University founded thein Balthetfirst imore, he Ax is just a linear combination of the column vectors of A. (h) ==> (i) If the column vectors of A are linearly independent, then Ax = 0 has only American Journal of journal in the United States. Mathematics, mathematical the trivial solution. Thus, by (c) ==> (b), Ax = b has a unique solution for every b in !R n. This means that every vector b in !R n can be written as a linear combination of the column vectors of A, establishing (i). (i) ==> (j) If the column vectors of A span W, then col (A) = !R n by definition, so rank(A) = dim(col (A)) = n. This is (f), and we have already established that (f) ==> (h). We conclude that the column vectors of A are linearly independent and so form a basis for !R n , since, by assumption, they also span !R n. (j) ==> (f) If the column vectors of A form a basis for !R n , then, in particular, they are linearly independent. It follows that the reduced row echelon form of A contains n leading l s, and thus rank(A) = n. The above discussion shows that (f) ==> (d) ==> (c) ==> (h) ==> (i) ==> (j) ==> (f) (g). Now recall that, by Theorem 3.25, rank(A T ) = rank(A), so what we have just proved gives us the corresponding results about the column vectors of A r_ These are then results about the row vectors of A, bringing (k), (1), and (m) into the network of equivalences and completing the proof. Theorems such as the Fundamental Theorem are not merely of theoretical inter­ est. They are tremendous labor-saving devices as well. The Fundamental Theorem has already allowed us to cut in half the work needed to check that two square matri­ ces are inverses. It also simplifies the task of showing that certain sets of vectors are bases for !R n. Indeed, when we have a set of n vectors in !R n , that set will be a basis for !R n if either of the necessary properties of linear independence or spanning set is true. The next example shows how easy the calculations can be.  Section 3. 5 Subspaces, Basis, Dimension, and Rank 201 m Exa m p l e 3. 5 2 Show that the vectors mr n and form a basis for IR 3. Solution According to the Fundamental Theorem, the vectors will form a basis for IR 3 if and only if a matrix with these vectors as its columns (or rows) has rank 3. We [ f l --7 [ - J perform just enough row operations to determine this: A - We see that A has rank 3, so the given vectors are a basis for IR 3 by the equivalence of 4 (f) and (j). The next theorem is an application of both the Rank Theorem and the Funda­ mental Theorem. We will require this result in Chapters 5 and 7. Theorem 3. 2 8 Let A be an m X n matrix. Then: a. rank(A TA) = rank(A) b. The n X n matrix A TA is invertible if and only if rank(A) = n. Proof (a) Since A TA is n X n, it has the same number of columns as A. The Rank Theorem then tells us that rank (A ) + nullity (A ) = n = rank (A TA ) + nullity (A TA ) Hence, to show that rank(A) = rank(A TA), it is enough to show that nullity(A) = nullity(A TA). We will do so by establishing that the null spaces of A and A TA are the same. To this end, let x be in null (A) so that Ax = 0. Then A TAx = A To = 0, and thus x is in null (A TA). Conversely, let x be in null (A TA). Then A TAx = 0, so xTA TAx = xTO = 0. But then and hence Ax = 0, by Theorem 1.2 (d). Therefore, x is in null (A), so null (A) null (A TA), as required. (b) By the Fundamental Theorem, the n X n matrix A TA is invertible if and only if rank(A TA) = n. But, by (a) this is so if and only if rank(A) = n. Coordin ates We now return to one of the questions posed at the very beginning of this section: How should we view vectors in IR 3 that live in a plane through the origin? Are they two-dimensional or three-dimensional? The notions of basis and dimension will help clarify things. 208 Chapter 3 Matrices A plane through the origin is a two-dimensional subspace o f IR 3 , with any set of two direction vectors serving as a basis. Basis vectors locate coordinate axes in the plane/subspace, in turn allowing us to view the plane as a "copy" of IR 2 Before we illustrate this approach, we prove a theorem guaranteeing that "coordinates" that arise in this way are unique. Theorem 3. 2 9 Let S be a subspace of !R n and let B = {v1 , v2 ,... , vk } be a basis for S. For every vector v in S, there is exactly one way to write v as a linear combination of the basis vectors in B: Proof Since B is a basis, it spans S, so v can be written in at least one way as a linear combination of v1, v2 ,... , vk. Let one of these linear combinations be Our task is to show that this is the only way to write v as a linear combination of v1, v2 ,... , vk. To this end, suppose that we also have v = d1 v1 + d2v2 + · · · + dkvk Then Rearranging (using properties of vector algebra), we obtain (c 1 - d 1 )v1 + (c2 - d2 )v2 + · · · + (ck - dk ) vk = 0 Since B is a basis, v1, v2 ,... , vk are linearly independent. Therefore, (c 1 - d1 ) = (c2 - d2 ) = · · · = (ck - dk ) = 0 In other words, c1 = d1, c 2 = d2 , , ck = dk, and the two linear combinations are actually the same. Thus, there is exactly one way to write v as a linear combination of the basis vectors in B. Definition Let S be a subspace of !R n and let B = {v1 , v2 ,... , vk } be a basis for S. Let v be a vector in S, and write v = c1v1 + c2v2 + · · · + ckvk. Then c1, c2 ,... , ck are called the coordinates of v with respect to B, and the column vector is called the coordinate vector of v with respect to B. Exa m p l e 3. 5 3 Let E = { e 1 , e2 , e 3 } be the standard basis for IR 3. Find the coordinate vector of with respect to E.  Section 3. 5 Subspaces, Basis, Dimension, and Rank 209 Since v = 2e1 7e 4e 2 [ 47 ] Solution + 2 + 3, [v] E = It should be clear that the coordinate vector of every (column) vector in !R n with respect to the standard basis is just the vector itself. [ -} m [ ;l Exa m p l e 3. 5 4 ID Exompk 3.44, we