Linear Algebra Solutions to the Review 4 Exercises

Solutions to the Review 4 Exercises 1. Find the least squares solution to Ax = b, given A and b below. Note that the columns of A are orthogonal, and use that fact.     2 −1 1    2 A= 2 b= 2  1 −2 1 SOLUTION: Since the columns of A are orthogonal, we can compute the b̂ directly. b̂ = bT a2 7 1 bT a1 a + a2 = a1 + a2 = Ax̂ 1 T T 9 9 a1 a1 a2 a2 so we can read x̂ off: [7/9, 1/9]T . (See page 414 for another example). 2. Find the line that best fits the data: (−1, −1), (0, 2), (1, 4), (2, 5). Do this by first finding a matrix equation that you will then find the least squares solution to (by using the normal equations). SOLUTION: The model equation is y = β0 + β1 x, so the matrix equation is:     1 −1  −1   1   0    β0 =  2   1  4  1  β1 1 2 5 Forming the normal equations, we have:     8 3 1 β0 = A Ac = A y ⇒ β1 18 1 10        1 62 1 10 −1 8 β0 = = 3 18 β1 29 −1 29 46 T T  3. Suppose A is m × n with linearly independent columns and b is in IRm . Use the normal equations to produce a formula for b̂, the projection of b onto the column space of A. (Hint: First find x̂ which does not require an orthogonal basis for Col(A).) SOLUTION: Given Ax = b, we know that x̂ solves the least squares problem: x̂ = (AT A)−1 AT b And that b̂ = Ax̂. Therefore, we get b̂ by multiplying both sides of our previous equation by A: b̂ = Ax̂ = A(AT A)−1 AT b Therefore, the matrix that sends b to b̂ is A(AT A)−1 AT . Side remark: If A was an invertible matrix, then this entire expression simplifies to I. 1 4. Show that if x ∈ Null(A), then x ∈ Null(AT A). SOLUTION: If x ∈ Null(A), then Ax = 0. Multiplying both sides by AT , we see that AT Ax = 0, so that x ∈ Null(AT A). Show that if AT Ax = 0, then kAxk =?. SOLUTION: Looking at the expression to the left, kAxk2 = (Ax · (Ax) = xT AT Ax. Now, if AT Ax = 0 then xT AT Ax = 0 ⇒ kAxk2 = 0 Use the above to show that, if x ∈ Null(AT A), then x ∈ Null(A). SOLUTION: In the previous problem, we showed that if x ∈ Null(AT A), then kAxk = 0. This implies that Ax = 0, or equivalently, that x ∈ Null(A). Altogether, this problem is showing that the null spaces of A and AT A are the same! 5. Using the last problem, what can we conclude about the rank of A versus the rank of AT A? SOLUTION: If A is m × n, then the null spaces of A and AT A are the same subspaces of IRn - thus they also have the same dimension. Therefore, the dimension of Row(A) and Row(AT A) are the same, and therefore, the dimension of Col(A) and Col(AT A) are the same. Therefore, A and AT A have the same rank. 6. Suppose I have a model equation: y = β0 + β1 sin(v) + β2 ln(w). Given the following data, set up the matrix equation from which we could determine a least squares solution for the β’s: v w y −1 2 1 1 1 2 0 3 −1 3 2 0  ⇒    1 sin(−1) ln(2)  1 β0  1   sin(1) ln(1)   2  β1  =   1  −1 sin(0) ln(3)  β2 1 sin(3) ln(2) 0 Side Remark: In Matlab, you could solve this: v=[-1 1 0 3]’; w=[2 1 3 2]’; y=[1 2 -1 0]’; A=[ones(4,1), sin(v), log(w)]; beta=A\y; 2     7. Given vectors u, v in the vector space IRn with the usual dot product as inner product, show that the Pythagorean Theorem still holds. That is, if u and v are orthogonal to each other, then: ku + vk2 = kuk2 + kvk2 SOLUTION: Write out the left side in terms of the dot product, and expand. ku + vk2 = (u + v) · (u + v) = u · u + u · v + v · u + v · v Since u · v = 0, this expression reduces to u · u + v · v = kuk2 + kvk2  8. Orthogonally diagonalize the symmetric matrix A =  7 2 . 2 4 SOLUTION: We notice that this matrix is symmetric. Find the eigenvalues first: λ2 − Tr(A)λ + det(A) = 0 λ2 − 11λ + 24 = 0 ⇒ ⇒ (λ − 8)(λ − 3) = 0 For λ = 8, we solve the following (I’m just using the first equation since the two equations should be constant multiples of each other):   1 v1 = 2v2 2 (7 − 8)v1 + 2v2 = 0 ⇒ ⇒ v=√ v2 = v2 5 1 Similarly, for λ = 3: (7 − 3)v1 + 2v2 = 0 ⇒ 4v1 + 2v2 = 0 ⇒ v1 = v1 v2 = −2v2 ⇒ 1 v=√ 5  1 −2  Therefore, A = P DP T , where 1 P =√ 5  2 1 1 −2   D= 8 0 0 3  (NOTE: The order of the columns should correspond to the order of the eigenvalues!) 9. True or False, and explain: For every non-zero vector v ∈ IRn , the matrix vvT is called a projection matrix. Generally, that would be false, but if v were a unit vector, then it would be true, since Projv (x) = vT x v = v(vT x) = vvT x vT v 3 10. Show that, if A is symmetric, then any two eigenvectors from distinct eigenvalues are orthogonal. Hint: Start with λ1 v1 · v2 , and see if you can transform this into λ2 v1 · v2 . SOLUTION: Starting with the hint, λ1 v1 · v2 = (Av1 ) · v2 = v1T AT v2 = v1T (Av2 ) = v1T λ2 v2 = λ2 v1 · v2 Subtracting the right side: (λ1 − λ2 )v1 · v2 = 0 Since λ1 6= λ2 , then v1 must be orthogonal to v2 . 11. Suppose we have the matrix A = [1, 1, 1]. (a) What will the singular values of A be? (Try to compute them in the easiest possible way). SOLUTION: We can use either AAT or AT A. In this case, use AAT = 3. The eigenvalue is 3, the others are 0. Therefore, there is one non-zero singular value √ σ1 = 3. (b) Find (by hand) the reduced SVD for the matrix A. See if you can do it without any computation. SOLUTION: The reduced SVD would look like:  T ∗ √ [1, 1, 1] = 1 · 3 ·  ∗  ∗ so we see that u1 = 1 and v1 = √1 [1, 1, 1]T . 3 (c) Find a basis for the null space of A using the rest of the SVD that hasn’t been computed yet (this one we’ll need to compute). For the other two columns of V , we solve for the null space of [111], or:     v1 = −v2 − v3 −1 −1 v2 = v2 ⇒ v = v1  1  + v2  0  v3 = v3 0 1 Side Remark: The full SVD for the problem would be: √ √ T  √ 1/ 3 −1 2 −1/ 2 √ √ √   [1, 1, 1] = 1 · [ 3, 0, 0] 1/√3 1 2 √0 0 1/ 2 1/ 3 12. Show that the eigenvalues of AT A are non-negative. Hint: Consider kAvi k. SOLUTION: Using the hint, we have kAvi k2 = (Avi )T (Avi ) = viT AT Avi = λi viT vi = λi 4 Therefore, λi must be non-negative. Side Remark: This was an important result so that we could define the singular values as the square root of these eigenvalues. 13. Suppose the SVD was given as the following:    T 0.65 −0.75 0 15.91 0 0 −0.52 −0.62 −0.57 0 0 1  0 3.26 0   −0.27 0.76 −0.57  A= 0.75 0.65 0 0 0 0 −0.80 0.14 0.57 (a) What is the rank of A? SOLUTION: The rank is the number of non-zero singular values, so in this case, the rank is 2. (b) Write a basis for the column space and null space of A. SOLUTION: The column space is spanned by the first two columns of U , and the null space is spanned by the last column of V . (c) Write the matrix product for the pseudoinverse of A (you don’t need to multiply it out). SOLUTION: Symbolically (Matlab notation for the columns), it is V (:, 1 : 2)Σ−1 (1 : 2, 1 : 2)U (:, 1 : 2)   −0.52 −0.62   −0.27 0.76  −0.80 0.14 1 15.91 0 0 1 3.26    0.65 −0.75  0 0  0.75 0.65 14. Suppose A is square and invertible. Find the SVD of A−1 . SOLUTION: If A is square and invertible, then in the SVD for A: A = U ΣV T the matrices U and V are orthogonal (so U U T = U T U  1 0 ··· 0 σ1  0 1 0··· 0  σ A−1 = V  . 2 ..  .. . 0 0 ··· 1 σn = I, and similarly for V ):    T U  15. Show that if A is square, then |det(A)| is the product of the singular values of A. SOLUTION: A = U ΣV T det(A) = det(U ΣV T ) ⇒ Here is where we need all matrices to be square- So the determinant is defined: det(A) = det(U )det(Σ)det(V ) 5 Since U and V are orthogonal, each of their determinants is ±1 (be sure that you can prove this). Therefore, det(A) = ±det(Σ) = ±σ1 σ2 · · · σn 6