Linear Algebra Essentials

Q1.

(a) Consider triangle with sides $\mathbf{a}$, $\mathbf{b}$ and $\mathbf{a}-\mathbf{b}$. Law of cosines: $\|\mathbf{a}-\mathbf{b}\|^2 = \|\mathbf{a}\|^2 + \|\mathbf{b}\|^2 - 2\|\mathbf{a}\|\|\mathbf{b}\|\cos\theta.$ Expand LHS: $\|\mathbf{a}-\mathbf{b}\|^2 = (\mathbf{a}-\mathbf{b})\cdot(\mathbf{a}-\mathbf{b}) = \|\mathbf{a}\|^2 - 2\,\mathbf{a}\cdot\mathbf{b} + \|\mathbf{b}\|^2$. (2) Equate and cancel $\|\mathbf{a}\|^2+\|\mathbf{b}\|^2$: $-2\,\mathbf{a}\cdot\mathbf{b} = -2\|\mathbf{a}\|\|\mathbf{b}\|\cos\theta \Rightarrow \mathbf{a}\cdot\mathbf{b} = \|\mathbf{a}\|\|\mathbf{b}\|\cos\theta$. (2)

(b) $\mathbf{a}\cdot\mathbf{b} = 3\cdot4 + 4\cdot0 = 12$; $\|\mathbf{b}\| = 4$. (1) Scalar projection $= \dfrac{\mathbf{a}\cdot\mathbf{b}}{\|\mathbf{b}\|} = \dfrac{12}{4} = 3$. (1) Vector projection $= \dfrac{\mathbf{a}\cdot\mathbf{b}}{\|\mathbf{b}\|^2}\mathbf{b} = \dfrac{12}{16}(4,0) = (3,0)$. (2)

(c) $\cos\theta = 0$ iff $\theta = 90°$; since $\mathbf{a}\cdot\mathbf{b} = \|\mathbf{a}\|\|\mathbf{b}\|\cos\theta$ (with nonzero norms), the product is zero exactly when $\cos\theta=0$, i.e. vectors are perpendicular. (2)

Q2.

(a) $\det\begin{bmatrix}2-\lambda & 1\\ 1 & 2-\lambda\end{bmatrix} = (2-\lambda)^2 - 1 = \lambda^2 - 4\lambda + 3 = 0$. (2) Roots: $(\lambda-1)(\lambda-3)=0 \Rightarrow \lambda_1 = 3,\ \lambda_2 = 1$. (2)

(b) For $\lambda=3$: $(A-3I)\mathbf{v}=0 \Rightarrow -v_1+v_2=0 \Rightarrow v=(1,1)$, unit $=\tfrac{1}{\sqrt2}(1,1)$. (2) For $\lambda=1$: $v_1+v_2=0 \Rightarrow v=(1,-1)$, unit $=\tfrac{1}{\sqrt2}(1,-1)$. (2)

(c) $Q = \frac{1}{\sqrt2}\begin{bmatrix}1 & 1\\ 1 & -1\end{bmatrix}$, $\Lambda = \begin{bmatrix}3&0\\0&1\end{bmatrix}$, and $A = Q\Lambda Q^\top$. (2) $Q$ is orthogonal because $A$ is symmetric ⇒ eigenvectors of distinct eigenvalues are orthogonal; normalized they form an orthonormal set so $Q^\top Q = I$. (2)

Q3.

(a) (6)

import numpy as np
def power_iteration(A, iters=100):
    n = A.shape[0]
    v = np.random.rand(n)
    v = v / np.linalg.norm(v)
    for _ in range(iters):
        w = A @ v
        v = w / np.linalg.norm(w)        # normalize each step
    eigval = v @ (A @ v) / (v @ v)        # Rayleigh quotient
    return eigval, v

Marks: normalization (2), iteration/matvec (2), Rayleigh quotient (2).

