Linear Algebra Ch.5 - Study Guide

Chapter 5 Linear Algebra It can be argued that all of linear algebra can be understood using the four fundamental subspaces associated with a matrix. Because they form the foundation on which we later work, we want an explicit method for analyzing these subspaces- That method will be the Singular Value Decomposition (SVD). It is unfortunate that most first courses in linear algebra do not cover this material, so we do it here. Again, we cannot stress the importance of this decomposition enough- We will apply this technique throughout the rest of this text. 5.1 Representation, Basis and Dimension Let us quickly review some notation and basic ideas from linear algebra. First, a basis is a linearly independent spanning set, and the dimension of a subspace is the number of basis vectors it needs. Suppose we have a subspace H ⊂ IRn , and a basis for H in the columns of matrix V . By the definition of a basis, every vector in the subspace H can be written as a linear combination of the basis elements. In particular, if x ∈ H, then we can write: . x = c1 v 1 + . . . + ck v k = V c = V [x]V (5.1) where c is sometimes denoted as [x]V , and is referred to as the coordinates of x with respect to the basis in V. Therefore, every vector in our subset of IRn can be identified with a point in IRk , which gives us a function that we’ll call the coordinate mapping:     x1 c1  x2      x =  .  ∈ IRn ←→  ...  = c ∈ IRk  ..  ck xn If k is small (with respect to n) we think of c is the low dimensional representation of the vector x, and that H is isomorphic to IRk (Isormorphic meaning one to one and onto linear map is the isormorphism) Example 5.1.1. If v i , v j are two linearly independent vectors, then the subspace created by their span is isomorphic to the plane IR2 - but is not equal to the plane. The isomorphism is the coordinate mapping. Generally, finding the coordinates of x with respect to an arbitrary basis (as columns of a matrix V ) means that we have to solve Equation 5.1. However, if the columns of V are orthogonal, then it is very simple to compute the coordinates. Start with Equation 5.1: x = c1 v 1 + · · · + ck v k 51 Now take the inner product of both sides with v j : x · v j = c1 v 1 · v j + · · · + cj v j · v j + · · · + ck v k · v j All the dot products are 0 (due to orthogonality) except for the dot product with x and v j leading to the formula: x · vj cj = vj · vj And we see that this is the scalar projection of x onto v j . Recall the formula from Calc III: Projv (u) = u·v v v·v Therefore, we can think of the linear combination as the following, which simplifies if we use orthonormal basis vectors: (5.2) x = Projv1 (x) + Projv2 (x) + · · · + Projvk (x) = (x · v1 )v1 + (x · v2 )v2 + · · · + (x · vk )vk IMPORTANT NOTE: In the event that x is NOT in H, then Equation 5.2 gives the (orthogonal) projection of x into H. Projections Consider the following example. If a matrix U = [u1 , . . . , uk ] then that requires k ≤ n), then  T  T  u1 u1 uT1 u2 · · · u1  uT2 u1 uT2 u2 · · ·    U T U =  ...  [u1 , . . . , uk ] =  ..  . uk uTk u1 uTk u2 · · · has orthonormal columns (so if U is n × k, uT1 uk uT2 uk .. .       =   uTk uk 1 0 0 1 .. . ··· ··· 0 0 .. . 0 0 ··· 1     = Ik  But U U T (which is n × n) is NOT the identity if k = n (If k = n, then the previous computation proves that the inverse is the transpose). Here is a computation one might make for U U T (these are OUTER products):  T  u1  ..  T U U = [u1 , . . . , uk ]  .  = u1 uT1 + u2 uT2 + · · · + uk uTk uk Example 5.1.2. Consider the following computations: U= 1 0 UT U = 1 UUT = 1 0 0 0 If U U T is not the identity, what is it? Consider the following computation: U U T x = u1 uT1 x + u2 uT2 x + · · · + uk uTk x = u1 (uT1 x) + u2 (uT2 x) + · · · + uk (uTk x) which we recognize as the projection of x into the space spanned by the orthonormal vectors of U . In summary, we can think of: the following matrix form for the coordinates: [x]U = c = U T x. and the projection matrix P that takes a vector x and produces the projection of x into the space spanned by the orthonormal columns of U is P = UUT 52 Exercises 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 2. Show that the plane H defined by:       1 1   H = α1  1  + α2  −1  such that α1 , α2 ∈ IR   1 0 is isormorphic to IR2 . 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 (a) Find the projector P that takes an arbitrary vector and projects it (orthogonally) to the plane G. (b) Find the orthogonal projection of the given x onto the plane G. (c) Find the distance from the plane G to the vector x. 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) 5. If the vector x = [10, 4, 2]T and the basis vectors are [1, 0, 1]T and [3, 1, 1]T , then what is the low dimensional representation for x? 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. 7. To prove that we have an orthogonal projection, the vector Proju (x) − x should be orthogonal to u. Use this definition to show that our earlier formula was correct- that is, Proju (x) = x·u u u·u is the orthogonal projection of x onto 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. 5.2 The Four Fundamental Subspaces Given any m × n matrix A, we consider the mapping A : IRn → IRm by: x → Ax = y The four subspaces allow us to completely understand the domain and range of the mapping. We will first define them, then look at some examples. 53 Definition 5.2.1. The Four Fundamental Subspaces • The row space of A is a subspace of IRn formed by taking all possible linear combinations of the rows of A. Formally, Row(A) = x ∈ IRn | x = AT y y ∈ IRm • The null space of A is a subspace of IRn formed by Null(A) = {x ∈ IRn | Ax = 0} • The column space of A is a subspace of IRm formed by taking all possible linear combinations of the columns of A. Col(A) = {y ∈ IRm | y = Ax ∈ IRn } The column space is also the image of the mapping. Notice that Ax is simply a linear combination of the columns of A: Ax = x1 a1 + x2 a2 + · · · + xn an • Finally, we define the null space of AT can be defined in the obvious way (see the Exercises). The fundamental subspaces subdivide the domain and range of the mapping in a particularly nice way: Theorem 5.2.1. Let A be an m × n matrix. Then • The nullspace of A is orthogonal to the row space of A • The nullspace of AT is orthogonal to the columnspace of A Proof: We’ll prove the first statement, the second statement is almost identical to the first. To prove the first statement, we have to show that if we take any vector x from nullspace of A and any vector y from the row space of A, then x · y = 0. Alternatively, if we can show that x is orthogonal to each and every row of A, then we’re done as well (since y is a linear combination of the rows of A). In fact, now we see a strategy: Write out what it means for x to be in the nullspace using the rows of A. For ease of notation, let aj denote the j th row of A, which will have size 1 × n. Then:  Ax = 0 ⇒     a1 a2 .. .       x =    am a1 x a2 x .. .    =0  am x Therefore, the dot product between any row of A and x is zero, so that x is orthogonal to every row of A. Therefore, x must be orthogonal to any linear combination of the rows of A, so that x is orthogonal to the row space of A. � Before going further, let us recall how to construct a basis for the column space, row space and nullspace of a matrix A. We’ll do it with a particular matrix: Example 5.2.1. Construct a basis for the column space, row space and that is row equivalent to the matrix beside it, RREF(A):    2 0 −2 2 1 5 7 3  A =  −2 RREF(A) =  0 3 −5 −8 −2 0 54 nullspace of the matrix A below 0 1 0  −1 1 1 1  0 0 The first two columns of the original matrix form a basis for the columnspace (which is a subspace of IR3 ):     2 2   Col(A) = span  −2  ,  −2    3 3 A basis for the row space is found by using the row reduced rows corresponding to the pivots (and is a subspace of IR4 ). You should also verify that you can find a basis for the null space of A, given below (also a subspace of IR4 ). If you’re having any difficulties here, be sure to look it up in a linear algebra text:         −1  1 0  1          −1   1  −1  0          , Null(A) = span  , Row(A) = span  1   0  −1   1            1 0 1 1 We will often refer to the dimensions of the four subspaces. We recall that there is a term for the dimension of the column space- That is, the rank. Definition 5.2.2. The rank of a matrix A is the number of independent columns of A. In our previous example, the rank of A is 2. Also from our example, we see that the rank is the dimension of the column space, and that this is the same as the dimension of the row space (all three numbers correspond to the number of pivots in the row reduced form of A). Finally, a handy theorem for counting is the following. The Rank Theorem. Let the m × n matrix A have rank r. Then r + dim (Null(A)) = n This theorem says that the number of pivot columns plus the other columns (which correspond to free variables) is equal to the total number of columns. Example 5.2.2. The Dimensions of the Subspaces. Given a matrix A that is m × n with rank k, then the dimensions of the four subspaces are shown below. • dim (Row(A)) = k • dim (Col(A)) = k • dim (Null(A)) = n − k • dim Null(AT ) = m − k There are some interesting implications of these theorems to matrices of data- For example, suppose A is m × n. With no other information, we do not know whether we should consider this matrix as n points in IRm , or m points in IRn . In one sense, it doesn’t matter! The theorems we’ve discussed shows that the dimension of the columnspace is equal to the dimension of the rowspace. Later on, we’ll find out that if we can find a basis for the columnspace, it is easy to find a basis for the rowspace. We’ll need some more machinery first. 5.3 Exercises 1. Show that Null(AT ) ⊥ Col(A). Hint: You may use what we already proved. 2. If A is m × n, how big can the rank of A possibly be? 3. Show that multiplication by an orthogonal matrix preserves lengths: Qx 2 = x 2 (Hint: Use properties of inner products). Conclude that multiplication by Q represents a rigid rotation. 55 4. Prove the Pythagorean Theorem by induction: Given a set of n orthogonal vectors {xi } n n xi 2 2 = xi 2 2 i=1 i=1 The case where n = 1 is trivial, so you might look at n = 2 first. Try starting with x+y and then simplify to get x 2 2 = (x + y)T (x + y) = · · · + y 2 . Now try the induction step on your own. 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: (a) Why is the projector not P = AAT ? (b) Since ŷ − y is orthogonal to the column space of A, show that AT (ŷ − y) = 0 (5.3) (c) Show that there exists x ∈ IRn so that Equation (5.3) can be written as: AT (Ax − y) = 0 (5.4) (d) Argue that AT A (which is n × n) is invertible, so that Equation (5.4) implies that x = AT A −1 AT y (e) Finally, show that this implies that P = A AT A −1 AT Note: If A has rank k = n, then we will need something different, since AT A will not be full rank. The missing piece is the singular value decomposition, to be discussed later. 6. The Orthogonal Decomposition Theorem: if x ∈ IRn and W is a (non-zero) subspace of IRn , then x can be written uniquely as x=w+z where w ∈ W and z ∈ W ⊥ . To prove this, let {ui }pi=1 be an orthonormal basis for W , define w = (x · u1 )u1 + . . . + (x · up )up , and define z = x − w. Then: 56 (a) Show that z ∈ W ⊥ by showing that it is orthogonal to every ui . (b) To show that the decomposition is unique, suppose it is not. That is, there are two decompositions: x = w1 + z 1 , x = w2 + z2 Show this implies that w1 − w2 = z 2 − z 1 , and that this vector is in both W and W ⊥ . What can we conclude from this? 7. Use the previous exercises to prove the The Best Approximation Theorem If W is a subspace of IRn and x ∈ IRn , then the point closest to x in W is the orthogonal projection of x into W . 5.4 The Decomposition Theorems The matrix factorization that arises from an eigenvector/eigenvalue decomposition is useful in many applications, so we’ll briefly review it here and build from it until we get to our main goal, the Singular Value Decomposition. 5.4.1 The Eigenvector/Eigenvalue Decomposition First we have a basic definition: Let A be an n × n matrix. If there exists a scalar λ and non-zero vector v so that Av = λv then we say that λ is an eigenvalue and v is an associated eigenvector. An equivalent formulation of the problem is to solve Av − v = 0, or, factoring v out, (A − λI)v = 0 This equation always has the zero solution (letting v = 0), however, we need to have non-trivial solutions, and the only way that will happen is if A − λI is non-invertible, or equivalently, det(A − λI) = 0 which, when multiplied out, is a polynomial equation in λ that is called the characteristic equation. Therefore, we find the eigenvalues first, then for each λ, there is an associated subspace- The null space of A − λI, or the eigenspace associated with λ, denoted by Eλ . The way to finish the problem is to give a “nice” basis for the eigenspace- If you’re working by hand, try one with integer values. If you’re on the computer, it is often convenient to make them unit vectors. Some vocabulary associated with eigenvalues: Solving the characteristic equation will mean that we can have repeated solutions. The number of repetitions is the algebraic multiplicity of λ. On the other hand, for each λ, we find the eigenspace which will have a certain dimension- The dimension of the eigenspace is the geometric multiplicity of λ. Examples: 1. Compute the eigenvalues and eigenvectors for the 2 × 2 identity matrix. SOLUTION: The eigenvalue is 1 (a double root), so the algebraic multiplicity of 1 is 2. On the other hand, if we take A − λI, we simply get the zero matrix, which implies that every vector in IR2 is an eigenvector. Therefore, we can take any basis of IR2 is a basis for E1 , and the geometric multiplicity is 2. 57 2. Consider the matrix 1 2 0 1 Again, the eigenvalue 1 is a double eigenvalue (so the algebraic multiplicity is 2), but solving (A−λI)v = 0 gives us: 2v2 = 0 ⇒ v2 = 0 That means v1 is free, and the basis for E1 is [1, 0]T . Therefore, the algebraic multiplicity is 1. Definition: A matrix for which the algebraic and geometric multiplicities are not equal is called defective. There is a nice theorem relating eigenvalues: Theorem: If X is square and invertible, then A and X −1 AX have the same eigenvalues. Sometimes this method of characterizing eigenvalues in terms of the determinant and trace of a matrix: det(A) = Πni=1 λi trace(A) = ∞ λi i=1 Symmetric Matrices and the Spectral Theorem There are some difficulties working with eigenvalues and eigenvectors of a general matrix. For one thing, they are only defined for square matrices, and even when they are defined, we may get real or complex eigenvalues. If a matrix is symmetric, beautiful things happen with the eigenvalues and eigenvectors, and it is summarized below in the Spectral Theorem. The Spectral Theorem: If A is an n × n symmetric matrix, then: 1. A has n real eigenvalues (counting multiplicity). 2. For each distinct λ, the algebraic and geometric multiplicities are the same. 3. The eigenspaces are mutually orthogonal- both for distinct eigenvalues, and we’ll take each Eλ to have an orthonormal basis. 4. A is orthogonally diagonalizeable, with D = diag(λ1 , λ2 , . . . , λn ). That is, if V is the matrix whose columns are the (othornormal) eigenvectors of A, then A = V DV T Some remarks about the Spectral Theorem: • If a matrix is real and symmetric, the Spectral Theorem says that its eigenvectors form an orthonormal basis for IRn . • The first part is somewhat difficult to prove in that we would have to bring in more machinery than we would like. If you would like to see a proof, it comes from the Schur Decomposition, which is given, for example, in “Matrix Computations” by Golub and Van Loan. The following is a proof of the third part. Supply justification for each step: Let v 1 , v 2 be eigenvectors from distinct eigenvalues, λ1 , λ2 . We show that v 1 · v 2 = 0: λ1 v 1 · v 2 = (Av 1 )T v 2 = v T1 AT v 2 = v T1 Av 2 = λ2 v 1 · v 2 Now, (λ1 − λ2 )v 1 · v 2 = 0. 58 The Spectral Decomposition: Since A is orthogonally diagonalizable,   T λ1 0 . . . 0 q1  0 λ2 . . . 0   q T2   A = (q 1 q 2 . . . q n )  . .. . . ..   ..  .. . .  . . 0 0    A = (λ1 q 1 λ2 q 2 . . . λn q n )   q T1 q T2 .. .     q Tn . . . λn so that: then       q Tn so finally: A = λ1 q 1 q T1 + λ2 q 2 q T2 + . . . + λn q n q Tn That is, A is a sum of n rank one matrices, each of which is a projection matrix. Exercises 1. Prove that if X is invertible and matrix A is square, then A and X −1 AX have the same eigenvalues. Matlab Exercise: Verify the spectral decomposition for a symmetric matrix. Type the following into Matlab (the lines that begin with a % denote comments that do not have to be typed in). %Construct a random, symmetric, 6 x 6 matrix: for i=1:6 for j=1:i A(i,j)=rand; A(j,i)=A(i,j); end end %Compute the eigenvalues of A: [Q,L]=eig(A); %NOTE: A = Q L Q’ %L is a diagonal matrix %Now form the spectral sum S=zeros(6,6); for i=1:6 S=S+L(i,i)*Q(:,i)*Q(:,i)’; end max(max(S-A)) Note that the maximum of S − A should be a very small number! (By the spectral decomposition theorem). 5.4.2 The Singular Value Decomposition There is a special matrix factorization that is extremely useful, both in applications and in proving theorems. This is mainly due to two facts, which we shall investigate in this section: (1) We can use this factorization on any matrix, (2) The factorization defines explicitly the rank of the matrix, and gives orthonormal bases for all four matrix subspaces. In what follows, assume that A is an m × n matrix (so A maps IRn to IRm and is not square). 59 1. Although A itself is not symmetric, AT A is n × n and symmetric, so the Spectral Theorem applies. In particular, AT A is orthogonally diagonalizable. Let {λi }ni=1 and V = [v 1 , v 2 , . . . , v n ] be the eigenvalues and orthonormal eigenvectors so that AT A = V DV T and D is the diagonal matrix with λi along the diagonal. 2. Exercise: Show that λi ≥ 0 for i = 1..n by showing that Avi 2 2 = λi . As a starting point, you might rewrite Av i 2 = (Av)T Av 3. Definition: We define the singular values of A by: σi = λi where λi is an eigenvalue of AT A. 4. In the rest of the section, we will assume any list (or diagonal matrix) of eigenvals of AT A (or singular values of A) will be ordered from highest to lowest: λ1 ≥ λ2 ≥ . . . ≥ λn . 5. Exercise: Prove that, if v i and v j are distinct eigenvectors of AT A, then their corresponding images, Av i and Av j , are orthogonal. 6. Exercise: Prove that, if x = α1 v 1 + . . . αn v n , then Ax 2 = α21 λ1 + . . . + α2n λn n 7. Exercise: Let W be the subspace generated by the basis {v j }j=k+1 , where v j are the eigenvectors associated with the zero eigenvalues of AT A (therefore, we are assuming that the first k eigenvalues are NOT zero). Show that W = Null(A). Hint: To show this, take an arbitrary vector x from W . Rather than showing directly that Ax = 0, instead show that the magnitude of Ax is zero. We also need to show that if we take any vector from the nullspace of A, then it is also in W . 8. Exercise: Prove that if the rank of AT A is r, then so is the rank of A. Hint: How does the previous exercise help? 9. Define the columns of a matrix U as: ui = 1 Av i 2 Av i = 1 Av i σi and let U be the matrix whose ith column is ui . We note that this definition only makes sense sense for the first r vectors v (otherwise, Av i = 0). Thus, we’ll have to extend the basis to span all of IRm , which can be done using Gram-Schmidt. 10. Exercise: Show that ui is an eigenvector of AAT whose eigenvalue is also λi . 11. Exercise: Show that AT ui = σi v i 12. So far, we have shown how to construct two matrices, U and V given a matrix A. That is, the matrix V is constructed by the eigenvectors of AT A, and the matrix U can be constructed using the v’s or by finding the eigenvectors of AAT . 60 1 2 v1 0.8 1.5 0.6 1 0.4 σ1u1 0.5 0.2 0 0 v2 −0.2 −0.5 −0.4 −1 σ2u2 −0.6 −1.5 −0.8 −2 −1 −0.5 0 0.5 1 −2.5 −2 −1.5 −1 −0.5 0 0.5 1 1.5 2 2.5 Figure 5.1: The geometric meaning of the right and left singular vectors of the SVD decomposition. Note that Av i = σi ui . The mapping x → Ax will map the unit circle on the left to the ellipse on the right. 13. Exercise: Let A be m × n. Define the m × n matrix Σ = diag(σ1 , . . . , σn ) where σi is the ith singular value of the matrix A. Show that AV = U Σ 14. Theorem: The Singular Value Decomposition (SVD) Let A be any m × n matrix of rank r. Then we can factor the matrix A as the following product: A = U ΣV T where U, Σ, V are the matrices defined in the previous exercises. That is, U is an orthogonal m × m matrix, Σ is a diagonal m × n matrix, and V is an orthogonal n × n matrix. The u’s are called the left singular vectors and the v’s are called the right singular vectors. 15. Keep in mind the following relationship between the right and left singular vectors: Av i AT ui = = σi ui σi v i 16. Computing The Four Subspaces to a matrix A. Let A = U ΣV T be the SVD of A which has rank r. Be sure that the singular values are ordered from highest to lowest. Then: (a) A basis for the columnspace of A, Col(A) is {ui }ri=1 (b) A basis for nullspace of A, Null(A) is {v i }ni=r+1 r (c) A basis for the rowspace of A, Row(A) is {v i }i=1 m (d) A basis for the nullspace of AT , Null(AT ) is {ui }i=r+1 17. We can also visualize the right and left singular values as in Figure 5.1. We think of the v i as a special orthogonal basis in Rn (Domain) that maps to the ellipse whose axes are defined by σi ui . 18. The SVD is one of the premier tools of linear algebra, because it allows us to completely reveal everything we need to know about a matrix mapping: The rank, the basis of the nullspace, a basis for the column space, the basis for the nullspace of AT , and of the row space. This is depicted in Figure 5.2. 61 Col(AT ) v1 u1 v2 .. . vk u2 .. . ⇐⇒ Col(A) uk N(A) vk+1 .. . =⇒ vn 0 IRn ⇐= 0 uk+1 .. . N(AT ) um IRm Figure 5.2: The SVD of A ([U,S,V]=svd(A)) completely and explicitly describes the 4 fundamental subspaces associated with the matrix, as shown. We have a one to one correspondence between the rowspace and columnspace of A, the remaining v’s map to zero, and the remaining u’s map to zero (under AT ). 62 19. Lastly, the SVD provides a decomposition of any linear mapping into two “rotations” and a scaling. This will become important later when we try to deduce a mapping matrix from data (See the section on signal separation). 20. Exercise: Compute the SVD by hand of the following matrices:  0  0 0 1 1 0 0  2 0  0 21. Remark: If m or n is very large, it might not make sense to keep the full matrix U and V . 22. The Reduced SVD Let A be m × n with rank r. Then we can write: A = Ũ Σ̃V˜T where Ũ is an m × r matrix with orthogonal columns, Σ̃ is an r × r square matrix, and Ṽ is an n × r matrix. 23. Theorem: (Actually, this is just another way to express the SVD). Let A = U ΣV T be the SVD of A, which has rank r. Then: r σi ui v Ti A= i=1 Therefore, we can approximate A by the sum of rank one matrices. 24. Matlab and the SVD Matlab has the SVD built in. The function specifications are: [U,S,V]=svd(A) and [U,S,V]=svd(A,0) where the first function call returns the full SVD, and the second call returns a reduced SVD- see Matlab’s help file for the details on the second call. 25. Matlab Exercise: Image Processing and the SVD. First, in Matlab, load the clown picture: load clown This loads a matrix X and a colormap, map, into the workspace. To see the clown, type: image(X); colormap(map) We now perform a Singular Value Decomposition on the clown. Type in: [U,S,V]=svd(X); How many vectors are needed to retain a good picture of the clown? Try performing a k−dimensional reconstruction of the image by typing: H=U(:,1:k)*S(1:k,1:k)*V(:,1:k)’; image(H) for k = 5, 10, 20 and 30. What do you see? 63 Generalized Inverses Let a matrix A be m × n with rank r. In the general case, A does not have an inverse. Is there a way of restricting the domain and range of the mapping y = Ax so that the map is invertible? We know that the columnspace and rowspace of A have the same dimensions. Therefore, there exists a 1-1 and onto map between these spaces, and this is our restriction. To “solve” y = Ax, we replace y by its orthogonal projection to the columnspace of A, ŷ. This gives the least squares solution, which makes the problem solvable. To get a unique solution, we replace x by its projection to the rowspace of A, x̂. The problem ŷ = Ax̂ now has a solution, and that solution is unique. We can rewrite this problem now in terms of the reduced SVD of A: ŷ = U U T y x̂ = V V T x, Now we can write: U U T y = U ΣV T V V T x so that V Σ−1 U T y = V V T x (Exercise: Verify that these computations are correct!) Given an m × n matrix A, define its pseudoinverse, A† by: A† = V Σ−1 U T We have shown that the least squares solution to y = Ax is given by: x̂ = A† y where x̂ is in the rowspace of A, and its image, Ax̂ is the projection of y into the columnspace of A. Geometrically, we can understand these computations in terms of the four fundamental subspaces. ✻Row(A) Ax = y ✲ ✻Col(A) qy ✲ Null(A) ✲ Null(AT ) IRn IRm In this case, there is no value of x ∈ IRn which will map onto y, since y is outside the columnspace of A. To get a solution, we project y onto the columnspace of A as shown below: ✻Row(A) ✻Col(A) qy ŷ = U U T y ✲ Null(A) ✲ Null(AT ) 64 Now it is possible to find an x that will map onto ŷ, but if the nullspace of A is nontrivial, then all of the points on the dotted line will also map to ŷ ✻Row(A) x̂ = V V T xr ✻Col(A) rx qy ŷ ✲ Null(A) ✲ Null(AT ) Finally, we must choose a unique value of x for the mapping- We choose the x inside the rowspace of A. This is a very useful idea, and it is one we will explore in more detail later. For now, notice that to get this solution, we analyzed our four fundamental subspaces in terms of the basis vectors given by the SVD. Exercises 1. Consider  2 1 3 1 −1 2  x1  x2  = x3 5 1 (a) Before solving this problem, what are the dimensions of the four fundamental subspaces? (b) Use Matlab to compute the SVD of the matrix A, and solve the problem by computing the pseudoinverse of A directly. (c) Check your answer explicitly and verify that x̂ and ŷ are in the rowspace and columnspace. (Hint: If a vector x is already in the rowspace, what is V V T x?) 2. Consider        2 1 −1 3  x1 −1 0 1 −2    x2  7 2 −5 12    x3  −3 −2 0 −4 x4 4 1 −3 7      =    5 1 0 −2 6       (a) Find the dimensions of the four fundamental subspaces by using the SVD of A (in Matlab). (b) Solve the problem. (c) Check your answer explicitly and verify that x̂ and ŷ are in the rowspace and columnspace. 3. Write the following in Matlab to reproduce Figure 5.1: theta=linspace(0,2*pi,30); z=exp(i*theta); X=[real(z);imag(z)]; %The domain points m=1/sqrt(2); A=(m*[1,1;1,-1])*[1,0;0,3]; Y=A*X; %The image of the circle t=linspace(0,1); vec1=[0;0]*(1-t)+[0;1]*t; %The basis vectors v 65 vec2=[0;0]*(1-t)+[1;0]*t; Avec1=A*vec1; Avec2=A*vec2; %Image of the basis vectors figure(1) %The domain plot(X(1,:),X(2,:),’k’,vec1(1,:),vec1(2,:),’k’, vec2(1,:),vec2(2,:),’k’); axis equal figure(2) %The image plot(Y(1,:),Y(2,:),’k’,Avec1(1,:),Avec1(2,:),’k’, Avec2(1,:),Avec2(2,:),’k’); axis equal 4. In the previous example, what was the matrix A? The vectors v? The vectors u? The singular values σ1 , σ2 ? Once you’ve written these down from the program, perform the SVD of A in Matlab. Are the vectors the same that you wrote down? NOTE: These show that the singular vectors are not unique- they vary by ±v, or ±u. 66