Linear Algebra · Solutions

Orthogonality and Least Squares

12 questions · about 108 minutes

Work this sheet on paper and show every step — the solutions are written as methods, so you can check your route and not merely your final vector. Name each theorem as you use it (“by the Orthogonal Decomposition Theorem”, “by the fundamental orthogonality relation”, “by Cauchy–Schwarz”), and whenever a formula needs an orthogonal or orthonormal set, say which it needs and why you have it. No calculator is needed anywhere: every length is an exact square root and every coefficient an exact fraction, and full worked solutions are on a separate page with a separate reveal for each question.

1.Computation
Leave every square root exact. In each part say which property of the dot product, or which named theorem, you are using.
1. (a)Let $u = ⟨ 2, 3, - 6 ⟩$ and $v = ⟨ 6, - 2, 3 ⟩$ . Compute $∥ u ∥$ , $∥ v ∥$ , $dist (u, v)$ and $cos θ$ for the angle $θ$ between them. Then confirm the distance a second way, using only the three numbers $∥ u ∥$ , $∥ v ∥$ and $u \cdot v$ .
2. (b)Find every real $t$ for which $a = ⟨ t, t, 1 ⟩$ and $b = ⟨ t, 2, - 3 ⟩$ are orthogonal, and check each value you find.
3. (c)Let $w = ⟨ 2, - 1, 0, 2 ⟩$ and $z = ⟨ 1, 2, 2, 0 ⟩$ in $R^{4}$ . Show that $w ⊥ z$ , then compute $∥ w + z ∥$ twice: once from the entries of $w + z$ and once without them. Explain why $∥ w + z ∥ \neq = ∥ w ∥ + ∥ z ∥$ is not a contradiction.
Solution
(a) Lengths and angle. $∥ u ∥^{2} = 4 + 9 + 36 = 49$ , so $∥ u ∥ = 7$ ; likewise $∥ v ∥^{2} = 36 + 4 + 9 = 49$ and $∥ v ∥ = 7$ . The dot product is $u \cdot v = 12 - 6 - 18 = - 12$ , so
$cos θ = \frac{u \cdot v}{∥ u ∥ ∥ v ∥} = - \frac{12}{49},$
which is negative: the angle is obtuse. Cauchy–Schwarz is comfortably satisfied, $∣ - 12 ∣ \leq 49$ , which is why a cosine came out.
Distance directly. $u - v = ⟨ - 4, 5, - 9 ⟩$ , so $∥ u - v ∥^{2} = 16 + 25 + 81 = 122$ and $dist (u, v) = 122$ .
Distance from the three numbers. Expand with linearity and symmetry of the dot product:
$∥ u - v ∥^{2} = u \cdot u - 2 u \cdot v + v \cdot v = 49 + 24 + 49 = 122. ✓$
(b) One scalar equation. $a \cdot b = t^{2} + 2 t - 3 = (t + 3) (t - 1)$ , which vanishes exactly for $t = 1$ and $t = - 3$ . Check $t = 1$ : $⟨ 1, 1, 1 ⟩ \cdot ⟨ 1, 2, - 3 ⟩ = 1 + 2 - 3 = 0$ ✓. Check $t = - 3$ : $⟨ - 3, - 3, 1 ⟩ \cdot ⟨ - 3, 2, - 3 ⟩ = 9 - 6 - 3 = 0$ ✓. Orthogonality is a single scalar condition; here it happens to be quadratic in $t$ , so it has two solutions rather than one.
(c) Pythagoras. $w \cdot z = 2 - 2 + 0 + 0 = 0$ , so $w ⊥ z$ . From the entries, $w + z = ⟨ 3, 1, 2, 2 ⟩$ and $∥ w + z ∥^{2} = 9 + 1 + 4 + 4 = 18$ , so $∥ w + z ∥ = 32$ .
Without the entries: $∥ w ∥^{2} = 4 + 1 + 0 + 4 = 9$ and $∥ z ∥^{2} = 1 + 4 + 4 + 0 = 9$ , and because the vectors are orthogonal the Pythagorean theorem gives $∥ w + z ∥^{2} = 9 + 9 = 18$ ✓.
Meanwhile $∥ w ∥ + ∥ z ∥ = 6 \neq = 32$ . There is no contradiction: Pythagoras is a statement about squared lengths. The equation $∥ w + z ∥ = ∥ w ∥ + ∥ z ∥$ is the equality case of the triangle inequality, which holds only when one vector is a non-negative multiple of the other — and two nonzero orthogonal vectors are as far from parallel as vectors can be.
2.Computation
Let $W = Span {w_{1}, w_{2}} \subseteq R^{4}$ with $w_{1} = ⟨ 1, 2, 0, - 1 ⟩$ and $w_{2} = ⟨ 0, 1, 1, 1 ⟩$ .
1. (a)Find a basis for $W^{⊥}$ . State which result lets you replace the condition “orthogonal to every vector of $W$ ” by finitely many equations, and confirm that $dim W + dim W^{⊥} = 4$ .
2. (b)Decide whether $y = ⟨ 5, - 2, 1, 1 ⟩$ and $y^{'} = ⟨ 1, 0, 1, 1 ⟩$ belong to $W^{⊥}$ . For whichever does, write it as a combination of your basis vectors from (a).
3. (c)Let $A$ be the $2 \times 4$ matrix whose rows are $w_{1}$ and $w_{2}$ . Give the dimension of each of the four fundamental subspaces of $A$ , identify which of them is $W^{⊥}$ , and explain what the dimension of $Nul A^{T}$ tells you about the system $A x = b$ .
Solution
(a) Set up the equations. By the finite test for orthogonal complements — a vector is in $W^{⊥}$ if and only if it is orthogonal to each vector of a spanning set of $W$ — $v = ⟨ v_{1}, v_{2}, v_{3}, v_{4} ⟩$ lies in $W^{⊥}$ exactly when $v \cdot w_{1} = 0$ and $v \cdot w_{2} = 0$ :
$v_{1} + 2 v_{2} - v_{4} = 0, v_{2} + v_{3} + v_{4} = 0.$
Row-reduce the coefficient matrix: subtracting twice the second row from the first turns $(102101 - 1 1)$ into $(1001 - 2 1 - 3 1)$ . Pivots sit in columns 1 and 2, so $v_{3} = s$ and $v_{4} = t$ are free, $v_{1} = 2 s + 3 t$ and $v_{2} = - s - t$ :
$v = s ⟨ 2, - 1, 1, 0 ⟩ + t ⟨ 3, - 1, 0, 1 ⟩ .$
A basis of $W^{⊥}$ is ${⟨ 2, - 1, 1, 0 ⟩, ⟨ 3, - 1, 0, 1 ⟩}$ ; the two are independent because of the $1, 0$ and $0, 1$ pattern in the free positions. Check all four dot products: $⟨ 2, - 1, 1, 0 ⟩ \cdot w_{1} = 2 - 2 + 0 + 0 = 0$ , $⟨ 2, - 1, 1, 0 ⟩ \cdot w_{2} = 0 - 1 + 1 + 0 = 0$ , $⟨ 3, - 1, 0, 1 ⟩ \cdot w_{1} = 3 - 2 + 0 - 1 = 0$ , $⟨ 3, - 1, 0, 1 ⟩ \cdot w_{2} = 0 - 1 + 0 + 1 = 0$ ✓.
Since $w_{1}, w_{2}$ are not multiples of each other, $dim W = 2$ , and $dim W^{⊥} = 2$ , so $2 + 2 = 4 = n$ ✓, as the dimension theorem for complements requires.
(b) Two membership tests. $y \cdot w_{1} = 5 - 4 + 0 - 1 = 0$ and $y \cdot w_{2} = 0 - 2 + 1 + 1 = 0$ , so $y \in W^{⊥}$ . For $y^{'}$ : $y^{'} \cdot w_{1} = 1 + 0 + 0 - 1 = 0$ but $y^{'} \cdot w_{2} = 0 + 0 + 1 + 1 = 2 \neq = 0$ , so $y^{'} \in / W^{⊥}$ — one failed equation is enough.
To express $y$ , read the free positions: the third and fourth entries force $s = 1$ and $t = 1$ , and indeed $⟨ 2, - 1, 1, 0 ⟩ + ⟨ 3, - 1, 0, 1 ⟩ = ⟨ 5, - 2, 1, 1 ⟩$ ✓.
(c) The four subspaces. The rows are independent, so $rank A = 2$ , with $m = 2$ , $n = 4$ . Hence $dim Row A = 2$ and $dim Nul A = 4 - 2 = 2$ in $R^{4}$ ; $dim Col A = 2$ and $dim Nul A^{T} = 2 - 2 = 0$ in $R^{2}$ .
By the fundamental orthogonality relation $(Row A)^{⊥} = Nul A$ , and $Row A = W$ , so $W^{⊥} = Nul A$ — which is exactly the homogeneous system solved in (a).
$Nul A^{T} = {0}$ means $(Col A)^{⊥} = {0}$ , so $Col A$ is all of $R^{2}$ : every $b \in R^{2}$ is reachable and $A x = b$ is consistent for every right-hand side. There is no direction in $R^{2}$ that this matrix cannot reach, so least squares would never be needed for it.
3.Computation
Let $u_{1} = ⟨ 2, 2, 1 ⟩$ , $u_{2} = ⟨ 1, - 2, 2 ⟩$ , $u_{3} = ⟨ 2, - 1, - 2 ⟩$ and $y = ⟨ 4, 4, - 7 ⟩$ .
1. (a)Show that ${u_{1}, u_{2}, u_{3}}$ is an orthogonal basis of $R^{3}$ , quoting the theorem that spares you a row reduction, and write $y$ as a combination of the three vectors without solving a linear system.
2. (b)Let $Q$ be the $3 \times 3$ matrix whose columns are $u_{1} /3$ , $u_{2} /3$ , $u_{3} /3$ . Explain, without multiplying anything out, why $Q^{T} Q = I$ and what $Q^{- 1}$ is. Then solve $Q x = y$ and verify that $∥ x ∥ = ∥ y ∥$ .
3. (c)A classmate writes $y = (y \cdot u_{1}) u_{1} + (y \cdot u_{2}) u_{2} + (y \cdot u_{3}) u_{3}$ . Compute what the right-hand side actually equals, and say precisely which hypothesis of the formula they used is missing.
Solution
(a) Three dot products. $u_{1} \cdot u_{2} = 2 - 4 + 2 = 0$ , $u_{1} \cdot u_{3} = 4 - 2 - 2 = 0$ , $u_{2} \cdot u_{3} = 2 + 2 - 4 = 0$ . The set is orthogonal and every vector is nonzero, so by the theorem that orthogonal sets of nonzero vectors are linearly independent, it is independent; three independent vectors in $R^{3}$ form a basis.
Coefficients. In an orthogonal basis $c_{j} = \frac{y \cdot u _{j}}{u _{j} \cdot u _{j}}$ . All three denominators equal $9$ ( $4 + 4 + 1$ , $1 + 4 + 4$ , $4 + 1 + 4$ ). The numerators are
$y \cdot u_{1} = 8 + 8 - 7 = 9, y \cdot u_{2} = 4 - 8 - 14 = - 18, y \cdot u_{3} = 8 - 4 + 14 = 18,$
so $c_{1} = 1$ , $c_{2} = - 2$ , $c_{3} = 2$ and $y = u_{1} - 2 u_{2} + 2 u_{3}$ . Check: $⟨ 2 - 2 + 4, 2 + 4 - 2, 1 - 4 - 4 ⟩ = ⟨ 4, 4, - 7 ⟩$ ✓.
(b) An orthogonal matrix. Each column of $Q$ has length $9 /3 = 1$ , and dividing by $3$ leaves a zero dot product zero, so the columns are orthonormal. The $(i, j)$ entry of $Q^{T} Q$ is the dot product of columns $i$ and $j$ , hence $Q^{T} Q = I$ . Because $Q$ is square this makes it an orthogonal matrix, and $Q^{- 1} = Q^{T}$ .
So $x = Q^{T} y$ , whose entries are the dot products of $y$ with the columns: $x = \frac{1}{3} ⟨ 9, - 18, 18 ⟩ = ⟨ 3, - 6, 6 ⟩$ . Check: $Q x = \frac{1}{3} (3 u_{1} - 6 u_{2} + 6 u_{3}) = u_{1} - 2 u_{2} + 2 u_{3} = y$ ✓. Lengths: $∥ x ∥^{2} = 9 + 36 + 36 = 81$ and $∥ y ∥^{2} = 16 + 16 + 49 = 81$ ✓ — multiplication by a matrix with orthonormal columns preserves length. ( $x$ is just the coordinate vector of $y$ in the orthonormal basis: each entry is $3 c_{j}$ .)
(c) The missing denominators. The right-hand side is $9 u_{1} - 18 u_{2} + 18 u_{3} = 9 (u_{1} - 2 u_{2} + 2 u_{3}) = 9 y = ⟨ 36, 36, - 63 ⟩$ , nine times too large. The formula $c_{j} = y \cdot u_{j}$ requires an orthonormal basis. These vectors are orthogonal but each has length $3$ , so every coefficient is missing its denominator $u_{j} \cdot u_{j} = 9$ .
4.Computation
Let $W = Span {u_{1}, u_{2}} \subseteq R^{3}$ with $u_{1} = ⟨ 1, 0, - 1 ⟩$ and $u_{2} = ⟨ 1, 1, 1 ⟩$ , and let $y = ⟨ 2, 0, 4 ⟩$ .
1. (a)Verify that ${u_{1}, u_{2}}$ is an orthogonal basis of $W$ , compute $\hat{y} = proj_{W} y$ and $z = y - \hat{y}$ , and find $dist (y, W)$ . Check that $z \in W^{⊥}$ and check the identity $∥ y ∥^{2} = ∥ \hat{y} ∥^{2} + ∥ z ∥^{2}$ .
2. (b)Find a vector $n$ spanning $W^{⊥}$ and recompute $z$ by projecting $y$ onto the line through $n$ . Explain why the two routes must agree, naming the theorem.
3. (c)Write down the projection matrix $P$ onto $W$ using the orthonormal-columns formula $P = U U^{T}$ , confirm $P y = \hat{y}$ , and identify $I - P$ in terms of $n$ .
Solution
(a) Project with the orthogonal basis. $u_{1} \cdot u_{2} = 1 + 0 - 1 = 0$ and both are nonzero, so they form an orthogonal set, hence an independent one, hence an orthogonal basis of the plane they span. The Orthogonal Decomposition Theorem then gives
$\hat{y} = \frac{y \cdot u _{1}}{u _{1} \cdot u _{1}} u_{1} + \frac{y \cdot u _{2}}{u _{2} \cdot u _{2}} u_{2} = \frac{- 2}{2} ⟨ 1, 0, - 1 ⟩ + \frac{6}{3} ⟨ 1, 1, 1 ⟩ = ⟨ 1, 2, 3 ⟩,$
using $y \cdot u_{1} = 2 + 0 - 4 = - 2$ , $u_{1} \cdot u_{1} = 2$ , $y \cdot u_{2} = 2 + 0 + 4 = 6$ , $u_{2} \cdot u_{2} = 3$ . Then $z = ⟨ 2, 0, 4 ⟩ - ⟨ 1, 2, 3 ⟩ = ⟨ 1, - 2, 1 ⟩$ and, by the Best Approximation Theorem, $dist (y, W) = ∥ z ∥ = 6$ .
Checks: $z \cdot u_{1} = 1 - 1 = 0$ and $z \cdot u_{2} = 1 - 2 + 1 = 0$ , so $z \in W^{⊥}$ by the finite test ✓. Pythagoras: $∥ y ∥^{2} = 4 + 0 + 16 = 20$ , $∥ \hat{y} ∥^{2} = 1 + 4 + 9 = 14$ , $∥ z ∥^{2} = 6$ , and $14 + 6 = 20$ ✓.
(b) The complement route. $n ⊥ u_{1}$ gives $n_{1} - n_{3} = 0$ and $n ⊥ u_{2}$ gives $n_{1} + n_{2} + n_{3} = 0$ , so $n_{1} = n_{3} = s$ and $n_{2} = - 2 s$ : $n = ⟨ 1, - 2, 1 ⟩$ spans $W^{⊥}$ , which has dimension $3 - 2 = 1$ . Projecting onto that line,
$proj_{n} y = \frac{y \cdot n}{n \cdot n} n = \frac{2 + 0 + 4}{6} ⟨ 1, - 2, 1 ⟩ = ⟨ 1, - 2, 1 ⟩ = z ✓,$
and $\hat{y} = y - z = ⟨ 1, 2, 3 ⟩$ again. The routes must agree by the uniqueness in the Orthogonal Decomposition Theorem: $y = \hat{y} + z$ with $\hat{y} \in W$ and $z \in W^{⊥}$ can be done in only one way, and the $W^{⊥}$ -component of $y$ is by definition $proj_{W^{⊥}} y$ , which is the projection onto the line through $n$ .
(c) The matrix. With $U = [u_{1} / 2 u_{2} / 3]$ ,
$P = U U^{T} = \frac{u _{1} u _{1}^{T}}{2} + \frac{u _{2} u _{2}^{T}}{3} = \frac{1}{6} 3 10 - 1 000 - 1 01 + 2111111111 = \frac{1}{6} 52 - 1 222 - 1 25 .$
Then $P y = \frac{1}{6} ⟨ 10 + 0 - 4, 4 + 0 + 8, - 2 + 0 + 20 ⟩ = \frac{1}{6} ⟨ 6, 12, 18 ⟩ = ⟨ 1, 2, 3 ⟩ = \hat{y}$ ✓. $P$ is visibly symmetric and $tr P = \frac{12}{6} = 2 = dim W$ .
Finally
$I - P = \frac{1}{6} 1 - 2 1 - 2 4 - 2 1 - 2 1 = \frac{n n ^{T}}{n \cdot n},$
since $n \cdot n = 6$ : it is the projection matrix onto the line $W^{⊥}$ , exactly as the theorem on symmetric idempotents promises.
5.Sketch
Let $A = (1326)$ . This question is about drawing the four fundamental subspaces of $A$ accurately: every line you draw must be labelled with a spanning vector, and every vector you place must be justified by a computation.
1. (a)Find a basis for each of $Row A$ , $Nul A$ , $Col A$ and $Nul A^{T}$ , state each dimension, and verify both fundamental orthogonality relations by a dot product.
2. (b)Draw two copies of $R^{2}$ side by side: the domain, showing $Row A$ and $Nul A$ , and the codomain, showing $Col A$ and $Nul A^{T}$ . In the domain draw $x = ⟨ 3, 1 ⟩$ and its components $x_{r} \in Row A$ and $x_{n} \in Nul A$ . In the codomain draw $A x$ , $A x_{r}$ and $A x_{n}$ , and say what the picture shows about which part of $x$ survives.
3. (c)Add $b = ⟨ 1, 1 ⟩$ to the codomain picture together with its components in $Col A$ and in $Nul A^{T}$ . Explain from the picture why $A x = b$ has no solution, and find the vector of $Row A$ that $A$ sends to the $Col A$ -component of $b$ .
Solution
(a) Four bases. The second row is three times the first, so $rank A = 1$ and each of the four subspaces is a line.
$Row A = Span {⟨ 1, 2 ⟩}$ , dimension $1$ . $Nul A$ : $x_{1} + 2 x_{2} = 0$ , so $Span {⟨ - 2, 1 ⟩}$ , dimension $2 - 1 = 1$ . $Col A = Span {⟨ 1, 3 ⟩}$ (the second column is twice the first), dimension $1$ . $Nul A^{T}$ : $A^{T} = (1236)$ gives $y_{1} + 3 y_{2} = 0$ , so $Span {⟨ - 3, 1 ⟩}$ , dimension $2 - 1 = 1$ .
Orthogonality: $⟨ 1, 2 ⟩ \cdot ⟨ - 2, 1 ⟩ = - 2 + 2 = 0$ , so $Row A ⊥ Nul A$ ; and $⟨ 1, 3 ⟩ \cdot ⟨ - 3, 1 ⟩ = - 3 + 3 = 0$ , so $Col A ⊥ Nul A^{T}$ ✓. In each copy of $R^{2}$ the dimensions add to $1 + 1 = 2$ .
(b) The domain. Draw $Row A$ as the line through the origin in direction $⟨ 1, 2 ⟩$ (slope $2$ ) and $Nul A$ as the line in direction $⟨ - 2, 1 ⟩$ (slope $- \frac{1}{2}$ ); the two are perpendicular. Project $x$ onto the row line:
$x_{r} = \frac{x \cdot ⟨ 1 , 2 ⟩}{⟨ 1 , 2 ⟩ \cdot ⟨ 1 , 2 ⟩} ⟨ 1, 2 ⟩ = \frac{3 + 2}{5} ⟨ 1, 2 ⟩ = ⟨ 1, 2 ⟩, x_{n} = x - x_{r} = ⟨ 2, - 1 ⟩,$
and $⟨ 2, - 1 ⟩ = - ⟨ - 2, 1 ⟩$ does lie in $Nul A$ ✓. Draw $x$ from the origin to $(3, 1)$ , $x_{r}$ along the row line to $(1, 2)$ , $x_{n}$ along the null line to $(2, - 1)$ ; $x$ is the diagonal of the rectangle they span.
The codomain. Draw $Col A$ in direction $⟨ 1, 3 ⟩$ (slope $3$ ) and $Nul A^{T}$ in direction $⟨ - 3, 1 ⟩$ (slope $- \frac{1}{3}$ ), again perpendicular. Compute
$A x = ⟨ 3 + 2, 9 + 6 ⟩ = ⟨ 5, 15 ⟩, A x_{r} = ⟨ 1 + 4, 3 + 12 ⟩ = ⟨ 5, 15 ⟩, A x_{n} = ⟨ 2 - 2, 6 - 6 ⟩ = ⟨ 0, 0 ⟩ .$
So $A x$ and $A x_{r}$ are the same arrow, $5 ⟨ 1, 3 ⟩$ , lying on the $Col A$ line, and $A x_{n}$ is a dot at the origin. The picture says: the null-space component of $x$ is crushed to zero, the row-space component carries everything, and its image lands in the column space. The row line is carried one-to-one onto the column line ( $⟨ 1, 2 ⟩ \mapsto 5 ⟨ 1, 3 ⟩$ ).
(c) An unreachable target. Project $b$ onto $Col A$ :
$\hat{b} = \frac{1 + 3}{1 + 9} ⟨ 1, 3 ⟩ = ⟨ \frac{2}{5}, \frac{6}{5} ⟩, b - \hat{b} = ⟨ \frac{3}{5}, - \frac{1}{5} ⟩ = - \frac{1}{5} ⟨ - 3, 1 ⟩ \in Nul A^{T} ✓ .$
Draw $b$ to $(1, 1)$ , $\hat{b}$ on the column line, and the short perpendicular leg from $\hat{b}$ to $b$ running parallel to $Nul A^{T}$ . Every vector $A x$ lies on the line $Col A$ , and $b$ does not: it has the nonzero component $⟨ \frac{3}{5}, - \frac{1}{5} ⟩$ in the perpendicular direction $Nul A^{T}$ , which no input can produce. That is what inconsistency looks like.
For the last part write $x_{r} = t ⟨ 1, 2 ⟩$ ; then $A x_{r} = t ⟨ 5, 15 ⟩$ , and this equals $⟨ \frac{2}{5}, \frac{6}{5} ⟩$ when $t = \frac{2}{25}$ . So $x_{r} = ⟨ \frac{2}{25}, \frac{4}{25} ⟩$ . Check: $A x_{r} = ⟨ \frac{2}{25} + \frac{8}{25}, \frac{6}{25} + \frac{24}{25} ⟩ = ⟨ \frac{2}{5}, \frac{6}{5} ⟩$ ✓. (Adding any multiple of $⟨ - 2, 1 ⟩$ gives another vector with the same image; the one in $Row A$ is the shortest of them.)
6.Proof
Work from the algebraic properties of the dot product (symmetry, linearity in each slot, positive definiteness) and from theorems you name explicitly. Throughout, ${u_{1}, \dots, u_{p}}$ is an orthonormal set in $R^{n}$ .
1. (a)Prove the polarization identity $u \cdot v = \frac{1}{4} (∥ u + v ∥^{2} - ∥ u - v ∥^{2})$ . Then prove: if a square matrix $Q$ satisfies $∥ Q x ∥ = ∥ x ∥$ for every $x$ , then $Q$ is an orthogonal matrix.
2. (b)Prove Bessel's inequality: for every $y \in R^{n}$ , $j = 1 \sum p (y \cdot u_{j})^{2} \leq ∥ y ∥^{2}$ , with equality if and only if $y \in Span {u_{1}, \dots, u_{p}}$ .
3. (c)Show that a matrix which is both orthogonal and symmetric satisfies $Q^{2} = I$ , and give a $2 \times 2$ example other than $\pm I$ .
Solution
(a) Polarization. Expand both squares using linearity in each slot and symmetry:
$∥ u + v ∥^{2} = u \cdot u + 2 u \cdot v + v \cdot v, ∥ u - v ∥^{2} = u \cdot u - 2 u \cdot v + v \cdot v .$
Subtracting, the squared lengths cancel and $4 u \cdot v$ remains; divide by $4$ . $■$
Length-preserving implies orthogonal. Let $x, y$ be arbitrary. Apply polarization to $Q x$ and $Q y$ , use linearity of $Q$ , then the hypothesis:
$(Q x) \cdot (Q y) = \frac{1}{4} (∥ Q (x + y) ∥^{2} - ∥ Q (x - y) ∥^{2}) = \frac{1}{4} (∥ x + y ∥^{2} - ∥ x - y ∥^{2}) = x \cdot y .$
Now the $(i, j)$ entry of $Q^{T} Q$ is the dot product of columns $i$ and $j$ of $Q$ , that is $(Q e_{i}) \cdot (Q e_{j}) = e_{i} \cdot e_{j}$ , which is $1$ if $i = j$ and $0$ otherwise. Hence $Q^{T} Q = I$ , and since $Q$ is square this is the definition of an orthogonal matrix. $■$ Together with the theorem on matrices with orthonormal columns, this says the orthogonal matrices are exactly the length-preserving ones.
(b) Bessel. Put $\hat{y} = \sum_{j} (y \cdot u_{j}) u_{j}$ and $z = y - \hat{y}$ . For each $k$ ,
$z \cdot u_{k} = y \cdot u_{k} - j \sum (y \cdot u_{j}) (u_{j} \cdot u_{k}) = y \cdot u_{k} - (y \cdot u_{k}) \cdot 1 = 0,$
because orthonormality kills every term with $j \neq = k$ and leaves $u_{k} \cdot u_{k} = 1$ . As $\hat{y}$ is a combination of the $u_{j}$ , linearity gives $z \cdot \hat{y} = 0$ . By the Pythagorean theorem,
$∥ y ∥^{2} = ∥ \hat{y} + z ∥^{2} = ∥ \hat{y} ∥^{2} + ∥ z ∥^{2} .$
Expanding $∥ \hat{y} ∥^{2} = \hat{y} \cdot \hat{y} = \sum_{j} \sum_{k} (y \cdot u_{j}) (y \cdot u_{k}) (u_{j} \cdot u_{k}) = \sum_{j} (y \cdot u_{j})^{2}$ by the same orthonormality. Therefore
$j = 1 \sum p (y \cdot u_{j})^{2} = ∥ y ∥^{2} - ∥ z ∥^{2} \leq ∥ y ∥^{2} .$
Equality holds if and only if $∥ z ∥^{2} = 0$ , if and only if $z = 0$ (positive definiteness), if and only if $y = \hat{y}$ , which lies in the span. Conversely, if $y = \sum_{j} c_{j} u_{j}$ is in the span, dotting with $u_{k}$ gives $c_{k} = y \cdot u_{k}$ (the coefficient theorem for orthonormal bases), so $y = \hat{y}$ , $z = 0$ , and equality holds. $■$
(In the language of projections, $\hat{y}$ is $proj_{W} y$ for $W$ the span and $z$ is the error; Bessel is Pythagoras for that decomposition.)
(c) Symmetric orthogonal matrices. If $Q^{T} = Q$ and $Q^{T} Q = I$ then $Q^{2} = Q Q = Q^{T} Q = I$ . Example: $Q = (0110)$ , which is symmetric and whose columns $e_{2}, e_{1}$ are orthonormal; indeed $Q^{2} = I$ . Geometrically it reflects the plane in the line $y = x$ , and reflecting twice is the identity. (Another: $diag (1, - 1)$ , reflection in the $x$ -axis.)
7.Computation
Let $x_{1} = ⟨ 2, 1, 2 ⟩$ , $x_{2} = ⟨ 1, 1, 0 ⟩$ and $x_{3} = ⟨ 0, 1, 1 ⟩$ ; you may take for granted that they form a basis of $R^{3}$ . Keep the arithmetic in integers by rescaling wherever it helps, and say each time why rescaling is legitimate.
1. (a)Run the Gram–Schmidt process in the order $x_{1}, x_{2}, x_{3}$ to obtain an orthogonal basis ${v_{1}, v_{2}, v_{3}}$ and then an orthonormal basis ${u_{1}, u_{2}, u_{3}}$ . Check every orthogonality you claim.
2. (b)Express $x_{2}$ and $x_{3}$ as combinations of $u_{1}, u_{2}, u_{3}$ . Which of the $u_{j}$ does each one use, and which of those facts was guaranteed before you computed anything?
3. (c)Now start again in the order $x_{3}, x_{2}, x_{1}$ and compute the first two Gram–Schmidt vectors. Then explain, without carrying out the third step, why the third vector must be a multiple of $⟨ 1, - 1, 1 ⟩$ .
Solution
(a) Step 1. $v_{1} = x_{1} = ⟨ 2, 1, 2 ⟩$ , with $v_{1} \cdot v_{1} = 9$ .
Step 2. $x_{2} \cdot v_{1} = 2 + 1 + 0 = 3$ , so
$v_{2} = x_{2} - \frac{3}{9} v_{1} = ⟨ 1, 1, 0 ⟩ - \frac{1}{3} ⟨ 2, 1, 2 ⟩ = ⟨ \frac{1}{3}, \frac{2}{3}, - \frac{2}{3} ⟩ .$
Rescale by $3$ to $v_{2} = ⟨ 1, 2, - 2 ⟩$ : multiplying by a nonzero scalar changes neither the span nor orthogonality to $v_{1}$ . Check $v_{1} \cdot v_{2} = 2 + 2 - 4 = 0$ ✓; note $v_{2} \cdot v_{2} = 9$ .
Step 3. $x_{3} \cdot v_{1} = 0 + 1 + 2 = 3$ and $x_{3} \cdot v_{2} = 0 + 2 - 2 = 0$ , so
$v_{3} = x_{3} - \frac{3}{9} v_{1} - \frac{0}{9} v_{2} = ⟨ 0, 1, 1 ⟩ - \frac{1}{3} ⟨ 2, 1, 2 ⟩ = ⟨ - \frac{2}{3}, \frac{2}{3}, \frac{1}{3} ⟩,$
rescaled to $v_{3} = ⟨ - 2, 2, 1 ⟩$ . Checks: $v_{3} \cdot v_{1} = - 4 + 2 + 2 = 0$ ✓ and $v_{3} \cdot v_{2} = - 2 + 4 - 2 = 0$ ✓. (Both projections were subtracted from the original $x_{3}$ , even though one of them happened to be zero.)
All three vectors have squared length $9$ , so the orthonormal basis is
$u_{1} = \frac{1}{3} ⟨ 2, 1, 2 ⟩, u_{2} = \frac{1}{3} ⟨ 1, 2, - 2 ⟩, u_{3} = \frac{1}{3} ⟨ - 2, 2, 1 ⟩ .$
(b) Coordinates by dot products. In an orthonormal basis the coefficient of $u_{j}$ is the dot product with $u_{j}$ . For $x_{2}$ : $x_{2} \cdot u_{1} = \frac{3}{3} = 1$ , $x_{2} \cdot u_{2} = \frac{1 + 2 + 0}{3} = 1$ , $x_{2} \cdot u_{3} = \frac{- 2 + 2 + 0}{3} = 0$ , so $x_{2} = u_{1} + u_{2}$ . For $x_{3}$ : $x_{3} \cdot u_{1} = 1$ , $x_{3} \cdot u_{2} = 0$ , $x_{3} \cdot u_{3} = \frac{0 + 2 + 1}{3} = 1$ , so $x_{3} = u_{1} + u_{3}$ . Checks: $u_{1} + u_{2} = \frac{1}{3} ⟨ 3, 3, 0 ⟩ = ⟨ 1, 1, 0 ⟩$ ✓ and $u_{1} + u_{3} = \frac{1}{3} ⟨ 0, 3, 3 ⟩ = ⟨ 0, 1, 1 ⟩$ ✓.
That $x_{2}$ uses no $u_{3}$ was guaranteed in advance: the correctness theorem says $Span {v_{1}, v_{2}} = Span {x_{1}, x_{2}}$ , so $x_{2} \in Span {u_{1}, u_{2}}$ — this is the triangular pattern that becomes the matrix $R$ in the $QR$ factorization. That $x_{3}$ uses no $u_{2}$ was not guaranteed; it is the accident $x_{3} ⊥ v_{2}$ discovered in step 3.
(c) Reversed order. $v_{1} = x_{3} = ⟨ 0, 1, 1 ⟩$ , $v_{1} \cdot v_{1} = 2$ , and $x_{2} \cdot v_{1} = 0 + 1 + 0 = 1$ , so
$v_{2} = ⟨ 1, 1, 0 ⟩ - \frac{1}{2} ⟨ 0, 1, 1 ⟩ = ⟨ 1, \frac{1}{2}, - \frac{1}{2} ⟩ ⟶ ⟨ 2, 1, - 1 ⟩,$
with $⟨ 2, 1, - 1 ⟩ \cdot ⟨ 0, 1, 1 ⟩ = 0 + 1 - 1 = 0$ ✓. Neither vector appeared in (a): the first output is always a multiple of the first input, so the order matters.
Third step without computing: $v_{3}$ is $x_{1}$ minus its projection onto $Span {v_{1}, v_{2}} = Span {x_{3}, x_{2}}$ , so by the correctness theorem $v_{3}$ lies in $Span {x_{2}, x_{3}}^{⊥}$ , a subspace of dimension $3 - 2 = 1$ . Since $⟨ 1, - 1, 1 ⟩ \cdot ⟨ 1, 1, 0 ⟩ = 0$ and $⟨ 1, - 1, 1 ⟩ \cdot ⟨ 0, 1, 1 ⟩ = 0$ , that vector spans the line, and $v_{3} \neq = 0$ by the theorem's first claim. Hence $v_{3}$ is a nonzero multiple of $⟨ 1, - 1, 1 ⟩$ . (Carrying the step out gives exactly $⟨ 1, - 1, 1 ⟩$ .) The two orthogonal bases share no vector, but both span $R^{3}$ : only the subspace is order-independent.
8.Computation
Let $A = 221131$ .
1. (a)Find the $QR$ factorization of $A$ with positive diagonal in $R$ . Give both factors exactly.
2. (b)Verify $R = Q^{T} A$ by computing all four entries of $Q^{T} A$ directly, confirm that the diagonal entries of $R$ are the lengths of the un-normalised Gram–Schmidt vectors, and multiply $QR$ out to recover $A$ .
3. (c)Explain why $Q^{- 1}$ does not exist. Then, without forming $Q Q^{T}$ , compute $Q Q^{T} x_{1}$ for the first column $x_{1}$ of $A$ and $Q Q^{T} n$ for $n = ⟨ 1, 1, - 4 ⟩$ , and say what $Q Q^{T}$ is.
Solution
(a) Gram–Schmidt on the columns. $x_{1} = ⟨ 2, 2, 1 ⟩$ and $x_{2} = ⟨ 1, 3, 1 ⟩$ are not proportional, so the columns are independent and the theorem applies. $v_{1} = x_{1}$ , $∥ v_{1} ∥ = 4 + 4 + 1 = 3$ , $u_{1} = \frac{1}{3} ⟨ 2, 2, 1 ⟩$ . Then $x_{2} \cdot v_{1} = 2 + 6 + 1 = 9$ and $v_{1} \cdot v_{1} = 9$ , so
$v_{2} = x_{2} - \frac{9}{9} v_{1} = ⟨ - 1, 1, 0 ⟩, ∥ v_{2} ∥ = 2, u_{2} = \frac{1}{2} ⟨ - 1, 1, 0 ⟩ .$
Check $u_{1} \cdot u_{2} = \frac{- 2 + 2 + 0}{3 2} = 0$ ✓.
The factors. $r_{jk} = x_{k} \cdot u_{j}$ for $j \leq k$ : $r_{11} = x_{1} \cdot u_{1} = \frac{9}{3} = 3$ , $r_{12} = x_{2} \cdot u_{1} = \frac{9}{3} = 3$ , $r_{22} = x_{2} \cdot u_{2} = \frac{- 1 + 3 + 0}{2} = \frac{2}{2} = 2$ . So
$Q = 2/3 2/3 1/3 - 1/ 2 1/ 2 0, R = (3032) .$
(b) Checks. The rows of $Q^{T}$ are $u_{1}^{T}$ and $u_{2}^{T}$ , so $Q^{T} A$ has entries $u_{1} \cdot x_{1} = 3$ , $u_{1} \cdot x_{2} = 3$ , $u_{2} \cdot x_{1} = \frac{- 2 + 2 + 0}{2} = 0$ , $u_{2} \cdot x_{2} = 2$ . That is $R$ ✓, and the zero below the diagonal is exactly the statement $x_{1} ⊥ u_{2}$ . The diagonal: $r_{11} = 3 = ∥ v_{1} ∥$ and $r_{22} = 2 = ∥ v_{2} ∥$ ✓, both positive as the theorem requires.
Multiplying out, column $1$ of $QR$ is $3 u_{1} + 0 \cdot u_{2} = ⟨ 2, 2, 1 ⟩$ ✓ and column $2$ is $3 u_{1} + 2 u_{2} = ⟨ 2, 2, 1 ⟩ + ⟨ - 1, 1, 0 ⟩ = ⟨ 1, 3, 1 ⟩$ ✓.
(c) A tall $Q$ . $Q$ is $3 \times 2$ ; only square matrices have inverses. Concretely, its two columns span a plane in $R^{3}$ , so $Q$ is not onto and no matrix can undo it. What $Q$ does satisfy is $Q^{T} Q = I_{2}$ .
Now $Q^{T} x_{1} = ⟨ u_{1} \cdot x_{1}, u_{2} \cdot x_{1} ⟩ = ⟨ 3, 0 ⟩$ , so $Q Q^{T} x_{1} = Q ⟨ 3, 0 ⟩ = 3 u_{1} = x_{1}$ : the matrix fixes $x_{1}$ . And $Q^{T} n = ⟨ \frac{2 + 2 - 4}{3}, \frac{- 1 + 1 + 0}{2} ⟩ = ⟨ 0, 0 ⟩$ , so $Q Q^{T} n = 0$ .
Since $n$ is orthogonal to both columns of $A$ , it spans $(Col A)^{⊥}$ , which has dimension $3 - 2 = 1$ . A matrix that fixes $Col A$ (it fixes $x_{1}$ , and likewise $x_{2} = Q ⟨ 3, 2 ⟩$ ) and annihilates $(Col A)^{⊥}$ is the orthogonal projection onto $Col A$ — which is also what the formula $P = U U^{T}$ for orthonormal columns says. For the record,
$Q Q^{T} = u_{1} u_{1}^{T} + u_{2} u_{2}^{T} = \frac{1}{18} 17 - 1 4 - 1 174 442,$
symmetric with trace $\frac{36}{18} = 2 = dim Col A$ , and certainly not $I_{3}$ .
9.Critique
A student is asked for the least-squares solution of $A x = b$ , where
$A = 112 1 - 1 0, b = 132,$
and submits the following.
Step 1. The columns $a_{1} = ⟨ 1, 1, 2 ⟩$ and $a_{2} = ⟨ 1, - 1, 0 ⟩$ are orthogonal, so $A^{T} A$ is diagonal: $A^{T} A = diag (6, 2)$ .
Step 2. Because the columns are orthogonal, the least-squares solution can be read off by dot products, just as coordinates in an orthogonal basis are: $\overset{x}{^}_{1} = b \cdot a_{1} = 1 + 3 + 4 = 8$ and $\overset{x}{^}_{2} = b \cdot a_{2} = 1 - 3 + 0 = - 2$ .
Step 3. Check: $A \hat{x} = ⟨ 6, 10, 16 ⟩$ , which is not $b$ . But a least-squares solution is not supposed to satisfy $A x = b$ , so this is expected and confirms that nothing is wrong.
Step 4. The least-squares error is $∥ b - A \hat{x} ∥^{2} = 25 + 49 + 196 = 270$ .
Step 1 is correct. Each of the other three steps contains an error.
1. (a)For Steps 2, 3 and 4, name the error, state the correct principle that was misapplied, and say how the student could have detected the error of Step 2 from their own numbers.
2. (b)Solve the problem correctly: find $\hat{x}$ , the residual and the least-squares error, and perform the check that actually certifies a least-squares solution.
Solution
(a) Step 2 — the missing denominators. The principle is right: with orthogonal columns the normal equations decouple and $\hat{x}$ consists of the coefficients of $proj_{Col A} b$ in the orthogonal basis ${a_{1}, a_{2}}$ . But that coefficient formula is $c_{j} = \frac{b \cdot a _{j}}{a _{j} \cdot a _{j}}$ ; the version with no denominator is for orthonormal vectors only. Here $a_{1} \cdot a_{1} = 6$ and $a_{2} \cdot a_{2} = 2$ , so $8$ and $- 2$ are too large by exactly those factors. The student's own Step 1 contained the denominators: the normal equations read $diag (6, 2) \hat{x} = A^{T} b = ⟨ 8, - 2 ⟩$ , which forces $\hat{x} = ⟨ \frac{8}{6}, \frac{- 2}{2} ⟩$ .
Step 3 — a non-check. The statement $A \hat{x} \neq = b$ is true of every least-squares solution of an inconsistent system, so observing it cannot tell a right answer from a wrong one. The check that certifies a least-squares solution is $A^{T} (b - A \hat{x}) = 0$ : the residual must be orthogonal to every column. With the student's $\hat{x}$ the residual is $r = b - A \hat{x} = ⟨ - 5, - 7, - 14 ⟩$ and
$A^{T} r = ⟨ - 5 - 7 - 28, - 5 + 7 ⟩ = ⟨ - 40, 2 ⟩ \neq = 0,$
which would have exposed Step 2 at once. A cruder detector was also available: the student's error $∥ r ∥ = 270$ exceeds $∥ b ∥ = 14$ , yet $x = 0$ already achieves error $∥ b ∥$ , so no minimiser can do worse than that.
Step 4 — off by a square root. The least-squares error is the length $∥ b - A \hat{x} ∥$ . The squared length is the quantity being minimised, but the error reported is the norm. (And $270$ is built from the wrong $\hat{x}$ in any case.)
(b) The correct solution. Normal equations: $A^{T} A = diag (6, 2)$ and $A^{T} b = ⟨ 8, - 2 ⟩$ , so $\hat{x} = ⟨ \frac{4}{3}, - 1 ⟩$ . Then
$A \hat{x} = ⟨ \frac{4}{3} - 1, \frac{4}{3} + 1, \frac{8}{3} ⟩ = ⟨ \frac{1}{3}, \frac{7}{3}, \frac{8}{3} ⟩, r = b - A \hat{x} = ⟨ \frac{2}{3}, \frac{2}{3}, - \frac{2}{3} ⟩ .$
The certifying check: $A^{T} r = ⟨ \frac{2}{3} + \frac{2}{3} - \frac{4}{3}, \frac{2}{3} - \frac{2}{3} ⟩ = ⟨ 0, 0 ⟩$ ✓. The error is
$∥ r ∥ = 3 \cdot \frac{4}{9} = \frac{2}{3} = \frac{2 3}{3} .$
Cross-check by the Pythagorean shortcut: $∥ b ∥^{2} = 14$ and $∥ A \hat{x} ∥^{2} = \frac{1 + 49 + 64}{9} = \frac{38}{3}$ , and $14 - \frac{38}{3} = \frac{4}{3} = ∥ r ∥^{2}$ ✓.
10.Computation
Four measurements are taken: $(x, y) = (0, 1), (1, 3), (2, 2), (3, 6)$ . All arithmetic is exact; keep fractions.
1. (a)Set up the design matrix $X$ for the model $y = β_{0} + β_{1} x$ , form $X^{T} X$ and $X^{T} y$ , and solve the normal equations for $\hat{β}_{0}$ and $\hat{β}_{1}$ .
2. (b)Compute the four residuals and verify the identities $\sum r_{i} = 0$ and $\sum x_{i} r_{i} = 0$ , explaining where each comes from. Then find the least-squares error two ways: directly from the residuals, and from $∥ y ∥^{2} - ∥ X \hat{β} ∥^{2}$ .
3. (c)A colleague proposes the richer model $y = β_{0} + β_{1} x + β_{2} (2 x + 1)$ . Without solving anything new, explain what happens to $X^{T} X$ , describe the full set of least-squares solutions, and explain why the fitted values are the same as in (a).
Solution
(a) The normal equations. One row per observation, one column per parameter:
$X = 11110123, y = 1326 .$
The sums are $m = 4$ , $\sum x_{i} = 6$ , $\sum x_{i}^{2} = 0 + 1 + 4 + 9 = 14$ , $\sum y_{i} = 12$ , $\sum x_{i} y_{i} = 0 + 3 + 4 + 18 = 25$ , so
$X^{T} X = (46614), X^{T} y = (1225) .$
The determinant is $56 - 36 = 20$ , so $(X^{T} X)^{- 1} = \frac{1}{20} (14 - 6 - 6 4)$ and
$\hat{β} = \frac{1}{20} (14 \cdot 12 - 6 \cdot 25 - 6 \cdot 12 + 4 \cdot 25) = \frac{1}{20} (1828) = (9/10 7/5) .$
The fitted line is $y = \frac{9}{10} + \frac{7}{5} x$ . Check the first normal equation: $4 \cdot \frac{9}{10} + 6 \cdot \frac{7}{5} = \frac{18}{5} + \frac{42}{5} = 12$ ✓.
(b) Residuals. The fitted values at $x = 0, 1, 2, 3$ are $\frac{9}{10}, \frac{23}{10}, \frac{37}{10}, \frac{51}{10}$ , so
$r = y - X \hat{β} = ⟨ \frac{1}{10}, \frac{7}{10}, - \frac{17}{10}, \frac{9}{10} ⟩ .$
$\sum r_{i} = \frac{1 + 7 - 17 + 9}{10} = 0$ ✓ and $\sum x_{i} r_{i} = \frac{0 + 7 - 34 + 27}{10} = 0$ ✓. Both come from the normal equations in the form $X^{T} r = 0$ : the first row of $X^{T}$ is the column of ones, giving $\sum r_{i} = 0$ , and the second row is the column of $x$ -values, giving $\sum x_{i} r_{i} = 0$ . The residual is orthogonal to every column of the design matrix.
Error, directly. $∥ r ∥^{2} = \frac{1 + 49 + 289 + 81}{100} = \frac{420}{100} = \frac{21}{5}$ , so the least-squares error is $21/5 = \frac{105}{5}$ .
Error, by Pythagoras. $∥ y ∥^{2} = 1 + 9 + 4 + 36 = 50$ and $∥ X \hat{β} ∥^{2} = \frac{81 + 529 + 1369 + 2601}{100} = \frac{4580}{100} = \frac{229}{5}$ , and $50 - \frac{229}{5} = \frac{21}{5}$ ✓. The identity holds because $X \hat{β} ⊥ r$ .
(c) A redundant column. The new column has entries $2 x_{i} + 1$ , which is twice the $x$ -column plus the column of ones: the three columns are linearly dependent. By the lemma on $A^{T} A$ , $X^{T} X$ (now $3 \times 3$ ) is invertible if and only if the columns are independent, so it is singular. The normal equations are still consistent — they always are — but have infinitely many solutions.
To describe them, rewrite the model as $y = (β_{0} + β_{2}) + (β_{1} + 2 β_{2}) x$ : it is the same family of lines. So the least-squares solutions are exactly the triples with $β_{0} + β_{2} = \frac{9}{10}$ and $β_{1} + 2 β_{2} = \frac{7}{5}$ , the line
$\hat{β} = ⟨ \frac{9}{10}, \frac{7}{5}, 0 ⟩ + t ⟨ - 1, - 2, 1 ⟩, t \in R,$
where $⟨ - 1, - 2, 1 ⟩$ spans $Nul X$ (each row gives $- 1 - 2 x_{i} + (2 x_{i} + 1) = 0$ ✓).
The fitted values are $X \hat{β} = proj_{Col X} y$ , and this depends only on the subspace $Col X$ . Adding a column that already lies in the span of the old ones leaves $Col X$ unchanged, so the projection, the residuals and the error are all identical to (a). The projection is unique even when the coefficient vector is not.
11.Proof
Let $W$ be a subspace of $R^{n}$ and let $P$ be the matrix of orthogonal projection onto $W$ . You may use that $P$ is symmetric and idempotent, and the Orthogonal Decomposition Theorem.
1. (a)Prove that $∥ P y ∥ \leq ∥ y ∥$ for every $y$ , with equality if and only if $y \in W$ .
2. (b)Let $Q = I - P$ . Prove that $PQ = QP = 0$ and that $F = P - Q$ is symmetric and orthogonal. Determine $F w$ for $w \in W$ and $F z$ for $z \in W^{⊥}$ , and describe $F$ geometrically.
3. (c)Take $W = Span {u}$ with $u$ a unit vector, and let $H = Q - P = I - 2 u u^{T}$ . For $u = \frac{1}{3} ⟨ 2, - 1, 2 ⟩$ write $H$ out as a $3 \times 3$ matrix, verify $H u = - u$ and $H w = w$ for $w = ⟨ 1, 2, 0 ⟩$ , and compute $H y$ for $y = ⟨ 3, 0, 3 ⟩$ together with a check that its length is preserved.
Solution
(a) Projection shrinks. Write $y = P y + (y - P y)$ . The first piece lies in $W$ . The second lies in $W^{⊥}$ : for any $w = P u \in W$ ,
$(y - P y) \cdot P u = y^{T} (I - P)^{T} P u = y^{T} (P - P^{2}) u = 0,$
using symmetry and then idempotence. (Equivalently: this is the orthogonal decomposition of $y$ , with $P y = proj_{W} y$ .) The two pieces are orthogonal, so by the Pythagorean theorem
$∥ y ∥^{2} = ∥ P y ∥^{2} + ∥ y - P y ∥^{2} \geq ∥ P y ∥^{2},$
and taking square roots gives $∥ P y ∥ \leq ∥ y ∥$ .
Equality holds if and only if $∥ y - P y ∥ = 0$ , i.e. $y = P y$ , which places $y$ in $W$ . Conversely, if $y \in W$ then $y = y + 0$ is a decomposition with $y \in W$ and $0 \in W^{⊥}$ , so by uniqueness in the Orthogonal Decomposition Theorem $P y = y$ and equality holds. $■$
(b) A reflection. $PQ = P (I - P) = P - P^{2} = P - P = 0$ and $QP = (I - P) P = P - P^{2} = 0$ . Next $F = P - (I - P) = 2 P - I$ . Symmetry: $F^{T} = 2 P^{T} - I = 2 P - I = F$ . Orthogonality:
$F^{T} F = F^{2} = (2 P - I)^{2} = 4 P^{2} - 4 P + I = 4 P - 4 P + I = I . ■$
For $w \in W$ , $P w = w$ as in (a), so $F w = 2 w - w = w$ . For $z \in W^{⊥}$ the decomposition $z = 0 + z$ gives $P z = 0$ , so $F z = - z$ . Hence for a general $y = \hat{y} + z$ we get $F y = \hat{y} - z$ : $F$ keeps the component in $W$ and reverses the component in $W^{⊥}$ . It is the reflection of $R^{n}$ through $W$ . Being orthogonal it preserves lengths, which agrees with $∥ \hat{y} - z ∥^{2} = ∥ \hat{y} ∥^{2} + ∥ z ∥^{2} = ∥ \hat{y} + z ∥^{2}$ , and $F^{2} = I$ says reflecting twice is the identity. (Along the way: $Q = I - P$ is symmetric and idempotent with $Q z = z$ , $Q w = 0$ , so it is the projection onto $W^{⊥}$ .)
(c) A Householder reflection. For a line, $P = u u^{T}$ , so $H = Q - P = I - 2 u u^{T} = - F$ . It is symmetric and orthogonal with $H^{2} = I$ , and by (b) it sends $u \mapsto - u$ while fixing every vector orthogonal to $u$ : the reflection in the plane $u^{⊥}$ .
Numerically, $u u^{T} = \frac{1}{9} 4 - 2 4 - 2 1 - 2 4 - 2 4$ , so
$H = I - \frac{2}{9} 4 - 2 4 - 2 1 - 2 4 - 2 4 = \frac{1}{9} 14 - 8 474 - 8 41 .$
$H u = \frac{1}{9} \cdot \frac{1}{3} ⟨ 2 - 4 - 16, 8 - 7 + 8, - 16 - 4 + 2 ⟩ = \frac{1}{27} ⟨ - 18, 9, - 18 ⟩ = \frac{1}{3} ⟨ - 2, 1, - 2 ⟩ = - u$ ✓. For $w$ : $w \cdot u = \frac{2 - 2 + 0}{3} = 0$ , so $w \in u^{⊥}$ , and $H w = \frac{1}{9} ⟨ 1 + 8, 4 + 14, - 8 + 8 ⟩ = ⟨ 1, 2, 0 ⟩ = w$ ✓.
For $y$ use $H y = y - 2 (u \cdot y) u$ with $u \cdot y = \frac{6 + 0 + 6}{3} = 4$ :
$H y = ⟨ 3, 0, 3 ⟩ - \frac{8}{3} ⟨ 2, - 1, 2 ⟩ = ⟨ - \frac{7}{3}, \frac{8}{3}, - \frac{7}{3} ⟩ .$
(Matrix check: $\frac{1}{9} ⟨ 3 - 24, 12 + 12, - 24 + 3 ⟩ = \frac{1}{9} ⟨ - 21, 24, - 21 ⟩$ , the same.) Lengths: $∥ y ∥^{2} = 18$ and $∥ H y ∥^{2} = \frac{49 + 64 + 49}{9} = \frac{162}{9} = 18$ ✓, as an orthogonal matrix requires.
12.Proof
Let $A$ be an $m \times n$ matrix and $b \in R^{m}$ . Do not assume the columns of $A$ are independent unless a part says so. Name every theorem you use (Rank–Nullity, the fundamental orthogonality relations, the Pythagorean theorem, the normal-equations theorem).
1. (a)Prove that $Nul (A^{T} A) = Nul A$ , and deduce that $Col (A^{T} A) = Col (A^{T})$ . Conclude that the normal equations $A^{T} A x = A^{T} b$ are consistent for every $b$ .
2. (b)Prove that if $\hat{x}_{1}$ and $\hat{x}_{2}$ are both least-squares solutions then $A \hat{x}_{1} = A \hat{x}_{2}$ . Describe the complete set of least-squares solutions in terms of one of them and a subspace, and say when it is a single point.
3. (c)Let $\hat{x}$ be a least-squares solution and $r = b - A \hat{x}$ . Prove that $∥ b ∥^{2} = ∥ A \hat{x} ∥^{2} + ∥ r ∥^{2}$ , and deduce that the least-squares error equals $∥ b ∥$ exactly when $b \in Nul A^{T}$ .
Solution
(a) Null spaces. If $A x = 0$ then $A^{T} A x = A^{T} 0 = 0$ , so $Nul A \subseteq Nul (A^{T} A)$ . Conversely, if $A^{T} A x = 0$ , multiply on the left by $x^{T}$ :
$0 = x^{T} A^{T} A x = (A x) \cdot (A x) = ∥ A x ∥^{2},$
so $A x = 0$ by positive definiteness. Hence $Nul (A^{T} A) = Nul A$ .
Column spaces. $A^{T} A$ is $n \times n$ and $A^{T}$ is $n \times m$ , so both column spaces live inside $R^{n}$ and can be compared. By Rank–Nullity applied to the two $n$ -column matrices $A^{T} A$ and $A$ ,
$rank (A^{T} A) = n - dim Nul (A^{T} A) = n - dim Nul A = rank A,$
and $rank A = rank A^{T}$ because row rank equals column rank. Every vector of $Col (A^{T} A)$ has the form $A^{T} A x = A^{T} (A x)$ , so $Col (A^{T} A) \subseteq Col (A^{T})$ . A subspace contained in another of the same finite dimension equals it: $Col (A^{T} A) = Col (A^{T})$ .
Consistency. $A^{T} b \in Col (A^{T}) = Col (A^{T} A)$ , and membership in $Col (A^{T} A)$ is exactly the statement that $A^{T} A x = A^{T} b$ has a solution. $■$ (The projection proof of the same fact argues through $\hat{b} \in Col A$ ; this one never mentions a projection.)
(b) The projection is unique. By the normal-equations theorem, least-squares solutions are exactly the solutions of $A^{T} A x = A^{T} b$ . Subtracting the two equations, $A^{T} A (\hat{x}_{1} - \hat{x}_{2}) = 0$ , so $\hat{x}_{1} - \hat{x}_{2} \in Nul (A^{T} A) = Nul A$ by (a), i.e. $A \hat{x}_{1} = A \hat{x}_{2}$ . $■$
The same computation read backwards describes the whole set: if $\hat{x}$ is one least-squares solution and $v \in Nul A$ , then $A^{T} A (\hat{x} + v) = A^{T} A \hat{x} = A^{T} b$ , so $\hat{x} + v$ is another; and every other differs from $\hat{x}$ by an element of $Nul A$ . The set is the translate $\hat{x} + Nul A$ . It is a single point exactly when $Nul A = {0}$ , i.e. when the columns of $A$ are independent — which by the lemma on $A^{T} A$ is also exactly when $A^{T} A$ is invertible and $\hat{x} = (A^{T} A)^{- 1} A^{T} b$ .
(c) Pythagoras for the residual. The normal equations say $A^{T} r = A^{T} b - A^{T} A \hat{x} = 0$ . Therefore
$(A \hat{x}) \cdot r = (A \hat{x})^{T} r = \hat{x}^{T} (A^{T} r) = \hat{x}^{T} 0 = 0,$
so $A \hat{x} ⊥ r$ . Since $b = A \hat{x} + r$ , the Pythagorean theorem gives $∥ b ∥^{2} = ∥ A \hat{x} ∥^{2} + ∥ r ∥^{2}$ . $■$ (In particular $∥ r ∥ \leq ∥ b ∥$ always, as it must be, since $x = 0$ is a competitor with error $∥ b ∥$ .)
When the error is as bad as possible. By the identity, $∥ r ∥ = ∥ b ∥$ if and only if $∥ A \hat{x} ∥^{2} = 0$ , i.e. $A \hat{x} = 0$ . If that holds, then $A^{T} b = A^{T} A \hat{x} = 0$ , so $b \in Nul A^{T}$ . Conversely, if $A^{T} b = 0$ then $\hat{x} = 0$ solves the normal equations, so by (b) every least-squares solution has $A \hat{x} = 0$ and the error is $∥ b ∥$ . By the fundamental orthogonality relation $Nul A^{T} = (Col A)^{⊥}$ , so this is the case in which $b$ has no component in any direction the columns of $A$ can reach: the best the model can do is predict $0$ , and it explains nothing.

← Back to the question sheet