18.06 Linear Algebra, Problem Set 2 Solutions

18.06 Problem Set 2 Solution Total: 100 points Section 2.5. Problem 24: Use Gauss-Jordan elimination on [U I] to U −1 :     1 a b 1 0 0 1 c  x1 x2 x3  = 0 1 U U −1 = I 0 0 1 0 0 Solution (4 points): Row  1 a b 1 0 0 1 c 0 1 0 0 1 0 0 reduce [U I] to get [I U −1 ] as follows (here   0 (R1 = R1 − aR2 ) 1 0 b − ac 0 −� (R2 = R2 − cR2 ) 0 1 0 0 0 1 1 ( ) R1 = R1 − (b − ac)R3 1 0 0 0 1 0 −� 0 0 1 find the upper triangular  0 0 . 1 Ri stands for the ith row):  1 −a 0 0 1 −c 0 0 1  1 −a ac − b 0 1 −c  . 0 0 1 Section 2.5. Problem 40: (Recommended) A is a 4 by 4 matrix with 1’s on the diagonal and −a, −b, −c on the diagonal above. Find A−1 for this bidiagonal matrix. Solution (12 points): Row reduce [A I] to get [I A−1 ] as follows (here Ri stands for the ith row):  1 −a 0 0 0 1 −b 0  0 0 1 −c 0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 0  (R1 = R1 + aR2 ) 1 (R = R2 + bR2 )  0 −� 2 (R3 = R3 + cR4 ) 0 0  (R1 = R1 + abR3 ) 1 (R = R2 + bcR4 )  0 −� 2 0 0  0 0  0 1  0 0  c 1  1 a ab abc 0 1 b bc  . 0 0 1 c  0 0 0 1 0 −ab 0 1 0 −bc 0 1 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 a 1 0 0 0 b 1 0 Alternatively, write A = I − N . Then N has a, b, c above the main diagonal, and all other entries equal to 0. Hence A−1 = (I − N )−1 = I + N + N 2 + N 3 as N 4 = 0. Section 2.6. Problem 13: (Recommended) Compute L and U for the symmetric matrix   a a a a a b b b   A= a b c c  . a b c d Find four conditions on a, b, c, d to get A = LU with four pivots. Solution (4 points): Elimination subtracts row 1 from rows 2–4, then row 2 from rows 3–4, and finally row 3 from row 4; the result is U. All the multipliers �ij are equal to 1; so L is the lower triangular matrix with 1’s on the diagonal and below it.     a a a a a a a a 0 b − a b − a b − a     −� 0 b − a b − a b − a A −�  0 b − a c − a c − a  0 0 c − b c − b 0 0 c−b d−b 0 b−a c−a d−a     a a a a 1 0 0 0 0 b − a b − a b − a 1 1 0 0  = U,  −�  L= 0  1 1 1 0 . 0 c−b c−b 0 0 0 d−c 1 1 1 1 The pivots are the nonzero entries on the diagonal of U . So there are four pivots when these four conditions are satisfied: a �= 0, b �= a, c = � b, and d �= c. Section 2.6. Problem 18: If A = LDU and also A = L1 D1 U1 with all factors invertible, then L = L1 and D = D1 and U = U1 . “The three factors are unique.” 1 −1 . Are the two sides triangular or diagonal? Deduce Derive the equation L− 1 LD = D1 U1 U L = L1 and U = U1 (they all have diagonal 1’s). Then D = D1 . 1 Solution (4 points): Notice that LDU = L1 D1 U1 . Multiply on the left by L− 1 and on the right by U −1 , getting −1 −1 L−1 = L−1 . 1 LDU U 1 L1 D1 U1 U 1 −1 −1 , as desired. But U U −1 = I and L− 1 L1 = I. Thus L1 LD = D1 U1 U −1 The left side L1 LD is lower triangular, and the right side D1 U1 U −1 is upper triangular. But 1 −1 are diagonal too. But they have they’re equal. So they’re both diagonal. Hence L− 1 L and U1 U 1 −1 . diagonal 1’s. So they’re both equal to I. Thus L = L1 and U = U1 . Also L− 1 LD = D1 U1 U Thus D = D1 . Section 2.6. Problem 25: For the 6 by 6 second difference constant-diagonal matrix K, put the pivots and multipliers into K = LU . (L and U will have only two nonzero diagonals, because K has three.) Find a formula for the i, j entry of L−1 , by software like MATLAB using inv(L) or by looking for a nice pattern.   2 −1 −1 • •      • • •  = toeplitz([2 -1 0 0 0 0]). − 1, 2, −1 matrix K =    • • •    • • −1 −1 2 Solution (12 points): Here is the transcript of a session with the software Octave, which is the open-source GNU clone of MATLAB. The decomposition K = LU is found using the teaching code slu.m, available from http://web.mit.edu/18.06/www/Course-Info/Tcodes.html octave:1> K=toeplitz([2 -1 0 0 0 0]); octave:2> [L,U]=slu(K); octave:3> inv(L) ans = 1.00000 0.00000 0.00000 0.00000 0.50000 1.00000 0.00000 0.00000 0.33333 0.66667 1.00000 0.00000 0.25000 0.50000 0.75000 1.00000 0.20000 0.40000 0.60000 0.80000 0.16667 0.33333 0.50000 0.66667 0.00000 0.00000 0.00000 0.00000 1.00000 0.83333 0.00000 0.00000 0.00000 0.00000 0.00000 1.00000 So the nice pattern is (L−1 )ij = j/i for j � i and (L−1 )ij = 0 for j > i. Section 2.6. Problem 26: If you print K −1 , it doesn’t look good. But if you print 7K −1 (when K is 6 by 6), that matrix looks wonderful. Write down 7K −1 by hand, following this pattern: 1 Row 1 and column 1 are (6, 5, 4, 3, 2, 1). 2 On and above the main diagonal, row i is i times row 1. 3 On and below the main diagonal, column j is j times column 1. Multiply K times that 7K −1 to produce 7I . Here is that pattern for n = 3:      3 by 3 case 2 −1 0 3 2 1 4 2 −1 2 4 2 =  4  . The determinant (K)(4K −1 ) = −1 of this K is 4 0 −1 2 1 2 3 4 Solution (12 points): For n = 6, following the pattern yields this matrix:   6 5 4 3 2 1 5 10 8 6 4 2   4 8 12 9 6 3   3 6 9 12 8 4 .   2 4 6 8 10 5 1 2 3 4 5 6 Here is the transcript of an Octave session that multiplies K times that 7K −1 . octave:1> K=toeplitz([2 -1 0 0 0 0]); octave:2> M=[6 5 4 3 2 1;5 10 8 6 4 2;4 8 12 9 6 3;3 6 9 12 8 4;2 4 6 8 10 5;1 2 3 4 5 6]; octave:3> K*M ans = 7 0 0 0 0 0 0 7 0 0 0 0 0 0 7 0 0 0 0 0 0 7 0 0 0 0 0 0 7 0 0 0 0 0 0 7 Section 2.7. Problem 13: (a) Find a 3 by 3 permutation matrix with P 3 = I (but not P = I). (b) Find a 4 by 4 permutation Pb with Pb4 = � I. Solution (4 points): (a) Let P move the rows in a third, and the third to the first. So    0 0 1 0 P = 1 0 0 , P 2 = 0 0 1 0 1 cycle: the first to the second, the second to the  1 0 0 1 , 0 0 and P 3 = I. (b) Let Pb be the block diagonal matrix with 1 and P on the diagonal: Pb = P 3 = I, also Pb3 = I. So Pb4 = Pb = � I. (1 0 0P ) . Since Section 2.7. Problem 36: A group of matrices includes AB and A−1 if it includes A and B. “Products and inverses stay in the group.” Which of these sets are groups? Lower triangular matrices L with 1’s on the diagonal, symmetric matrices S, positive matrices M , diagonal invertible matrices D, permutation matrices P , matrices with QT = Q−1 . Invent two more matrix groups. Solution (4 points): Yes, the lower triangular matrices L with 1’s on the diagonal form a group. Clearly, the product of two is a third. Further, the Gauss-Jordan method shows that the inverse of one is another. No, the symmetric matrices do not form a group. For example, here are two symmetric matrices A and B whose product AB is not symmetric.       0 1 0 1 2 3 2 4 5 A = 1 0 0 , B = 2 4 5 , AB = 1 2 3 . 0 0 1 3 5 6 3 5 6 (1 1) ( 1 −1No, ) the positive matrices do not form a group. For example, 0 1 is positive, but its inverse 0 1 is not. Yes, clearly, the diagonal invertible matrices form a group. Yes, clearly, the permutation matrices matrices form a group. Yes, the matrices with QT = Q−1 form a group. Indeed, if A and B are two such matrices, then so are AB and A−1 , as (AB)T = B T AT = B −1 A−1 = (AB)−1 and (A−1 )T = (AT )−1 = A−1 . ( ) There are many more matrix groups. For example, given two, the block matrices A0 B0 form a third as A ranges over the first group and B ranges over the second. Another example is the set of all products cP where c is a nonzero scalar and P is a permutation matrix of given size. Section 2.7. Problem 40: Suppose QT equals Q−1 (transpose equal inverse, so QT Q = I). (a) Show that the columns q1 , . . . , qn are unit vectors: → qi →2 = 1. (b) Show that every two distinct columns of Q are perpendicular: qiT qj = 0 for i = � j. (c) Find a 2 by 2 example with first entry q11 = cos �. Solution (12 points): In any case, the ij entry of QT Q is qiT qj . So QT(Q = I leads to (a) qiT qi = 1 ) � − sin � works. for all i and to (b) qiT qj = 0 for i = � j. As for (c), the rotation matrix cos sin � cos � Section 3.1. Problem 18: True or false (check addition or give a counterexample): (a) The symmetric matrices in M (with AT = A) form a subspace. (b) The skew-symmetric matrices in M (with AT = −A) form a subspace. (c) The unsymmetric matrices in M (with AT = � A) form a subspace. Solution (4 points): (a) True: AT = A and B T = B lead to (A + B)T = AT + B T = A + B. T T T T T (b) True: A ( 1 1= ) −A( 0and ) B ( 1=1−B ) lead to (A + B) = A + B = −A − B = −(A + B). 0 (c) False: 0 0 + 1 1 = 1 1 . Section 3.1. Problem 23: (Recommended) If we add an extra column b to a matrix A, then the column space gets larger unless . Give an example where the column space gets larger and an example where it doesn’t. Why is Ax = b solvable exactly when the column space doesn’t get larger—it is the same for A and [ A b ]? Solution (4 points): The column space gets larger unless ( 1 0 ) it contains b; that is, b is a linear combination of the columns of( A). For example, let A = 0 0 ; then the column space gets larger if ( ) b = 01 and it doesn’t if b = 10 . The equation Ax = b is solvable exactly when b is a (nontrivial) linear combination of the columns of A (with the components of x as combining coefficients); so Ax = b is solvable exactly when b lies in the column space, so exactly when the column space doesn’t get larger. Section 3.1. Problem 30: Suppose S and T are two subspaces of a vector space V. (a) Definition: The sum S + T contains all sums s + t of a vector s in S and a vector t in T. Show that S + T satisfies the requirements (addition and scalar multiplication) for a vector space. (b) If S and T are lines in Rm , what is the difference between S + T and S ≤ T? That union contains all vectors from S and T or both. Explain this statement: The span of S ≤ T is S + T. (Section 3.5 returns to this word “span.”) Solution (12 points): (a) Let s, s� be vectors in S, let t, t� be vectors in T, and let c be a scalar. Then (s + t) + (s� + t� ) = (s + s� ) + (t + t� ) and c(s + t) = cs + ct. Thus S + T is closed under addition and scalar multiplication; in other words, it satisfies the two requirements for a vector space. (b) If S and T are distinct lines, then S + T is a plane, whereas S ≤ T is not even closed under addition. The span of S ≤ T is the set of all combinations of vectors in this union. In particular, it contains all sums s + t of a vector s in S and a vector t in T, and these sums form S + T. On the other hand, S + T contains both S and T; so it contains S ≤ T. Further, S + T is a vector space. So it contains all combinations of vectors in itself; in particular, it contains the span of S ≤ T. Thus the span of S ≤ T is S + T. Section 3.1. Problem 32: Show that the matrices A and [ A AB ] (with extra columns) have the same column space. But find a square matrix with C(A2 ) smaller than C(A). Important point: An n by n matrix has C(A) = Rn exactly when A is an matrix. Solution (12 points): Each column of AB is a combination of the columns of A (the combining coefficients are the entries in the corresponding column of B). So any combination of the columns of [ A AB ] is a combination of the columns of A alone. Thus A and [ A AB ] have the same column space. ( ) ( ) Let A = 00 10 . Then A2 = 0, so C(A2 ) = Z. But C(A) is the line through 01 . An n by n matrix has C(A) = Rn exactly when A is an invertible matrix, because Ax = b is solvable for any given b exactly when A is invertible.