(b) Expand the start vector in the eigenbasis $v_0 = \sum c_i q_i$. Then $A^k v_0 = \sum c_i \lambda_i^k q_i = \lambda_1^k(c_1 q_1 + \sum_{i>1} c_i(\lambda_i/\lambda_1)^k q_i)$. Since $|\lambda_i/\lambda_1|<1$ for $i>1$, all other terms vanish, leaving the direction of $q_1$. (2) Fails if $|\lambda_1|$ is not strictly dominant (e.g. $\lambda_1=-\lambda_2$ or complex pair equal magnitude), or if $c_1=0$ (start vector orthogonal to dominant eigenvector). (2)

Q4.

(a) Rows $R_2 \leftarrow R_2 - 2R_1$, $R_3 \leftarrow R_3 - 3R_1$: $\begin{bmatrix}1&2&1&|&1\\0&0&1&|&1\\0&0&1&|&1\end{bmatrix}$ Then $R_3 \leftarrow R_3 - R_2$: $\begin{bmatrix}1&2&1&|&1\\0&0&1&|&1\\0&0&0&|&0\end{bmatrix}$ (4)

(b) Rank $=2$ (two nonzero pivot rows). (2) Null space: from echelon form, $x_3=0$ (from row 2 homogeneous), $x_1 + 2x_2 + x_3 = 0 \Rightarrow x_1 = -2x_2$. Free variable $x_2$: null vector $(-2,1,0)$. Basis $\{(-2,1,0)\}$. (2)

(c) Consistent (no $0=$nonzero row). Particular: $x_3=1$, choose $x_2=0 \Rightarrow x_1 = 1 - x_3 = 0$, so $x_p=(0,0,1)$. General: $\mathbf{x} = (0,0,1) + t(-2,1,0)$. (2)

Q5.

(a) $M = \begin{bmatrix}2 & 1\\ 1 & 2\end{bmatrix}$ (off-diagonals split the $2x_1x_2$ term equally). (3)

(b) Eigenvalue test: from Q2, eigenvalues are $3$ and $1$, both $>0$ ⇒ positive definite. (2.5) Sylvester: leading minors $D_1 = 2 > 0$, $D_2 = \det M = 4-1 = 3 > 0$ ⇒ positive definite. (2.5)

(c) A positive-definite Hessian at a critical point means the point is a strict local minimum (locally convex). (2)

Q6.

(a) $A = U\Sigma V^\top$ with $U,V$ orthogonal, $\Sigma$ diagonal (nonneg singular values). $V^\top$ rotates/reflects input basis, $\Sigma$ scales along axes by singular values (unit sphere → axis-aligned ellipsoid), $U$ rotates the ellipsoid into output space. (4)

(b) $A^\top A = V\Sigma^\top U^\top U \Sigma V^\top = V\Sigma^2 V^\top$, an eigendecomposition. Hence eigenvalues of $A^\top A$ are $\sigma_i^2$, so singular values $\sigma_i = \sqrt{\lambda_i(A^\top A)}$ (nonnegative). (4)

[
  {"claim":"Q1b vector projection of (3,4) onto (4,0) is (3,0)","code":"a=Matrix([3,4]); b=Matrix([4,0]); proj=(a.dot(b)/b.dot(b))*b; result = proj==Matrix([3,0])"},
  {"claim":"Q2 eigenvalues of [[2,1],[1,2]] are 1 and 3","code":"A=Matrix([[2,1],[1,2]]); result = set(A.eigenvals().keys())=={1,3}"},
  {"claim":"Q4 rank of coefficient matrix is 2","code":"M=Matrix([[1,2,1],[2,4,3],[3,6,4]]); result = M.rank()==2"},
  {"claim":"Q4 null space basis vector (-2,1,0)","code":"M=Matrix([[1,2,1],[2,4,3],[3,6,4]]); ns=M.nullspace(); result = ns[0]== -2*Matrix([1,Rational(-1,2),0]) or ns[0].T*Matrix([1,2,1])==Matrix([0]) and (M*Matrix([-2,1,0])==Matrix([0,0,0]))"},
  {"claim":"Q5 M=[[2,1],[1,2]] is positive definite (both leading minors positive)","code":"M=Matrix([[2,1],[1,2]]); result = (M[0,0]>0) and (M.det()>0)"}
]