Projection onto a Subspace, linear algebra I lesson

Two vectors span a plane in $\mathbb{R}^3$ , and a target vector $\mathbf{b}$ lies off the plane. Which point of the plane is closest to $\mathbf{b}$ ? Projecting $\mathbf{b}$ onto each spanning vector separately and adding the results looks natural, but when the spanning vectors are not perpendicular it generally gives the wrong point. This lesson finds the closest point by making the residual perpendicular to the whole plane, packages the answer as a projection matrix, and shows that the answer depends only on the subspace, not on the basis used to describe it. Throughout, a tuple such as $(1, 0, 1)$ stands for a column vector, and all vectors are real with the ordinary dot product.

Key terms

Orthogonal projection onto a subspace

Definition Let $W$ be a subspace of $\mathbb{R}^m$ and let $\mathbf{b}$ be a vector in $\mathbb{R}^m$ . The orthogonal projection of $\mathbf{b}$ onto $W$ is the unique vector $\mathbf{p} = \operatorname{proj}_W \mathbf{b}$ with

\mathbf{p} \in W \quad \text{and} \quad \mathbf{b} - \mathbf{p} \in W^{\perp}.

It exists and is unique because $\mathbb{R}^m = W \oplus W^{\perp}$ , so $\mathbf{p}$ is the $W$ part of the orthogonal decomposition $\mathbf{b} = \mathbf{p} + \mathbf{r}$ . The vector $\mathbf{r} = \mathbf{b} - \mathbf{p}$ is the residual. If $\mathbf{w}_1, \dots, \mathbf{w}_k$ span $W$ , the residual condition is $\mathbf{r} \cdot \mathbf{w}_i = 0$ for every $i$ . The projection onto the zero subspace is $\mathbf{0}$ . When $\mathbf{w}_1, \dots, \mathbf{w}_k$ is an orthogonal basis of $W$ , made of nonzero and mutually perpendicular vectors, the separate line projections add,

\operatorname{proj}_W \mathbf{b} = \sum_{i=1}^{k} \frac{\mathbf{w}_i \cdot \mathbf{b}}{\mathbf{w}_i \cdot \mathbf{w}_i}\,\mathbf{w}_i,

but for a basis that is not orthogonal this sum is in general not the projection.

In plain words Split $\mathbf{b}$ into a piece inside the subspace and a piece perpendicular to all of it. The inside piece is the projection.

Example Let $W$ be the plane spanned by $\mathbf{c}_1 = (1, 0, 1)$ and $\mathbf{c}_2 = (0, 1, 1)$ , which is the plane $z = x + y$ , and let $\mathbf{b} = (1, 1, 0)$ . Adding the two line projections gives $\tfrac12\mathbf{c}_1 + \tfrac12\mathbf{c}_2 = (\tfrac12, \tfrac12, 1)$ . This point lies in $W$ , but its residual $(\tfrac12, \tfrac12, -1)$ has dot product $-\tfrac12$ with $\mathbf{c}_1$ , so it is not perpendicular to the plane. The shortcut fails because $\mathbf{c}_1 \cdot \mathbf{c}_2 = 1 \ne 0$ . The true projection, computed in the next card, is $\mathbf{p} = (\tfrac13, \tfrac13, \tfrac23)$ , whose residual $(\tfrac23, \tfrac23, -\tfrac23)$ is perpendicular to both $\mathbf{c}_1$ and $\mathbf{c}_2$ .

Normal equations

Definition Let $C$ be a real $m \times k$ matrix with linearly independent columns $\mathbf{c}_1, \dots, \mathbf{c}_k$ , so that $W = \operatorname{Col} C$ has dimension $k$ , and let $\mathbf{b}$ be in $\mathbb{R}^m$ . Write the projection as $\mathbf{p} = C\hat{\mathbf{x}}$ with $\hat{\mathbf{x}}$ in $\mathbb{R}^k$ . The residual conditions $\mathbf{c}_i^{\top}(\mathbf{b} - C\hat{\mathbf{x}}) = 0$ for $i = 1, \dots, k$ stack into $C^{\top}(\mathbf{b} - C\hat{\mathbf{x}}) = \mathbf{0}$ , that is

C^{\top}C\,\hat{\mathbf{x}} = C^{\top}\mathbf{b}.

