Linear Algebra (Full)

Question 1

(a) $|\mathbf{u}\cdot\mathbf{v}|\le\|\mathbf{u}\|\,\|\mathbf{v}\|$. [2]

(b) If $\mathbf{v}=\mathbf{0}$ trivial. Else define $f(t)=\|\mathbf{u}-t\mathbf{v}\|^2=\|\mathbf{u}\|^2-2t(\mathbf{u}\cdot\mathbf{v})+t^2\|\mathbf{v}\|^2\ge0$ for all $t$ [2] (norm-squared is nonneg). This is a quadratic in $t$ with positive leading coefficient that is never negative, so its discriminant $\le0$: [2] $4(\mathbf{u}\cdot\mathbf{v})^2-4\|\mathbf{v}\|^2\|\mathbf{u}\|^2\le0 \Rightarrow (\mathbf{u}\cdot\mathbf{v})^2\le\|\mathbf{u}\|^2\|\mathbf{v}\|^2$. Taking square roots gives the result. [2]

(c) Equality iff $f(t)=0$ for some $t$, i.e. $\mathbf{u}=t\mathbf{v}$ — the vectors are linearly dependent (parallel/antiparallel). [2]

Question 2

(a) Let $\{\mathbf{v}_1,\dots,\mathbf{v}_k\}$ be a basis of $\operatorname{Null} A$ ($k=\dim\operatorname{Null}A$). Extend to a basis $\{\mathbf{v}_1,\dots,\mathbf{v}_k,\mathbf{w}_1,\dots,\mathbf{w}_r\}$ of $\mathbb{R}^n$, so $k+r=n$. [2] Claim $\{A\mathbf{w}_1,\dots,A\mathbf{w}_r\}$ is a basis of $\operatorname{Col}A$. Spanning: any $A\mathbf{x}$ with $\mathbf{x}=\sum a_i\mathbf{v}_i+\sum b_j\mathbf{w}_j$ gives $A\mathbf{x}=\sum b_jA\mathbf{w}_j$ (since $A\mathbf{v}_i=0$). [2] Independence: if $\sum c_jA\mathbf{w}_j=0$ then $A(\sum c_j\mathbf{w}_j)=0$, so $\sum c_j\mathbf{w}_j\in\operatorname{Null}A=\operatorname{span}(\mathbf{v}_i)$, giving $\sum c_j\mathbf{w}_j=\sum d_i\mathbf{v}_i$. By independence of the full basis all $c_j=0$. [2] Hence $\operatorname{rank}A=r$ and $k+r=n$. [1]

(b) Row reduce: $R_2-2R_1$, $R_3+R_1$: $\begin{pmatrix}1&2&1&0\\0&0&1&1\\0&0&1&1\end{pmatrix}\to R_3-R_2\to\begin{pmatrix}1&2&1&0\\0&0&1&1\\0&0&0&0\end{pmatrix}$. Two pivots ⇒ $\operatorname{rank}=2$. [2] $\dim\operatorname{Null}=4-2=2$; check $2+2=4=n$. ✓ [1]

Question 3

(a) For $i=1,\dots,k$: $\mathbf{u}_i=\mathbf{a}_i-\sum_{j<i}\dfrac{\langle\mathbf{a}_i,\mathbf{q}_j\rangle}{1}\mathbf{q}_j$ (projections onto already-computed $\mathbf{q}_j$), then $\mathbf{q}_i=\mathbf{u}_i/\|\mathbf{u}_i\|$. [4]

(b) $\mathbf{q}_1=\frac{1}{\sqrt2}(1,1,0)^T$. [1] $\langle\mathbf{a}_2,\mathbf{q}_1\rangle=\frac{1}{\sqrt2}(1)= \frac{1}{\sqrt2}$. [1] $\mathbf{u}_2=(1,0,1)-\frac{1}{\sqrt2}\cdot\frac{1}{\sqrt2}(1,1,0)=(1,0,1)-(\tfrac12,\tfrac12,0)=(\tfrac12,-\tfrac12,1)$. [2] $\|\mathbf{u}_2\|=\sqrt{\tfrac14+\tfrac14+1}=\sqrt{3/2}$, so $\mathbf{q}_2=\sqrt{\tfrac23}(\tfrac12,-\tfrac12,1)=\frac{1}{\sqrt6}(1,-1,2)^T$. [1]

(c) Rearranging Gram–Schmidt, $\mathbf{a}_i=\sum_{j\le i}r_{ji}\mathbf{q}_j$ with $r_{ji}=\langle\mathbf{a}_i,\mathbf{q}_j\rangle$ and $r_{ii}=\|\mathbf{u}_i\|$. Since $\mathbf{a}_i$ is a combination of only $\mathbf{q}_1..\mathbf{q}_i$, the matrix $R=[r_{ji}]$ has zeros below the diagonal ⇒ upper triangular; $A=QR$ with $Q$ orthonormal columns. [3]

