MAT 102 Linear Algebra · DSE · Intake 2/1 · Dr. Ronobir Chandra Sarker

Orthogonality — Part 2: Projections

Lecture notes on section 4.2 of Strang, Introduction to Linear Algebra. Read with pen and paper beside you, work each example yourself before reading its solution, and do every exercise before opening the answer.

The chapter in three parts: Part 1 · Orthogonal vectors and subspaces  |  Part 2 · Projections  |  Part 3 · Least squares and orthonormal bases

⬇ Download Part 2 as PDF 🎯 Practice page
Contents
  1. Before you start
  2. Projection onto a line
  3. Projection onto a subspace
  4. Question types and model answers
  5. Practice test
  6. Formula sheet

0Before you start

Why we study this

Given a line or a plane through the origin and a point \(\vb b\) outside it, which point of the line or plane is nearest to \(\vb b\)? The answer is the projection of \(\vb b\). A GPS receiver, a robot arm and a photo editor all solve this problem constantly, and so does every statistician: the least-squares fit of Part 3 is a projection. The whole of this part follows from one sentence: the error from \(\vb b\) to its projection is perpendicular to the subspace.

What you need

Notation

SymbolMeaning
\(\vb a\), \(A = [\,\vb a_1\ \ \vb a_2\,]\)the direction of the line; the matrix whose columns span the plane
\(\hat x\), \(\hat{\vb x}\)the number (or vector of numbers) of coefficients chosen by the projection
\(\vb p\)the projection: the closest point, \(\vb p = \hat x\,\vb a\) or \(\vb p = A\hat{\vb x}\)
\(\vb e\)the error \(\vb e = \vb b - \vb p\), perpendicular to the line or plane
\(P\)a projection matrix: \(\vb p = P\vb b\)
\(\vb a\T\vb a\) and \(\vb a\,\vb a\T\)a number (row times column) and an \(n \times n\) matrix (column times row)

1Projection onto a line (4.2)

At noon the shadow of a vertical pole falls directly below its tip: the shadow is the point of the ground closest to the tip, and the line from the shadow to the tip is perpendicular to the ground. Projection is exactly this idea. The closest point is found by making the error perpendicular, and the rest of the chapter uses this one picture again and again.

The problem. A line passes through the origin in the direction of a vector \(\vb a\). Given a vector \(\vb b\), which point \(\vb p\) on the line is closest to \(\vb b\)?

Figure 1.1 — projection onto a line. \(\vb p = \hat x\,\vb a\) is the point of the line closest to \(\vb b\); the error \(\vb e = \vb b - \vb p\) meets the line at a right angle. The three vectors \(\vb p\), \(\vb e\), \(\vb b\) form a right triangle, so \(\nrm{\vb p}^2 + \nrm{\vb e}^2 = \nrm{\vb b}^2\).

Setting up. The point \(\vb p\) lies on the line, so it is a multiple of \(\vb a\): write \(\vb p = \hat x\,\vb a\), where the number \(\hat x\) is what we must find. The error is \(\vb e = \vb b - \vb p\). The closest point is reached by dropping a perpendicular from \(\vb b\) onto the line, so the error must be perpendicular to \(\vb a\). That single condition determines \(\hat x\).

Derivation of \(\hat x\). \[ \begin{aligned} \vb a\T\vb e &= 0 && \text{(the error is perpendicular to } \vb a\text{)} \\ \vb a\T(\vb b - \hat x\,\vb a) &= 0 && (\vb e = \vb b - \vb p \text{ and } \vb p = \hat x\,\vb a) \\ \vb a\T\vb b - \hat x\,(\vb a\T\vb a) &= 0 && (\text{multiply out; } \hat x \text{ is a number, so it can be moved in front}) \\ \hat x\,(\vb a\T\vb a) &= \vb a\T\vb b && (\text{move the second term across}) \\ \hat x &= \frac{\vb a\T\vb b}{\vb a\T\vb a} && (\text{divide by } \vb a\T\vb a = \nrm{\vb a}^2, \text{ which is not } 0 \text{ because } \vb a \ne \vb 0) \end{aligned} \]
Projection onto the line through \(\vb a\). \[ \begin{aligned} \hat x &= \frac{\vb a\T\vb b}{\vb a\T\vb a} && \text{(a number)} \\ \vb p &= \hat x\,\vb a && \text{(the projection: the closest point on the line)} \\ \vb e &= \vb b - \vb p && \text{(the error, with } \vb e\T\vb a = 0\text{)} \end{aligned} \]
Method 1.1 (four steps).
  1. Compute the two dot products \(\vb a\T\vb b\) and \(\vb a\T\vb a\).
  2. Compute the number \(\hat x = \vb a\T\vb b \,/\, \vb a\T\vb a\). Keep it as a fraction.
  3. Compute \(\vb p = \hat x\,\vb a\): multiply every entry of \(\vb a\) by \(\hat x\).
  4. Compute \(\vb e = \vb b - \vb p\) and check that \(\vb e\T\vb a = 0\).

