18.06SC Final Exam Solutions

18.06SC Final Exam Solutions 1 (4+7=11 pts.) Suppose A is 3 by 4, and Ax = 0 has exactly 2 special solutions:     1 −2         1  −1      x1 =   and x2 =   1  0     0 1 (a) Remembering that A is 3 by 4, find its row reduced echelon form R. (b) Find the dimensions of all four fundamental subspaces C(A), N(A), C(AT ), N(AT ). You have enough information to find bases for one or more of these subspaces—find those bases. Solution. (a) Each special solution tells us the solution to Rx = 0 when we set one free variable = 1 and the others = 0. Here, the third andfourth variables  must be the two free variables, 1 0 ∗ ∗     and the other two are the pivots: R =  0 1 ∗ ∗    0 0 0 0  1 0 −1 2      Now multiply out Rx1 = 0 and Rx2 = 0 to find the ∗’s: R =  0 1 −1 1    0 0 0 0 (The ∗’s are just the negatives of the special solutions’ pivot entries.) (b) We know the nullspace N(A) has n − r = 4 − 2 = 2 dimensions: the special solutions x1 , x2 form a basis. The row space C(AT ) has r = 2 dimensions. It’s orthogonal to N(A), so just pick two linearly-independent vectors orthogonal to x1 and x2 to form a basis: for example,     1 0          0  1  , x4 =   x3 =     .  −1   −1      2 1 (Or: C(AT ) = C(RT ) is just the row space of R, so the first two rows are a basis. Same thing!) The column space C(A) has r = 2 dimensions (same as C(AT )). We can’t write down a basis because we don’t know what A is, but we can say that the first two columns of A are a basis. The left nullspace N(AT ) has m − r = 1 dimension; it’s orthogonal to C(A), so any vector orthogonal to the first two columns of A (whatever they are) will be a basis. 2 (6+3+2=11 pts.) (a) Find the inverse of a 3 by 3 upper triangular matrix U, with nonzero entries a, b, c, d, e, f . You could use cofactors and the formula for the inverse. Or possibly Gauss-Jordan elimination.   a b c     Find the inverse of U =  0 d e .   0 0 f (b) Suppose the columns of U are eigenvectors of a matrix A. Show that A is also upper triangular. (c) Explain why this U cannot be the same matrix as the first factor in the Singular Value Decomposition A = UΣV T . Solution. (a) By elimination: (We keep track of the elimination matrix E on one side, and the product  a b   0 d  0 0 EU on the other. When   1 c 1 0 0     e 0 1 0 � 0   0 f 0 0 1  1   � 0  0 EU = I, then E = U −1 .) b/a c/a 1/a 0 0 0   0 1/d 0  0 0 1/f 1 e/d 0 0  1 1/a −b/ad (be − cd)/adf 1 0 0 1/d 0 1 0 0   h i  −e/df  = I U −1  1/f By cofactors: (Take the minor, then “checkerboard” the signs to get the cofactor matrix, then transpose and divide by det(U) = adf .)         df 0 0 df −bf be − cd a b c df 0 0                 0 d e �  af 0  �  0 af −ae  � bf af 0  �  −bf         be − cd −ae ad 0 0 ad 0 0 f be − cd ae ad   1/a −b/ad (be − cd)/adf      0 1/d −e/df  = U −1   0 0 1/f (b) We have a complete set of eigenvectors for A, so we can diagonalize: A = UΛU −1 . We know U is upper-triangular, and so is the diagonal matrix Λ, and we’ve just shown that U −1 is upper-triangular too. So their product A is also upper-triangular. (c) The columns aren’t orthogonal! (For example, the product uT 1 u2 of the first two columns is ab + 0d + 0 · 0 = ab, which is nonzero because we’re assuming all the entries are nonzero.) 3 (3+3+5=11 pts.) (a) A and B are any matrices with the same number of rows. What can you say (and explain why it is true) about the comparison of rank of A h rank of the block matrix A B i (b) Suppose B = A2 . How do those ranks compare ? Explain your reason­ ing. (c) If A is m by n of rank r, what are the dimensions of these nullspaces ? h i Nullspace of A Nullspace of A A Solution. (a) All you can say is that rank A ≤ rank [A B]. (A can have any number r of pivot columns, and these will all be pivot columns for [A B]; but there could be more pivot columns among the columns of B.) (b) Now rank A = rank [A A2 ]. (Every column of A2 is a linear combination of columns of A. For instance, if we call A’s first column a1 , then Aa1 is the first column of A2 . So there are no new pivot columns in the A2 part of [A A2 ].) (c) The nullspace N(A) has dimension n − r, as always. Since [A A] only has r pivot columns — the n columns we added are all duplicates — [A A] is an m-by-2n matrix of rank r, and its nullspace N ([A A]) has dimension 2n − r. 4 (3+4+5=12 pts.) Suppose A is a 5 by 3 matrix and Ax is never zero (except when x is the zero vector). (a) What can you say about the columns of A ? (b) Show that AT Ax is also never zero (except when x = 0) by explaining this key step: If AT Ax = 0 then obviously xT AT Ax = 0 and then (WHY ?) Ax = 0. (c) We now know that AT A is invertible. Explain why B = (AT A)−1 AT is a one-sided inverse of A (which side of A ?). B is NOT a 2-sided inverse of A (explain why not). Solution. (a) N(A) = 0 so A has full column rank r = n = 3: the columns are linearly independent. (b) xT AT Ax = (Ax)T Ax is the squared length of Ax. The only way it can be zero is if Ax has zero length (meaning Ax = 0). (c) B is a left inverse of A, since BA = (AT A)−1 AT A = I is the (3-by-3) identity matrix. B is not a right inverse of A, because AB is a 5-by-5 matrix but can only have rank 3. (In fact, BA = A(AT A)−1 AT is the projection onto the (3-dimensional) column space of A.) 5 (5+5=10 pts.) If A is 3 by 3 symmetric positive definite, then Aqi = λi qi with positive eigenvalues and orthonormal eigenvectors qi . Suppose x = c1 q1 + c2 q2 + c3 q3 . (a) Compute xT x and also xT Ax in terms of the c’s and λ’s. (b) Looking at the ratio of xT Ax in part (a) divided by xT x in part (a), what c’s would make that ratio as large as possible ? You can assume λ1 < λ2 < . . . < λn . Conclusion: the ratio xT Ax/xT x is a maximum when x is . Solution. (a) xT x = (c1 q1T + c2 q2T + c3 q3T )(c1 q1 + c2 q2 + c3 q3 ) = c21 q1T q1 + c1 c2 q1T q2 + · · · + c3 c2 q3T q2 + c23 q3T q3 = c21 + c22 + c23 . xT Ax = (c1 q1T + c2 q2T + c3 q3T )(c1 Aq1 + c2 Aq2 + c3 Aq3 ) = (c1 q1T + c2 q2T + c3 q3T )(c1 λ1 q1 + c2 λ2 q2 + c3 λ3 q3 ) = c21 λ1 q1T q1 + c1 c2 λ2 q1T q2 + · · · + c3 c2 λ2 q3T q2 + c23 λ3 q3T q3 = c21 λ1 + c22 λ2 + c23 λ3 . (b) We maximize (c21 λ1 + c22 λ2 + c23 λ3 )/(c21 + c22 + c23 ) when c1 = c2 = 0, so x = c3 q3 is a multiple of the eigenvector q3 with the largest eigenvalue λ3 . (Also notice that the maximum value of this “Rayleigh quotient” xT Ax/xT x is the largest eigenvalue itself. This is another way of finding eigenvectors: maximize xT Ax/xT x numerically.) 6 (4+4+4=12 pts.) (a) Find a linear combination w of the linearly independent vec­ tors v and u that is perpendicular to u. h i (b) For the 2-column matrix A = u v , find Q (orthonormal columns) and R (2 by 2 upper triangular) so that A = QR. (c) In terms of Q only, using A = QR, find the projection matrix P onto the plane spanned by u and v. Solution. (a) You could just write down w = 0u + 0v = 0 — that’s perpendicular to everything! But a more useful choice is to subtract off just enough u so that w = v −cu is perpendicular to u. That means 0 = w T u = v T u − cuT u, so c = (v T u)/(uT u) and w =v−( vTu )u. uT u (b) We already know u and w are orthogonal; just normalize them! Take q1 =  u/|u|  and |u| q2 = w/|w|. Then solve for the columns r1 , r2 of R: Qr1 = u so r1 =  , and 0   c|u| . (Where c = (v T u)/(uT u) as before.) Qr2 = v so r2 =  |w| Then Q = [q1 q2 ] and R = [r1 r2 ]. (c) P = A(AT A)−1 AT = (QR)(RT QT QR)−1 (RT QT ) = (QR)(RT QT ) = QQT . 7 (4+3+4=11 pts.) (a) Find the  0   1 C=  0  0 eigenvalues of   0 0 0 0 1     0 0 0 0 0  and C 2 =    1 0 1 0 0   0 1 0 1 0 1 0    0 1 .  0 0  0 0 (b) Those are both permutation matrices. What are their inverses C −1 and (C 2 )−1 ? (c) Find the determinants of C and C + I and C + 2I. Solution. (a) Take the determinant of C − λI (I expanded by cofactors): λ4 − 1 = 0. The roots of this “characteristic equation” are the eigenvalues: +1, −1, i, −i. The eigenvalues of C 2 are just λ2 = ±1 (two of each). (Here’s a “guessing” approach. Since C 4 = I, all the eigenvalues λ4 of C 4 are 1: so λ = 1, −1, i, −i are the only possibilities. Just check to see which ones work. Then the eigenvalues of C 2 must be ±1.) (b) For any permutation matrix, C −1 = C T : so  0   0 C −1 =   0  1 1 0 0    0 1 0   0 0 1  0 0 0 and (C 2 )−1 = C 2 is itself. (c) The determinant of C is the product of its eigenvalues: 1(−1)i(−i) = −1. Add 1 to every eigenvalue to get the eigenvalues of C + I (if C = SΛS −1 , then C + I = S(Λ + I)S −1 ): 2(0)(1 + i)(1 − i) = 0. (Or let λ = −1 in the characteristic equation det(C − λI).) Add 2 to get the eigenvalues of C + 2I (or let λ = −2): 3(1)(2 + i)(2 − i) = 15. 8 (4+3+4=11 pts.) Suppose a rectangular matrix A has independent columns. (a) How do you find the best least squares solution x b to Ax = b ? By taking those steps, give me a formula (letters not numbers) for x b and also for p = Ax b. (b) The projection p is in which fundamental subspace associated with A ? The error vector e = b − p is in which fundamental subspace ? (c) Find by any method the projection matrix P onto the column space of A:  1 0      3 0  . A=   0 −1    0 −3 Solution. (a) Ax = b Least-squares “solution”: AT Ax̂ = AT b AT A is invertible: x̂ = (AT A)−1 AT b and p = Ax̂ is: Ax̂ = A(AT A)−1 AT b (b) p = Ax̂ is a linear combination of columns of A, so it’s in the column space C(A). The error e = b − p is orthogonal to this space, so it’s in the left nullspace N(AT ).     10 0 1/10 0 , its inverse is  = (c) I used P = A(AT A)−1 AT . Since AT A =  0 10 0 1/10 and   1 3 0 0     3 9 0 0 1    P =  10  0 0 1 3   0 0 3 9 1 I, 10 9 (3+4+4=11 pts.) This question is about the matrices with 3’s on the main diagonal, 2’s on the diagonal above, 1’s on the diagonal below. h i A1 = 3  A2 =  3 2 1 3    3 2 0      A3 =  1 3 2    0 1 3  3   1 An =   0  0 2 0 0    3 2 0   1 3 ·  0 · · (a) What are the determinants of A2 and A3 ? (b) The determinant of An is Dn . Use cofactors of row 1 and column 1 to find the numbers a and b in the recursive formula for Dn : (∗) Dn = a Dn−1 + b Dn−2 . (c) This equation (∗) is the same as      Dn a b Dn−1  =  . Dn−1 1 0 Dn−2 >From the eigenvalues of that matrix, how fast do the determinants Dn grow ? (If you didn’t find a and b, say how you would answer part (c) for any a and b ) For 1 point, find D5 . Solution. (a) det(A2 ) = 3 · 3 − 1 · 2 = 7 and det(A3 ) = 3 det(A2 ) − 2 · 1 · 3 = 15. (b) Dn = 3Dn−1 + (−2)Dn−2 . (Show your work.) (c) The trace of that matrix A is a = 3, and the determinant is −b = 2. So the character­ istic equation of A is λ2 − aλ − b = 0, which has roots (the eigenvalues of A) p a ± a2 − 4(−b) 3±1 = = 1 or 2. λ± = 2 2 Dn grows at the same rate as the largest eigenvalue of An , λn+ = 2n . The final point: D5 = 3D4 + 2D3 = 3(3D3 + 2D2 ) + 2D3 = 11D3 + 6D2 = 207.