Print this page and work through it on paper. Revealed answers are never printed, so you can check one question and still print a clean sheet.

1. 1.Computation · 6 min

   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 $\mathbf{u}=⟨2,3,-6⟩$ and $\mathbf{v}=⟨6,-2,3⟩$. Compute $\Vert \mathbf{u}\Vert$, $\Vert \mathbf{v}\Vert$, $\mathrm{dist}(\mathbf{u},\mathbf{v})$ and $\cos \theta$ for the angle $\theta$ between them. Then confirm the distance a second way, using only the three numbers $\Vert \mathbf{u}\Vert$, $\Vert \mathbf{v}\Vert$ and $\mathbf{u}\cdot \mathbf{v}$.
   2. (b)Find every real $t$ for which $\mathbf{a}=⟨t,t,1⟩$ and $\mathbf{b}=⟨t,2,-3⟩$ are orthogonal, and check each value you find.
   3. (c)Let $\mathbf{w}=⟨2,-1,0,2⟩$ and $\mathbf{z}=⟨1,2,2,0⟩$ in ${\mathbb{R}}^4$. Show that $\mathbf{w}\perp \mathbf{z}$, then compute $\Vert \mathbf{w}+\mathbf{z}\Vert$ twice: once from the entries of $\mathbf{w}+\mathbf{z}$ and once without them. Explain why $\Vert \mathbf{w}+\mathbf{z}\Vert \ne \Vert \mathbf{w}\Vert +\Vert \mathbf{z}\Vert$ is not a contradiction.
   Show the solution to question 1

   (a) Lengths and angle. $\Vert \mathbf{u}{\Vert }^2=4+9+36=49$, so $\Vert \mathbf{u}\Vert =7$; likewise $\Vert \mathbf{v}{\Vert }^2=36+4+9=49$ and $\Vert \mathbf{v}\Vert =7$. The dot product is $\mathbf{u}\cdot \mathbf{v}=12-6-18=-12$, so

   $$\cos \theta =\frac{\mathbf{u}\cdot \mathbf{v}}{\Vert \mathbf{u}\Vert \Vert \mathbf{v}\Vert }=-\frac{12}{49},$$

   which is negative: the angle is obtuse. Cauchy–Schwarz is comfortably satisfied, $|-12|\le 49$, which is why a cosine came out.

   Distance directly. $\mathbf{u}-\mathbf{v}=⟨-4,5,-9⟩$, so $\Vert \mathbf{u}-\mathbf{v}{\Vert }^2=16+25+81=122$ and $\mathrm{dist}(\mathbf{u},\mathbf{v})=\sqrt{122}$.

   Distance from the three numbers. Expand with linearity and symmetry of the dot product:

   $$\Vert \mathbf{u}-\mathbf{v}{\Vert }^2=\mathbf{u}\cdot \mathbf{u}-2\mathbf{u}\cdot \mathbf{v}+\mathbf{v}\cdot \mathbf{v}=49+24+49=122.✓$$

   (b) One scalar equation. $\mathbf{a}\cdot \mathbf{b}=t^2+2t-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. $\mathbf{w}\cdot \mathbf{z}=2-2+0+0=0$, so $\mathbf{w}\perp \mathbf{z}$. From the entries, $\mathbf{w}+\mathbf{z}=⟨3,1,2,2⟩$ and $\Vert \mathbf{w}+\mathbf{z}{\Vert }^2=9+1+4+4=18$, so $\Vert \mathbf{w}+\mathbf{z}\Vert =3\sqrt{2}$.

   Without the entries: $\Vert \mathbf{w}{\Vert }^2=4+1+0+4=9$ and $\Vert \mathbf{z}{\Vert }^2=1+4+4+0=9$, and because the vectors are orthogonal the Pythagorean theorem gives $\Vert \mathbf{w}+\mathbf{z}{\Vert }^2=9+9=18$ ✓.

   Meanwhile $\Vert \mathbf{w}\Vert +\Vert \mathbf{z}\Vert =6\ne 3\sqrt{2}$. There is no contradiction: Pythagoras is a statement about squared lengths. The equation $\Vert \mathbf{w}+\mathbf{z}\Vert =\Vert \mathbf{w}\Vert +\Vert \mathbf{z}\Vert$ 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. 2.Computation · 7 min

   Let $W=\mathrm{Span}\{{\mathbf{w}}_1,{\mathbf{w}}_2\}\subseteq {\mathbb{R}}^4$ with ${\mathbf{w}}_1=⟨1,2,0,-1⟩$ and ${\mathbf{w}}_2=⟨0,1,1,1⟩$.

   1. (a)Find a basis for $W^{\perp }$. 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^{\perp }=4$.
   2. (b)Decide whether $\mathbf{y}=⟨5,-2,1,1⟩$ and ${\mathbf{y}}^{\prime }=⟨1,0,1,1⟩$ belong to $W^{\perp }$. 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 ${\mathbf{w}}_1$ and ${\mathbf{w}}_2$. Give the dimension of each of the four fundamental subspaces of $A$, identify which of them is $W^{\perp }$, and explain what the dimension of $\mathrm{Nul}{A}^T$ tells you about the system $A\mathbf{x}=\mathbf{b}$.
   Show the solution to question 2

   (a) Set up the equations. By the finite test for orthogonal complements — a vector is in $W^{\perp }$ if and only if it is orthogonal to each vector of a spanning set of $W$ — $\mathbf{v}=⟨v_1,v_2,v_3,v_4⟩$ lies in $W^{\perp }$ exactly when $\mathbf{v}\cdot {\mathbf{w}}_1=0$ and $\mathbf{v}\cdot {\mathbf{w}}_2=0$:

   $$v_1+2v_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 $\left(\begin{array}{cccc}1& 2& 0& -1\\ 0& 1& 1& 1\end{array}\right)$ into $\left(\begin{array}{cccc}1& 0& -2& -3\\ 0& 1& 1& 1\end{array}\right)$. Pivots sit in columns 1 and 2, so $v_3=s$ and $v_4=t$ are free, $v_1=2s+3t$ and $v_2=-s-t$:

   $$\mathbf{v}=s⟨2,-1,1,0⟩+t⟨3,-1,0,1⟩.$$

   A basis of $W^{\perp }$ 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 {\mathbf{w}}_1=2-2+0+0=0$, $⟨2,-1,1,0⟩\cdot {\mathbf{w}}_2=0-1+1+0=0$, $⟨3,-1,0,1⟩\cdot {\mathbf{w}}_1=3-2+0-1=0$, $⟨3,-1,0,1⟩\cdot {\mathbf{w}}_2=0-1+0+1=0$ ✓.

   Since ${\mathbf{w}}_1,{\mathbf{w}}_2$ are not multiples of each other, $\dim W=2$, and $\dim W^{\perp }=2$, so $2+2=4=n$ ✓, as the dimension theorem for complements requires.

   (b) Two membership tests. $\mathbf{y}\cdot {\mathbf{w}}_1=5-4+0-1=0$ and $\mathbf{y}\cdot {\mathbf{w}}_2=0-2+1+1=0$, so $\mathbf{y}\in W^{\perp }$. For ${\mathbf{y}}^{\prime }$: ${\mathbf{y}}^{\prime }\cdot {\mathbf{w}}_1=1+0+0-1=0$ but ${\mathbf{y}}^{\prime }\cdot {\mathbf{w}}_2=0+0+1+1=2\ne 0$, so ${\mathbf{y}}^{\prime }\notin W^{\perp }$ — one failed equation is enough.

   To express $\mathbf{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 $\mathrm{rank}A=2$, with $m=2$, $n=4$. Hence $\dim \mathrm{Row}A=2$ and $\dim \mathrm{Nul}A=4-2=2$ in ${\mathbb{R}}^4$; $\dim \mathrm{Col}A=2$ and $\dim \mathrm{Nul}{A}^T=2-2=0$ in ${\mathbb{R}}^2$.

   By the fundamental orthogonality relation $(\mathrm{Row}A{)}^{\perp }=\mathrm{Nul}A$, and $\mathrm{Row}A=W$, so $W^{\perp }=\mathrm{Nul}A$ — which is exactly the homogeneous system solved in (a).

   $\mathrm{Nul}{A}^T=\{0\}$ means $(\mathrm{Col}A{)}^{\perp }=\{0\}$, so $\mathrm{Col}A$ is all of ${\mathbb{R}}^2$: every $\mathbf{b}\in {\mathbb{R}}^2$ is reachable and $A\mathbf{x}=\mathbf{b}$ is consistent for every right-hand side. There is no direction in ${\mathbb{R}}^2$ that this matrix cannot reach, so least squares would never be needed for it.

3. 3.Computation · 7 min

   Let ${\mathbf{u}}_1=⟨2,2,1⟩$, ${\mathbf{u}}_2=⟨1,-2,2⟩$, ${\mathbf{u}}_3=⟨2,-1,-2⟩$ and $\mathbf{y}=⟨4,4,-7⟩$.

   1. (a)Show that $\{{\mathbf{u}}_1,{\mathbf{u}}_2,{\mathbf{u}}_3\}$ is an orthogonal basis of ${\mathbb{R}}^3$, quoting the theorem that spares you a row reduction, and write $\mathbf{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 ${\mathbf{u}}_1/3$, ${\mathbf{u}}_2/3$, ${\mathbf{u}}_3/3$. Explain, without multiplying anything out, why $Q^{T}Q=I$ and what $Q^{-1}$ is. Then solve $Q\mathbf{x}=\mathbf{y}$ and verify that $\Vert \mathbf{x}\Vert =\Vert \mathbf{y}\Vert$.
   3. (c)A classmate writes $\mathbf{y}=(\mathbf{y}\cdot {\mathbf{u}}_1){\mathbf{u}}_1+(\mathbf{y}\cdot {\mathbf{u}}_2){\mathbf{u}}_2+(\mathbf{y}\cdot {\mathbf{u}}_3){\mathbf{u}}_3$. Compute what the right-hand side actually equals, and say precisely which hypothesis of the formula they used is missing.
   Show the solution to question 3

   (a) Three dot products. ${\mathbf{u}}_1\cdot {\mathbf{u}}_2=2-4+2=0$, ${\mathbf{u}}_1\cdot {\mathbf{u}}_3=4-2-2=0$, ${\mathbf{u}}_2\cdot {\mathbf{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 ${\mathbb{R}}^3$ form a basis.

   Coefficients. In an orthogonal basis $c_j=\frac{\mathbf{y}\cdot {\mathbf{u}}_j}{{\mathbf{u}}_j\cdot {\mathbf{u}}_j}$. All three denominators equal $9$ ($4+4+1$, $1+4+4$, $4+1+4$). The numerators are

   $$\mathbf{y}\cdot {\mathbf{u}}_1=8+8-7=9,\mathbf{y}\cdot {\mathbf{u}}_2=4-8-14=-18,\mathbf{y}\cdot {\mathbf{u}}_3=8-4+14=18,$$

   so $c_1=1$, $c_2=-2$, $c_3=2$ and $\mathbf{y}={\mathbf{u}}_1-2{\mathbf{u}}_2+2{\mathbf{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 $\sqrt{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 $\mathbf{x}=Q^T\mathbf{y}$, whose entries are the dot products of $\mathbf{y}$ with the columns: $\mathbf{x}=\frac{1}{3}⟨9,-18,18⟩=⟨3,-6,6⟩$. Check: $Q\mathbf{x}=\frac{1}{3}(3{\mathbf{u}}_1-6{\mathbf{u}}_2+6{\mathbf{u}}_3)={\mathbf{u}}_1-2{\mathbf{u}}_2+2{\mathbf{u}}_3=\mathbf{y}$ ✓. Lengths: $\Vert \mathbf{x}{\Vert }^2=9+36+36=81$ and $\Vert \mathbf{y}{\Vert }^2=16+16+49=81$ ✓ — multiplication by a matrix with orthonormal columns preserves length. ($\mathbf{x}$ is just the coordinate vector of $\mathbf{y}$ in the orthonormal basis: each entry is $3c_j$.)

   (c) The missing denominators. The right-hand side is $9{\mathbf{u}}_1-18{\mathbf{u}}_2+18{\mathbf{u}}_3=9({\mathbf{u}}_1-2{\mathbf{u}}_2+2{\mathbf{u}}_3)=9\mathbf{y}=⟨36,36,-63⟩$, nine times too large. The formula $c_j=\mathbf{y}\cdot {\mathbf{u}}_j$ requires an orthonormal basis. These vectors are orthogonal but each has length $3$, so every coefficient is missing its denominator ${\mathbf{u}}_j\cdot {\mathbf{u}}_j=9$.

4. 4.Computation · 8 min

   Let $W=\mathrm{Span}\{{\mathbf{u}}_1,{\mathbf{u}}_2\}\subseteq {\mathbb{R}}^3$ with ${\mathbf{u}}_1=⟨1,0,-1⟩$ and ${\mathbf{u}}_2=⟨1,1,1⟩$, and let $\mathbf{y}=⟨2,0,4⟩$.

   1. (a)Verify that $\{{\mathbf{u}}_1,{\mathbf{u}}_2\}$ is an orthogonal basis of $W$, compute $\hat{\mathbf{y}}={\mathrm{proj}}_W\mathbf{y}$ and $\mathbf{z}=\mathbf{y}-\hat{\mathbf{y}}$, and find $\mathrm{dist}(\mathbf{y},W)$. Check that $\mathbf{z}\in W^{\perp }$ and check the identity $\Vert \mathbf{y}{\Vert }^2=\Vert \hat{\mathbf{y}}{\Vert }^2+\Vert \mathbf{z}{\Vert }^2$.
   2. (b)Find a vector $\mathbf{n}$ spanning $W^{\perp }$ and recompute $\mathbf{z}$ by projecting $\mathbf{y}$ onto the line through $\mathbf{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\mathbf{y}=\hat{\mathbf{y}}$, and identify $I-P$ in terms of $\mathbf{n}$.
   Show the solution to question 4

   (a) Project with the orthogonal basis. ${\mathbf{u}}_1\cdot {\mathbf{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{\mathbf{y}}=\frac{\mathbf{y}\cdot {\mathbf{u}}_1}{{\mathbf{u}}_1\cdot {\mathbf{u}}_1}{\mathbf{u}}_1+\frac{\mathbf{y}\cdot {\mathbf{u}}_2}{{\mathbf{u}}_2\cdot {\mathbf{u}}_2}{\mathbf{u}}_2=\frac{-2}{2}⟨1,0,-1⟩+\frac{6}{3}⟨1,1,1⟩=⟨1,2,3⟩,$$

   using $\mathbf{y}\cdot {\mathbf{u}}_1=2+0-4=-2$, ${\mathbf{u}}_1\cdot {\mathbf{u}}_1=2$, $\mathbf{y}\cdot {\mathbf{u}}_2=2+0+4=6$, ${\mathbf{u}}_2\cdot {\mathbf{u}}_2=3$. Then $\mathbf{z}=⟨2,0,4⟩-⟨1,2,3⟩=⟨1,-2,1⟩$ and, by the Best Approximation Theorem, $\mathrm{dist}(\mathbf{y},W)=\Vert \mathbf{z}\Vert =\sqrt{6}$.

   Checks: $\mathbf{z}\cdot {\mathbf{u}}_1=1-1=0$ and $\mathbf{z}\cdot {\mathbf{u}}_2=1-2+1=0$, so $\mathbf{z}\in W^{\perp }$ by the finite test ✓. Pythagoras: $\Vert \mathbf{y}{\Vert }^2=4+0+16=20$, $\Vert \hat{\mathbf{y}}{\Vert }^2=1+4+9=14$, $\Vert \mathbf{z}{\Vert }^2=6$, and $14+6=20$ ✓.

   (b) The complement route. $\mathbf{n}\perp {\mathbf{u}}_1$ gives $n_1-n_3=0$ and $\mathbf{n}\perp {\mathbf{u}}_2$ gives $n_1+n_2+n_3=0$, so $n_1=n_3=s$ and $n_2=-2s$: $\mathbf{n}=⟨1,-2,1⟩$ spans $W^{\perp }$, which has dimension $3-2=1$. Projecting onto that line,

   $${\mathrm{proj}}_{\mathbf{n}}\mathbf{y}=\frac{\mathbf{y}\cdot \mathbf{n}}{\mathbf{n}\cdot \mathbf{n}}\mathbf{n}=\frac{2+0+4}{6}⟨1,-2,1⟩=⟨1,-2,1⟩=\mathbf{z}✓,$$

   and $\hat{\mathbf{y}}=\mathbf{y}-\mathbf{z}=⟨1,2,3⟩$ again. The routes must agree by the uniqueness in the Orthogonal Decomposition Theorem: $\mathbf{y}=\hat{\mathbf{y}}+\mathbf{z}$ with $\hat{\mathbf{y}}\in W$ and $\mathbf{z}\in W^{\perp }$ can be done in only one way, and the $W^{\perp }$-component of $\mathbf{y}$ is by definition ${\mathrm{proj}}_{W^{\perp }}\mathbf{y}$, which is the projection onto the line through $\mathbf{n}$.

   (c) The matrix. With $U=[{\mathbf{u}}_1/\sqrt{2}{\mathbf{u}}_2/\sqrt{3}]$,

   $$P=U{U}^T=\frac{{\mathbf{u}}_1{\mathbf{u}}_1^T}{2}+\frac{{\mathbf{u}}_2{\mathbf{u}}_2^T}{3}=\frac{1}{6}\left(3\left(\begin{array}{ccc}1& 0& -1\\ 0& 0& 0\\ -1& 0& 1\end{array}\right)+2\left(\begin{array}{ccc}1& 1& 1\\ 1& 1& 1\\ 1& 1& 1\end{array}\right)\right)=\frac{1}{6}\left(\begin{array}{ccc}5& 2& -1\\ 2& 2& 2\\ -1& 2& 5\end{array}\right).$$

   Then $P\mathbf{y}=\frac{1}{6}⟨10+0-4,4+0+8,-2+0+20⟩=\frac{1}{6}⟨6,12,18⟩=⟨1,2,3⟩=\hat{\mathbf{y}}$ ✓. $P$ is visibly symmetric and $\mathrm{tr}P=\frac{12}{6}=2=\dim W$.

   Finally

   $$I-P=\frac{1}{6}\left(\begin{array}{ccc}1& -2& 1\\ -2& 4& -2\\ 1& -2& 1\end{array}\right)=\frac{\mathbf{n}{\mathbf{n}}^T}{\mathbf{n}\cdot \mathbf{n}},$$

   since $\mathbf{n}\cdot \mathbf{n}=6$: it is the projection matrix onto the line $W^{\perp }$, exactly as the theorem on symmetric idempotents promises.

5. 5.Sketch · 9 min

   Let $A=\left(\begin{array}{cc}1& 2\\ 3& 6\end{array}\right)$. 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 $\mathrm{Row}A$, $\mathrm{Nul}A$, $\mathrm{Col}A$ and $\mathrm{Nul}{A}^T$, state each dimension, and verify both fundamental orthogonality relations by a dot product.
   2. (b)Draw two copies of ${\mathbb{R}}^2$ side by side: the domain, showing $\mathrm{Row}A$ and $\mathrm{Nul}A$, and the codomain, showing $\mathrm{Col}A$ and $\mathrm{Nul}{A}^T$. In the domain draw $\mathbf{x}=⟨3,1⟩$ and its components ${\mathbf{x}}_r\in \mathrm{Row}A$ and ${\mathbf{x}}_n\in \mathrm{Nul}A$. In the codomain draw $A\mathbf{x}$, $A{\mathbf{x}}_r$ and $A{\mathbf{x}}_n$, and say what the picture shows about which part of $\mathbf{x}$ survives.
   3. (c)Add $\mathbf{b}=⟨1,1⟩$ to the codomain picture together with its components in $\mathrm{Col}A$ and in $\mathrm{Nul}{A}^T$. Explain from the picture why $A\mathbf{x}=\mathbf{b}$ has no solution, and find the vector of $\mathrm{Row}A$ that $A$ sends to the $\mathrm{Col}A$-component of $\mathbf{b}$.
   Show the solution to question 5

   (a) Four bases. The second row is three times the first, so $\mathrm{rank}A=1$ and each of the four subspaces is a line.

   $\mathrm{Row}A=\mathrm{Span}\{⟨1,2⟩\}$, dimension $1$. $\mathrm{Nul}A$: $x_1+2x_2=0$, so $\mathrm{Span}\{⟨-2,1⟩\}$, dimension $2-1=1$. $\mathrm{Col}A=\mathrm{Span}\{⟨1,3⟩\}$ (the second column is twice the first), dimension $1$. $\mathrm{Nul}{A}^T$: $A^T=\left(\begin{array}{cc}1& 3\\ 2& 6\end{array}\right)$ gives $y_1+3y_2=0$, so $\mathrm{Span}\{⟨-3,1⟩\}$, dimension $2-1=1$.

   Orthogonality: $⟨1,2⟩\cdot ⟨-2,1⟩=-2+2=0$, so $\mathrm{Row}A\perp \mathrm{Nul}A$; and $⟨1,3⟩\cdot ⟨-3,1⟩=-3+3=0$, so $\mathrm{Col}A\perp \mathrm{Nul}{A}^T$ ✓. In each copy of ${\mathbb{R}}^2$ the dimensions add to $1+1=2$.

   (b) The domain. Draw $\mathrm{Row}A$ as the line through the origin in direction $⟨1,2⟩$ (slope $2$) and $\mathrm{Nul}A$ as the line in direction $⟨-2,1⟩$ (slope $-\frac{1}{2}$); the two are perpendicular. Project $\mathbf{x}$ onto the row line:

   $${\mathbf{x}}_r=\frac{\mathbf{x}\cdot ⟨1,2⟩}{⟨1,2⟩\cdot ⟨1,2⟩}⟨1,2⟩=\frac{3+2}{5}⟨1,2⟩=⟨1,2⟩,{\mathbf{x}}_n=\mathbf{x}-{\mathbf{x}}_r=⟨2,-1⟩,$$

   and $⟨2,-1⟩=-⟨-2,1⟩$ does lie in $\mathrm{Nul}A$ ✓. Draw $\mathbf{x}$ from the origin to $(3,1)$, ${\mathbf{x}}_r$ along the row line to $(1,2)$, ${\mathbf{x}}_n$ along the null line to $(2,-1)$; $\mathbf{x}$ is the diagonal of the rectangle they span.

   The codomain. Draw $\mathrm{Col}A$ in direction $⟨1,3⟩$ (slope $3$) and $\mathrm{Nul}{A}^T$ in direction $⟨-3,1⟩$ (slope $-\frac{1}{3}$), again perpendicular. Compute

   $$A\mathbf{x}=⟨3+2,9+6⟩=⟨5,15⟩,A{\mathbf{x}}_r=⟨1+4,3+12⟩=⟨5,15⟩,A{\mathbf{x}}_n=⟨2-2,6-6⟩=⟨0,0⟩.$$

   So $A\mathbf{x}$ and $A{\mathbf{x}}_r$ are the same arrow, $5⟨1,3⟩$, lying on the $\mathrm{Col}A$ line, and $A{\mathbf{x}}_n$ is a dot at the origin. The picture says: the null-space component of $\mathbf{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 $\mathbf{b}$ onto $\mathrm{Col}A$:

   $$\hat{\mathbf{b}}=\frac{1+3}{1+9}⟨1,3⟩=⟨\frac{2}{5},\frac{6}{5}⟩,\mathbf{b}-\hat{\mathbf{b}}=⟨\frac{3}{5},-\frac{1}{5}⟩=-\frac{1}{5}⟨-3,1⟩\in \mathrm{Nul}{A}^T✓.$$

   Draw $\mathbf{b}$ to $(1,1)$, $\hat{\mathbf{b}}$ on the column line, and the short perpendicular leg from $\hat{\mathbf{b}}$ to $\mathbf{b}$ running parallel to $\mathrm{Nul}{A}^T$. Every vector $A\mathbf{x}$ lies on the line $\mathrm{Col}A$, and $\mathbf{b}$ does not: it has the nonzero component $⟨\frac{3}{5},-\frac{1}{5}⟩$ in the perpendicular direction $\mathrm{Nul}{A}^T$, which no input can produce. That is what inconsistency looks like.

   For the last part write ${\mathbf{x}}_r=t⟨1,2⟩$; then $A{\mathbf{x}}_r=t⟨5,15⟩$, and this equals $⟨\frac{2}{5},\frac{6}{5}⟩$ when $t=\frac{2}{25}$. So ${\mathbf{x}}_r=⟨\frac{2}{25},\frac{4}{25}⟩$. Check: $A{\mathbf{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 $\mathrm{Row}A$ is the shortest of them.)

6. 6.Proof · 10 min

   Work from the algebraic properties of the dot product (symmetry, linearity in each slot, positive definiteness) and from theorems you name explicitly. Throughout, $\{{\mathbf{u}}_1,\dots ,{\mathbf{u}}_p\}$ is an orthonormal set in ${\mathbb{R}}^n$.

   1. (a)Prove the polarization identity $\mathbf{u}\cdot \mathbf{v}=\frac{1}{4}\left(\Vert \mathbf{u}+\mathbf{v}{\Vert }^2-\Vert \mathbf{u}-\mathbf{v}{\Vert }^2\right)$. Then prove: if a square matrix $Q$ satisfies $\Vert Q\mathbf{x}\Vert =\Vert \mathbf{x}\Vert$ for every $\mathbf{x}$, then $Q$ is an orthogonal matrix.
   2. (b)Prove Bessel's inequality: for every $\mathbf{y}\in {\mathbb{R}}^n$, $\sum _{j=1}^p(\mathbf{y}\cdot {\mathbf{u}}_j{)}^2\le \Vert \mathbf{y}{\Vert }^2$, with equality if and only if $\mathbf{y}\in \mathrm{Span}\{{\mathbf{u}}_1,\dots ,{\mathbf{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$.
   Show the solution to question 6

   (a) Polarization. Expand both squares using linearity in each slot and symmetry:

   $$\Vert \mathbf{u}+\mathbf{v}{\Vert }^2=\mathbf{u}\cdot \mathbf{u}+2\mathbf{u}\cdot \mathbf{v}+\mathbf{v}\cdot \mathbf{v},\Vert \mathbf{u}-\mathbf{v}{\Vert }^2=\mathbf{u}\cdot \mathbf{u}-2\mathbf{u}\cdot \mathbf{v}+\mathbf{v}\cdot \mathbf{v}.$$

   Subtracting, the squared lengths cancel and $4\mathbf{u}\cdot \mathbf{v}$ remains; divide by $4$. $■$

   Length-preserving implies orthogonal. Let $\mathbf{x},\mathbf{y}$ be arbitrary. Apply polarization to $Q\mathbf{x}$ and $Q\mathbf{y}$, use linearity of $Q$, then the hypothesis:

   $$(Q\mathbf{x})\cdot (Q\mathbf{y})=\frac{1}{4}\left(\Vert Q(\mathbf{x}+\mathbf{y}){\Vert }^2-\Vert Q(\mathbf{x}-\mathbf{y}){\Vert }^2\right)=\frac{1}{4}\left(\Vert \mathbf{x}+\mathbf{y}{\Vert }^2-\Vert \mathbf{x}-\mathbf{y}{\Vert }^2\right)=\mathbf{x}\cdot \mathbf{y}.$$

   Now the $(i,j)$ entry of $Q^{T}Q$ is the dot product of columns $i$ and $j$ of $Q$, that is $(Q{\mathbf{e}}_i)\cdot (Q{\mathbf{e}}_j)={\mathbf{e}}_i\cdot {\mathbf{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{\mathbf{y}}={\sum }_j(\mathbf{y}\cdot {\mathbf{u}}_j){\mathbf{u}}_j$ and $\mathbf{z}=\mathbf{y}-\hat{\mathbf{y}}$. For each $k$,

   $$\mathbf{z}\cdot {\mathbf{u}}_k=\mathbf{y}\cdot {\mathbf{u}}_k-\sum _j(\mathbf{y}\cdot {\mathbf{u}}_j)({\mathbf{u}}_j\cdot {\mathbf{u}}_k)=\mathbf{y}\cdot {\mathbf{u}}_k-(\mathbf{y}\cdot {\mathbf{u}}_k)\cdot 1=0,$$

   because orthonormality kills every term with $j\ne k$ and leaves ${\mathbf{u}}_k\cdot {\mathbf{u}}_k=1$. As $\hat{\mathbf{y}}$ is a combination of the ${\mathbf{u}}_j$, linearity gives $\mathbf{z}\cdot \hat{\mathbf{y}}=0$. By the Pythagorean theorem,

   $$\Vert \mathbf{y}{\Vert }^2=\Vert \hat{\mathbf{y}}+\mathbf{z}{\Vert }^2=\Vert \hat{\mathbf{y}}{\Vert }^2+\Vert \mathbf{z}{\Vert }^2.$$

   Expanding $\Vert \hat{\mathbf{y}}{\Vert }^2=\hat{\mathbf{y}}\cdot \hat{\mathbf{y}}={\sum }_j{\sum }_k(\mathbf{y}\cdot {\mathbf{u}}_j)(\mathbf{y}\cdot {\mathbf{u}}_k)({\mathbf{u}}_j\cdot {\mathbf{u}}_k)={\sum }_j(\mathbf{y}\cdot {\mathbf{u}}_j{)}^2$ by the same orthonormality. Therefore

   $$\sum _{j=1}^p(\mathbf{y}\cdot {\mathbf{u}}_j{)}^2=\Vert \mathbf{y}{\Vert }^2-\Vert \mathbf{z}{\Vert }^2\le \Vert \mathbf{y}{\Vert }^2.$$

   Equality holds if and only if $\Vert \mathbf{z}{\Vert }^2=0$, if and only if $\mathbf{z}=0$ (positive definiteness), if and only if $\mathbf{y}=\hat{\mathbf{y}}$, which lies in the span. Conversely, if $\mathbf{y}={\sum }_j{c}_j{\mathbf{u}}_j$ is in the span, dotting with ${\mathbf{u}}_k$ gives $c_k=\mathbf{y}\cdot {\mathbf{u}}_k$ (the coefficient theorem for orthonormal bases), so $\mathbf{y}=\hat{\mathbf{y}}$, $\mathbf{z}=0$, and equality holds. $■$

   (In the language of projections, $\hat{\mathbf{y}}$ is ${\mathrm{proj}}_W\mathbf{y}$ for $W$ the span and $\mathbf{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=QQ=Q^{T}Q=I$. Example: $Q=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$, which is symmetric and whose columns ${\mathbf{e}}_2,{\mathbf{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: $\mathrm{diag}(1,-1)$, reflection in the $x$-axis.)

7. 7.Computation · 10 min

   Let ${\mathbf{x}}_1=⟨2,1,2⟩$, ${\mathbf{x}}_2=⟨1,1,0⟩$ and ${\mathbf{x}}_3=⟨0,1,1⟩$; you may take for granted that they form a basis of ${\mathbb{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 ${\mathbf{x}}_1,{\mathbf{x}}_2,{\mathbf{x}}_3$ to obtain an orthogonal basis $\{{\mathbf{v}}_1,{\mathbf{v}}_2,{\mathbf{v}}_3\}$ and then an orthonormal basis $\{{\mathbf{u}}_1,{\mathbf{u}}_2,{\mathbf{u}}_3\}$. Check every orthogonality you claim.
   2. (b)Express ${\mathbf{x}}_2$ and ${\mathbf{x}}_3$ as combinations of ${\mathbf{u}}_1,{\mathbf{u}}_2,{\mathbf{u}}_3$. Which of the ${\mathbf{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 ${\mathbf{x}}_3,{\mathbf{x}}_2,{\mathbf{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⟩$.
   Show the solution to question 7

   (a) Step 1. ${\mathbf{v}}_1={\mathbf{x}}_1=⟨2,1,2⟩$, with ${\mathbf{v}}_1\cdot {\mathbf{v}}_1=9$.

   Step 2. ${\mathbf{x}}_2\cdot {\mathbf{v}}_1=2+1+0=3$, so

   $${\mathbf{v}}_2={\mathbf{x}}_2-\frac{3}{9}{\mathbf{v}}_1=⟨1,1,0⟩-\frac{1}{3}⟨2,1,2⟩=⟨\frac{1}{3},\frac{2}{3},-\frac{2}{3}⟩.$$

   Rescale by $3$ to ${\mathbf{v}}_2=⟨1,2,-2⟩$: multiplying by a nonzero scalar changes neither the span nor orthogonality to ${\mathbf{v}}_1$. Check ${\mathbf{v}}_1\cdot {\mathbf{v}}_2=2+2-4=0$ ✓; note ${\mathbf{v}}_2\cdot {\mathbf{v}}_2=9$.

   Step 3. ${\mathbf{x}}_3\cdot {\mathbf{v}}_1=0+1+2=3$ and ${\mathbf{x}}_3\cdot {\mathbf{v}}_2=0+2-2=0$, so

   $${\mathbf{v}}_3={\mathbf{x}}_3-\frac{3}{9}{\mathbf{v}}_1-\frac{0}{9}{\mathbf{v}}_2=⟨0,1,1⟩-\frac{1}{3}⟨2,1,2⟩=⟨-\frac{2}{3},\frac{2}{3},\frac{1}{3}⟩,$$

   rescaled to ${\mathbf{v}}_3=⟨-2,2,1⟩$. Checks: ${\mathbf{v}}_3\cdot {\mathbf{v}}_1=-4+2+2=0$ ✓ and ${\mathbf{v}}_3\cdot {\mathbf{v}}_2=-2+4-2=0$ ✓. (Both projections were subtracted from the original ${\mathbf{x}}_3$, even though one of them happened to be zero.)

   All three vectors have squared length $9$, so the orthonormal basis is

   $${\mathbf{u}}_1=\frac{1}{3}⟨2,1,2⟩,{\mathbf{u}}_2=\frac{1}{3}⟨1,2,-2⟩,{\mathbf{u}}_3=\frac{1}{3}⟨-2,2,1⟩.$$

   (b) Coordinates by dot products. In an orthonormal basis the coefficient of ${\mathbf{u}}_j$ is the dot product with ${\mathbf{u}}_j$. For ${\mathbf{x}}_2$: ${\mathbf{x}}_2\cdot {\mathbf{u}}_1=\frac{3}{3}=1$, ${\mathbf{x}}_2\cdot {\mathbf{u}}_2=\frac{1+2+0}{3}=1$, ${\mathbf{x}}_2\cdot {\mathbf{u}}_3=\frac{-2+2+0}{3}=0$, so ${\mathbf{x}}_2={\mathbf{u}}_1+{\mathbf{u}}_2$. For ${\mathbf{x}}_3$: ${\mathbf{x}}_3\cdot {\mathbf{u}}_1=1$, ${\mathbf{x}}_3\cdot {\mathbf{u}}_2=0$, ${\mathbf{x}}_3\cdot {\mathbf{u}}_3=\frac{0+2+1}{3}=1$, so ${\mathbf{x}}_3={\mathbf{u}}_1+{\mathbf{u}}_3$. Checks: ${\mathbf{u}}_1+{\mathbf{u}}_2=\frac{1}{3}⟨3,3,0⟩=⟨1,1,0⟩$ ✓ and ${\mathbf{u}}_1+{\mathbf{u}}_3=\frac{1}{3}⟨0,3,3⟩=⟨0,1,1⟩$ ✓.

   That ${\mathbf{x}}_2$ uses no ${\mathbf{u}}_3$ was guaranteed in advance: the correctness theorem says $\mathrm{Span}\{{\mathbf{v}}_1,{\mathbf{v}}_2\}=\mathrm{Span}\{{\mathbf{x}}_1,{\mathbf{x}}_2\}$, so ${\mathbf{x}}_2\in \mathrm{Span}\{{\mathbf{u}}_1,{\mathbf{u}}_2\}$ — this is the triangular pattern that becomes the matrix $R$ in the $QR$ factorization. That ${\mathbf{x}}_3$ uses no ${\mathbf{u}}_2$ was not guaranteed; it is the accident ${\mathbf{x}}_3\perp {\mathbf{v}}_2$ discovered in step 3.

   (c) Reversed order. ${\mathbf{v}}_1={\mathbf{x}}_3=⟨0,1,1⟩$, ${\mathbf{v}}_1\cdot {\mathbf{v}}_1=2$, and ${\mathbf{x}}_2\cdot {\mathbf{v}}_1=0+1+0=1$, so

   $${\mathbf{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: ${\mathbf{v}}_3$ is ${\mathbf{x}}_1$ minus its projection onto $\mathrm{Span}\{{\mathbf{v}}_1,{\mathbf{v}}_2\}=\mathrm{Span}\{{\mathbf{x}}_3,{\mathbf{x}}_2\}$, so by the correctness theorem ${\mathbf{v}}_3$ lies in $\mathrm{Span}\{{\mathbf{x}}_2,{\mathbf{x}}_3{\}}^{\perp }$, 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 ${\mathbf{v}}_3\ne 0$ by the theorem's first claim. Hence ${\mathbf{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 ${\mathbb{R}}^3$: only the subspace is order-independent.

8. 8.Computation · 9 min

   Let $A=\left(\begin{array}{cc}2& 1\\ 2& 3\\ 1& 1\end{array}\right)$.

   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{\mathbf{x}}_1$ for the first column ${\mathbf{x}}_1$ of $A$ and $Q{Q}^T\mathbf{n}$ for $\mathbf{n}=⟨1,1,-4⟩$, and say what $Q{Q}^T$ is.
   Show the solution to question 8

   (a) Gram–Schmidt on the columns. ${\mathbf{x}}_1=⟨2,2,1⟩$ and ${\mathbf{x}}_2=⟨1,3,1⟩$ are not proportional, so the columns are independent and the theorem applies. ${\mathbf{v}}_1={\mathbf{x}}_1$, $\Vert {\mathbf{v}}_1\Vert =\sqrt{4+4+1}=3$, ${\mathbf{u}}_1=\frac{1}{3}⟨2,2,1⟩$. Then ${\mathbf{x}}_2\cdot {\mathbf{v}}_1=2+6+1=9$ and ${\mathbf{v}}_1\cdot {\mathbf{v}}_1=9$, so

   $${\mathbf{v}}_2={\mathbf{x}}_2-\frac{9}{9}{\mathbf{v}}_1=⟨-1,1,0⟩,\Vert {\mathbf{v}}_2\Vert =\sqrt{2},{\mathbf{u}}_2=\frac{1}{\sqrt{2}}⟨-1,1,0⟩.$$

   Check ${\mathbf{u}}_1\cdot {\mathbf{u}}_2=\frac{-2+2+0}{3\sqrt{2}}=0$ ✓.

   The factors. $r_{jk}={\mathbf{x}}_k\cdot {\mathbf{u}}_j$ for $j\le k$: $r_{11}={\mathbf{x}}_1\cdot {\mathbf{u}}_1=\frac{9}{3}=3$, $r_{12}={\mathbf{x}}_2\cdot {\mathbf{u}}_1=\frac{9}{3}=3$, $r_{22}={\mathbf{x}}_2\cdot {\mathbf{u}}_2=\frac{-1+3+0}{\sqrt{2}}=\frac{2}{\sqrt{2}}=\sqrt{2}$. So

   $$Q=\left(\begin{array}{cc}2/3& -1/\sqrt{2}\\ 2/3& 1/\sqrt{2}\\ 1/3& 0\end{array}\right),R=\left(\begin{array}{cc}3& 3\\ 0& \sqrt{2}\end{array}\right).$$

   (b) Checks. The rows of $Q^T$ are ${\mathbf{u}}_1^T$ and ${\mathbf{u}}_2^T$, so $Q^{T}A$ has entries ${\mathbf{u}}_1\cdot {\mathbf{x}}_1=3$, ${\mathbf{u}}_1\cdot {\mathbf{x}}_2=3$, ${\mathbf{u}}_2\cdot {\mathbf{x}}_1=\frac{-2+2+0}{\sqrt{2}}=0$, ${\mathbf{u}}_2\cdot {\mathbf{x}}_2=\sqrt{2}$. That is $R$ ✓, and the zero below the diagonal is exactly the statement ${\mathbf{x}}_1\perp {\mathbf{u}}_2$. The diagonal: $r_{11}=3=\Vert {\mathbf{v}}_1\Vert$ and $r_{22}=\sqrt{2}=\Vert {\mathbf{v}}_2\Vert$ ✓, both positive as the theorem requires.

   Multiplying out, column $1$ of $QR$ is $3{\mathbf{u}}_1+0\cdot {\mathbf{u}}_2=⟨2,2,1⟩$ ✓ and column $2$ is $3{\mathbf{u}}_1+\sqrt{2}{\mathbf{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 ${\mathbb{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{\mathbf{x}}_1=⟨{\mathbf{u}}_1\cdot {\mathbf{x}}_1,{\mathbf{u}}_2\cdot {\mathbf{x}}_1⟩=⟨3,0⟩$, so $Q{Q}^T{\mathbf{x}}_1=Q⟨3,0⟩=3{\mathbf{u}}_1={\mathbf{x}}_1$: the matrix fixes ${\mathbf{x}}_1$. And $Q^T\mathbf{n}=⟨\frac{2+2-4}{3},\frac{-1+1+0}{\sqrt{2}}⟩=⟨0,0⟩$, so $Q{Q}^T\mathbf{n}=0$.

   Since $\mathbf{n}$ is orthogonal to both columns of $A$, it spans $(\mathrm{Col}A{)}^{\perp }$, which has dimension $3-2=1$. A matrix that fixes $\mathrm{Col}A$ (it fixes ${\mathbf{x}}_1$, and likewise ${\mathbf{x}}_2=Q⟨3,\sqrt{2}⟩$) and annihilates $(\mathrm{Col}A{)}^{\perp }$ is the orthogonal projection onto $\mathrm{Col}A$ — which is also what the formula $P=U{U}^T$ for orthonormal columns says. For the record,

   $$Q{Q}^T={\mathbf{u}}_1{\mathbf{u}}_1^T+{\mathbf{u}}_2{\mathbf{u}}_2^T=\frac{1}{18}\left(\begin{array}{ccc}17& -1& 4\\ -1& 17& 4\\ 4& 4& 2\end{array}\right),$$

   symmetric with trace $\frac{36}{18}=2=\dim \mathrm{Col}A$, and certainly not $I_3$.

9. 9.Critique · 8 min

   A student is asked for the least-squares solution of $A\mathbf{x}=\mathbf{b}$, where

   $$A=\left(\begin{array}{cc}1& 1\\ 1& -1\\ 2& 0\end{array}\right),\mathbf{b}=\left(\begin{array}{c}1\\ 3\\ 2\end{array}\right),$$

   and submits the following.

   Step 1. The columns ${\mathbf{a}}_1=⟨1,1,2⟩$ and ${\mathbf{a}}_2=⟨1,-1,0⟩$ are orthogonal, so $A^{T}A$ is diagonal: $A^{T}A=\mathrm{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: ${\hat{x}}_1=\mathbf{b}\cdot {\mathbf{a}}_1=1+3+4=8$ and ${\hat{x}}_2=\mathbf{b}\cdot {\mathbf{a}}_2=1-3+0=-2$.

   Step 3. Check: $A\hat{\mathbf{x}}=⟨6,10,16⟩$, which is not $\mathbf{b}$. But a least-squares solution is not supposed to satisfy $A\mathbf{x}=\mathbf{b}$, so this is expected and confirms that nothing is wrong.

   Step 4. The least-squares error is $\Vert \mathbf{b}-A\hat{\mathbf{x}}{\Vert }^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{\mathbf{x}}$, the residual and the least-squares error, and perform the check that actually certifies a least-squares solution.
   Show the solution to question 9

   (a) Step 2 — the missing denominators. The principle is right: with orthogonal columns the normal equations decouple and $\hat{\mathbf{x}}$ consists of the coefficients of ${\mathrm{proj}}_{\mathrm{Col}A}\mathbf{b}$ in the orthogonal basis $\{{\mathbf{a}}_1,{\mathbf{a}}_2\}$. But that coefficient formula is $c_j=\frac{\mathbf{b}\cdot {\mathbf{a}}_j}{{\mathbf{a}}_j\cdot {\mathbf{a}}_j}$; the version with no denominator is for orthonormal vectors only. Here ${\mathbf{a}}_1\cdot {\mathbf{a}}_1=6$ and ${\mathbf{a}}_2\cdot {\mathbf{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 $\mathrm{diag}(6,2)\hat{\mathbf{x}}=A^T\mathbf{b}=⟨8,-2⟩$, which forces $\hat{\mathbf{x}}=⟨\frac{8}{6},\frac{-2}{2}⟩$.

   Step 3 — a non-check. The statement $A\hat{\mathbf{x}}\ne \mathbf{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(\mathbf{b}-A\hat{\mathbf{x}})=0$: the residual must be orthogonal to every column. With the student's $\hat{\mathbf{x}}$ the residual is $\mathbf{r}=\mathbf{b}-A\hat{\mathbf{x}}=⟨-5,-7,-14⟩$ and

   $$A^T\mathbf{r}=⟨-5-7-28,-5+7⟩=⟨-40,2⟩\ne 0,$$

   which would have exposed Step 2 at once. A cruder detector was also available: the student's error $\Vert \mathbf{r}\Vert =\sqrt{270}$ exceeds $\Vert \mathbf{b}\Vert =\sqrt{14}$, yet $\mathbf{x}=0$ already achieves error $\Vert \mathbf{b}\Vert$, so no minimiser can do worse than that.

   Step 4 — off by a square root. The least-squares error is the length $\Vert \mathbf{b}-A\hat{\mathbf{x}}\Vert$. The squared length is the quantity being minimised, but the error reported is the norm. (And $270$ is built from the wrong $\hat{\mathbf{x}}$ in any case.)

   (b) The correct solution. Normal equations: $A^{T}A=\mathrm{diag}(6,2)$ and $A^T\mathbf{b}=⟨8,-2⟩$, so $\hat{\mathbf{x}}=⟨\frac{4}{3},-1⟩$. Then

   $$A\hat{\mathbf{x}}=⟨\frac{4}{3}-1,\frac{4}{3}+1,\frac{8}{3}⟩=⟨\frac{1}{3},\frac{7}{3},\frac{8}{3}⟩,\mathbf{r}=\mathbf{b}-A\hat{\mathbf{x}}=⟨\frac{2}{3},\frac{2}{3},-\frac{2}{3}⟩.$$

   The certifying check: $A^T\mathbf{r}=⟨\frac{2}{3}+\frac{2}{3}-\frac{4}{3},\frac{2}{3}-\frac{2}{3}⟩=⟨0,0⟩$ ✓. The error is

   $$\Vert \mathbf{r}\Vert =\sqrt{3\cdot \frac{4}{9}}=\frac{2}{\sqrt{3}}=\frac{2\sqrt{3}}{3}.$$

   Cross-check by the Pythagorean shortcut: $\Vert \mathbf{b}{\Vert }^2=14$ and $\Vert A\hat{\mathbf{x}}{\Vert }^2=\frac{1+49+64}{9}=\frac{38}{3}$, and $14-\frac{38}{3}=\frac{4}{3}=\Vert \mathbf{r}{\Vert }^2$ ✓.

10. 10.Computation · 11 min

    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={\beta }_0+{\beta }_{1}x$, form $X^{T}X$ and $X^T\mathbf{y}$, and solve the normal equations for ${\hat{\beta }}_0$ and ${\hat{\beta }}_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 $\Vert \mathbf{y}{\Vert }^2-\Vert X\hat{\mathbf{\beta }}{\Vert }^2$.
    3. (c)A colleague proposes the richer model $y={\beta }_0+{\beta }_{1}x+{\beta }_2(2x+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).
    Show the solution to question 10

    (a) The normal equations. One row per observation, one column per parameter:

    $$X=\left(\begin{array}{cc}1& 0\\ 1& 1\\ 1& 2\\ 1& 3\end{array}\right),\mathbf{y}=\left(\begin{array}{c}1\\ 3\\ 2\\ 6\end{array}\right).$$

    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=\left(\begin{array}{cc}4& 6\\ 6& 14\end{array}\right),X^T\mathbf{y}=\left(\begin{array}{c}12\\ 25\end{array}\right).$$

    The determinant is $56-36=20$, so $(X^{T}X{)}^{-1}=\frac{1}{20}\left(\begin{array}{cc}14& -6\\ -6& 4\end{array}\right)$ and

    $$\hat{\mathbf{\beta }}=\frac{1}{20}\left(\begin{array}{c}14\cdot 12-6\cdot 25\\ -6\cdot 12+4\cdot 25\end{array}\right)=\frac{1}{20}\left(\begin{array}{c}18\\ 28\end{array}\right)=\left(\begin{array}{c}9/10\\ 7/5\end{array}\right).$$

    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

    $$\mathbf{r}=\mathbf{y}-X\hat{\mathbf{\beta }}=⟨\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\mathbf{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. $\Vert \mathbf{r}{\Vert }^2=\frac{1+49+289+81}{100}=\frac{420}{100}=\frac{21}{5}$, so the least-squares error is $\sqrt{21/5}=\frac{\sqrt{105}}{5}$.

    Error, by Pythagoras. $\Vert \mathbf{y}{\Vert }^2=1+9+4+36=50$ and $\Vert X\hat{\mathbf{\beta }}{\Vert }^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{\mathbf{\beta }}\perp \mathbf{r}$.

    (c) A redundant column. The new column has entries $2x_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=({\beta }_0+{\beta }_2)+({\beta }_1+2{\beta }_2)x$: it is the same family of lines. So the least-squares solutions are exactly the triples with ${\beta }_0+{\beta }_2=\frac{9}{10}$ and ${\beta }_1+2{\beta }_2=\frac{7}{5}$, the line

    $$\hat{\mathbf{\beta }}=⟨\frac{9}{10},\frac{7}{5},0⟩+t⟨-1,-2,1⟩,t\in \mathbb{R},$$

    where $⟨-1,-2,1⟩$ spans $\mathrm{Nul}X$ (each row gives $-1-2x_i+(2x_i+1)=0$ ✓).

    The fitted values are $X\hat{\mathbf{\beta }}={\mathrm{proj}}_{\mathrm{Col}X}\mathbf{y}$, and this depends only on the subspace $\mathrm{Col}X$. Adding a column that already lies in the span of the old ones leaves $\mathrm{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. 11.Proof · 12 min

    Let $W$ be a subspace of ${\mathbb{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 $\Vert P\mathbf{y}\Vert \le \Vert \mathbf{y}\Vert$ for every $\mathbf{y}$, with equality if and only if $\mathbf{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\mathbf{w}$ for $\mathbf{w}\in W$ and $F\mathbf{z}$ for $\mathbf{z}\in W^{\perp }$, and describe $F$ geometrically.
    3. (c)Take $W=\mathrm{Span}\{\mathbf{u}\}$ with $\mathbf{u}$ a unit vector, and let $H=Q-P=I-2\mathbf{u}{\mathbf{u}}^T$. For $\mathbf{u}=\frac{1}{3}⟨2,-1,2⟩$ write $H$ out as a $3\times 3$ matrix, verify $H\mathbf{u}=-\mathbf{u}$ and $H\mathbf{w}=\mathbf{w}$ for $\mathbf{w}=⟨1,2,0⟩$, and compute $H\mathbf{y}$ for $\mathbf{y}=⟨3,0,3⟩$ together with a check that its length is preserved.
    Show the solution to question 11

    (a) Projection shrinks. Write $\mathbf{y}=P\mathbf{y}+(\mathbf{y}-P\mathbf{y})$. The first piece lies in $W$. The second lies in $W^{\perp }$: for any $\mathbf{w}=P\mathbf{u}\in W$,

    $$(\mathbf{y}-P\mathbf{y})\cdot P\mathbf{u}={\mathbf{y}}^T(I-P{)}^{T}P\mathbf{u}={\mathbf{y}}^T(P-P^2)\mathbf{u}=0,$$

    using symmetry and then idempotence. (Equivalently: this is the orthogonal decomposition of $\mathbf{y}$, with $P\mathbf{y}={\mathrm{proj}}_W\mathbf{y}$.) The two pieces are orthogonal, so by the Pythagorean theorem

    $$\Vert \mathbf{y}{\Vert }^2=\Vert P\mathbf{y}{\Vert }^2+\Vert \mathbf{y}-P\mathbf{y}{\Vert }^2\ge \Vert P\mathbf{y}{\Vert }^2,$$

    and taking square roots gives $\Vert P\mathbf{y}\Vert \le \Vert \mathbf{y}\Vert$.

    Equality holds if and only if $\Vert \mathbf{y}-P\mathbf{y}\Vert =0$, i.e. $\mathbf{y}=P\mathbf{y}$, which places $\mathbf{y}$ in $W$. Conversely, if $\mathbf{y}\in W$ then $\mathbf{y}=\mathbf{y}+0$ is a decomposition with $\mathbf{y}\in W$ and $0\in W^{\perp }$, so by uniqueness in the Orthogonal Decomposition Theorem $P\mathbf{y}=\mathbf{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)=2P-I$. Symmetry: $F^T=2P^T-I=2P-I=F$. Orthogonality:

    $$F^{T}F=F^2=(2P-I{)}^2=4P^2-4P+I=4P-4P+I=I.■$$

    For $\mathbf{w}\in W$, $P\mathbf{w}=\mathbf{w}$ as in (a), so $F\mathbf{w}=2\mathbf{w}-\mathbf{w}=\mathbf{w}$. For $\mathbf{z}\in W^{\perp }$ the decomposition $\mathbf{z}=0+\mathbf{z}$ gives $P\mathbf{z}=0$, so $F\mathbf{z}=-\mathbf{z}$. Hence for a general $\mathbf{y}=\hat{\mathbf{y}}+\mathbf{z}$ we get $F\mathbf{y}=\hat{\mathbf{y}}-\mathbf{z}$: $F$ keeps the component in $W$ and reverses the component in $W^{\perp }$. It is the reflection of ${\mathbb{R}}^n$ through $W$. Being orthogonal it preserves lengths, which agrees with $\Vert \hat{\mathbf{y}}-\mathbf{z}{\Vert }^2=\Vert \hat{\mathbf{y}}{\Vert }^2+\Vert \mathbf{z}{\Vert }^2=\Vert \hat{\mathbf{y}}+\mathbf{z}{\Vert }^2$, and $F^2=I$ says reflecting twice is the identity. (Along the way: $Q=I-P$ is symmetric and idempotent with $Q\mathbf{z}=\mathbf{z}$, $Q\mathbf{w}=0$, so it is the projection onto $W^{\perp }$.)

    (c) A Householder reflection. For a line, $P=\mathbf{u}{\mathbf{u}}^T$, so $H=Q-P=I-2\mathbf{u}{\mathbf{u}}^T=-F$. It is symmetric and orthogonal with $H^2=I$, and by (b) it sends $\mathbf{u}\mapsto -\mathbf{u}$ while fixing every vector orthogonal to $\mathbf{u}$: the reflection in the plane ${\mathbf{u}}^{\perp }$.

    Numerically, $\mathbf{u}{\mathbf{u}}^T=\frac{1}{9}\left(\begin{array}{ccc}4& -2& 4\\ -2& 1& -2\\ 4& -2& 4\end{array}\right)$, so

    $$H=I-\frac{2}{9}\left(\begin{array}{ccc}4& -2& 4\\ -2& 1& -2\\ 4& -2& 4\end{array}\right)=\frac{1}{9}\left(\begin{array}{ccc}1& 4& -8\\ 4& 7& 4\\ -8& 4& 1\end{array}\right).$$

    $H\mathbf{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⟩=-\mathbf{u}$ ✓. For $\mathbf{w}$: $\mathbf{w}\cdot \mathbf{u}=\frac{2-2+0}{3}=0$, so $\mathbf{w}\in {\mathbf{u}}^{\perp }$, and $H\mathbf{w}=\frac{1}{9}⟨1+8,4+14,-8+8⟩=⟨1,2,0⟩=\mathbf{w}$ ✓.

    For $\mathbf{y}$ use $H\mathbf{y}=\mathbf{y}-2(\mathbf{u}\cdot \mathbf{y})\mathbf{u}$ with $\mathbf{u}\cdot \mathbf{y}=\frac{6+0+6}{3}=4$:

    $$H\mathbf{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: $\Vert \mathbf{y}{\Vert }^2=18$ and $\Vert H\mathbf{y}{\Vert }^2=\frac{49+64+49}{9}=\frac{162}{9}=18$ ✓, as an orthogonal matrix requires.

12. 12.Proof · 11 min

    Let $A$ be an $m\times n$ matrix and $\mathbf{b}\in {\mathbb{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 $\mathrm{Nul}(A^{T}A)=\mathrm{Nul}A$, and deduce that $\mathrm{Col}(A^{T}A)=\mathrm{Col}(A^T)$. Conclude that the normal equations $A^{T}A\mathbf{x}=A^T\mathbf{b}$ are consistent for every $\mathbf{b}$.
    2. (b)Prove that if ${\hat{\mathbf{x}}}_1$ and ${\hat{\mathbf{x}}}_2$ are both least-squares solutions then $A{\hat{\mathbf{x}}}_1=A{\hat{\mathbf{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{\mathbf{x}}$ be a least-squares solution and $\mathbf{r}=\mathbf{b}-A\hat{\mathbf{x}}$. Prove that $\Vert \mathbf{b}{\Vert }^2=\Vert A\hat{\mathbf{x}}{\Vert }^2+\Vert \mathbf{r}{\Vert }^2$, and deduce that the least-squares error equals $\Vert \mathbf{b}\Vert$ exactly when $\mathbf{b}\in \mathrm{Nul}{A}^T$.
    Show the solution to question 12

    (a) Null spaces. If $A\mathbf{x}=0$ then $A^{T}A\mathbf{x}=A^{T}0=0$, so $\mathrm{Nul}A\subseteq \mathrm{Nul}(A^{T}A)$. Conversely, if $A^{T}A\mathbf{x}=0$, multiply on the left by ${\mathbf{x}}^T$:

    $$0={\mathbf{x}}^T{A}^{T}A\mathbf{x}=(A\mathbf{x})\cdot (A\mathbf{x})=\Vert A\mathbf{x}{\Vert }^2,$$

    so $A\mathbf{x}=0$ by positive definiteness. Hence $\mathrm{Nul}(A^{T}A)=\mathrm{Nul}A$.

    Column spaces. $A^{T}A$ is $n\times n$ and $A^T$ is $n\times m$, so both column spaces live inside ${\mathbb{R}}^n$ and can be compared. By Rank–Nullity applied to the two $n$-column matrices $A^{T}A$ and $A$,

    $$\mathrm{rank}(A^{T}A)=n-\dim \mathrm{Nul}(A^{T}A)=n-\dim \mathrm{Nul}A=\mathrm{rank}A,$$

    and $\mathrm{rank}A=\mathrm{rank}{A}^T$ because row rank equals column rank. Every vector of $\mathrm{Col}(A^{T}A)$ has the form $A^{T}A\mathbf{x}=A^T(A\mathbf{x})$, so $\mathrm{Col}(A^{T}A)\subseteq \mathrm{Col}(A^T)$. A subspace contained in another of the same finite dimension equals it: $\mathrm{Col}(A^{T}A)=\mathrm{Col}(A^T)$.

    Consistency. $A^T\mathbf{b}\in \mathrm{Col}(A^T)=\mathrm{Col}(A^{T}A)$, and membership in $\mathrm{Col}(A^{T}A)$ is exactly the statement that $A^{T}A\mathbf{x}=A^T\mathbf{b}$ has a solution. $■$ (The projection proof of the same fact argues through $\hat{\mathbf{b}}\in \mathrm{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\mathbf{x}=A^T\mathbf{b}$. Subtracting the two equations, $A^{T}A({\hat{\mathbf{x}}}_1-{\hat{\mathbf{x}}}_2)=0$, so ${\hat{\mathbf{x}}}_1-{\hat{\mathbf{x}}}_2\in \mathrm{Nul}(A^{T}A)=\mathrm{Nul}A$ by (a), i.e. $A{\hat{\mathbf{x}}}_1=A{\hat{\mathbf{x}}}_2$. $■$

    The same computation read backwards describes the whole set: if $\hat{\mathbf{x}}$ is one least-squares solution and $\mathbf{v}\in \mathrm{Nul}A$, then $A^{T}A(\hat{\mathbf{x}}+\mathbf{v})=A^{T}A\hat{\mathbf{x}}=A^T\mathbf{b}$, so $\hat{\mathbf{x}}+\mathbf{v}$ is another; and every other differs from $\hat{\mathbf{x}}$ by an element of $\mathrm{Nul}A$. The set is the translate $\hat{\mathbf{x}}+\mathrm{Nul}A$. It is a single point exactly when $\mathrm{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{\mathbf{x}}=(A^{T}A{)}^{-1}{A}^T\mathbf{b}$.

    (c) Pythagoras for the residual. The normal equations say $A^T\mathbf{r}=A^T\mathbf{b}-A^{T}A\hat{\mathbf{x}}=0$. Therefore

    $$(A\hat{\mathbf{x}})\cdot \mathbf{r}=(A\hat{\mathbf{x}}{)}^T\mathbf{r}={\hat{\mathbf{x}}}^T(A^T\mathbf{r})={\hat{\mathbf{x}}}^{T}0=0,$$

    so $A\hat{\mathbf{x}}\perp \mathbf{r}$. Since $\mathbf{b}=A\hat{\mathbf{x}}+\mathbf{r}$, the Pythagorean theorem gives $\Vert \mathbf{b}{\Vert }^2=\Vert A\hat{\mathbf{x}}{\Vert }^2+\Vert \mathbf{r}{\Vert }^2$. $■$ (In particular $\Vert \mathbf{r}\Vert \le \Vert \mathbf{b}\Vert$ always, as it must be, since $\mathbf{x}=0$ is a competitor with error $\Vert \mathbf{b}\Vert$.)

    When the error is as bad as possible. By the identity, $\Vert \mathbf{r}\Vert =\Vert \mathbf{b}\Vert$ if and only if $\Vert A\hat{\mathbf{x}}{\Vert }^2=0$, i.e. $A\hat{\mathbf{x}}=0$. If that holds, then $A^T\mathbf{b}=A^{T}A\hat{\mathbf{x}}=0$, so $\mathbf{b}\in \mathrm{Nul}{A}^T$. Conversely, if $A^T\mathbf{b}=0$ then $\hat{\mathbf{x}}=0$ solves the normal equations, so by (b) every least-squares solution has $A\hat{\mathbf{x}}=0$ and the error is $\Vert \mathbf{b}\Vert$. By the fundamental orthogonality relation $\mathrm{Nul}{A}^T=(\mathrm{Col}A{)}^{\perp }$, so this is the case in which $\mathbf{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.