Linear Algebra

Reactivation sheet — results and the proofs whose tricks carry the subject. The organizing claim: every matrix is diagonal between the right pair of orthonormal bases (SVD). Everything before it is machinery needed to state and prove that; everything after is statistics cashing it in. The recurring workhorse is $A^TA$: it powers least squares, definiteness, and singular values.

1. Four ways to read $Ax$, four subspaces

Four readings of matrix multiplication, each the right tool somewhere:

• Row picture: entry $i$ of $Ax$ is (row $i$) $\cdot\,x$ — the system $Ax = b$ is $m$ hyperplane constraints intersecting.
• Column picture: $Ax = x_1(\text{col}_1) + \cdots + x_n(\text{col}_n)$ — a linear combination of columns with weights $x$. This is the picture that generalizes: $Ax = b$ solvable ⟺ $b \in C(A)$.
• Column-wise product: $AB = [Ab_1 \cdots Ab_p]$ — apply $A$ to each column of $B$.
• Outer-product sum: $AB = \sum_k (\text{col}_k \text{ of } A)(\text{row}_k \text{ of } B)$ — a sum of rank-1 matrices. This view makes SVD’s $\sum \sigma_i u_i v_i^T$ natural before you ever see it.

Fundamental theorem. For $A \in R^{m \times n}$ with rank $r$:

Subspace	Lives in	Dim	Orthogonal complement of
Row space $C(A^T)$	$R^n$	$r$	$N(A)$
Null space $N(A)$	$R^n$	$n - r$	$C(A^T)$
Column space $C(A)$	$R^m$	$r$	$N(A^T)$
Left null space $N(A^T)$	$R^m$	$m - r$	$C(A)$

Build it up:

• $x \in N(A)$ ⟺ $Ax = 0$ ⟺ every row dots to zero against $x$ ⟺ $x \perp$ row space. So $N(A) = C(A^T)^\perp$ — the orthogonality is nearly definitional.
• Apply the same statement to $A^T$: $N(A^T) = C(A)^\perp$.
• Row rank = column rank: one number $r$ sets all four dimensions. Rank–nullity is the bookkeeping: $r + (n-r) = n$.
• Restricted to the row space, $A$ is a bijection onto the column space: injective because row space ∩ null space $= \{0\}$ (they’re complements), surjective because dims match ($r$ on both sides). The null space is what $A$ forgets; the left null space is what $A$ can’t reach.
• Elimination ($A = LU$) computes $r$ as the pivot count and never changes $N(A)$ — row operations are invertible, so solutions are preserved.

The picture to hold (and redraw cold): two panes. Left pane $R^n$, split into row space (dim $r$) ⊥ null space (dim $n-r$); right pane $R^m$, split into column space (dim $r$) ⊥ left null space (dim $m-r$). One arrow carries the row space bijectively onto the column space; a second arrow crushes the null space to $0$.

Solvability regimes for $Ax = b$:

Rank	Shape of $R$	$N(A)$	# solutions
$r = n < m$ (full col)	$[\,I;\,0\,]$	$\{0\}$	0 or 1
$r = m < n$ (full row)	$[\,I \;\; F\,]$	dim $n-m$	∞
$r = m = n$	$I$	$\{0\}$	1 (invertible)
$r < m, n$	$\begin{bmatrix} I & F \\ 0 & 0\end{bmatrix}$	dim $n-r$	0 or ∞

• Complete solution $= x_p + N(A)$: one particular solution plus the whole null space — an affine subspace, a copy of $N(A)$ shifted off the origin.
• Free variables: $n - r$ of them, one special solution each; the special solutions are a basis for $N(A)$.

Implications — what falls out of the four-subspace picture:

• Fredholm alternative: $Ax = b$ is solvable ⟺ $b \perp N(A^T)$. Either you can solve the system, or there exists a certificate $y$ with $A^Ty = 0$ and $y^Tb \neq 0$ — never both. (Just restating $C(A) = N(A^T)^\perp$, but it converts “is it solvable?” into a checkable orthogonality condition.)
• Every $x \in R^n$ splits uniquely as $x = x_{row} + x_{null}$ with the two parts orthogonal. $A$ acts only on $x_{row}$; this split is the engine behind the minimum-norm solution in §6.
• Rank-1 matrices are exactly outer products $uv^T$; rank $k$ ⟺ a sum of $k$ outer products ⟺ factorization into $(n \times k)(k \times d)$ — the seed of low-rank approximation.

