Matrix Decompositions & SVD

The punchline of the whole unit, up front: almost every matrix you'll meet can be written as rotate → stretch along axes → rotate. The three famous decompositions are not three unrelated tricks — they are one idea applied to progressively harder matrices, each rung dropping one requirement and gaining one power:

Why climb in this order? Because each rung teaches one lesson. Spectral shows the dream scenario: perpendicular axes, real scalings, no distortion. Eigendecomposition asks what if the natural axes lean? — the idea survives, but the tidy transpose becomes a real inverse. And SVD asks the boldest question — what if the matrix isn't even square, so "eigenvector" is meaningless? — and answers it with one elegant move that works for every matrix in existence.

Every decomposition in this unit is a scheme for smuggling a diagonal matrix into the middle of the product. Why the obsession? Because for a diagonal

every hard matrix question collapses into arithmetic on $n$ separate numbers. The determinant is just the product $\prod_i d_i$ (Unit 4's volume dial, read off directly). The $k$-th power $D^k$ is each entry raised to the $k$ — no matrix multiplication at all. The inverse is each non-zero entry flipped to $1/d_i$. Solving $D\mathbf{x}=\mathbf{b}$ is $n$ one-line divisions. A diagonal matrix is $n$ independent one-dimensional problems wearing a trench coat — nothing interacts, nothing tangles.

So the game is: given a general $A$, find a change of viewpoint in which $A$ becomes diagonal. That's it. That's the unit.

Formally: $A\in\mathbb{R}^{n\times n}$ is diagonalizable if there is an invertible $P$ and a diagonal $D$ with

Where do $P$ and $D$ come from? Multiply the definition out. $AP=PD$, and because $D$ is diagonal, the product $PD$ just scales each column of $P$ by its own diagonal entry. Column by column, $AP=PD$ says:

— which you have seen before. The columns of $P$ must be eigenvectors of $A$, and the diagonal of $D$ must be their eigenvalues. Diagonalization isn't a new technique; it is Unit 4's eigen-hunt, repackaged as a factorization. The lecture's opening example: $A=\begin{bmatrix}1&4\\2&3\end{bmatrix}$ with $P=\begin{bmatrix}-2&1\\1&1\end{bmatrix}$ gives $P^{-1}AP=\begin{bmatrix}-1&0\\0&5\end{bmatrix}$ — and sure enough, the columns $(-2,1)$ and $(1,1)$ are exactly the eigenvectors of $A$ for $\lambda=-1$ and $\lambda=5$ (check: $A\binom{-2}{1}=\binom{2}{-1}=-1\binom{-2}{1}$ ✓).

One catch, straight from Unit 4's fine print: this needs n independent eigenvectors to fill $P$'s columns — and $P$ must be genuinely invertible. Matrices with enough eigenvectors get the luxury; defective ones (the shear!) are turned away at the door. Hold that thought for Section 6.

Now the new reading, and it's the most important formula of the unit. Multiply $Q\Lambda Q^{\top}$ out column-against-row instead of the usual row-against-column, and the product unpacks into a sum of rank-1 layers:

Each block $\mathbf{q}_i\mathbf{q}_i^{\top}$ is a projector — Unit 3's shadow machine, boxed up as a matrix: it flattens any input onto the line through $\mathbf{q}_i$. So a symmetric matrix literally reads: "project onto axis 1 and amplify by $\lambda_1$, plus project onto axis 2 and amplify by $\lambda_2$, …" The eigenvalues become an honest importance ranking of the axes. Toggle the layers yourself:

The price of leaving the symmetric world: the eigenvectors lean. For the lecture's $A=\begin{bmatrix}1&4\\2&3\end{bmatrix}$: eigenvalues from $\lambda^2-4\lambda-5=(\lambda-5)(\lambda+1)=0$, so $\lambda_1=5,\ \lambda_2=-1$ (a negative eigenvalue — flip-and-scale — something a positive-definite symmetric matrix never shows). Eigenvectors: $\mathbf{p}_1=(1,1)$ and $\mathbf{p}_2=(-2,1)$. Check the angle: $\mathbf{p}_1\cdot\mathbf{p}_2=-1\neq0$ — not perpendicular. So $P=\begin{bmatrix}1&-2\\1&1\end{bmatrix}$ is invertible but not orthonormal, and the clean transpose is gone: $P^{-1}=\tfrac13\begin{bmatrix}1&2\\-1&1\end{bmatrix}$, computed honestly.

Why bother? The payoff is matrix powers for free. Sandwiched between $P$ and $P^{-1}$, repeated multiplication telescopes — every interior $P^{-1}P$ collapses to $I$:

Computing $A^3$ by brute force is nine dot products, twice. With the decomposition: cube two numbers ($5^3=125$, $(-1)^3=-1$) and translate once — $A^3=\begin{bmatrix}41&84\\42&83\end{bmatrix}$, done. The same telescope drives matrix exponentials, Markov-chain steady states, and the long-run behaviour of recurrent networks. Watch the translator and the telescope run:

Eigendecomposition is powerful, but it has a door policy, and Unit 4 already showed you both bouncers. Defective matrices: the shear $\begin{bmatrix}1&1\\0&1\end{bmatrix}$ owns a single eigen-direction — algebraic multiplicity 2, geometric multiplicity 1 — so there aren't enough independent columns to build an invertible $P$. No decomposition. Rotations: $\begin{bmatrix}0&-1\\1&0\end{bmatrix}$ turns every real direction, its eigenvalues fled to $\pm i$ — no real $P$ exists at all. And beyond both: a $3\times2$ data matrix isn't even square, so $A\mathbf{v}=\lambda\mathbf{v}$ is meaningless — the input is 2-D, the output 3-D; they can't be parallel because they don't live in the same space.

Three failures, one root cause: eigendecomposition insists on using a single set of axes for both input and output. The fix — dropping that insistence — is the SVD, and it repairs all three failures at once.

The theorem, in full dress. Every $A\in\mathbb{R}^{m\times n}$ of rank $r$ factors as

where $V\in\mathbb{R}^{n\times n}$ is orthonormal (the right-singular vectors — input axes), $U\in\mathbb{R}^{m\times m}$ is orthonormal (the left-singular vectors — output axes), and $\Sigma\in\mathbb{R}^{m\times n}$ is "diagonal" with the singular values $\sigma_1\ge\sigma_2\ge\cdots\ge\sigma_r>0$ on its diagonal, sorted loudest-first by convention, padded with zeros to match $A$'s shape. Read right-to-left, it is the unit's mantra in its final form: $V^{\top}$ rotates the input so the special directions sit on the axes, $\Sigma$ stretches each axis by $\sigma_i$, $U$ rotates into the final pose. Rotate · stretch · rotate — now for any matrix, including the ones eigendecomposition rejected:

Where do the three factors come from? From the rung we already own. $A$ may be rectangular, but $A^{\top}A$ (size $n\times n$) and $AA^{\top}$ (size $m\times m$) are both square, symmetric — Unit 4's Gram matrices — so Rung 1 applies to them. Substitute the SVD and watch the structure fall out:

That is a spectral decomposition of $A^{\top}A$ — so $V$ is its eigenvector matrix, and the eigenvalues sitting in $\Sigma^{\top}\Sigma$ are $\sigma_i^2$: the singular values are the square roots of $A^{\top}A$'s eigenvalues (which the spectral theorem guarantees are real and $\ge0$ — this is why σ's never go negative or complex). Symmetrically, $AA^{\top}=U\Sigma\Sigma^{\top}U^{\top}$ hands $U$ to us as the eigenvectors of $AA^{\top}$. And in practice you never even compute the second one: post-multiplying $A=U\Sigma V^{\top}$ by $V$ gives $AV=U\Sigma$, i.e. column by column