Example 1.1 (book). Project \(\vb b = (1, 1, 1)\) onto the line through \(\vb a = (1, 2, 2)\).

  1. \(\vb a\T\vb b = 1\cdot 1 + 2\cdot 1 + 2\cdot 1 = 5\) and \(\vb a\T\vb a = 1 + 4 + 4 = 9\).
  2. \(\hat x = \dfrac{5}{9}\).
  3. \(\vb p = \dfrac{5}{9}\begin{bmatrix} 1 \\ 2 \\ 2 \end{bmatrix} = \begin{bmatrix} 5/9 \\ 10/9 \\ 10/9 \end{bmatrix}\).
  4. \(\vb e = \vb b - \vb p = \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} - \begin{bmatrix} 5/9 \\ 10/9 \\ 10/9 \end{bmatrix} = \begin{bmatrix} 4/9 \\ -1/9 \\ -1/9 \end{bmatrix}\). Check: \(\vb e\T\vb a = \dfrac{4}{9} - \dfrac{2}{9} - \dfrac{2}{9} = 0\). \(\checkmark\)

A second check with Pythagoras: \(\nrm{\vb p}^2 = \dfrac{25 + 100 + 100}{81} = \dfrac{25}{9}\), \(\nrm{\vb e}^2 = \dfrac{16 + 1 + 1}{81} = \dfrac{2}{9}\), and \(\dfrac{25}{9} + \dfrac{2}{9} = 3 = \nrm{\vb b}^2\). \(\checkmark\)

Example 1.2 (book, worked example 4.2A). Project \(\vb b = (3, 4, 4)\) onto the line through \(\vb a = (2, 2, 1)\).

  1. \(\vb a\T\vb b = 2\cdot 3 + 2\cdot 4 + 1\cdot 4 = 6 + 8 + 4 = 18\) and \(\vb a\T\vb a = 4 + 4 + 1 = 9\).
  2. \(\hat x = \dfrac{18}{9} = 2\).
  3. \(\vb p = 2\begin{bmatrix} 2 \\ 2 \\ 1 \end{bmatrix} = \begin{bmatrix} 4 \\ 4 \\ 2 \end{bmatrix}\).
  4. \(\vb e = \begin{bmatrix} 3 \\ 4 \\ 4 \end{bmatrix} - \begin{bmatrix} 4 \\ 4 \\ 2 \end{bmatrix} = \begin{bmatrix} -1 \\ 0 \\ 2 \end{bmatrix}\). Check: \(\vb e\T\vb a = -2 + 0 + 2 = 0\). \(\checkmark\)

Pythagoras: \(\nrm{\vb p}^2 + \nrm{\vb e}^2 = 36 + 5 = 41 = 9 + 16 + 16 = \nrm{\vb b}^2\). \(\checkmark\)

Example 1.3 (book, problem 1b). Project \(\vb b = (1, 3, 1)\) onto the line through \(\vb a = (-1, -3, -1)\).

  1. \(\vb a\T\vb b = -1 - 9 - 1 = -11\) and \(\vb a\T\vb a = 1 + 9 + 1 = 11\).
  2. \(\hat x = \dfrac{-11}{11} = -1\).
  3. \(\vb p = -1\begin{bmatrix} -1 \\ -3 \\ -1 \end{bmatrix} = \begin{bmatrix} 1 \\ 3 \\ 1 \end{bmatrix} = \vb b\).
  4. \(\vb e = \vb b - \vb p = \vb 0\). The check \(\vb e\T\vb a = 0\) is automatic.

The vector \(\vb b\) was already on the line (\(\vb b = -\vb a\)), so its closest point is itself.

Two special cases.

In every case \(\vb p\), \(\vb e\), \(\vb b\) form a right triangle, so \(\nrm{\vb p}^2 + \nrm{\vb e}^2 = \nrm{\vb b}^2\) and \(\vb p\) is never longer than \(\vb b\).

The projection matrix

Projection is a linear operation, so some matrix \(P\) must produce it: \(\vb p = P\vb b\). To find \(P\), write the number \(\hat x\) on the right of \(\vb a\) and regroup:

\[ \vb p = \vb a\,\hat x = \vb a\,\frac{\vb a\T\vb b}{\vb a\T\vb a} = \frac{\vb a\,\vb a\T}{\vb a\T\vb a}\,\vb b = P\vb b. \]
Projection matrix onto the line through \(\vb a\). \[ P = \frac{\vb a\,\vb a\T}{\vb a\T\vb a} \qquad (\text{an } n \times n \text{ matrix: a column times a row, divided by a number}). \]

Note the difference: \(\vb a\T\vb a\) is a row times a column, a number. \(\vb a\,\vb a\T\) is a column times a row, an \(n \times n\) matrix whose \((i, j)\) entry is \(a_i a_j\).

Example 1.4. Find the projection matrix onto the line through \(\vb a = (1, 2, 2)\), and use it to recover Example 1.1.