Question 4

(a) $\det(A-\lambda I)=(2-\lambda)^2-1=\lambda^2-4\lambda+3=(\lambda-1)(\lambda-3)$; eigenvalues $\lambda=1,3$. [3]

(b) $\lambda=3$: $(A-3I)=\begin{pmatrix}-1&1\\1&-1\end{pmatrix}$ ⇒ eigenvector $(1,1)^T$. [2] $\lambda=1$: $(A-I)=\begin{pmatrix}1&1\\1&1\end{pmatrix}$ ⇒ eigenvector $(1,-1)^T$. [2]

(c) Normalize: $P=\frac{1}{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}$, $D=\begin{pmatrix}3&0\\0&1\end{pmatrix}$, $A=PDP^{-1}=PDP^T$. [3]

(d) Key facts: symmetric matrices have all real eigenvalues; eigenvectors from distinct eigenvalues are orthogonal (from $\lambda\langle x,y\rangle=\langle Ax,y\rangle=\langle x,Ay\rangle=\mu\langle x,y\rangle$); repeated eigenvalues still yield orthogonal eigenbases within eigenspaces — combining gives an orthonormal eigenbasis, so $A=Q\Lambda Q^T$. [2]

Question 5

(a) $A=\begin{pmatrix}1&0\\1&1\\1&2\end{pmatrix}$, $\mathbf{b}=(1,3,4)^T$. Minimizing $E=\|A\mathbf{c}-\mathbf{b}\|^2$, $\nabla E=2A^T(A\mathbf{c}-\mathbf{b})=0\Rightarrow A^TA\mathbf{c}=A^T\mathbf{b}$. [4]

(b) $A^TA=\begin{pmatrix}3&3\\3&5\end{pmatrix}$, $A^T\mathbf{b}=\begin{pmatrix}8\\11\end{pmatrix}$. Solve: $\det=15-9=6$. $c_0=\frac{5\cdot8-3\cdot11}{6}=\frac{40-33}{6}=\frac{7}{6}$, $c_1=\frac{3\cdot11-3\cdot8}{6}=\frac{9}{6}=\frac{3}{2}$. [4]

(c) QR avoids forming $A^TA$, which squares the condition number and can lose precision; QR is numerically more stable. [2]

Question 6

(a) Expand along first column: $1\cdot(3\cdot1-1\cdot0)-0+2\cdot(2\cdot1-0\cdot3)=1\cdot3+2\cdot2=7$. [3]

(b) $D=\det\begin{pmatrix}1&2\\3&1\end{pmatrix}=1-6=-5$. $x=\dfrac{\det\begin{pmatrix}3&2\\5&1\end{pmatrix}}{-5}=\dfrac{3-10}{-5}=\dfrac{7}{5}$. [2] Geometric meaning: $D$ is the signed area of the parallelogram spanned by the coefficient columns; nonzero ⇒ unique solution. [1]

[
{"claim":"Q2 rank of A is 2","code":"A=Matrix([[1,2,1,0],[2,4,3,1],[-1,-2,0,1]]); result=(A.rank()==2)"},
{"claim":"Q2 nullity 2, theorem 2+2=4","code":"A=Matrix([[1,2,1,0],[2,4,3,1],[-1,-2,0,1]]); result=(len(A.nullspace())==2 and A.rank()+len(A.nullspace())==4)"},
{"claim":"Q3 q2 = (1,-1,2)/sqrt6 orthonormal to q1","code":"q1=Matrix([1,1,0])/sqrt(2); q2=Matrix([1,-1,2])/sqrt(6); result=(simplify(q1.dot(q2))==0 and simplify(q2.dot(q2))==1)"},
{"claim":"Q4 eigenvalues 1 and 3","code":"A=Matrix([[2,1],[1,2]]); result=(set(A.eigenvals().keys())=={1,3})"},
{"claim":"Q5 least squares c0=7/6, c1=3/2","code":"A=Matrix([[1,0],[1,1],[1,2]]); b=Matrix([1,3,4]); c=(A.T*A).inv()*A.T*b; result=(c[0]==Rational(7,6) and c[1]==Rational(3,2))"},
{"claim":"Q6 determinant equals 7","code":"M=Matrix([[1,2,0],[0,3,1],[2,0,1]]); result=(M.det()==7)"},
{"claim":"Q6 Cramer x = 7/5","code":"result=(Rational((3*1-2*5),(1*1-2*3))==Rational(7,5))"}
]