Core competency set

• Draw the four-subspace picture with dimensions and orthogonality from a blank page.
• Read solution count straight off the rank regime.
• State the Fredholm alternative and the orthogonal split $x = x_{row} + x_{null}$.

2. Projection and least squares

Build the projection from one dimension up:

• Project $b$ onto the line through $a$. The projection lies on the line: $p = \hat{x}a$ for some scalar $\hat{x}$. The defining property is that the error is perpendicular: $e = b - \hat{x}a \perp a$. Solve that one condition:

$a^T(b - \hat{x}a) = 0 \;\Rightarrow\; a^Tb = \hat{x}\,a^Ta \;\Rightarrow\; \hat{x} = \frac{a^Tb}{a^Ta}$

• Repackage to expose the matrix acting on $b$:

$p = a\hat{x} = a\,\frac{a^Tb}{a^Ta} = \frac{aa^T}{a^Ta}\,b \;\Rightarrow\; P = \frac{aa^T}{a^Ta}$

— rank 1, built from an outer product.

• Project onto a subspace $C(A)$. Same logic, scalar → vector: $p = A\hat{x}$, and the error must be perpendicular to every column at once, which is exactly one matrix statement:

$A^T(b - A\hat{x}) = 0 \;\iff\; \boxed{A^TA\hat{x} = A^Tb}$

• The normal equations are the orthogonality condition — there is nothing else in the derivation.
• $A^TA$ is invertible ⟺ $A$ has independent columns. Why: they share a null space —

$A^TAx = 0 \;\Rightarrow\; x^TA^TAx = \|Ax\|^2 = 0 \;\Rightarrow\; Ax = 0$

• So with independent columns:

$\hat{x} = (A^TA)^{-1}A^Tb, \qquad P = A(A^TA)^{-1}A^T$

Numbers: project $b = (2,0)$ onto $a = (1,1)$: $\hat{x} = \frac{a^Tb}{a^Ta} = \frac{2}{2} = 1$, so $p = (1,1)$ and $e = b - p = (1,-1)$; check $e^Ta = 0$. The right triangle $b = p + e$ is the whole subject in one sketch — that triangle is also the picture to redraw cold.

Calculus arrives at the same place. Expand the loss, differentiate, set to zero:

$\|Ax - b\|^2 = (Ax - b)^T(Ax - b) = x^TA^TAx - 2x^TA^Tb + b^Tb$

$\nabla_x\|Ax - b\|^2 = 2A^TAx - 2A^Tb = 2A^T(Ax - b)$

$\nabla_x = 0 \;\iff\; A^TA\hat{x} = A^Tb$

Geometry and calculus give the same equations because “gradient zero” and “error ⊥ columns” are the same statement: the loss stops decreasing exactly when no direction in $C(A)$ has any component of the error left to remove.

Reading $P$:

• Projection matrices are exactly the symmetric idempotents: $P^T = P$, $P^2 = P$ (projecting twice changes nothing).
• $b \in C(A) \Rightarrow Pb = b$; $b \perp C(A) \Rightarrow Pb = 0$; in general $b = Pb + (I-P)b$ splits $b$ into column-space part + left-null-space part. $I - P$ projects onto the complement.
• Least squares is this picture applied to an unsolvable system: $b \notin C(A)$, so solve the nearest solvable problem $A\hat{x} = Pb$. The residual $e = b - A\hat{x}$ lives in $N(A^T)$.

Implications — what falls out of the projection picture:

• Pythagoras for regression. Since $Pb \perp (I-P)b$:

$\|b\|^2 = \|Pb\|^2 + \|(I-P)b\|^2$

Total = explained + residual. Applied to centered data this is the $R^2$ decomposition: $R^2 = \|Pb\|^2 / \|b\|^2$.

• In regression language: $P$ is the hat matrix, $\hat{y} = Pb$ are fitted values, residuals are orthogonal to every regressor and to the fitted values — not an assumption, a theorem of the geometry.
• Adding a column to $A$ grows $C(A)$, so the residual norm can only shrink or stay — why $R^2$ never decreases when you add variables, and why that’s not evidence of a better model.