\[ P = \frac{1}{9}\begin{bmatrix} 1 \\ 2 \\ 2 \end{bmatrix}\begin{bmatrix} 1 & 2 & 2 \end{bmatrix} = \frac{1}{9}\begin{bmatrix} 1 & 2 & 2 \\ 2 & 4 & 4 \\ 2 & 4 & 4 \end{bmatrix} \] \[ P\vb b = \frac{1}{9}\begin{bmatrix} 1 & 2 & 2 \\ 2 & 4 & 4 \\ 2 & 4 & 4 \end{bmatrix}\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} = \frac{1}{9}\begin{bmatrix} 5 \\ 10 \\ 10 \end{bmatrix} = \vb p \quad\checkmark \]
Theorem 1.2 (properties of \(P\)). The projection matrix \(P = \vb a\,\vb a\T / \vb a\T\vb a\) satisfies \[ P\T = P, \qquad P^2 = P, \qquad \operatorname{rank} P = 1. \]
Proof. \(P\T = (\vb a\,\vb a\T)\T / \vb a\T\vb a = \vb a\,\vb a\T / \vb a\T\vb a = P\). For \(P^2\), regroup the middle factor, which is the number \(\vb a\T\vb a\): \[ P^2 = \frac{\vb a\,(\vb a\T\vb a)\,\vb a\T}{(\vb a\T\vb a)^2} = \frac{\vb a\,\vb a\T}{\vb a\T\vb a} = P. \] Every column of \(P\) is a multiple of \(\vb a\), so the rank is \(1\). ∎

The meaning of \(P^2 = P\): projecting a second time changes nothing, because \(\vb p\) is already on the line.

Exercise 1.

  1. Project \(\vb b = (2, 2, 2)\) onto the line through \(\vb a = (1, 0, 1)\). Give \(\hat x\), \(\vb p\), \(\vb e\) and the check.
  2. Write the projection matrix for that line and verify that \(P\vb b = \vb p\).
Show answer
Answer
  1. \(\vb a\T\vb b = 2 + 0 + 2 = 4\), \(\vb a\T\vb a = 1 + 0 + 1 = 2\), so \(\hat x = 4/2 = 2\). \(\vb p = 2(1, 0, 1) = (2, 0, 2)\). \(\vb e = (2,2,2) - (2,0,2) = (0, 2, 0)\). Check: \(\vb e\T\vb a = 0 + 0 + 0 = 0\). \(\checkmark\)
  2. \(\vb a\,\vb a\T = \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix}\begin{bmatrix} 1 & 0 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 0 & 1 \\ 0 & 0 & 0 \\ 1 & 0 & 1 \end{bmatrix}\) and \(\vb a\T\vb a = 2\), so \(P = \dfrac12\begin{bmatrix} 1 & 0 & 1 \\ 0 & 0 & 0 \\ 1 & 0 & 1 \end{bmatrix}\). Then \(P\vb b = \dfrac12(2 + 0 + 2,\ 0,\ 2 + 0 + 2) = (2, 0, 2) = \vb p\). \(\checkmark\)

2Projection onto a subspace (4.2)

Now the “ground” is a plane through the origin, spanned by two vectors \(\vb a_1\) and \(\vb a_2\). The closest point to \(\vb b\) is a combination \(\vb p = \hat x_1\vb a_1 + \hat x_2\vb a_2\), so there are two numbers to find instead of one. The idea is unchanged: the error must be perpendicular to the plane, which means perpendicular to both \(\vb a_1\) and \(\vb a_2\). Two conditions, two unknowns.

Figure 2.1 — projection onto a plane. The plane is the column space of \(A = [\,\vb a_1\ \ \vb a_2\,]\). The projection \(\vb p = \hat x_1\vb a_1 + \hat x_2\vb a_2\) lies in the plane (dashed parallelogram); the error \(\vb e = \vb b - \vb p\) stands on the plane at a right angle, so it is orthogonal to \(\vb a_1\) and to \(\vb a_2\).

Setting up. Put \(\vb a_1, \vb a_2\) as the columns of a matrix \(A\) (\(m \times 2\)). The plane is the column space \(\mathbf C(A)\), and a point of it is \(A\vb x = x_1\vb a_1 + x_2\vb a_2\). We look for \(\hat{\vb x} = (\hat x_1, \hat x_2)\) such that \(\vb p = A\hat{\vb x}\) is closest to \(\vb b\).

Derivation of the normal equations. \[ \begin{aligned} \vb a_1\T\vb e = 0 \quad\text{and}\quad \vb a_2\T\vb e &= 0 && (\vb e \text{ is perpendicular to both columns}) \\ A\T\vb e &= \vb 0 && (\text{both equations at once; see below}) \\ A\T(\vb b - A\hat{\vb x}) &= \vb 0 && (\vb e = \vb b - A\hat{\vb x}) \\ A\T\vb b - A\T A\,\hat{\vb x} &= \vb 0 && \text{(multiply out)} \\ A\T A\,\hat{\vb x} &= A\T\vb b && \text{(the normal equations)} \end{aligned} \]

The second line is the first line written as one matrix equation: the rows of \(A\T\) are \(\vb a_1\T\) and \(\vb a_2\T\), so \(A\T\vb e = \vb 0\) says exactly that \(\vb e\) is perpendicular to both columns.

Projection onto the column space of \(A\). \[ \begin{aligned} A\T A\,\hat{\vb x} &= A\T\vb b && \text{(solve this small system for } \hat{\vb x}\text{)} \\ \vb p &= A\hat{\vb x} = \hat x_1\vb a_1 + \hat x_2\vb a_2 && \text{(the projection)} \\ \vb e &= \vb b - \vb p && \text{(the error, with } A\T\vb e = \vb 0\text{)} \end{aligned} \]