These are the normal equations, where normal means perpendicular and refers to the residual. The $k \times k$ matrix $C^{\top}C$ is invertible. Indeed, if $C^{\top}C\mathbf{v} = \mathbf{0}$ , then $0 = \mathbf{v}^{\top}C^{\top}C\mathbf{v} = \lVert C\mathbf{v} \rVert^2$ , so $C\mathbf{v} = \mathbf{0}$ , and independence of the columns forces $\mathbf{v} = \mathbf{0}$ . So the coordinate vector $\hat{\mathbf{x}}$ is unique, and the projection is the vector $\mathbf{p} = C\hat{\mathbf{x}}$ of $\mathbb{R}^m$ .

In plain words There is one equation per column, and each says that the residual is perpendicular to that column. Solving them gives the coordinates of the projection, and multiplying by $C$ gives the projection itself.

Example Let $C$ have columns $\mathbf{c}_1 = (1, 0, 1)$ and $\mathbf{c}_2 = (0, 1, 1)$ , and let $\mathbf{b} = (1, 1, 0)$ . Then

C^{\top}C = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}, \qquad C^{\top}\mathbf{b} = \begin{bmatrix} 1 \\ 1 \end{bmatrix}.

The equations $2\hat{x}_1 + \hat{x}_2 = 1$ and $\hat{x}_1 + 2\hat{x}_2 = 1$ give $\hat{x}_1 = \hat{x}_2 = \tfrac13$ , so

\begin{gathered} \mathbf{p} = \tfrac13\mathbf{c}_1 + \tfrac13\mathbf{c}_2 = \begin{bmatrix} 1/3 \\ 1/3 \\ 2/3 \end{bmatrix}, \\[0.4em] \mathbf{r} = \mathbf{b} - \mathbf{p} = \begin{bmatrix} 2/3 \\ 2/3 \\ -2/3 \end{bmatrix}. \end{gathered}

The residual passes both tests, since $\mathbf{r} \cdot \mathbf{c}_1 = \tfrac23 - \tfrac23 = 0$ and $\mathbf{r} \cdot \mathbf{c}_2 = \tfrac23 - \tfrac23 = 0$ .

Projection matrix

Definition For a real $m \times k$ matrix $C$ with linearly independent columns, the projection matrix onto $\operatorname{Col} C$ is the $m \times m$ matrix

P = C(C^{\top}C)^{-1}C^{\top},

and $\operatorname{proj}_{\operatorname{Col} C} \mathbf{b} = P\mathbf{b}$ for every $\mathbf{b}$ in $\mathbb{R}^m$ . The inverse is taken of the square $k \times k$ matrix $C^{\top}C$ , never of $C$ itself, which is not even square when $k < m$ . If the columns are orthonormal, then $C^{\top}C = I$ and the formula becomes $P = CC^{\top}$ . To project a single vector it is usually simpler to solve the normal equations than to form $P$ .

In plain words The matrix $P$ does the whole job at once. It takes any target in $\mathbb{R}^m$ and returns its projection onto the subspace.

Example For the same $C$ ,

(C^{\top}C)^{-1} = \frac{1}{3}\begin{bmatrix} 2 & -1 \\ -1 & 2 \end{bmatrix},

and multiplying out gives

P = \frac{1}{3}\begin{bmatrix} 2 & -1 & 1 \\ -1 & 2 & 1 \\ 1 & 1 & 2 \end{bmatrix}.

Then $P(1, 1, 0) = (\tfrac13, \tfrac13, \tfrac23)$ , as before. For the new target $(0, 0, 3)$ the same matrix gives $(1, 1, 2)$ , with residual $(-1, -1, 1)$ , which is the normal direction of the plane.

Idempotence

Definition A square matrix $P$ is idempotent if $P^2 = P$ . Every projection matrix $P = C(C^{\top}C)^{-1}C^{\top}$ is idempotent and symmetric. With $G = C^{\top}C$ ,

\begin{aligned} P^2 &= CG^{-1}(C^{\top}C)G^{-1}C^{\top} \\[0.4em] &= CG^{-1}C^{\top} = P, \end{aligned}

and $P^{\top} = C(G^{-1})^{\top}C^{\top} = P$ , because $G$ is symmetric and so is its inverse. Conversely, every real square matrix with $P^2 = P$ and $P^{\top} = P$ is the orthogonal projection onto its own column space. Idempotence alone is not enough. An idempotent matrix that is not symmetric projects along a slanted direction, and some of its residuals $\mathbf{b} - P\mathbf{b}$ are not perpendicular to $\operatorname{Col} P$ .