Orthogonal matrices. $Q$ has orthonormal columns: $q_i^Tq_j = 1$ if $i = j$, else $0$; equivalently $Q^TQ = I$ (square ⟹ $Q^T = Q^{-1}$).

• They preserve lengths and inner products: $\|Qx\| = \|x\|$ — pure rotations/reflections.
• With orthonormal columns, projection collapses:

$P = Q(Q^TQ)^{-1}Q^T = QQ^T$

No inverse to compute — this is the reason to orthogonalize. Coefficients are just inner products: $\hat{x}_i = q_i^Tb$, each computed independently of the others.

Gram–Schmidt — the procedure that manufactures orthonormal bases. One move, repeated: subtract from each new vector its projections onto everything already built; what survives is the genuinely new direction.

• Input: independent $a, b, c$. Output: orthogonal $A, B, C$, then orthonormal $q_i$.
• Step 1: $A = a$. The first direction is kept as-is.
• Step 2: remove $b$‘s shadow on $A$:

$B = b - \frac{A^Tb}{A^TA}A$

Verify the move worked:

$A^TB = A^Tb - \frac{A^Tb}{A^TA}\,A^TA = A^Tb - A^Tb = 0$

• Step 3: remove shadows on both prior directions:

$C = c - \frac{A^Tc}{A^TA}A - \frac{B^Tc}{B^TB}B$

Subtracting projections onto orthogonal directions doesn’t interfere — removing the $B$-shadow leaves the $A$-orthogonality intact, which is why the procedure can work one direction at a time.

• Normalize last: $q_1 = \frac{A}{\|A\|}$, $q_2 = \frac{B}{\|B\|}$, $q_3 = \frac{C}{\|C\|}$.
• Spans are preserved at every step: $\operatorname{span}(q_1, \ldots, q_k) = \operatorname{span}(a_1, \ldots, a_k)$.
• Bookkeeping form $A = QR$: since $a_k$ involves only $q_1, \ldots, q_k$ (never later ones), the coefficient matrix $R = Q^TA$ is upper triangular with $r_{ij} = q_i^Ta_j$.

Implications — why QR earns its keep:

• Least squares via QR: substitute $A = QR$ into the normal equations and watch them collapse:

$A^TA\hat{x} = A^Tb \;\Rightarrow\; R^TQ^TQR\hat{x} = R^TQ^Tb \;\Rightarrow\; R\hat{x} = Q^Tb$

One triangular solve. Better conditioned than forming $A^TA$, whose condition number is the square of $A$‘s.

• The same “project out what’s already explained” move is the engine elsewhere: a regression coefficient measures what a variable adds beyond the others (successive orthogonalization), orthogonal polynomials, Arnoldi/Lanczos iterations.

Core competency set

• Run the 1-D → subspace projection derivation; state that normal equations = orthogonality = gradient zero.
• Reproduce the calculus derivation of the normal equations from the expanded loss.
• Execute Gram–Schmidt on three vectors; explain why $R$ is triangular and how QR collapses the normal equations.
• Narrate the Pythagoras/$R^2$ decomposition as projection geometry.

3. Determinants — the load-bearing facts

Three axioms (det $I = 1$; sign flips per row swap; linear in each row separately) generate every property. Keep:

• $\det A$ = product of pivots (± for swaps) = product of eigenvalues = signed volume of the column parallelepiped.
• $\det A = 0 \iff$ singular; $\det AB = \det A \det B$; $\det A^T = \det A$; $\det A^{-1} = 1/\det A$.
• Elimination doesn’t change the determinant: subtracting a multiple of one row from another adds a multiple of a repeated-row determinant, which is 0 —

$\det\begin{bmatrix} a & b \\ c - \ell a & d - \ell b \end{bmatrix} = \det\begin{bmatrix} a & b \\ c & d \end{bmatrix} - \ell\det\begin{bmatrix} a & b \\ a & b \end{bmatrix} = \det\begin{bmatrix} a & b \\ c & d \end{bmatrix}$

That’s why “product of pivots” works: eliminate (det unchanged), then a triangular determinant is the diagonal product.