Compare with a line. There \(A\T A\) was the single number \(\vb a\T\vb a\) and \(A\T\vb b\) the single number \(\vb a\T\vb b\). Now \(A\T A\) is a \(2 \times 2\) matrix holding the dot products of the columns with each other, and \(A\T\vb b\) is a \(2 \times 1\) vector holding the dot products of the columns with \(\vb b\).

Method 2.1.
  1. Compute \(A\T A\) (\(2 \times 2\)) and \(A\T\vb b\) (\(2 \times 1\)).
  2. Solve \(A\T A\hat{\vb x} = A\T\vb b\) by Gaussian elimination on the augmented matrix \([\,A\T A \mid A\T\vb b\,]\), then back substitution.
  3. Compute \(\vb p = A\hat{\vb x} = \hat x_1\vb a_1 + \hat x_2\vb a_2\).
  4. Compute \(\vb e = \vb b - \vb p\) and check \(\vb a_1\T\vb e = 0\) and \(\vb a_2\T\vb e = 0\).

Example 2.1 (book, Example 3). Project \(\vb b = \begin{bmatrix} 6 \\ 0 \\ 0 \end{bmatrix}\) onto the column space of \(A = \begin{bmatrix} 1 & 0 \\ 1 & 1 \\ 1 & 2 \end{bmatrix}\).

  1. \(A\T A = \begin{bmatrix} 1 & 1 & 1 \\ 0 & 1 & 2 \end{bmatrix}\begin{bmatrix} 1 & 0 \\ 1 & 1 \\ 1 & 2 \end{bmatrix} = \begin{bmatrix} 3 & 3 \\ 3 & 5 \end{bmatrix}\) and \(A\T\vb b = \begin{bmatrix} 6 + 0 + 0 \\ 0 + 0 + 0 \end{bmatrix} = \begin{bmatrix} 6 \\ 0 \end{bmatrix}\).
  2. Elimination and back substitution: \[ \left[\begin{array}{cc|c} 3 & 3 & 6 \\ 3 & 5 & 0 \end{array}\right] \xrightarrow{\ R_2 - R_1\ } \left[\begin{array}{cc|c} 3 & 3 & 6 \\ 0 & 2 & -6 \end{array}\right] \qquad \begin{aligned} 2\hat x_2 &= -6 &&\Rightarrow\ \hat x_2 = -3 \\ 3\hat x_1 + 3(-3) &= 6 &&\Rightarrow\ \hat x_1 = 5 \end{aligned} \]
  3. \(\vb p = 5\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} - 3\begin{bmatrix} 0 \\ 1 \\ 2 \end{bmatrix} = \begin{bmatrix} 5 \\ 2 \\ -1 \end{bmatrix}\).
  4. \(\vb e = \vb b - \vb p = \begin{bmatrix} 6 \\ 0 \\ 0 \end{bmatrix} - \begin{bmatrix} 5 \\ 2 \\ -1 \end{bmatrix} = \begin{bmatrix} 1 \\ -2 \\ 1 \end{bmatrix}\). Checks: \((1,1,1)\cdot\vb e = 1 - 2 + 1 = 0\) and \((0,1,2)\cdot\vb e = 0 - 2 + 2 = 0\). \(\checkmark\)

Example 2.2 (book, Problem 12a). Project \(\vb b = (2, 3, 4)\) onto the column space of \(A = \begin{bmatrix} 1 & 1 \\ 0 & 1 \\ 0 & 0 \end{bmatrix}\).

  1. \(A\T A = \begin{bmatrix} 1 & 1 \\ 1 & 2 \end{bmatrix}\) and \(A\T\vb b = \begin{bmatrix} 2 \\ 2 + 3 \end{bmatrix} = \begin{bmatrix} 2 \\ 5 \end{bmatrix}\).
  2. \(\left[\begin{array}{cc|c} 1 & 1 & 2 \\ 1 & 2 & 5 \end{array}\right] \xrightarrow{\ R_2 - R_1\ } \left[\begin{array}{cc|c} 1 & 1 & 2 \\ 0 & 1 & 3 \end{array}\right]\), so \(\hat x_2 = 3\) and \(\hat x_1 = 2 - 3 = -1\).
  3. \(\vb p = -1\begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix} + 3\begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix} = \begin{bmatrix} 2 \\ 3 \\ 0 \end{bmatrix}\).
  4. \(\vb e = (2, 3, 4) - (2, 3, 0) = (0, 0, 4)\). Checks: \((1,0,0)\cdot\vb e = 0\) and \((1,1,0)\cdot\vb e = 0\). \(\checkmark\)

The column space is the \(xy\)-plane, so the projection simply drops the third coordinate, as the shadow picture predicts.

