Linear Algebra Essentials

Question 1

(a) [6 marks] Let $Ax=\lambda x$, $x\neq0$. Take conjugate transpose: $x^* A = \bar\lambda x^*$ (using $A$ real symmetric so $A^*=A$). Then $x^*Ax = \lambda x^*x, \qquad x^*Ax = \bar\lambda x^*x.$ Since $x^*x=\|x\|^2>0$, $\lambda=\bar\lambda$, so $\lambda\in\mathbb{R}$. (3) For distinct eigenvalues $\lambda_i\neq\lambda_j$ with $Ax_i=\lambda_i x_i$, $Ax_j=\lambda_j x_j$: $\lambda_i (x_i^\top x_j) = (Ax_i)^\top x_j = x_i^\top A x_j = \lambda_j (x_i^\top x_j).$ So $(\lambda_i-\lambda_j)x_i^\top x_j=0 \Rightarrow x_i^\top x_j=0$. (3)

(b) [5 marks] $q(x)=x^\top A x = x^\top Q\Lambda Q^\top x = y^\top\Lambda y=\sum_i\lambda_i y_i^2$ where $y=Q^\top x$. (2) Since $Q$ is orthogonal (invertible), $x\neq0 \iff y\neq0$. ($\Leftarrow$) If all $\lambda_i>0$, then $\sum\lambda_i y_i^2>0$ for $y\neq0$ ⇒ PD. (1.5) ($\Rightarrow$) If some $\lambda_k\le0$, choose $y=e_k$ (i.e. $x=Qe_k$, the eigenvector), giving $q=\lambda_k\le0$ ⇒ not PD. Contrapositive complete. (1.5)

(c) [6 marks] Characteristic polynomial of the tridiagonal $[2,-1]$ matrix (size 3): eigenvalues are $2-2\cos\frac{k\pi}{4}$, $k=1,2,3$: $\lambda_1 = 2-\sqrt2 \approx 0.5858,\quad \lambda_2=2,\quad \lambda_3=2+\sqrt2\approx3.4142.$ (3) All positive ⇒ $A$ is positive definite. (1) By the Rayleigh quotient, $\min_{\|x\|_2=1} x^\top A x = \lambda_{\min} = 2-\sqrt2$, attained at the corresponding unit eigenvector. (2)

(d) [3 marks] Positive definiteness means the potential energy $\tfrac12 x^\top A x$ is strictly positive for any nonzero displacement, so the equilibrium at $x=0$ is a strict energy minimum — the system is stable; any displacement raises the elastic energy and produces restoring forces. (3)

Question 2

(a) [6 marks] Row 3 = Row 1 + Row 2, and column 3 = column 1 + column 2. So $\operatorname{rank}(M)=2$. (2) Column space basis: $\{(1,0,1)^\top,(0,1,1)^\top\}$ (columns 1 and 2, independent). (2) Null space: solve $Mx=0$. From column dependence $c_1+c_2-c_3=0$ ⇒ null vector $(1,1,-1)^\top$. Basis: $\{(1,1,-1)^\top\}$ (dim = $3-2=1$). (2)

(b) [6 marks] $M^\top M$ is symmetric PSD, so it has orthonormal eigenvectors $v_i$ with eigenvalues $\mu_i\ge0$: $M^\top M v_i=\mu_i v_i$. (2) Define $\sigma_i=\sqrt{\mu_i}$. For $\mu_i>0$ set $u_i = Mv_i/\sigma_i$; then $\|Mv_i\|^2 = v_i^\top M^\top M v_i=\mu_i$, so $\|Mv_i\|=\sigma_i$ and $u_i$ is unit; these $u_i$ are orthonormal (from orthonormality of $v_i$). This yields $M=U\Sigma V^\top$ with $\Sigma$ holding $\sigma_i$. (2) Rank$(M)=$ dim of column space $=$ number of independent $u_i=Mv_i$ $=$ number of $\sigma_i>0$ $=$ number of nonzero singular values. (2)

(c) [5 marks] $M^\top M = \begin{pmatrix}2&1&3\\1&2&3\\3&3&6\end{pmatrix}.$ Rank 2 ⇒ one zero eigenvalue. Trace $=10=\mu_1+\mu_2$. Sum of $2\times2$ principal minors gives $\mu_1\mu_2$: compute $\mu_1\mu_2 =$ (nonzero eigenvalue product). Eigenvalues of $M^\top M$: $\{0,\ 5+\sqrt{24},\ 5-\sqrt{24}\}$? Check: eigenvalues are $0$, and roots of $\mu^2-10\mu+9=0$ ⇒ $\mu=9,1$. (3) So singular values: $\sigma_1=3,\ \sigma_2=1,\ \sigma_3=0$. (2)