• Similar matrices share determinant, trace, and eigenvalues — these are basis-free numbers attached to the underlying map.
• Cofactor expansion exists; in practice eliminate instead.
• $|\det J|$ = local volume scaling of a map — the bridge to change of variables in probability.

4. Eigenvalues and diagonalization

$Ax = \lambda x$: directions the map only stretches; $\lambda$ is the stretch factor (negative = flip).

The procedure:

1. $Ax = \lambda x \iff (A - \lambda I)x = 0$ — we need $A - \lambda I$ singular.
2. So set $\det(A - \lambda I) = 0$: the characteristic polynomial, degree $n$, $n$ roots with multiplicity.
3. For each root $\lambda_i$, the eigenvectors are $N(A - \lambda_i I)$ — find by elimination. The whole null space is the eigenspace.
4. Sanity-check instantly: $\sum \lambda_i = \operatorname{tr} A$, $\prod \lambda_i = \det A$.

Numbers: $A = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}$ — trace 4, det 3, so $\lambda = 3, 1$ on sight. Eigenvectors $(1,1)$ and $(1,-1)$: orthogonal, because $A$ is symmetric (§5 coming). Powers grow like $3^k$ along $(1,1)$.

Fast facts:

• Triangular ⟹ eigenvalues sit on the diagonal.
• Singular ⟺ $\lambda = 0$ is present.
• $A$ and $A^T$ share eigenvalues (same characteristic polynomial), not eigenvectors.
• Distinct eigenvalues ⟹ independent eigenvectors ⟹ diagonalizable. Repeated eigenvalues may starve you of eigenvectors (eigenspace dimension < multiplicity); Jordan form is the fallback, rarely needed.

Diagonalization. With $n$ independent eigenvectors as columns of $S$, apply $A$ column by column:

$AS = A[x_1 \cdots x_n] = [\lambda_1 x_1 \cdots \lambda_n x_n] = S\Lambda \;\Rightarrow\; A = S\Lambda S^{-1}$

Read it as a recipe: $S^{-1}$ translates into eigen-coordinates, $\Lambda$ stretches each coordinate independently, $S$ translates back. In the right basis, the map has no cross-talk at all.

Implications — what falls out of knowing $A$ is diagonalizable:

• Powers cost one decomposition. The inner pairs cancel:

$A^k = (S\Lambda S^{-1})(S\Lambda S^{-1})\cdots = S\Lambda^kS^{-1}$

Only the eigenvalues get powered.

• Linear recurrences get closed forms. $u_{k+1} = Au_k$ solves as $u_k = A^ku_0$: expand $u_0 = \sum c_ix_i$ in eigenvectors, then

$u_k = \sum_i c_i\lambda_i^k x_i$

Each mode evolves independently. Fibonacci is the classic instance: $\binom{F_{k+1}}{F_k} = \begin{bmatrix}1 & 1\\ 1 & 0\end{bmatrix}\binom{F_k}{F_{k-1}}$, eigenvalues $\frac{1 \pm \sqrt 5}{2}$ — golden-ratio growth is the dominant eigenvalue showing through.

• Stability is a one-number question. $A^k \to 0 \iff$ all $|\lambda_i| < 1$; long-run behavior is owned by $\lambda_{max}$. This single fact is LDS stability, Markov chain convergence, and power iteration (repeatedly applying $A$ amplifies the top eigenvector until it’s all that’s left).
• ODEs decouple. $\dot{u} = Au$ solves as $u(t) = Se^{\Lambda t}S^{-1}u_0$ — exponentials $e^{\lambda_i t}$ per mode; continuous-time stability ⟺ all $\operatorname{Re}(\lambda_i) < 0$.
• Functions of matrices become functions of scalars: $f(A) = S\,f(\Lambda)\,S^{-1}$ for any polynomial/power series — matrix exponentials, square roots, inverses all ride the same identity.
• Convergence rates come from the spectral gap: a Markov chain approaches its steady state like $|\lambda_2|^k$ — the second eigenvalue, not the first, sets the speed.

Markov matrices (entries ≥ 0, columns sum to 1):

• $\lambda = 1$ always: columns of $A - I$ sum to 0, so the rows are dependent, so $A - I$ is singular.
• All other $|\lambda| \leq 1$; the steady state is the $\lambda = 1$ eigenvector, reached because every other mode decays as $\lambda_i^k$.

Core competency set