Example 2.3 (book, Problem 12b). Project \(\vb b = (4, 4, 6)\) onto the column space of \(A = \begin{bmatrix} 1 & 1 \\ 1 & 1 \\ 0 & 1 \end{bmatrix}\).

  1. \(A\T A = \begin{bmatrix} 2 & 2 \\ 2 & 3 \end{bmatrix}\) and \(A\T\vb b = \begin{bmatrix} 4 + 4 \\ 4 + 4 + 6 \end{bmatrix} = \begin{bmatrix} 8 \\ 14 \end{bmatrix}\).
  2. \(\left[\begin{array}{cc|c} 2 & 2 & 8 \\ 2 & 3 & 14 \end{array}\right] \xrightarrow{\ R_2 - R_1\ } \left[\begin{array}{cc|c} 2 & 2 & 8 \\ 0 & 1 & 6 \end{array}\right]\), so \(\hat x_2 = 6\) and \(2\hat x_1 + 2(6) = 8\), \(\hat x_1 = -2\).
  3. \(\vb p = -2\begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix} + 6\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} = \begin{bmatrix} 4 \\ 4 \\ 6 \end{bmatrix} = \vb b\).
  4. \(\vb e = \vb 0\).

This \(\vb b\) was already in the column space, so the projection is \(\vb b\) itself and \(A\vb x = \vb b\) is solvable exactly, with \(\vb x = (-2, 6)\).

Remark (solving the small system). The multiplier in the elimination step is (entry below the pivot) \(\div\) (pivot). In Example 2.1 it is \(3 \div 3 = 1\), so we subtract row 1 once. If row 2 began with \(8\) and the pivot were \(4\), we would subtract \(2\) times row 1. After the step, read \(\hat x_2\) from row 2 and substitute it into row 1 to get \(\hat x_1\). Finally put both numbers back into the original two equations as a check.

The projection matrix

Projection matrix onto \(\mathbf C(A)\). Solving the normal equations in symbols, \[ \begin{aligned} \hat{\vb x} &= (A\T A)^{-1}A\T\vb b \\ \vb p &= A\hat{\vb x} = A(A\T A)^{-1}A\T\vb b \\ P &= A(A\T A)^{-1}A\T \qquad \text{with } P\T = P \text{ and } P^2 = P. \end{aligned} \]

For the \(2 \times 2\) inverse we use the formula from Chapter 2: \[ \begin{bmatrix} a & b \\ c & d \end{bmatrix}^{-1} = \frac{1}{ad - bc}\begin{bmatrix} d & -b \\ -c & a \end{bmatrix}. \] Swap the diagonal entries, change the signs of the other two, and divide by the determinant \(ad - bc\).

Example 2.4. Find the projection matrix onto the column space of \(A = \begin{bmatrix} 1 & 0 \\ 1 & 1 \\ 1 & 2 \end{bmatrix}\) (Example 2.1) and check it on \(\vb b = (6, 0, 0)\).

\[ (A\T A)^{-1} = \begin{bmatrix} 3 & 3 \\ 3 & 5 \end{bmatrix}^{-1} = \frac{1}{15 - 9}\begin{bmatrix} 5 & -3 \\ -3 & 3 \end{bmatrix} = \frac{1}{6}\begin{bmatrix} 5 & -3 \\ -3 & 3 \end{bmatrix} \] \[ A(A\T A)^{-1} = \frac16\begin{bmatrix} 1 & 0 \\ 1 & 1 \\ 1 & 2 \end{bmatrix}\begin{bmatrix} 5 & -3 \\ -3 & 3 \end{bmatrix} = \frac16\begin{bmatrix} 5 & -3 \\ 2 & 0 \\ -1 & 3 \end{bmatrix} \] \[ P = A(A\T A)^{-1}A\T = \frac16\begin{bmatrix} 5 & -3 \\ 2 & 0 \\ -1 & 3 \end{bmatrix}\begin{bmatrix} 1 & 1 & 1 \\ 0 & 1 & 2 \end{bmatrix} = \frac16\begin{bmatrix} 5 & 2 & -1 \\ 2 & 2 & 2 \\ -1 & 2 & 5 \end{bmatrix} \] \[ P\vb b = \frac16\begin{bmatrix} 30 \\ 12 \\ -6 \end{bmatrix} = \begin{bmatrix} 5 \\ 2 \\ -1 \end{bmatrix} = \vb p \quad\checkmark \] \(P\) is symmetric, as it must be.
Theorem 2.2. \(A\T A\) is invertible exactly when the columns of \(A\) are independent.
Proof. \(A\T A\) has the same nullspace as \(A\). If \(A\vb x = \vb 0\) then certainly \(A\T A\vb x = \vb 0\). Conversely, if \(A\T A\vb x = \vb 0\), multiply by \(\vb x\T\): \(\vb x\T A\T A\vb x = \nrm{A\vb x}^2 = 0\), so \(A\vb x = \vb 0\). Independent columns mean the nullspace of \(A\) is \(\{\vb 0\}\); then the nullspace of the square matrix \(A\T A\) is \(\{\vb 0\}\), so \(A\T A\) is invertible. ∎

Two special cases.

Exercise 2. Project \(\vb b = (1, 1, 7)\) onto the column space of \(A = \begin{bmatrix} 1 & 0 \\ 1 & 1 \\ 1 & 2 \end{bmatrix}\). Give \(\hat{\vb x}\), \(\vb p\), \(\vb e\) and the two checks.

