18.06 Linear Algebra, Problem Set 10 Solutions

18.06 Problem Set 10 Solution Total: 100 points Section 6.6. Problem 12. These Jordan matrices have eigenvalues 0, 0, 0, 0. They have two eigenvectors (one from each block). But the block sizes don’t match and they are not similar: ⎛ ⎞ ⎞ ⎛ 0 1 0 0 0 1 0 0 ⎜ 0 0 1 0 ⎟ ⎜ 0 0 0 0 ⎟ ⎜ ⎟ ⎟ and K = J =⎜ ⎝ 0 0 0 0 ⎠ ⎝ 0 0 0 1 ⎠ 0 0 0 0 0 0 0 0 For any matrix M , compare JM with M K. If they are equal show that M is not invertible. Then M −1 JM = K is impossible; J is not similar to K. Solution (4 points) Let M = (mij ). Then ⎞ ⎛ m21 m22 m23 m24 ⎜ 0 0 0 0 ⎟ ⎟ and JM = ⎜ ⎝ m41 m42 m43 m44 ⎠ 0 0 0 0 ⎛ 0 ⎜ 0 MK = ⎜ ⎝ 0 0 m11 m21 m31 m41 m12 m22 m32 m42 ⎞ 0 0 ⎟ ⎟. 0 ⎠ 0 If JM = M K then m21 = m22 = m24 = m41 = m42 = m44 = 0, which in particular means that the second row is either a multiple of the fourth row, or the fourth row is all 0’s. In either of these cases M is not invertible. Suppose that J were similar to K. Then there would be some invertible matrix M such that K = M −1 JM , which would mean that M K = JM . But we just showed that in this case M is never invertible! Contradiction. Thus J is not similar to K. Section 6.6. Problem 14. Prove that AT is always similar to A (we know that the λ’s are the same): 1. For one Jordan block Ji : find Mi so that Mi−1 Ji Mi = JiT (see example 3). 2. For any J with blocks Ji : build M0 from blocks so that M0−1 JM0 = J T . 1 3. For any A = M JM −1 : Show that AT is similar to J T and so to J and so to A. Solution (4 points) 1. Suppose that we have one Jordan block Ji . Then ⎞⎛ ⎞⎛ ⎛ ⎞ ⎛ λ 1 0 ··· 0 λ 1 1 ⎜ ⎟⎜ ⎜ 1 λ ⎜ ⎟ ⎟ λ 1 · · · 0 1 1 ⎟⎜ ⎜ ⎟⎜ ⎟ ⎜ ⎜ ⎟⎜ ⎜ ⎟ ⎟=⎜ λ · · · 0 0 1 λ . . ⎟⎜ ⎜ ⎟⎜ ⎟ ⎜ ⎜ ⎟ ⎜ . ... ⎝ ⎠⎝ ⎠ ⎝ .. . . ⎠⎝ 1 1 λ 0 0 0 ··· λ ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ so J is similar to J T . 2. Suppose that each Ji satisfies JiT = Mi−1 Ji Mi . Let M0 be the matrix consisting of the Mi ’s along the diagonal. Then ⎛ −1 ⎞⎛ M1 J1 −1 ⎜ ⎟ ⎜ M2 J2 ⎜ ⎟⎜ M0−1 JM0 = ⎜ ⎟ ⎜ . ... .. ⎝ ⎠⎝ Mn−1 Jn ⎛ −1 ⎞ M 1 J1 M 1 ⎜ ⎟ M2−1 J2 M2 ⎜ ⎟ = ⎜ ⎟ . . ⎝ ⎠ . −1 M n Jn M n ⎛ ⎞ J1T ⎜ ⎟ J2T ⎜ ⎟ = ⎜ ⎟ = JT . . ⎝ ⎠ . T Jn block-diagonal ⎞⎛ ⎟⎜ ⎟⎜ ⎟⎜ ⎠⎝ ⎞ M1 M2 3. AT = (M JM −1 )T = (M −1 )T J T M T = (M T )−1 J T (M T ). So AT is similar to J T , which is similar to J, which is similar to A. Thus any matrix is similar to its transpose. Section 6.6. Problem 20. Why are these statements all true? 2 ⎟ ⎟ ⎟ ⎠ ... Mn (a) If A is similar to B then A2 is similar to B 2 . (b) A2 and B 2 can be similar when A and B are not similar. � � � � 3 0 3 1 (c) is similar to . 0 4 0 4 � � � � 3 0 3 1 (d) is not similar to . 0 3 0 3 (e) If we exchange rows 1 and 2 of A, and then exchange columns 1 and 2 the eigenvalues stay the same. In this case M =? Solution (4 points) (a) If A is similar to B then we can write A = M −1 BM for some M . Then A2 = M −1 B 2 M , so A2 is similar to B 2 . (b) Let � A= 0 0 0 0 � � B= 0 1 0 0 � . Then A2 = B 2 (so they are obviously similar) but A is not similar to B because nothing but the zero matrix is similar to the zero matrix. (c) � 3 0 0 4 � � = 1 −1 0 1 �� 3 1 0 4 �� 1 1 0 1 � . (d) These are not similar because the first matrix has a plane of eigenvectors for the eigenvalue 3, while the second only has a line. (e) In order to exchange two rows of A we multiply on the left by ⎛ ⎞ 0 1 ⎟ ⎜ 1 0 ⎟ M =⎜ ⎝ ⎠. 1 1 In order to exchange two columns we multiply on the right by the same M . As M = M −1 we see that the new matrix is similar to the old one, so the eigenvalues stay the same. 3 Section 6.6. Problem 22. If an n × n matrix A has all eigenvalues λ = 0 prove that An is the zero matrix. Solution (12 points) Suppose that we have a Jordan block of size i with eigenvalue 0. Then notice that J 2 will have a diagonal of 1’s two diagonals above the main diagonal and zeroes elsewhere. J 3 will have a diagonal of 1’s three diagonals above the main diagonal, and zeroes elsewhere. Therefore J i = 0, since there is no diagonal i diagonals above the main diagonal. If A has all eigenvalues λ = 0 then then A is similar to some matrix with Jordan blocks J1 , . . . , Jk with each Ji of size ni and � k ni i=1 nk = n. Each Jordan block will have eigenvalue 0, so we know that Ji = 0, and thus Jin = 0. As An is similar to a block-diagonal matrix with blocks J1n , J2n , . . . , Jkn and each of these is 0 we know that An = 0. Another way to see this is to note that if A has all eigenvalues 0 this means that the characteristic polynomial of A must be xn , as this is the only polynomial of degree n all of whose roots are 0. Thus An = 0 by the Cayley-Hamilton theorem. Section 6.6. Problem 23. For the shifted QR method in the Worked Example 6.6 B, show that A2 is similar to A1 . No change in eigenvalues, and the A’s quickly approach a diagonal matrix. Solution (12 points) We are asked to show that A2 = R1 Q1 − cs2 I is similar to A1 = Q1 R1 − cs2 I. Note that 2 −1 2 −1 2 Q1 A2 Q−1 1 = Q1 (R1 Q1 − cs I)Q1 = Q1 R1 − Q1 cs IQ1 = Q1 R1 − cs I = A1 . Thus A2 is similar to A1 , and thus their eigenvalues are the same. Section 6.6. Problem 24. If A is similar to A−1 , must all the eigenvalues equal 1 or −1? Solution (12 points) No. Consider: � � Thus 2 0 0 12 2 0 0 12 � � � = � is similar to 0 1 1 0 2 0 0 12 �−1 � �−1 . 4 1 2 0 0 2 �� 0 1 1 0 � . Section 6.7. Problem 4. Find the eigenvalues and unit�eigenvectors of AT A and � 1 1 AAT . Keep each Av = σu for the Fibonacci matrix A = . Construct the 1 0 singular value decomposition and verify that A equal sU ΣV T . Solution (4 points) T � A A= 2 1 1 1 � � T AA = 2 1 1 1 � . Note that these are the same. (This makes sense, as A√is symmetric.) The eigenval­ ues of this are the roots of x2 − 3x + 1, which are (3 ± 5)/2. The unit eigenvectors of this will be ⎛ � ⎞ ⎛ � √ ⎞ 2√ 3−√5 ⎝ � 5−√5 ⎠ and 3−√5 5− 5 Then ⎛ � U =⎝ 2√ 5− 5 � √ 3−√5 5− 5 � − � √ 3−√5 5− 5 2√ 5− 5 and � Σ= ⎝ ⎞ �5− 5 ⎠ . − 5−2√5 ⎛ � V =⎝ ⎠ √ 1+ 5 2 2√ 5− 5 � √ 3−√5 5− 5 � √ 3−√5 5− 5 ⎞ ⎠ � − 5−2√5 � √ 5−1 2 . Section 6.7. Problem 11. Suppose A has orthogonal columns w1 , . . . , wn of lengths σ1 , . . . , σn . What are U ,Σ and V in the SVD? Solution (4 points) We will first solve this assuming all of the wi are nonzero; at the end we will give a modification for the solution in the case that some are 0. As the columns of A are orthogonal we know that AT A will be a diagonal matrix with diagonal entries σ12 , . . . , σn2 . Thus U = I and Σ is the diagonal matrix with entries σ1 , . . . , σn . Then if we define V to be the matrix whose i-th row is the vector wi /σi we will have A = U ΣV T , as desired. Suppose that some of wi are zero. Take all of the w’s that are nonzero and complete them to an orthogonal basis u1 , . . . , un satisfying the conditions that if wi �= 0 then ui = wi , and if wi = 0 then |ui | = 1. Then let U, Σ be as above, and V be the matrix whose i-th row is wi /σi if σi = � 0, and ui if σi = 0. Then A = U ΣV T , as desired. 5 Section 6.7. Problem 17. The 1, −1 first difference matrix A has AT A the second difference matrix. The singular vectors of A are sine vectors V and cosine vectors u. Then Av = σu is the discrete form of d/dx(sin cx) = c(cos cx). This is the best SVD I have seen. ⎛ ⎞ ⎛ ⎞ 1 0 0 2 −1 0 ⎜ −1 1 ⎟ 0 ⎟ AT A = ⎝ −1 2 −1 ⎠ . A=⎜ ⎝ 0 −1 1 ⎠ 0 −1 2 0 0 −1 Then the orthogonal sine matrix is ⎛ ⎞ sin π/4 sin 2π/4 sin 3π/4 1 sin 4π/4 sin 6π/4 ⎠ . V = √ ⎝ sin 2π/4 2 sin 3π/4 sin 6π/4 sin 9π/4 (a) Put numbers in V : The unit eigenvectors of AT A are singular √ vectors√of A. Show that the columns of V have AT Av = λv with λ = 2 − 2, 2, 2 + 2. (b) Multiply AV and verify taht its columns are orthogonal. They are σ1 u1 and σ2 u2 and σ3 u3 . The first columns of the cosine matrix U are u1 , u2 , u3 . (c) Since A is 4 × 3 weneed a fourth orthogonal vector u4 . It comes from the nullspace of AT . What is u4 ? Solution (12 points) (a) We are asked to show that the columns of V are eigenvectors of AT A. The characteristic polynomial of AT A is x3 − 6x2 + 10x − 4, which can be factored as (x − 2)(x2 − 4x + 2). By the quadratic formua the roots of this are exactly the eigenvalues specified. Note that √ ⎞ 1/ 2 1/2 1/2 √ √ V = ⎝ 1/ 2 0√ −1/ 2 ⎠ . 1/2 1/2 −1/ 2 ⎛ ⎞ ⎛ ⎞ ⎛ ⎞ 1 1 √1 √ Then note that the three vectors ⎝ 2 ⎠ , ⎝ 0 ⎠ , ⎝ − 2 ⎠ are scalar −1 1 1 multiples of the columns of V , and it is easy to check that they are indeed eigenvectors of AT A with the right eigenvalues. ⎛ 6 (b) √ ⎞ 1 2 1 √ √ √ ⎟ 1⎜ 2− 1 − 2 − 2√ −1 ⎟ ⎜ √ √ AV = ⎝ . 1 − 2 −√ 2 1 + 2 ⎠ 2 −1 2 −1 It is easy to check that these columns are orthogonal. ⎛ ⎞ 1 −1 0 0 (c) Note that AT = ⎝ 0 1 −1 0 ⎠. The nullspace of this is generated by 0 0 1 −1 ⎛ ⎞ 1 ⎜ 1 ⎟ ⎜ ⎟. ⎝ 1 ⎠ 1 ⎛ Section 8.5. Problem 4. The first three Legendre polynomials are 1, x, x2 − 1/3. Choose c so that the fourth polynomial x3 − cx is orthogonal to the first three. All integrals go from −1 to 1. Solution (4 points) We compute � 1 � 1 2 2 3 x − cx dx = 0 (x3 − cx)x dx = − c 5 3 −1 −1 � 1 1 (x3 − cx)(x2 − ) dx = 0. 3 −1 Thus in order for x3 − cx to be orthogonal to the other three we need c = 3/5. Section 8.5. Problem 5. For the square wave f (x) in Example 3 show that � 2π � 2π � 2π f (x) cos x dx = 0 f (x) sin x dx = 4 f (x) sin 2x dx = 0. 0 0 0 Which three Fourier coefficients come from those integrals? Solution (4 points) By definition, respectively. We compute � 2π f (x) cos x dx = 0 � 2π f (x) sin x dx = 0 � 2π f (x) sin 2x dx = 0 coefficients that come from these are a1 , b1 , b2 , � π 2π � cos x dx − 0 � cos x dx = 0 � π2π π sin x dx − 0 � sin x dx = 4 π π � sin 2x dx − 0 sin 2x dx = 0. π 7 2π Section 8.5. Problem 12. The functions 1, cos x, sin x, cos 2x, sin 2x, . . . are a basis for a Hilberts space. Write the derivatives of those first five functions as combinations of the same five functions. What is the 5 × 5 “differentiation matrix” for those functions? Solution (12 points) We know that 1� = 0, and that (cos x)� = − sin x (sin x)� = cos x (cos 2x)� = −2 sin 2x Thus the “differentiation matrix” is ⎛ 0 0 0 0 0 ⎜ 0 0 −1 0 0 ⎜ ⎜ 0 1 0 0 0 ⎜ ⎝ 0 0 0 0 −2 0 0 0 2 0 (sin 2x)� = 2 cos 2x. ⎞ ⎟ ⎟ ⎟. ⎟ ⎠ Section 8.5. Problem 13. Find the Fourier coefficients ak and bk of the square pulse F (x) centered at x = 0: f (x) = 1/h for |x| ≤ h/2 and F (x) = 0 for h/2 < |x| ≤ π. As h → 0, this F (x) approaches a delta function. Find the limits of ak and bk . Solution (12 points) We compute � � h/2 1 π 1 1 a0 = F (x) dx = 1 dx = . π −π hπ −h/2 π �h/2 � π � h/2 � 1 1 1 2 kh F (x) cos kx dx = cos kx dx = sin kx�� = ak = sin . π −π πh −h/2 πhk πhk 2 −h/2 �h/2 � π � h/2 � 1 1 1 bk = F (x) sin kx dx = sin kx dx = cos kx�� = 0. π −π πh −h/2 πk −h/2 Thus as h → 0 we see that a0 → 1/π and bk → 0. We also compute 1 2 hk 1 sin x 1 sin = lim = h→0 π hk 2 π x→0 x π lim ak = lim h→0 where we set x = hk/2. 8