• Run the eigen-procedure; sanity-check with trace/det reflexively.
• Derive $A = S\Lambda S^{-1}$ from $AS = S\Lambda$ and narrate it as a change into eigen-coordinates.
• Produce the implications unprompted: powers, recurrences (Fibonacci), stability via $|\lambda_{max}|$, ODE decoupling, $f(A) = Sf(\Lambda)S^{-1}$, spectral-gap rates.

5. Symmetric and positive definite matrices

Spectral theorem: $A = A^T$ ⟹ real eigenvalues and a full set of orthonormal eigenvectors:

$A = Q\Lambda Q^T = \sum_i \lambda_i q_iq_i^T$

• Reading: every symmetric matrix is a weighted sum of rank-1 orthogonal projections — $A$ acts by projecting onto each eigendirection and scaling by $\lambda_i$.
• Proof beat (orthogonality): symmetry lets $A$ hop across the inner product —

$\lambda_1 x_1^Tx_2 = (Ax_1)^Tx_2 = x_1^T(Ax_2) = \lambda_2 x_1^Tx_2$

so $\lambda_1 \neq \lambda_2$ forces $x_1^Tx_2 = 0$.

• Proof beat (reality): compute $\bar{x}^TAx$ two ways —

$\bar{x}^TAx = \bar{x}^T(\lambda x) = \lambda\|x\|^2 \qquad \text{and} \qquad \bar{x}^TAx = (A\bar{x})^Tx = \bar{\lambda}\|x\|^2$

so $\lambda = \bar{\lambda}$: real.

• For symmetric matrices, # positive pivots = # positive eigenvalues — elimination and the spectrum agree on signs.

Implications — what falls out of the spectral theorem:

• Rayleigh quotient bounds. Expanding $x$ in the eigenbasis, $x^TAx = \sum \lambda_i(q_i^Tx)^2$, so

$\lambda_{min} \leq \frac{x^TAx}{x^Tx} \leq \lambda_{max}$

with equality at the eigenvectors. “Maximize variance” problems (PCA) are this: the top eigenvector is the argmax of the quadratic form on the sphere.

• Quadratic-form geometry: the level set $x^TAx = 1$ (PD case) is an ellipsoid with axes along the $q_i$ and semi-lengths $1/\sqrt{\lambda_i}$ — eigen-decomposition literally draws the picture of the form.
• Whitening / matrix roots: $A^{1/2} = Q\Lambda^{1/2}Q^T$ exists for PSD $A$; transform data by $\Sigma^{-1/2}$ to make its covariance the identity.

Positive definite — four equivalent tests, cycle freely:

1. All eigenvalues $> 0$.
2. $x^TAx > 0$ for all $x \neq 0$ (the defining quadratic-form test).
3. All pivots $> 0$.
4. All leading principal subdeterminants $> 0$.

• The quadratic form $x^TAx$ is a bowl; PD means the bowl opens upward in every direction.
• Completing the square is elimination:

$2x^2 + 12xy + 20y^2 = 2(x + 3y)^2 + 2y^2$

The outer coefficients (2, 2) are the pivots; the inside multiplier (3) is the elimination multiplier $\ell_{21}$. PD ⟺ all completed squares have positive coefficients — that’s why test 3 works.

• PD matrices are exactly the valid covariance matrices and the valid inner products ($\langle x, y\rangle = x^TAy$).
• Semi-definite: $x^TAx \geq 0$ — eigenvalues allowed to touch zero.

$A^TA$ is always PSD:

$x^TA^TAx = (Ax)^T(Ax) = \|Ax\|^2 \geq 0$

with equality exactly on $N(A)$ — so PD ⟺ full column rank. This single fact ties together least squares (§2), covariance matrices, and SVD (§6).

Cholesky: PD $A = LL^T$, $L$ lower triangular with positive diagonal, unique — a matrix square root recorded by elimination. How you sample correlated Gaussians ($x = Lz$ for iid $z$ gives $\operatorname{Cov}(x) = LL^T = A$) and the cheap way to solve PD systems. Also $\det A = \prod l_{ii}^2$.

Core competency set

