Linear Algebra Example Solutions Exam 3

Example Solutions, Exam 3, Math 244 1. Let A and its RREF be given as:  −1 −5 3 9  −48 −40 24 92 A=  94 70 −42 −166 −48 −40 24 92      2 0  0 10 rref(A) =   0 0 0 0  0 −1 −3 −17   0 0  0 0 We also note two facts: λ = 4 is an eigenvalue of A, and u = [1, 0, 2, 0]T is an eigenvector of A. (a) Find a basis for the eigenspace E4 : SOLN: We find that A − 4I row reduces to the following, which means it is only 1-dimensional:     2 1 0 0 −2  1   0 1 0 −1       0 0 1 −2  ⇒ v =  2  1 0 0 0 0 (b) What is the eigenvalue for the eigenvector u? SOLN: We see that Au is the sum of the first and twice the third column of A:   5  0   Au =   10  ⇒ λ = 5 0 (c) You might have noticed that the second and fourth rows are the same. Does that imply we have a certain eigenvalue? Find a basis for its eigenspace. To save you some time, we have included the RREF of A. SOLN: If rows 2 and 4 are the same, the matrix A is not invertible, and λ = 0 is an eigenvalue. Using the given RREF,    5  0 v1 = 1/2v4      17  3  v2 = 3/10v3 + 17/10v4     ⇒ E0 = span  10   0  v3 = v3      10 0 v4 = v4 NOTE: We can check our answer since these vectors, which form a basis for the null space of A, should be orthogonal to the row space of A, whose basis is formed from the reduced form. (d) What is the characteristic polynomial of A? SOLN: We know that the eigenvalues are 4, 5, 0, 0, so the polynomial in factored form is: λ2 (λ − 4)(λ − 5) (e) Show that A is diagonalizable by finding an appropriate P and D. SOLN: We have already found all the components,    2 5 0 5 4 0 0  1   0 5 0 0 3 17  P = D=  2 10 10 0   0 0 0 1 0 1 1 0 0 0 2. Short Answer: 1  0 0   0  0 (a) Show that if A2 is the zero matrix, the only eigenvalue of A is zero. SOLN: If Av = λv, then A2 v = λAv = λ2 v. Therefore, if A2 is the zero matrix, then λ2 = 0 (since v cannot be the zero vector), or λ must be zero. (b) 1−3i 2+i = (1−3i)(2−i) (2+i)(2−i) = −1−7i 5 = − 15 − 7 5 i (c) Write in polar form: −1 − 3i. The number is reiθ , where r= √ 1+9= √ θ = tan−1 10   1 +π 3 (d) Normalize the vector [1, −2, 1, 1]T . √ √ SOLN: Multiply of the length, the length being 1 + 4 + 1 + 1 = 7, so the new √ by the √ reciprocal √ √ vector is: [1/ 7, −2/ 7, 1/ 7, 1/ 7]T . (e) Suppose A is 3 × 3, and u is an eigenvector of A corresponding to an eigenvalue of 7. Is u an eigenvector of 2I − A? If so, find the corresponding eigenvalue. If not, explain why not. SOLN: Let’s see: (2I − A)u = 2u − Au = 2u − 7u = −5u So yes, u is an eigenvector, with the new eigenvalue −5. (f) True or False? A matrix with orthonormal columns is an orthogonal matrix. SOLN: False- By definition, an orthogonal matrix must be a square matrix with orthonormal columns. 3. Show the following: If U, V are orthogonal matrices, then so is U V . SOLN: To show that a matrix B is orthogonal, show that B T B = I. In this case, let B = U V , so: B T B = (U V )T (U V ) = V T U T U V = V T IV = V T V = I The third equality is due to U being orthogonal, as is the last equality.   0.7 0.2 4. Let A = . Diagonalize the matrix A. 0.3 0.8 SOLUTION: To diagonalize the matrix, find the eigenvalues and eigenvectors. For λ = 1, solve (A − λI)x = 0. Do try to make your life a bit easier by the following simplifications:       −0.3 0.2 −3 2 2 → ⇒v= 0.3 −0.2 0 0 3 Similarly, for λ = 1/2, we have:  0.2 0.2 0.3 0.3   → 1 0 1 0   ⇒v= −1 1  Therefore, A = P DP −1  where P = 2 3 −1 1   D= 1 0 0 0.5  P −1 1 = 5  1 −3 1 2  (For a 2 × 2, go ahead and give P −1 ). 5. If the rows of A each sum to r, then from the following, we see that r is one eigenvalue with an eigenvector of all ones:     1 r  1   r      A .  =  .   ..   ..  1 2 r 6. Let U be m × n with orthonormal columns. Show that the length of U x is the same as the length of x. Use the first part of your answer to show that the angle between x and y is the same as the angle between U x and U y. SOLUTION: For the first question, we show that kU xk2 = kxk2 (which is equivalent, but does away with the square root). Start with the dot product definition of the norm: kU xk2 = (U x) · (U x) = (U x)T U x = xT U T U x = xT Ix = xT x = kxk2 The angle between x and y is given by solving: cos(θ) = x·y kxk kyk In the denominator, we know from what we just computed that kU xk = kxk. Therefore, the statement will be true if (U x) · (U y) = x · y: (U x) · (U y) = (U x)T (U y) = xT U T U y = x · y Therefore, x·y (U x) · (U y) = kU xk kU yk kxk kyk 7. Show that the eigenvalues of A and AT are the same. SOLUTION: Begin with λ being an eigenvalue of A. We show that |AT − λI| = 0. Since λ is an eigenvalue of A, and the determinant of the transpose is the determinant of the matrix, we have: 0 = |A − λI| = |(A − λI)T | = |AT − λI T | = |AT − λI| (the last equality is because I is symmetric- I T = I). Therefore, λ is an eigenvalue of AT . 8. Show that if v1 , v2 , · · · , vn are eigenvectors corresponding to distinct eigenvalues, then the vectors are linearly independent. Hint: What if the eigenvectors are linearly dependent? Then there is a p ≤ n so that vp = c1 v1 + c2 v2 + · · · + cp−1 vp−1 and v1 , · · · , vp−1 are linearly independent. If we multiply both sides by A, we get: Avp = c1 Av1 + c2 Av2 + · · · + cp−1 Avp−1 = c1 λ1 v1 + c2 λ2 v2 + · · · + cp−1 λp−1 vp−1 If we multiply both sides by λp , we get: λp vp = c1 λp v1 + c2 λp v2 + · · · + cp−1 λp vp−1 Subtract these and we get: 0 = c1 (λ1 − λp )v1 + · · · + cp−1 (λp−1 − λp )vp−1 These are linearly independent, so that means ci (λi − λp ) must all be zero- Which implies that ci must all be zero, since the eigenvalues are distinct. But that means that vp = ~0, which it cannot be (we can’t choose eigenvectors to be zero). Therefore, the statement we started with must be false: The eigenvectors must be linearly independent. NOTE: The main thing I want you to see here is how we can expand a vector in terms of eigenvectors, then multiply by A and analyze the result. The proof we gave is called a “proof by contradiction”- I won’t ask you to do the whole thing on the exam without some hints along the way, as we did here. 3  9. Find the eigenvalues and bases for the eigenspaces if A = 5 1 −5 1  . SOLUTION: In this case, the eigenvalues are complex. We give one here- The others are the conjugates.   2−i λ=3−i v= 1 NOTE: If you get a different v, see if you can determine if yours is a constant multiple (could be a complex multiple) of mine.   5 −5 10. Compute an appropriate factorization for the matrix A = . 1 1 SOLUTION: Use the real and imaginary parts of the vector v to construct the matrix P :     2 1 3 −1 0 1 A= 1 0 1 3 −1 2 11. Let matrix A be m × n. Show that the row space is orthogonal to the null space. SOLUTION: Since the rows of A span the row space, it will suffice to show that each row vector is orthogonal to any vector in the null space. Let x be any arbitrary vector in the null space of A. Then Ax = 0 Now write A in terms of its rows:      0 0 .. .   r1 r2 .. .      Ax =    0       x =    rm r1 · x r2 · x .. .      rm · x Therefore, the dot product of any row of A with x must be zero, and so the rows of A are orthogonal to the null space of A. 12. If u = [3, 2, −5, 0] and v = [1, 1, −1, 2], then compute: (a) The distance between u and v. p SOLUTION: The distance between u and v is computed by ku−vk = 22 + 12 + (−4)2 + (−2)2 = 5 (b) An approximate angle between u and v (use your calculator). SOLUTION: u·v 10 cos(θ) = =√ √ kukkvk 38 7   10√ Therefore, θ = cos−1 √38 7 (c) The orthogonal projection of u onto v SOLUTION:   1  uT v 10   1  Projv (u) = v=  2 −1  kvk 7 2 (d) For the projection to be orthogonal, Projv (u) ⊥ u − Projv (u). NOTE: You could also say that v is orthogonal to u − Projv (u), because:  u·v  v =v·u−v·u=0 v· u− v·v 4 13. Prove the Pythagorean Theorem for two vectors x and y: kx + yk2 = kxk2 + kyk2 NOTE: The vectors x, y must be orthogonal for this to be true, which we will see. First, write the norm in terms of the dot product, then expand and simplify: kx + yk2 = (x + y) · (x + y) = (x + y)T (x + y) = (xT + yT )(x + y) = xT x + 2xT y + yT y We get the desired result if (and only if) the vectors x, y are orthogonal. 14. If A is similar to B, show that they have the same eigenvalues. SOLUTION: By definition, if A is similar to B, there is a matrix P such that A = P BP −1 We can take two approaches. One is using the determinant (as done in class), but here is an alternative solution: If λ is an eigenvalue of A, then Ax = λx ⇒ P BP −1 x = λx ⇒ B(P −1 x) = λ(P −1 x) ⇒ Bu = λu Therefore, λ is also an eigenvalue of B, but with a different eigenvector. 15. Prove that if the set {v1 , · · · vk } form a basis for subspace W , and x is orthogonal to each vi , for i = 1 to k, then x is orthogonal to W . (Hint: Start with a generic vector w ∈ W , and show that x · w = 0.) SOLUTION: Let w ∈ W . Then we can write w in terms of the basis vectors, w = c1 v1 + c2 v2 + · · · + ck vk Now take the dot product of both sides with x and simplify the right hand side: w · x = (c1 v1 + c2 v2 + · · · + ck vk ) · x = c1 v1 · x + c2 v2 · x + · · · + ck vk · x = 0 + 0 + · · · + 0 Therefore, x is orthogonal to every vector in W . 16. Prove that the eigenvalues of a triangular matrix are the entries on its main diagonal. SOLUTION: By the properties of the determinant, we know that the determinant of a triangular matrix is the product of the diagonal entries. By taking the determinant of A − λI, we only change the diagonal entries- That is, if A is triangular, then so is A − λI. Therefore, the characteristic polynomial is given by: (a11 − λ)(a22 − λ) · · · (ann − λ) = 0 From which we get that λ1 = a11 , λ2 = a22 , and so on until λn = ann . 17. (More) True or False? If the statement is false and you can provide a counterexample to demonstrate this, then do so. If the statement is false and be can slightly modified so as to make it true then indicate how this may be done. (a) If v1 and v2 are linearly independent eigenvectors, then they correspond to distinct eigenvalues. SOLUTION: False. For example,   1 0 0 1 has two eigenvalues, λ = 1, 1, but two linearly independent eigenvectors e1 and e2 . If we had said “distinct eigenvalues” correspond to “linearly independent eigenvectors”, the answer would have been “true”. 5 (b) If A is invertible, then A is diagonalizable. SOLUTION: False. Saying that A is invertible simply means that λ = 0 is not an eigenvalue of A. There is no direct connection between a matrix being invertible and being diagonalizable. For example, we can imagine that a 2 × 2 matrix has two eigenvalues, 1 and 0 (not invertible), but since we have distinct eigenvalues, the matrix is diagonalizable. On the other hand, we might have had complex eigenvalues (invertible), but the matrix is not diagonalizable (in the sense of D being a diagonal matrix in P DP −1 ). (c) The orthogonal projection of y onto a vector v is the same as the orthogonal projection of y onto cv whenever c 6= 0. SOLUTION: True: yT v Projv (y) = T v v v And yT cv c2 y T v Projcv (y) = T cv = 2 T v = Projv (y) cv cv c v v (d) If A is an orthogonal matrix, then AT is an orthogonal matrix. SOLUTION: True. Since A is orthogonal, then AT = A−1 , so I = AA−1 = AAT = (AT )T AT And therefore, AT is orthogonal. (e) If A, B have the same eigenvalues, then they are similar. SOLUTION: If we had said “Similar implies the same eigenvalues”, that would have been true. However, the reverse is not- Even if A, B have the same eigenvalues, the matrices may not be diagonalizable (either or both may be defective)- For example,     1 0 1 1 A= B= 0 1 0 1 In this case, A, B have the same eigenvalues, A is diagonalizable, but B is not. 18. Show that if U is a matrix with orthonormal columns, then the projection of x into the column space of U is U U T x. Proof: Write U in terms of its columns:   T  u1   uT2    U U T x = [u1 u2 · · · uk ]   · · ·  x = [u1 u2 · · · uk ]  uTk  uT1 x