— each output axis is just the normalized image of its input axis. One eigendecomposition plus $r$ matrix–vector products and you own the whole factorization.

The lecture's wide example, walked through. $A=\begin{bmatrix}1&0&1\\-2&1&0\end{bmatrix}$ (2×3, rank 2). Step 1: $A^{\top}A=\begin{bmatrix}5&-2&1\\-2&1&0\\1&0&1\end{bmatrix}$, symmetric as promised. Step 2: its eigenvalues are $6,\ 1,\ 0$ — the zero is no accident: a 2×3 matrix has rank at most 2, so one input direction must be crushed. Step 3: $\sigma_1=\sqrt6,\ \sigma_2=1$, so $\Sigma=\begin{bmatrix}\sqrt6&0&0\\0&1&0\end{bmatrix}$ — 2×3 like $A$, with a zero column of padding. Step 4: eigenvectors $\mathbf{v}_1=\tfrac{1}{\sqrt{30}}(5,-2,1)$, $\mathbf{v}_2=\tfrac{1}{\sqrt5}(0,1,2)$, $\mathbf{v}_3=\tfrac{1}{\sqrt6}(-1,-2,1)$ — and $\mathbf{v}_3$, riding the zero eigenvalue, is exactly the nullspace direction $A$ annihilates. Step 5: $\mathbf{u}_1=\tfrac{1}{\sigma_1}A\mathbf{v}_1=\tfrac{1}{\sqrt5}(1,-2)$, $\mathbf{u}_2=\tfrac{1}{\sigma_2}A\mathbf{v}_2=\tfrac{1}{\sqrt5}(2,1)$ — automatically orthonormal. Assembled, $A=U\Sigma V^{\top}$ exactly.