In plain words Projecting a second time changes nothing, because a vector already in the subspace is its own projection. Symmetry is what makes the projection perpendicular rather than slanted.

Example With $P$ from the previous card and $\mathbf{b} = (1, 1, 0)$ , the projection $\mathbf{p} = (\tfrac13, \tfrac13, \tfrac23)$ satisfies $P\mathbf{p} = \mathbf{p}$ , and the residual satisfies $P\mathbf{r} = \mathbf{0}$ . By contrast, the matrix

K = \begin{bmatrix} 1 & 1 \\ 0 & 0 \end{bmatrix}

has $K^2 = K$ and column space the $x$ -axis, but it sends $(0, 1)$ to $(1, 0)$ and leaves the residual $(-1, 1)$ , which is not perpendicular to the $x$ -axis. The closest point of the $x$ -axis to $(0, 1)$ is $(0, 0)$ , not $(1, 0)$ .

Closest vector in a subspace

Definition Let $W$ be a subspace of $\mathbb{R}^m$ , let $\mathbf{b}$ be in $\mathbb{R}^m$ , and let $\mathbf{p} = \operatorname{proj}_W \mathbf{b}$ with residual $\mathbf{r} = \mathbf{b} - \mathbf{p}$ . For every $\mathbf{y}$ in $W$ ,

\lVert \mathbf{b} - \mathbf{y} \rVert^2 = \lVert \mathbf{r} \rVert^2 + \lVert \mathbf{p} - \mathbf{y} \rVert^2.

Hence $\lVert \mathbf{b} - \mathbf{y} \rVert \ge \lVert \mathbf{b} - \mathbf{p} \rVert$ , with equality only for $\mathbf{y} = \mathbf{p}$ . So $\mathbf{p}$ is the unique vector of $W$ closest to $\mathbf{b}$ , and the distance from $\mathbf{b}$ to $W$ is $\lVert \mathbf{r} \rVert$ . The identity is the Pythagorean theorem. Write $\mathbf{b} - \mathbf{y} = \mathbf{r} + (\mathbf{p} - \mathbf{y})$ . Since $\mathbf{p} - \mathbf{y}$ lies in $W$ and $\mathbf{r}$ lies in $W^{\perp}$ , the cross term $2\,\mathbf{r} \cdot (\mathbf{p} - \mathbf{y})$ in the expansion is zero.

In plain words Moving away from $\mathbf{p}$ inside the subspace adds an error perpendicular to the residual, so every other candidate is farther from $\mathbf{b}$ .

Example For $\mathbf{b} = (1, 1, 0)$ and the plane $z = x + y$ , the squared distance is $\lVert \mathbf{r} \rVert^2 = \tfrac49 + \tfrac49 + \tfrac49 = \tfrac43$ , so the distance is $2/\sqrt{3}$ . The shortcut point $\mathbf{y} = (\tfrac12, \tfrac12, 1)$ has $\mathbf{p} - \mathbf{y} = (-\tfrac16, -\tfrac16, -\tfrac13)$ and $\lVert \mathbf{p} - \mathbf{y} \rVert^2 = \tfrac16$ , so its squared distance to $\mathbf{b}$ is $\tfrac43 + \tfrac16 = \tfrac32$ . A direct computation agrees, since $\mathbf{b} - \mathbf{y} = (\tfrac12, \tfrac12, -1)$ has squared length $\tfrac14 + \tfrac14 + 1 = \tfrac32$ .

Basis independence of a projection

Definition The projection $\operatorname{proj}_W \mathbf{b}$ depends only on the subspace $W$ and the dot product, not on the basis chosen for $W$ . If $C$ and $D$ are real $m \times k$ matrices with linearly independent columns and $\operatorname{Col} C = \operatorname{Col} D$ , then

C(C^{\top}C)^{-1}C^{\top} = D(D^{\top}D)^{-1}D^{\top}.

The reason is uniqueness. Both formulas return a vector of $W$ whose residual lies in $W^{\perp}$ , and there is only one such vector. The coordinates $\hat{\mathbf{x}}$ , by contrast, generally change with the basis. If the spanning list is dependent, then $C^{\top}C$ is singular and the formula cannot be used, yet the projection still exists and is unique, while its coordinates in that list are not. One remedy is to remove redundant columns first.

In plain words Different bases describe the same plane with different coordinates, but the closest point of the plane does not depend on how the plane is described.

