Math 350 Week 10 Homework Summary

Week 10 Homework Summary I. From Monday: 1, 4, 5 on p. 55: 1. Show that Null(AT ) ⊥ Col(A). SOLUTION: Let B = AT . Then we prove that Null(B) ⊥ Row(B) which is equivalent. If we write B in terms of rows, B = [r1 , r2 , . . . , rm ]T , then the ith component of Bx can be written as r i x = 0. Thus, if x is in the nullspace of B, then it is orthogonal to every row of B. 4. Prove the Pythagorean Theorem by induction: Given a set of n orthogonal vectors {xi } n n X X 2 k kxi k22 x i k2 = i=1 i=1 The case where n = 1 is trivial, so you might look at n = 2 first. Try starting with kx + yk2 = (x + y)T (x + y) = · · · and then simplify to get kxk2 + kyk2 . Now try the induction step on your own. SOLUTION: The case with n = 1 is trivial. The case with n = 2 is straightforward. Assume true for k = n, n n X X k x i k2 = kxi k2 i=1 i=1 Show true for k = n + 1: k n+1 X n X x i k2 = i=1 n X i=1 !T xi n X !T xi + xn+1 i=1 ! xi + i=1 n X ! xi + xn+1 = i=1 n X ! xi xTn+1 + xn+1 i=1 n X !T xi + xTn+1 xn+1 i=1 By the induction step, that first term is: !T ! n n n X X X xi xi = kxi k2 i=1 i=1 i=1 The second and third terms are zero since xn+1 is orthogonal to the first n vectors, and the last term is kxn+1 k2 . Therefore, the expression simplifies to the desired value, n+1 n+1 X X k x i k2 = kxi k2 i=1 i=1 1 5. Let A be an m × n matrix where m > n, and let A have rank n. Let y, ŷ ∈ IRm , such that ŷ is the orthogonal projection of y onto the column space of A. We want a formula for the matrix P : IRm → IRm so that Py = ŷ. The following image shows the relevant subspaces (See page 56 for the graph) (a) Why is the projector not P = AAT ? SOLUTION: If the columns of A were orthonormal, it would be. In class, we found the actual projection matrix to be the one below, which is: P = A(AT A)−1 AT which we are showing now. (b) Since ŷ − y is orthogonal to the column space of A, show that AT (ŷ − y) = 0 (1) SOLUTION: We know that Col(A) ⊥ Null(AT ). Therefore, if ŷ − y is orthogonal to the column space of A, then it must be in the null space of AT . (c) Show that there exists x ∈ IRn so that Equation (1) can be written as: AT (Ax − y) = 0 (2) SOLUTION: Since ŷ is in the columnspace of A, by definition there exists a x ∈ IRn such that Ax = ŷ. (d) Argue that AT A (which is n × n) is invertible, so that Equation (2) implies that
−1 T A y x = AT A SOLUTION: The matrix A has rank n, therefore AT A is an n × n matrix with rank n as well (the ranks are equal). Therefore, AT A is invertible, and we get the pseudoinverse, A† = (AT A)−1 AT . (e) Finally, show that this implies that
−1 T P = A AT A A SOLUTION: Multiply both sides of the previous equation by A. 2 II. From Tuesday: 1, 3, 4, 6, 7, 8 on p. 53 (Yes, we were working a little backwards). 1. Let the subspace H be formed by the span of the vectors v 1 , v 2 given below. Given the point x1 , x2 below, find which one belongs to H, and if it does, give its coordinates. (NOTE: The basis vectors are NOT orthonormal)         1 2 7 4 v 1 =  2  v 2 =  −1  x1 =  4  x2 =  3  −1 1 0 −1 SOLUTION: Rather than row-reduce twice, we’ll do it once on the augmented matrix below.     4 1 0 3 2 1 2 7  2 −1 4 3 → 0 1 2 1  −1 1 0 −1 0 0 1 0 How should this be interpreted? The second vector, x2 is in H, as it can be expressed as 2v 1 + v 2 . Its low dimensional representation is thus [2, 1]T . The first vector, x1 , cannot be expressed as a linear combination of v 1 and v 2 , so it does not belong to H. 3. Let the subspace G be the plane defined below, and consider the vector x, where:         1 3 1   G = α1  3  + α2  −1  such that α1 , α2 ∈ IR x= 0    −2 0 2 (Skip part (a)) b. Find the orthogonal projection of the given x onto the plane G (note that the vectors are orthogonal). SOLUTION: Let the vectors given (normalize them) be u1 and u2 . Then we compute:       1 3 0.686 3  −3   3 + −1  ≈  −0.943  ProjG (x) = (x · u1 )u1 + (x · u2 )u2 = 14 10 2 0 0.429 (Added) Show that the formula in 5(e) from the previous page works for this problem as well. SOLUTION: I shouldn’t have added this- This was enough computation. c. Find the distance from the plane G to the vector x. SOLUTION: The distance is the length of the vector going from x to the projection of x in G, or 1 − 0.686 0.943 2 − 0.429 3 ≈ 1.859 4. If the low dimensional representation of a vector x is [9, −1]T and the basis vectors are [1, 0, 1]T and [3, 1, 1]T , then what was the original vector x? (HINT: it is easy to compute it directly) SOLUTION: [6, −1, 8]T . 6. Let a = [−1, 3]T . Find a square matrix P so that P x is the orthogonal projection of x onto the span of a. SOLUTION: We’re thinking of the outer product divided by the inner product, or   1 1 −3 P = 9 10 −3 7. (Reworded from the text) Suppose we have vectors x, u, and the projection of x onto u (Call it x̂). • If the projection is orthogonal, then which vectors should be perpendicular? SOLUTION: The vector x − x̂ should be orthogonal to u. • If x̂ = cu, find the constant c from your previous answer. SOLUTION: The constant comes from the orthogonality (x − cu) · u = 0 ⇒ x · u = cu · u ⇒ c= x·u u·u 8. Continuing with the last exercise, show that U U T x is the orthogonal projection of x into the space spanned by the columns of U by showing that (U U T x − x) is orthogonal to ui for any i = 1, 2, · · · , k. SOLUTION: Notice that U U T = u1 uT1 + u2 uT2 + · · · + uk uTk so that (U U T x − x) · ui = [(0 + 0 + · · · + 0) + (ui · ui )(ui · x) + (0 + 0 + · · · + 0)] − x · ui = 0 4 III. Homework from Thursday, Nov 6th 1 . Assume that A and B are row equivalent, where:     1 2 −2 0 7 1 0 4 0 −3  −2 −3  0 1 −3 0 1 −1 −5  5  ,   A= B =  −3 −4  0 0 0 −2 −3  0 1 −4  3 6 −6 5 1 0 0 0 0 0 (a) State which vector space (IR? ) contains each of the four subspaces, and state the dimension of each of the four subspaces: SOLUTION: Here are the spaces and dimensions: A. The row space of A is a subspace of IR5 and has dimension 3 (this is the number of pivot rows). B. The column space of A is a subspace of IR4 and has dimension 3 (this is also known as the rank of A and is the number of pivot columns). C. The null space of A is a subspace of IR5 and has dimension 2 (the number of free variables). D. The null space of AT is a subspace of IR4 and has dimension 1 (because the dimension of the column space is 3, and they should add to 4). (b) Find a basis for Col(A): SOLUTION: We see from the RREF that the pivot columns are cols 1, 2, and 4. Be sure to use the columns from the original matrix A! The basis is the set       1 2 0        −3   −1  −2 ,   ,  −3   −4   −2       3 6 5 (c) Find a basis for Row(A): SOLUTION: We can use the reduced rows (written as columns) for the basis:       1 0 0               0   1   0    4  ,  −3  ,  0            0   0   1        −3 5 −4 (d) Find a basis for Null(A): SOLUTION: Solve Ax = 0, and the vectors are the basis vectors:     x1 = −4x3 + 3x5 −4 3        −5   x2 = 3x3 − 5x5  3        x3 = x3 ⇒   1  ,  0    0   4  x4 = 4x5       x5 = x5 0 1 5 2. From Monday’s HW, we said that if we’re solving for Ax = y and A has linearly independent columns, then we can solve for x using the normal equations (just as we did in the linear regression problem): ⇒ Ax = y AT Ax = AT y And since A has full rank (it has linearly independent columns), then x = (AT A)−1 AT y The matrix (AT A)−1 AT is called the pseudoinverse of A, and is denoted by A† . Find the pseudoinverse matrix of A, if   1 1 A= 1 2  1 3 SOLUTION: This is just a matter of multiplying it out. See the exam review sheet. 3. Also from Monday’s HW, we said that if x = (AT A)−1 AT y then Ax = A(AT A)−1 AT y Since Ax is in the column space of A, then the vector on the right side of the equation must be the orthogonal projection of y into the column space of A. Therefore, the matrix that takes y and produces the projection of y is: P = A(AT A)−1 AT Find the matrix P using the matrix A from the previous exercise. SOLUTION: It’s just a matter of multiplying it out. See the exam review sheet. 6