MAT 102 Linear Algebra · DSE · Intake 2/1 · Dr. Ronobir Chandra Sarker
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
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.
| Symbol | Meaning |
|---|---|
| \(\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) |
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\).
Example 1.1 (book). Project \(\vb b = (1, 1, 1)\) onto the line through \(\vb a = (1, 2, 2)\).
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)\).
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)\).
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\).
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. \]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 \]The meaning of \(P^2 = P\): projecting a second time changes nothing, because \(\vb p\) is already on the line.
Exercise 1.
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\).
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.
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\).
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}\).
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}\).
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}\).
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.
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.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.
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.
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} \]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} \]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} \]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.
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.
Q3. Write the projection matrix onto the line through \(\vb a = (1, 2)\) and verify \(P^2 = P\).
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.
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.
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?
| Topic | Formulas |
|---|---|
| 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\) |