• Write the spectral theorem in both forms; reproduce both proof beats (hop, reality).
• Cycle between the four PD tests; narrate completing-the-square as elimination.
• Derive the Rayleigh bounds from the eigenbasis expansion; connect top-eigenvector to variance maximization.
• Explain $A^TA \succeq 0$ in one line and when it upgrades to $\succ 0$.

6. SVD — the capstone

$A = U\Sigma V^T = \sum_{i=1}^{r} \sigma_i u_iv_i^T, \qquad U, V \text{ orthogonal},\ \Sigma \text{ diagonal} \geq 0$

Exists for every matrix — no squareness, no symmetry, no diagonalizability needed. Meaning: rotate (orthonormal basis $V$ in the domain), scale each axis by $\sigma_i$, rotate (orthonormal basis $U$ in the codomain). Eigendecomposition uses one basis and needs a lucky matrix; SVD buys universality by allowing two.

The picture: the unit circle, hit by $V^T$ (rotate), then $\Sigma$ (stretch into an ellipse with semi-axes $\sigma_1, \sigma_2$ along the coordinate axes), then $U$ (rotate the ellipse into place). Every matrix does exactly this to the unit sphere — the $\sigma_i$ are the ellipse’s axis lengths.

Construction — also the existence proof, built entirely from §5:

1. Form $A^TA$: symmetric PSD, the workhorse again.
2. Spectral theorem gives orthonormal eigenvectors $v_1, \ldots, v_n$ with eigenvalues $\lambda_i \geq 0$. Define $\sigma_i = \sqrt{\lambda_i}$, sorted descending.
3. For each $\sigma_i > 0$, define $u_i = \frac{Av_i}{\sigma_i}$ — push the right basis through $A$ and renormalize.
4. The $u_i$ come out orthonormal automatically — the one computation worth memorizing:

$u_i^Tu_j = \frac{(Av_i)^T(Av_j)}{\sigma_i\sigma_j} = \frac{v_i^TA^TAv_j}{\sigma_i\sigma_j} = \frac{\sigma_j^2\,v_i^Tv_j}{\sigma_i\sigma_j} = \delta_{ij}$

5. Extend $\{u_i\}$ to an orthonormal basis of $R^m$; assemble $AV = U\Sigma$, i.e. $A = U\Sigma V^T$.

Numbers — run the construction on $A = \begin{bmatrix} 4 & 4 \\ -3 & 3 \end{bmatrix}$:

$A^TA = \begin{bmatrix} 25 & 7 \\ 7 & 25 \end{bmatrix} \;\Rightarrow\; \lambda = 32,\, 18; \quad v_1 = \tfrac{1}{\sqrt{2}}\begin{bmatrix} 1 \\ 1 \end{bmatrix},\; v_2 = \tfrac{1}{\sqrt{2}}\begin{bmatrix} 1 \\ -1 \end{bmatrix}; \quad \sigma_1 = \sqrt{32},\; \sigma_2 = \sqrt{18}$

$u_1 = \frac{Av_1}{\sigma_1} = \frac{1}{\sqrt{2}\sqrt{32}}\begin{bmatrix} 8 \\ 0 \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \end{bmatrix}, \qquad u_2 = \frac{Av_2}{\sigma_2} = \frac{1}{\sqrt{2}\sqrt{18}}\begin{bmatrix} 0 \\ -6 \end{bmatrix} = \begin{bmatrix} 0 \\ -1 \end{bmatrix}$

Note $u_2 = (0, -1)$, not $(0, 1)$. The signs must come from $u_i = Av_i/\sigma_i$ — eigendecomposing $AA^T$ separately and picking signs independently is the classic way to assemble an “SVD” that doesn’t multiply back to $A$.

Consequences to keep paired with the construction:

• Right singular vectors = eigenvectors of $A^TA$; left = eigenvectors of $AA^T$; $\sigma_i = \sqrt{\lambda_i(A^TA)}$ — both products share the same nonzero eigenvalues.
• SVD is the fundamental theorem made computational: $v_1 \ldots v_r$ span the row space, $v_{r+1} \ldots v_n$ the null space, $u_1 \ldots u_r$ the column space, $u_{r+1} \ldots u_m$ the left null space. Orthonormal bases for all four subspaces, with the row→column bijection scaled by the $\sigma_i$.
• $\|A\|_F^2 = \sum_i \sigma_i^2$ — total “energy” lives in the singular values (orthogonal rotations don’t change Frobenius norm).