(d) [5 marks]

def minnorm_lstsq(U, S, Vt, b, eps=1e-10):
    # M = U @ diag(S) @ Vt
    S_inv = np.array([1/s if s > eps else 0.0 for s in S])
    # pseudoinverse M+ = V @ diag(S_inv) @ U^T
    x = Vt.T @ (S_inv * (U.T @ b))
    return x

(3) Explanation: The pseudoinverse gives the minimum-$L_2$-norm solution among all least-squares minimizers. Tiny $\sigma_k$ produce huge $1/\sigma_k$ factors that amplify noise in $b$; the condition number $\kappa=\sigma_{\max}/\sigma_{\min}$ blows up as $\sigma_{\min}\to0$. Zeroing singular values below $\varepsilon$ (truncated SVD) discards these unstable directions, bounding the effective condition number and stabilizing the solution. (2)

Question 3

(a) [5 marks] Given $\operatorname{tr}(XY)=\operatorname{tr}(YX)$ (1, standard identity). Let $X=A$, $Y=BC$: $\operatorname{tr}(A(BC))=\operatorname{tr}((BC)A)=\operatorname{tr}(BCA).$ (2) Again with $X=AB$, $Y=C$: $\operatorname{tr}((AB)C)=\operatorname{tr}(C(AB))=\operatorname{tr}(CAB)$. (2) Hence all three cyclic permutations equal.

(b) [5 marks] $(A^\top A)_{jj}=\sum_i A_{ij}A_{ij}=\sum_i A_{ij}^2$, so $\operatorname{tr}(A^\top A)=\sum_j\sum_i A_{ij}^2=\|A\|_F^2$. (2.5) With SVD $A=U\Sigma V^\top$: $A^\top A=V\Sigma^\top\Sigma V^\top$, similar to $\Sigma^\top\Sigma=\operatorname{diag}(\sigma_k^2)$. Trace is invariant under similarity ⇒ $\operatorname{tr}(A^\top A)=\sum_k\sigma_k^2$. (2.5)

(c) [8 marks] Norm preservation: $\|Qx\|_2^2=(Qx)^\top(Qx)=x^\top Q^\top Q x = x^\top I x=\|x\|_2^2$ (using $Q^\top Q=I$). (2) Dot product: $(Qx)^\top(Qy)=x^\top Q^\top Q y=x^\top y$. (2) Determinant: $\det(Q^\top Q)=\det(I)=1$; and $\det(Q^\top)\det(Q)=\det(Q)^2=1$ ⇒ $\det(Q)=\pm1$. (2) Trace: $Q^\top Q=I_n$ so $\operatorname{tr}(Q^\top Q)=\operatorname{tr}(I_n)=n$. (2)

[
  {"claim": "Eigenvalues of the 3x3 tridiagonal [2,-1] matrix are 2-sqrt2, 2, 2+sqrt2",
   "code": "A=Matrix([[2,-1,0],[-1,2,-1],[0,-1,2]]); ev=set(A.eigenvals().keys()); expected={2-sqrt(2),Integer(2),2+sqrt(2)}; result = (ev==expected)"},
  {"claim": "Minimum of Rayleigh quotient equals smallest eigenvalue 2-sqrt2",
   "code": "A=Matrix([[2,-1,0],[-1,2,-1],[0,-1,2]]); lam=min(A.eigenvals().keys(),key=lambda z:float(z)); result = simplify(lam-(2-sqrt(2)))==0"},
  {"claim": "Singular values of M are 3,1,0 (eigenvalues of M^T M are 9,1,0)",
   "code": "M=Matrix([[1,0,1],[0,1,1],[1,1,2]]); mm=M.T*M; evs=sorted([float(v) for v in mm.eigenvals().keys()]); result = evs==[0.0,1.0,9.0]"},
  {"claim": "rank(M)=2 and null space spanned by (1,1,-1)",
   "code": "M=Matrix([[1,0,1],[0,1,1],[1,1,2]]); ns=M.nullspace(); result = (M.rank()==2 and len(ns)==1 and simplify(ns[0]-ns[0][0]*Matrix([1,1,-1]))==zeros(3,1))"},
  {"claim": "trace(M^T M) equals sum of squares of singular values (9+1+0=10)",
   "code": "M=Matrix([[1,0,1],[0,1,1],[1,1,2]]); result = trace(M.T*M)==10"}
]