Show answer
Answer
  1. \(A\T A = \begin{bmatrix} 3 & 3 \\ 3 & 5 \end{bmatrix}\) (as in Example 2.1) and \(A\T\vb b = \begin{bmatrix} 1 + 1 + 7 \\ 0 + 1 + 14 \end{bmatrix} = \begin{bmatrix} 9 \\ 15 \end{bmatrix}\).
  2. \(\left[\begin{array}{cc|c} 3 & 3 & 9 \\ 3 & 5 & 15 \end{array}\right] \xrightarrow{\ R_2 - R_1\ } \left[\begin{array}{cc|c} 3 & 3 & 9 \\ 0 & 2 & 6 \end{array}\right]\), so \(\hat x_2 = 3\) and \(3\hat x_1 + 3(3) = 9\), \(\hat x_1 = 0\). \(\hat{\vb x} = (0, 3)\).
  3. \(\vb p = 0\,(1,1,1) + 3\,(0,1,2) = (0, 3, 6)\).
  4. \(\vb e = (1,1,7) - (0,3,6) = (1, -2, 1)\). Checks: \((1,1,1)\cdot\vb e = 1 - 2 + 1 = 0\) and \((0,1,2)\cdot\vb e = 0 - 2 + 2 = 0\). \(\checkmark\)

3Question types and model answers

Almost every question on this part is one of the three types below. Each model answer is written out the way I expect to see it on paper: the formula first, then the numbers, the arithmetic, the check, and a one-line conclusion.

Type 1 — Projection onto a line, and the matrix \(P\)

Question. Project \(\vb b = (3, 4, 4)\) onto the line through \(\vb a = (2, 2, 1)\). Find the projection matrix and verify \(P^2 = P\).

\[ \begin{aligned} \vb a\T\vb b &= 2\cdot 3 + 2\cdot 4 + 1\cdot 4 = 18, \qquad \vb a\T\vb a = 4 + 4 + 1 = 9 \\ \hat x &= \frac{\vb a\T\vb b}{\vb a\T\vb a} = \frac{18}{9} = 2 \\ \vb p &= \hat x\,\vb a = 2\begin{bmatrix} 2 \\ 2 \\ 1 \end{bmatrix} = \begin{bmatrix} 4 \\ 4 \\ 2 \end{bmatrix} \\ \vb e &= \vb b - \vb p = \begin{bmatrix} 3 \\ 4 \\ 4 \end{bmatrix} - \begin{bmatrix} 4 \\ 4 \\ 2 \end{bmatrix} = \begin{bmatrix} -1 \\ 0 \\ 2 \end{bmatrix}, \qquad \text{check: } \vb e\T\vb a = -2 + 0 + 2 = 0 \ \checkmark \\ P &= \frac{\vb a\,\vb a\T}{\vb a\T\vb a} = \frac19\begin{bmatrix} 4 & 4 & 2 \\ 4 & 4 & 2 \\ 2 & 2 & 1 \end{bmatrix} \\ P^2 &= \frac{1}{81}\begin{bmatrix} 36 & 36 & 18 \\ 36 & 36 & 18 \\ 18 & 18 & 9 \end{bmatrix} = \frac19\begin{bmatrix} 4 & 4 & 2 \\ 4 & 4 & 2 \\ 2 & 2 & 1 \end{bmatrix} = P \ \checkmark \end{aligned} \]

Type 2 — Projection onto a column space (normal equations)

Question. Project \(\vb b = (6, 0, 0)\) onto the column space of \(A = \begin{bmatrix} 1 & 0 \\ 1 & 1 \\ 1 & 2 \end{bmatrix}\).

\[ \begin{aligned} A\T A &= \begin{bmatrix} 3 & 3 \\ 3 & 5 \end{bmatrix}, \qquad A\T\vb b = \begin{bmatrix} 6 \\ 0 \end{bmatrix} \\ \left[\begin{array}{cc|c} 3 & 3 & 6 \\ 3 & 5 & 0 \end{array}\right] &\xrightarrow{\ R_2 - R_1\ } \left[\begin{array}{cc|c} 3 & 3 & 6 \\ 0 & 2 & -6 \end{array}\right] \\ 2\hat x_2 &= -6 \ \Rightarrow\ \hat x_2 = -3, \qquad 3\hat x_1 + 3(-3) = 6 \ \Rightarrow\ \hat x_1 = 5 \\ \vb p &= A\hat{\vb x} = 5\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} - 3\begin{bmatrix} 0 \\ 1 \\ 2 \end{bmatrix} = \begin{bmatrix} 5 \\ 2 \\ -1 \end{bmatrix} \\ \vb e &= \vb b - \vb p = \begin{bmatrix} 1 \\ -2 \\ 1 \end{bmatrix} \\ \text{checks: } (1,1,1)\cdot\vb e &= 1 - 2 + 1 = 0, \qquad (0,1,2)\cdot\vb e = 0 - 2 + 2 = 0 \ \checkmark \end{aligned} \]

Type 3 — The projection matrix onto a column space

Question. Find the projection matrix onto the column space of \(A = \begin{bmatrix} 1 & 0 \\ 1 & 1 \\ 1 & 2 \end{bmatrix}\), and check it on \(\vb b = (6, 0, 0)\).