uT2 x   = u1 uT1 x + u2 uT2 x + · · · + uk uTk x  ··· uTk x And, by taking U T U :   u1 · u1 u1 · u2 uT1  u2 · u1 u2 · u2  uT2     ..  · · ·  [u1 u2 · · · uk ] =   . T uk uk · u1 uk · u2  ··· ··· u1 · uk u2 · uk .. . ··· uk · uk     = Ik  19. When we originally partitioned IRn into one part as the row space and the other part as the null space for a matrix, we said that the only thing in both spaces was the zero vector. How do we know that there is not a vector in IRn that is in neither the row space nor the null space? (Think about 6.3- the orthogonal decomposition theorem, for example). 6 SOLUTION: Suppose there is a vector v that is in W and in W ⊥ . Then v·v =0 From the properties of the magnitude, kvk = 0 if and only if v = ~0. Therefore, the only vector in both a subspace W and in W ⊥ is the zero vector. 20. Use Gram-Schmidt to give us an orthogonal set of vectors to replace the columns of the matrix A below.   1 0 0  1 1 0     1 1 1  1 1 1 SOLUTION: Since we allow the magnitude to be anything, we should re-scale the vectors to have whole numbers.           0 −3 1 1 −3  1  3 1  1 1   1   1          v2 =  v1 =   1  − 4  1  = 4  1  ⇒ v2 =  1   1 , 1 1 1 1 1 Finally,   0  0  2   v3 =   1 − 4 1         0 1 −3 −2/3     1   − 2  1  =  1/3  ⇒ v3 =  −2      1  1 1 12 1/3 1 1 1 21. Let A = QR. (a) If A is 4 × 3, what dimensions could Q and R be, if we use Gram-Schmidt to compute Q? SOLUTION: Q is 4 × 3 with R being 3 × 3. (b) Here are matrices A, Q and R. See if you can tell which is which.       −1 −3 1 −1 6 6 1 −3 1/2  3 −1  3 −8 1  3       0 −1 −5/2   1 −1 −3   1 −2 6  0 0 −1 1 1 1 1 −4 −3 SOLUTION: They appear in order: R, then A then Q. (c) If A = QR, as given in the previous part, then write a3 as a linear combination of q1 , .q2 , q3 . SOLUTION: 1 5 a3 = q1 − q2 − q3 2 2 (d) If Ax = b, and A = QR, then write the solution x in terms of Q, R. SOLUTION: 1 QRx = b ⇒ QT QRx = QT b ⇒ 12IRx = QT b ⇒ x = 12 R−1 QT b. (We see that R is invertible and QT Q = 12I).   2 0 −1 22. Suppose A = P DP with a suitable 2 × 2 matrix P and D = . 0 7 (a) If B = 3I − 2A + A2 , show that B is diagonalizable by finding an appropriate factorization of B. SOLUTION: Substitute P DP −1 for A, P P −1 for I, and P D2 P −1 for A2 : B = 3P P −1 − 2P DP −1 + P D2 P −1 = P (3I − 2D + D2 )P −1 where D2 − 2D + 3I =  22 − 2(2) + 3 0 0 72 − 2(7) + 3 7   = 3 0 0 38  (b) From your previous answer, if λ is an eigenvalue of A, then what would an eigenvalue of A2 +bA+cI be? SOLUTION: λ2 + bλ + c. Additional Questions, 4.9- Markov Chains 1. (A calculator may be used on this problem. On the exam, I will choose numerical values that will be easy to work with, since you won’t have a calculator). On any given day, a student is either healthy or ill. Of the students that are healthy today, 95% will be healthy tomorrow. Of the students that are ill today, 55% will be ill tomorrow. (a) What is the stochastic matrix for this system if we model it as a Markov chain? SOLUTION: Decide on whether healthy (H) or ill (I) will be first- Remember that “to” goes along the side, “from” along the top, so that the (1, 2) element will represent ill students today that are healthy tomorrow.   0.95 0.45 P = 0.05 0.55 (b) Suppose 20% of the students are ill on Monday. What is the fraction or percentage of the students that will likely be ill on Tuesday?  0.8 SOLUTION: Make a vector x = and compute P x: 0.2      0.95 0.45 0.8 0.85 = 0.05 0.55 0.2 0.15 So approximately 15% of the students will be ill on Tuesday. (c) What happens to the percentages in the long run? SOLUTION: We look for the steady state, so that P q = q. This is the same as the eigenvector for λ = 1:    −0.05 0.45 q1 ~ (P − I)q = 0 ⇒ = ~0 0.05 −0.45 q2 so that 9 1 q1 = q2 20 20  ⇒ q= 0.90 0.10  In the long run, 90% of the students are healthy and 10% are ill. 2. Show that every 2 × 2 stochastic matrix has at least one steady-state vector.   1−α β , where α, β are constants between 0 Any such matrix can be written in the form P = α 1−β and 1. Also, how many steady state vectors are there if α = β = 0? SOLUTION: Using the form of P given, we look for the eigenvector(s) associated with λ = 1:   −α β (P − I) = α −β so the eigenvector will satisfy −αq1 + βq2 = 0, of q1 = β/αq2 , or   β q= α This formula also works if one of α or β = 0 (but not both). If they are both 0, then P becomes the identity matrix, with a double eigenvalues λ = 1 and a two dimensional eigenspace (the eigenvectors can be any basis for IR2 )- In this case, every state is a steady state. 8 3. Let S be the 1 × n row of all ones. If P is an n × n square matrix with all non-negative entries, show that P is stochastic if SP = S. SOLUTON: For any n × n matrix A, the product SA returns a row vector, where each element of the row is the sum of the corresponding column (try it with a 2 × 2 to see). Therefore, if P is stochastic, then the columns each sum to 1, and SP will be a row of ones, which is S again. 9