Eckart–Young / low-rank approximation. Truncate to the top $k$ rank-1 terms: $A_k = U_k\Sigma_kV_k^T$.

• The error identity comes free, because multiplying by orthogonal matrices preserves Frobenius norm:

$\|A - A_k\|_F^2 = \|U(\Sigma - \Sigma_k)V^T\|_F^2 = \|\Sigma - \Sigma_k\|_F^2 = \sum_{i>k}\sigma_i^2$

Truncation error = exactly the discarded energy.

• The theorem’s content is optimality: no rank-$k$ matrix of any kind beats $A_k$ (in Frobenius or operator norm). Intuition for why: any rank-$k$ $B$ has an $(n-k)$-dimensional null space, which must intersect the $(k+1)$-dimensional span of $v_1, \ldots, v_{k+1}$ — on that intersection $B$ contributes nothing while $A$ still carries energy $\geq \sigma_{k+1}$. You cannot avoid missing the top of what you cut.
• Reading: singular values rank the “concepts” in $A$ by signal strength — rows of $V^T$ are canonical row-types, columns of $U$ canonical column-types, each row/column of $A$ a mixture of them (the customers × movies story). PCA, compression, denoising, matrix completion all start here.
• Storage drops $O(nd) \to O(k(n+d))$. Choose $k$ at the spectrum’s elbow, or to capture a target share of $\sum \sigma_i^2$.

Pseudoinverse. $A^+ = V\Sigma^+U^T$, where $\Sigma^+$ inverts the nonzero $\sigma$‘s and transposes the shape.

• Subspace-by-subspace: $A^+$ inverts the row↔column bijection ($u_i \mapsto v_i/\sigma_i$) and kills $N(A^T)$.
• Claim: $A^+b$ is the minimum-norm least-squares solution. Motivate it, both halves:
  • Least squares half: the set of least-squares solutions is $\hat{x} + N(A)$ — all solutions of the normal equations differ by null-space vectors, since adding $x_n \in N(A)$ changes nothing about $A\hat{x}$.
  • Minimum-norm half: split any solution into orthogonal parts $x = x_{row} + x_{null}$ (§1). The fit only sees the row part ($Ax = Ax_{row}$); the null part adds pure norm. By Pythagoras:

$\|x\|^2 = \|x_{row}\|^2 + \|x_{null}\|^2 \geq \|x_{row}\|^2$

• So the minimizer is the unique solution with zero null-space component — a pure row-space vector. $A^+b = \sum_{i \leq r} \frac{u_i^Tb}{\sigma_i}v_i$ is built entirely from the $v_i$ spanning the row space: it is that solution.
• Full column rank ⟹ $N(A) = \{0\}$, the solution is unique anyway, and $A^+ = (A^TA)^{-1}A^T$ — recovering §2’s left inverse exactly.

Implications — what falls out of having an SVD:

• Operator norm and conditioning: $\|A\|_2 = \sigma_1$ (max stretch over the unit sphere); condition number $\kappa = \sigma_1/\sigma_r$ measures how much relative error in $b$ can amplify in $x$ — the practical reason QR beats normal equations (forming $A^TA$ squares $\kappa$).
• Numerical rank: count singular values above a tolerance — far more robust than counting pivots, which rounding pollutes.
• PCA is SVD of the centered data matrix: principal directions = right singular vectors, component variances = $\sigma_i^2/(n-1)$; “maximize variance” = Rayleigh quotient on the covariance $\frac{1}{n-1}X^TX$ (§5 implications, cashed in).
• Polar decomposition: $A = (UV^T)(V\Sigma V^T)$ = orthogonal × symmetric-PSD — every linear map is a rotation followed by a stretch.

Core competency set

• Construct the SVD from the spectral theorem on $A^TA$, including the $u_i$ orthonormality computation.
• Map singular vectors onto the four subspaces; state Eckart–Young with the discarded-energy identity and the null-space-intersection intuition for optimality.
• Prove the min-norm property of $A^+b$ via the row/null split and Pythagoras.
• Connect $\sigma_1$, $\kappa$, PCA, and polar decomposition back to the SVD without prompting.

7. Matrix calculus — working table