Example Replace $\mathbf{c}_2$ by $\mathbf{c}_1 + \mathbf{c}_2 = (1, 1, 2)$ , so that $D$ has columns $(1, 0, 1)$ and $(1, 1, 2)$ and the same column space as $C$ . For $\mathbf{b} = (1, 1, 0)$ ,

D^{\top}D = \begin{bmatrix} 2 & 3 \\ 3 & 6 \end{bmatrix}, \qquad D^{\top}\mathbf{b} = \begin{bmatrix} 1 \\ 2 \end{bmatrix},

with solution $\hat{\mathbf{x}} = (0, \tfrac13)$ . The coordinates changed from $(\tfrac13, \tfrac13)$ , but $0 \cdot (1, 0, 1) + \tfrac13(1, 1, 2) = (\tfrac13, \tfrac13, \tfrac23)$ is the same $\mathbf{p}$ . With the dependent list $(1, 0, 1)$ , $(0, 1, 1)$ , $(1, 1, 2)$ , the coefficient vectors $(\tfrac13, \tfrac13, 0)$ and $(0, 0, \tfrac13)$ both produce this same $\mathbf{p}$ .

Check yourself

Project $\mathbf{b} = (2, 3, 1)$ onto the plane spanned by $\mathbf{w}_1 = (1, 0, 0)$ and $\mathbf{w}_2 = (0, 1, 1)$ , and find the distance from $\mathbf{b}$ to the plane.

Show the answer

The spanning vectors are perpendicular, since $\mathbf{w}_1 \cdot \mathbf{w}_2 = 0$ , so the line projections add. The coefficients are $\tfrac21 = 2$ and $\tfrac{3 + 1}{2} = 2$ , which gives $\mathbf{p} = 2\mathbf{w}_1 + 2\mathbf{w}_2 = (2, 2, 2)$ . The residual $(0, 1, -1)$ has zero dot product with both $\mathbf{w}_1$ and $\mathbf{w}_2$ , and the distance is its length $\sqrt{2}$ .

Let $C$ have columns $(1, 1, 0)$ and $(0, 1, 1)$ , and let $\mathbf{b} = (3, 0, 0)$ . Solve the normal equations, then find the projection of $\mathbf{b}$ onto $\operatorname{Col} C$ , the residual and the distance.

Show the answer

Here

C^{\top}C = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}, \qquad C^{\top}\mathbf{b} = \begin{bmatrix} 3 \\ 0 \end{bmatrix}.

The equations $2\hat{x}_1 + \hat{x}_2 = 3$ and $\hat{x}_1 + 2\hat{x}_2 = 0$ give $\hat{x}_1 = 2$ and $\hat{x}_2 = -1$ . So $\mathbf{p} = 2(1, 1, 0) - (0, 1, 1) = (2, 1, -1)$ and $\mathbf{r} = (1, -1, 1)$ . The residual is perpendicular to both columns, since $1 - 1 + 0 = 0$ and $0 - 1 + 1 = 0$ , and the distance is $\sqrt{3}$ . Adding the separate line projections would give $(\tfrac32, \tfrac32, 0)$ , at squared distance $\tfrac92$ from $\mathbf{b}$ instead of $3$ .

Both matrices below satisfy $M^2 = M$ , and both have the line spanned by $(1, 1)$ as column space. Which one is the orthogonal projection onto that line?

P = \frac{1}{2}\begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix}, \qquad E = \begin{bmatrix} 1 & 0 \\ 1 & 0 \end{bmatrix}

Show the answer

Idempotence cannot decide, since both matrices have it. The matrix $P$ is symmetric and equals $\mathbf{a}\mathbf{a}^{\top}/(\mathbf{a}^{\top}\mathbf{a})$ for $\mathbf{a} = (1, 1)$ , so it is the orthogonal projection. The matrix $E$ is not symmetric, and it fails the residual test. It sends $(1, 0)$ to $(1, 1)$ , leaving the residual $(0, -1)$ , whose dot product with $(1, 1)$ is $-1$ . The matrix $P$ sends $(1, 0)$ to $(\tfrac12, \tfrac12)$ , leaving $(\tfrac12, -\tfrac12)$ , which is perpendicular to the line. That point is at distance $1/\sqrt{2}$ from $(1, 0)$ , closer than the distance $1$ to the point $(1, 1)$ chosen by $E$ .

Projection onto a Subspace

Key terms

Orthogonal projection onto a subspace

Normal equations

Projection matrix

Idempotence

Closest vector in a subspace

Basis independence of a projection

Check yourself

How this lesson connects

Builds on

Used later in