\[ \begin{aligned} A\T A &= \begin{bmatrix} 3 & 3 \\ 3 & 5 \end{bmatrix}, \qquad (A\T A)^{-1} = \frac{1}{15 - 9}\begin{bmatrix} 5 & -3 \\ -3 & 3 \end{bmatrix} = \frac16\begin{bmatrix} 5 & -3 \\ -3 & 3 \end{bmatrix} \\ A(A\T A)^{-1} &= \frac16\begin{bmatrix} 1 & 0 \\ 1 & 1 \\ 1 & 2 \end{bmatrix}\begin{bmatrix} 5 & -3 \\ -3 & 3 \end{bmatrix} = \frac16\begin{bmatrix} 5 & -3 \\ 2 & 0 \\ -1 & 3 \end{bmatrix} \\ P &= A(A\T A)^{-1}A\T = \frac16\begin{bmatrix} 5 & -3 \\ 2 & 0 \\ -1 & 3 \end{bmatrix}\begin{bmatrix} 1 & 1 & 1 \\ 0 & 1 & 2 \end{bmatrix} = \frac16\begin{bmatrix} 5 & 2 & -1 \\ 2 & 2 & 2 \\ -1 & 2 & 5 \end{bmatrix} \\ P\vb b &= \frac16\begin{bmatrix} 30 \\ 12 \\ -6 \end{bmatrix} = \begin{bmatrix} 5 \\ 2 \\ -1 \end{bmatrix} = \vb p \ \checkmark \qquad (P \text{ is symmetric, as it must be}) \end{aligned} \]

4Practice test

Six questions, about fifty minutes of work. Write full answers on paper first and open each answer only afterwards. Question 6 is theory.

Q1. Project \(\vb b = (1, 2, 3)\) onto the line through \(\vb a = (1, 1, 1)\). Give \(\hat x\), \(\vb p\), \(\vb e\) and the check.

Show answer
Answer
\(\vb a\T\vb b = 1 + 2 + 3 = 6\), \(\vb a\T\vb a = 1 + 1 + 1 = 3\), so \(\hat x = 6/3 = 2\).
\(\vb p = \hat x\,\vb a = 2(1,1,1) = (2, 2, 2)\).
\(\vb e = \vb b - \vb p = (1,2,3) - (2,2,2) = (-1, 0, 1)\).
Check: \(\vb e\T\vb a = -1 + 0 + 1 = 0\). \(\checkmark\)   Also \(\nrm{\vb p}^2 + \nrm{\vb e}^2 = 12 + 2 = 14 = \nrm{\vb b}^2\).

Q2. Project \(\vb b = (1, 0, 0)\) onto the line through \(\vb a = (1, 1, 1)\). Give \(\hat x\), \(\vb p\), \(\vb e\) and the check.

Show answer
Answer
\(\vb a\T\vb b = 1 + 0 + 0 = 1\), \(\vb a\T\vb a = 3\), so \(\hat x = \dfrac13\).
\(\vb p = \dfrac13(1,1,1) = \left(\dfrac13, \dfrac13, \dfrac13\right)\).
\(\vb e = \vb b - \vb p = \left(\dfrac23, -\dfrac13, -\dfrac13\right)\).
Check: \(\vb e\T\vb a = \dfrac23 - \dfrac13 - \dfrac13 = 0\). \(\checkmark\) Fractions are normal here; keep them as fractions.

Q3. Write the projection matrix onto the line through \(\vb a = (1, 2)\) and verify \(P^2 = P\).

Show answer
Answer
\(\vb a\,\vb a\T = \begin{bmatrix} 1 \\ 2 \end{bmatrix}\begin{bmatrix} 1 & 2 \end{bmatrix} = \begin{bmatrix} 1 & 2 \\ 2 & 4 \end{bmatrix}\) and \(\vb a\T\vb a = 1 + 4 = 5\), so \(P = \dfrac15\begin{bmatrix} 1 & 2 \\ 2 & 4 \end{bmatrix}\).
\(P^2 = \dfrac{1}{25}\begin{bmatrix} 1\cdot 1 + 2\cdot 2 & 1\cdot 2 + 2\cdot 4 \\ 2\cdot 1 + 4\cdot 2 & 2\cdot 2 + 4\cdot 4 \end{bmatrix} = \dfrac{1}{25}\begin{bmatrix} 5 & 10 \\ 10 & 20 \end{bmatrix} = \dfrac15\begin{bmatrix} 1 & 2 \\ 2 & 4 \end{bmatrix} = P\). \(\checkmark\)   \(P\) is symmetric and has rank \(1\).

Q4. Project \(\vb b = (3, 2, 7)\) onto the column space of \(A = \begin{bmatrix} 1 & 0 \\ 1 & 1 \\ 1 & 2 \end{bmatrix}\). Give \(\hat{\vb x}\), \(\vb p\), \(\vb e\), and the checks.

