Orthogonal Projections and Reections (with exercises) by D. Klain Version 2010.01.23 Corrections and comments are welcome!
Orthogonal Projections
Let X1 , . . . , Xk be a family of linearly independent (column) vectors in Rn , and let W = Span(X1 , . . . , Xk ). In other words, the vectors X1 , . . . , Xk form a basis for the k-dimensional subspace W of Rn . Suppose we are given another vector Y Rn . How can we project Y onto W orthogonally? In other words, can we nd a vector Y W so that Y Y is orthogonal (perpendicular) to all of W ? See Figure 1. To begin, translate this question into the language of matrices and dot products. We need to nd a vector Y W such that (Y Y ) Z, for all vectors Z W . (1)
Actually, its enough to know that Y Y is perpendicular to the vectors X1 , . . . , Xk that span W . This would imply that (1) holds. (Why?) Expressing this using dot products, we need to nd Y W so that XiT (Y Y ) = 0, for all i = 1, 2, . . . , k. (2)
This condition involves taking k dot products, one for each Xi . We can do them all at once by setting up a matrix A using the Xi as the columns of A, that is, let A = X1 X2 Xk .
Note that each vector Xi Rn has n coordinates, so that A is an n k matrix. The set of conditions listed in (2) can now be re-written: AT (Y Y ) = 0, which is equivalent to AT Y = AT Y . (3)
Figure 1: Projection of a vector onto a subspace. Meanwhile, we need the projected vector Y to be a vector in W , since we are projecting lies in the span of the vectors X1 , . . . , Xk . In other words, onto W . This means that Y c1 c2 Y = c1 X1 + c2 X2 + + ck Xk = A . = AC. . . ck where C is a k-dimensional column vector. On combining this with the matrix equation (3) we have AT Y = AT AC. If we knew what C was then we would also know Y , since we were given the columns Xi of A, and Y = AC. To solve for C just invert the k k matrix AT A to get (AT A)1 AT Y = C. (4)
How do we know that (AT A)1 exists? Lets assume it does for now, and then address this question later on. Now nally we can nd our projected vector Y . Since Y = AC, multiply both sides of (4) to obtain A(AT A)1 AT Y = AC = Y . The matrix Q = A(AT A)1 AT is called the projection matrix for the subspace W . According to our derivation above, the projection matrix Q maps a vector Y Rn to its orthogonal projection (i.e. its shadow) QY = Y in the subspace W . It is easy to check that Q has the following nice properties: 2
1. QT = Q. 2. Q2 = Q. One can show that any matrix satisfying these two properties is in fact a projection matrix for its own column space. You can prove this using the hints given in the exercises. There remains one problem. At a crucial step in the derivation above we took the inverse of the k k matrix AT A. But how do we know this matrix is invertible? It is invertible, because the columns of A, the vectors X1 , . . . , Xk , were assumed to be linearly independent. But this claim of invertibility needs a proof. Lemma 1. Suppose A is an nk matrix, where k n, such that the columns of A are linearly independent. Then the k k matrix AT A is invertible. Proof of Lemma 1: Suppose that AT A is not invertible. In this case, there exists a vector X = 0 such that AT AX = 0. It then follows that (AX) (AX) = (AX)T AX = X T AT AX = X T 0 = 0, so that the length AX = (AX) (AX) = 0. In other words, the length of AX is zero, so that AX = 0. Since X = 0, this implies that the columns of A are linearly dependent. Therefore, if the columns of A are linearly independent, then AT A must be invertible. Example: Compute the projection matrix Q for the 2-dimensional subspace W of R4 spanned by the vectors (1, 1, 0, 2) and (1, 0, 0, 1). What is the orthogonal projection of the vector (0, 2, 5, 1) onto W ? Solution: Let 1 1 1 0 . A= 0 0 2 1 AT A =
1 11 6 11
2 6 1 11 and (AT A)1 = 1 1 2 11 so that the projection matrix Q is given by 1 1 2 1 0 11 1 1 1 0 2 1 11 Q = A(AT A)1 AT = 6 0 0 1 0 0 1 11 11 2 1
Then
10 11 3 11
3 11 2 11
0
1 11
0 0 0 0 3 11 0
1 11 3 11 10 11
We can now compute the orthogonal projection of the vector (0, 2, 5, 1) onto W . This is 10 3 7 1 0 11 11 0 11 11 2 3 1 3 0 11 2 11 11 11 0 0 0 5 = 0 0 1 4 3 10 1 11 11 0 11 11 3
Reections
We have seen earlier in the course that reections of space across (i.e. through) a plane is linear transformation. Like rotations, a reection preserves lengths and angles, although, unlike rotations, a reection reverses orientation (handedness). Once we have projection matrices it is easy to compute the matrix of a reection. Let W denote a plane passing through the origin, and suppose we want to reect a vector v across this plane, as in Figure 2. Let u denote a unit vector along W , that is, let u be a normal to the plane W . We will think of u and v as column vectors. The projection of v along the line through u is then given by: v = P roju (v) = u(uT u)1 uT v. But since we chose u to be a unit vector, uT u = u u = 1, so that v = P roju (v) = uuT v. Let Qu denote the matrix uuT , so that v = Qu v. What is the reection of v across W ? It is the vector ReW (v) that lies on the other side of W from v, exactly the same distance from W as is v, and having the same projection into W as v. See Figure 2. The distance between v and its reection is exactly twice the distance of v to W , and the dierence between v and its reection is perpendicular to W . That is, the dierence between v and its reection is exactly twice the projection of v along the unit normal u to W . This observation yields the equation: v ReW (v) = 2Qu v, so that ReW (v) = v 2Qu v = Iv 2Qu v = (I 2uuT )v. The matrix HW = I 2uuT is called the reection matrix for the plane W , and is also sometimes called a Householder matrix. Example: Compute the reection of the vector v = (1, 3, 4) across the plane 2x y + 7z = 0. Solution: The vector w = (2, 1, 7) is normal to the plane, and wT w = 22 + (1)2 + 72 = 54, so a unit normal will be w 1 u= = (2, 1, 7). |w| 54 The reection matrix is then given by 2 2 1 1 2 1 7 = H = I 2uuT = I wwT = I 54 27 7 4
Figure 2: Reection of the vector v across the plane W . 1 0 0 4 2 14 1 2 1 7 , = 0 1 0 27 0 0 1 14 7 49 so that 23/27 2/27 14/27 2/27 26/27 7/27 H= 14/27 7/27 22/27
The reection of v across W is then given by 23/27 2/27 14/27 1 39/27 2/27 26/27 7/27 3 = 48/27 Hv = 14/27 7/27 22/27 4 123/27
Reections and Projections
Notice in Figure 2 that the projection of v into W is the midpoint of the vector v and its reection Hv = ReW (v); that is, 1 Qv = (v + Hv) or, equivalently Hv = 2Qv v, 2 where Q = QW denotes the projection onto W . (This is not the same as Qu in the previous section, which was projection onto the normal of W .) Recall that v = Iv, where I is the identity matrix. Since these identities hold for all v, we obtain the matrix identities: 1 Q = (I + H) and H = 2Q I, 2 So once you have computed the either the projection or reection matrix for a subspace of Rn , the other is quite easy to obtain.
Exercises
1. Suppose that M is an n n matrix such that M T = M = M 2 . Let W denote the column space of M . (a) Suppose that Y W . (This means that Y = M X for some X.) Prove that M Y = Y . (b) Suppose that v is a vector in Rn . Why is M v W ? (c) If Y W , why is v M v Y ? (d) Conclude that M v is the projection of v into W . 2. Compute the projection of the vector v = (1, 1, 0) onto the plane x + y z = 0. 3. Compute the projection matrix Q for the subspace W of R4 spanned by the vectors (1, 2, 0, 0) and (1, 0, 1, 1). 4. Compute the orthogonal projection of the vector z = (1, 2, 2, 2) onto the subspace W of Problem 3. above. What does your answer tell you about the relationship between the vector z and the subspace W ? 5. Recall that a square matrix P is said to be an orthogonal matrix if P T P = I. Show that Householder matrices are always orthogonal matrices; that is, show that H T H = I. 6. Compute the Householder matrix for reection across the plane x + y z = 0. 7. Compute the reection of the vector v = (1, 1, 0) across the plane x + y z = 0. What happens when you add v to its reection? How does this sum compare to your answer from Exercise 2? Draw a sketch to explain this phenomenon. 8. Compute the reection of the vector v = (1, 1) across the line in R2 spanned by the vector (2, 3). Sketch the vector v, the line and the reection of v across . (Do not confuse the spanning vector for with the normal vector to .) 9. Compute the Householder matrix H for reection across the hyperplane x1 + 2x2 x3 3x4 = 0 in R4 . Then compute the projection matrix Q for this hyperplane. 10. Compute the Householder matrix for reection across the plane z = 0 in R3 . Sketch the reection involved. Your answer should not be too surprising!
Selected Solutions to Exercises: 2. We describe two ways to solve this problem. Solution 1: Pick a basis for the plane. Since the plane is 2-dimensional, any two independent vectors in the plane will do, say, (1, 1, 0) and (0, 1, 1). Set 1 0 2 1 A = 1 1 and AT A = 1 2 0 1 The projection matrix Q for the plane is 1 0 2/3 1/3 Q = A(AT A)1 AT = 1 1 1/3 2/3 0 1
1 1 0 0 1 1
2/3 1/3 1/3 2/3 1/3 = 1/3 1/3 1/3 2/3
We can now project any vector onto the plane by multiplying by Q: 2/3 1/3 1/3 1 1/3 2/3 1/3 1 = 1/3 P rojection(v) = Qv = 1/3 1/3 1/3 2/3 0 2/3 Solution 2: First, project v onto the normal vector n = (1, 1, 1) to the plane: y = P rojn (v) = vn n = (2/3, 2/3, 2/3). nn
Since y is the component of v orthogonal to the plane, the vector v y is the orthogonal projection of v onto the plane. The solution (given in row vector notation) is v y = (1, 1, 0) (2/3, 2/3, 2/3) = (1/3, 1/3, 2/3), as in the previous solution. Note: Which method is better? The second way is shorter for hyperplanes (subspaces of
Rn having dimension n1), but nding the projection matrix Q is needed if you are projecting from Rn to some intermediate dimension k, where you no longer have a single normal vector to work with. For example, a 2-subspace in R4 has a 2-dimensional orthogonal complement as well, so one must compute a projection matrix in order to project to either component of R4 ,
as in the next problem. 4. Set 1 2 A= 0 0 1 0 1 1
so that AT A =
5 1 1 3
The projection matrix Q for the plane is 1 2 Q = A(AT A)1 AT = 0 0 1 0 1 1
3 14 1 14 1 14 5 14 6 14 4 14 4 14 4 14 4 14 12 14 2 14 2 14 4 14 2 14 5 14 5 14 4 14 2 14 5 14 5 14
1 2 0 0 1 0 1 1
5. Here is a hint: Use the fact that H = I 2uuT , where I is the identity matrix and u is a unit column vector. What is H T =? What is H T H =? 6. The vector v = (1, 1, 1) is normal to the plane x + y z = 0, so the vector u = 1 1 (1, 1, 1) = v is a unit normal. Expressing u and v as column vectors we nd that 3 3 2 I 2uuT = I (2/3)vv T = I 3 1 1 1 1 1 1 2 3
1 3 2 3 2 3 2 3 1 3
1 1 1 1 1 0 0 3 2 1 1 = 2 = 0 1 0 1 3 3 2 1 1 1 0 0 1
3