This is the picture eigendecomposition could never draw: a matrix whose input and output live in different spaces. $B=\begin{bmatrix}1&1\\0&1\\1&0\end{bmatrix}$ eats a flat 2-D vector and produces a point in 3-D. Feed it the whole unit circle and the output is an ellipse — but an ellipse floating on a tilted plane inside 3-D space, the plane spanned by $\mathbf{u}_1$ and $\mathbf{u}_2$. The third output direction $\mathbf{u}_3$ sticks out of that plane and receives exactly nothing — it is the zero row of $\Sigma$ made visible. Drag the probe around the input circle and watch its image travel the ellipse:

Now collect the unit's two best ideas and let them collide. Section 4 read a symmetric matrix as a sum of importance-ranked projection layers. The SVD does the same for every matrix: multiply $U\Sigma V^{\top}$ out column-against-row and $\Sigma$'s diagonal pairs each $\mathbf{u}_i$ with its $\mathbf{v}_i$:

— a stack of rank-1 layers, sorted loudest-first because the σ's are sorted. Since real-world matrices concentrate their energy in the first few singular values, truncating the sum at $k$ terms gives the rank-$k$ approximation $\hat A(k)=\sum_{i=1}^{k}\sigma_i\mathbf{u}_i\mathbf{v}_i^{\top}$, and the Eckart–Young theorem says this is not merely a compression — it is provably the best possible rank-$k$ approximation of $A$, with error exactly the loudest singular value you discarded: $\|A-\hat A(k)\|_2=\sigma_{k+1}$.

The companion's tiny example, by hand: keep only the loudest layer of the tall $B$. $\hat B(1)=\sigma_1\mathbf{u}_1\mathbf{v}_1^{\top}=\sqrt3\cdot\tfrac{1}{\sqrt6}(2,1,1)^{\top}\cdot\tfrac{1}{\sqrt2}(1,1)=\begin{bmatrix}1&1\\0.5&0.5\\0.5&0.5\end{bmatrix}$, and the error is the dropped $\sigma_2=1$. Six numbers describing a matrix of six — no saving yet at this toy size. But scale it up: an image is a matrix, and now the layer cake becomes a compressor. Try it:

One last gift from the SVD. Ask: what is the most a matrix can ever amplify a vector? That worst-case stretch is the spectral norm,

— simply the longest semi-axis of the output ellipsoid, achieved by feeding in $\mathbf{v}_1$ (the output points along $\mathbf{u}_1$). The lecture's example: $A=\begin{bmatrix}1&2\\3&4\end{bmatrix}$ has $\Sigma=\operatorname{diag}(5.465,\,0.366)$, so $\|A\|_2=5.465$ — and the ratio $\sigma_1/\sigma_2\approx15$ says this matrix amplifies its favourite direction fifteen times more than its least favourite: fairly ill-conditioned, the kind of matrix that makes numerical software sweat. Spectral norms bound errors, govern the stability of deep networks (exploding/vanishing signals track products of σ's), and put the "spectral" in spectral normalization for GANs.

And the family portrait, one table to close the ladder:

① A matrix is a transformation, and decomposition is prime factorization for transformations: rewrite $A$ as rotate → stretch → rotate, without changing what it does. ② The chase is always for a diagonal middle — because diagonal matrices reduce every question to arithmetic on $n$ separate numbers. ③ Spectral ($A=Q\Lambda Q^{\top}$, symmetric only) is the flawless rung: perpendicular axes, free transpose, and the layer reading $A=\sum\lambda_i\mathbf{q}_i\mathbf{q}_i^{\top}$. Eigen ($A=PDP^{-1}$, square + enough eigenvectors) keeps the idea on tilted axes and pays with an inverse — earning $A^k=PD^kP^{-1}$. ④ SVD ($A=U\Sigma V^{\top}$) drops every remaining requirement by using two orthonormal frames bridged by non-negative stretches — built from the spectral decomposition of $A^{\top}A$, with $\mathbf{u}_i=A\mathbf{v}_i/\sigma_i$ for free. ⑤ Sorting the σ's turns every matrix into a loudest-first layer cake: truncate for the provably-best low-rank approximation (Eckart–Young), read $\sigma_1$ as the worst-case amplification (spectral norm), and you hold the mathematics of compression, denoising, PCA, and recommenders in one formula.