Show answer
Answer
\(A\T A = \begin{bmatrix} 3 & 3 \\ 3 & 5 \end{bmatrix}\), \(A\T\vb b = \begin{bmatrix} 3 + 2 + 7 \\ 0 + 2 + 14 \end{bmatrix} = \begin{bmatrix} 12 \\ 16 \end{bmatrix}\).
\(\left[\begin{array}{cc|c} 3 & 3 & 12 \\ 3 & 5 & 16 \end{array}\right] \xrightarrow{\ R_2 - R_1\ } \left[\begin{array}{cc|c} 3 & 3 & 12 \\ 0 & 2 & 4 \end{array}\right]\), so \(\hat x_2 = 2\) and \(3\hat x_1 + 3(2) = 12\), \(\hat x_1 = 2\). \(\hat{\vb x} = (2, 2)\).
\(\vb p = 2(1,1,1) + 2(0,1,2) = (2, 4, 6)\).
\(\vb e = (3,2,7) - (2,4,6) = (1, -2, 1)\).
Checks: \((1,1,1)\cdot\vb e = 1 - 2 + 1 = 0\) and \((0,1,2)\cdot\vb e = 0 - 2 + 2 = 0\). \(\checkmark\)

Q5. Find the projection matrix onto the column space of \(A = \begin{bmatrix} 1 & 1 \\ 1 & 0 \\ 0 & 1 \end{bmatrix}\). Check that it is symmetric and that \(P\vb a_1 = \vb a_1\) for the first column.

Show answer
Answer
\(A\T A = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}\), \((A\T A)^{-1} = \dfrac{1}{4 - 1}\begin{bmatrix} 2 & -1 \\ -1 & 2 \end{bmatrix} = \dfrac13\begin{bmatrix} 2 & -1 \\ -1 & 2 \end{bmatrix}\).
\(A(A\T A)^{-1} = \dfrac13\begin{bmatrix} 1 & 1 \\ 1 & 0 \\ 0 & 1 \end{bmatrix}\begin{bmatrix} 2 & -1 \\ -1 & 2 \end{bmatrix} = \dfrac13\begin{bmatrix} 1 & 1 \\ 2 & -1 \\ -1 & 2 \end{bmatrix}\), and
\(P = \dfrac13\begin{bmatrix} 1 & 1 \\ 2 & -1 \\ -1 & 2 \end{bmatrix}\begin{bmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \end{bmatrix} = \dfrac13\begin{bmatrix} 2 & 1 & 1 \\ 1 & 2 & -1 \\ 1 & -1 & 2 \end{bmatrix}\).
\(P\) is symmetric. \(P\vb a_1 = \dfrac13(2 + 1,\ 1 + 2,\ 1 - 1) = (1, 1, 0) = \vb a_1\) \(\checkmark\) (a vector already in the column space is its own projection).

Q6 (theory). (a) Starting from “the error is perpendicular to every column of \(A\)”, derive the normal equations. (b) Explain in one sentence why \(P^2 = P\) for a projection matrix. (c) When is \(A\T A\) invertible?

Show answer
Answer
(a) The error is \(\vb e = \vb b - A\hat{\vb x}\). Perpendicular to each column \(\vb a_i\) means \(\vb a_i\T(\vb b - A\hat{\vb x}) = 0\) for every \(i\). Stacking these equations (the rows of \(A\T\) are the \(\vb a_i\T\)) gives \(A\T(\vb b - A\hat{\vb x}) = \vb 0\), that is \(A\T\vb b - A\T A\hat{\vb x} = \vb 0\), so \(A\T A\hat{\vb x} = A\T\vb b\).
(b) \(P\vb b\) already lies in the subspace, and projecting a vector that is already in the subspace leaves it unchanged, so \(P(P\vb b) = P\vb b\) for every \(\vb b\).
(c) Exactly when the columns of \(A\) are independent: \(A\T A\) has the same nullspace as \(A\), because \(A\T A\vb x = \vb 0\) gives \(\vb x\T A\T A\vb x = \nrm{A\vb x}^2 = 0\), so \(A\vb x = \vb 0\).

5Formula sheet

TopicFormulas
Projection onto a line\(\hat x = \dfrac{\vb a\T\vb b}{\vb a\T\vb a}\),   \(\vb p = \hat x\,\vb a\),   \(\vb e = \vb b - \vb p\)
check \(\vb e\T\vb a = 0\);   also \(\nrm{\vb p}^2 + \nrm{\vb e}^2 = \nrm{\vb b}^2\)
Projection matrix (line)\(P = \dfrac{\vb a\,\vb a\T}{\vb a\T\vb a}\)   (column times row, divided by a number)
\(P\T = P\),   \(P^2 = P\),   rank \(1\)
Projection onto \(\mathbf C(A)\)\(A\T A\hat{\vb x} = A\T\vb b\) (normal equations),   \(\vb p = A\hat{\vb x}\),   \(\vb e = \vb b - \vb p\)
check \(A\T\vb e = \vb 0\): \(\vb e\) is perpendicular to every column
Projection matrix (subspace)\(P = A(A\T A)^{-1}A\T\),   \(P\T = P\),   \(P^2 = P\)
\(A\T A\) is invertible exactly when the columns of \(A\) are independent
\(2 \times 2\) inverse\(\begin{bmatrix} a & b \\ c & d \end{bmatrix}^{-1} = \dfrac{1}{ad - bc}\begin{bmatrix} d & -b \\ -c & a \end{bmatrix}\)
Special cases\(\vb b\) in the subspace: \(\vb p = \vb b\), \(\vb e = \vb 0\)
\(\vb b\) perpendicular to the subspace: \(\vb p = \vb 0\), \(\vb e = \vb b\)