Numerator layout (gradient of a scalar = row vector; Jacobian of $f: R^n \to R^m$ is $m \times n$). Chain rule = Jacobian product: $\partial_x f(g(x)) = J_fJ_g$ — the shapes self-check.

$f(x)$	$\partial f / \partial x$
$a^Tx$	$a^T$
$x^TAx$	$x^T(A + A^T)$ → $2x^TA$ if symmetric
$\|x\|^2$	$2x^T$
$\|Ax - b\|^2$	$2(Ax-b)^TA$ — zero ⟹ normal equations
$Ax$ (Jacobian)	$A$

Worked chain-rule template — the least-squares gradient, done the modular way (this is the pattern backprop generalizes):

$L = \|e\|^2, \quad e = b - Ax \qquad \frac{\partial L}{\partial x} = \frac{\partial L}{\partial e}\frac{\partial e}{\partial x} = (2e^T)(-A) = -2(b - Ax)^TA$

• Element-wise operations ⟹ diagonal Jacobians; sums pull outside derivatives.
• $|\det J|$ = volume scaling (ties to §3 and the probability change-of-variables).
• Taylor: $f(x) \approx f(x_0) + \nabla f\,\delta + \frac{1}{2}\delta^TH\delta$ — Hessian PD at a critical point ⟹ local min (§5 cashing in).

8. Decompositions roundup

Decomposition	Form	Requires	Use
LU	$A = LU$	square, (P for swaps)	solving systems, det via pivots
QR	$A = QR$	independent columns	least squares, Gram–Schmidt record
Cholesky	$A = LL^T$	symmetric PD	sampling Gaussians, fast PD solves
Eigen	$A = S\Lambda S^{-1}$	$n$ indep. eigenvectors	powers, dynamics, stability
Spectral	$A = Q\Lambda Q^T$	symmetric	quadratic forms, PSD theory
SVD	$A = U\Sigma V^T$	nothing	everything else

9. Memorize cold

The instant-recall layer — these should cost nothing to produce. Everything else in the guide is rederivable from them plus the named moves; the fluency flashcards drill exactly this list.

• Four subspaces: dims $r,\, n-r,\, r,\, m-r$; row ⊥ null, column ⊥ left-null; $A$ = bijection row space → column space.
• Normal equations $A^TA\hat{x} = A^Tb$; $\hat{x} = (A^TA)^{-1}A^Tb$; $P = A(A^TA)^{-1}A^T$; orthonormal case $P = QQ^T$.
• Projection test: symmetric + idempotent. Pythagoras $\|b\|^2 = \|Pb\|^2 + \|(I-P)b\|^2$.
• Eigen: $\det(A - \lambda I) = 0$; $\sum\lambda = \operatorname{tr}$, $\prod\lambda = \det$; $A = S\Lambda S^{-1}$, $A^k = S\Lambda^kS^{-1}$; stability ⟺ all $|\lambda| < 1$.
• Spectral theorem: symmetric ⟹ $A = Q\Lambda Q^T = \sum\lambda_iq_iq_i^T$, real $\lambda$, orthonormal $q$.
• PD tests (all positive): eigenvalues / $x^TAx$ / pivots / leading minors. $A^TA \succeq 0$ always; $\succ 0$ ⟺ full column rank.
• SVD: $A = U\Sigma V^T = \sum\sigma_iu_iv_i^T$; $v$ = eigvecs of $A^TA$, $u$ = eigvecs of $AA^T$, $\sigma_i = \sqrt{\lambda_i(A^TA)}$; $\|A\|_F^2 = \sum\sigma_i^2$, $\|A\|_2 = \sigma_1$.
• Pseudoinverse $A^+ = V\Sigma^+U^T$; full column rank ⟹ $A^+ = (A^TA)^{-1}A^T$; $A^+b$ = min-norm least squares.
• Gradient rows: $\partial(a^Tx) = a^T$; $\partial(x^TAx) = x^T(A + A^T)$; $\partial\|Ax-b\|^2 = 2(Ax-b)^TA$.
• The decompositions table: form, requirement, use — all six rows.
• Named moves: error ⊥ subspace (normal equations); the inner-product hop (spectral orthogonality); project-out-what’s-built (Gram–Schmidt); row/null split + Pythagoras (min-norm); shared-null-space ($A^TA$ invertibility).