Unit 5 · Matrix Decompositions & SVD — The Math Behind the Machine

1

Taking things apart — the oldest trick in mathematics

Imagine this

Open any photo on your phone and tap Edit. You get two simple tools. Rotate turns the photo. Resize lets you drag the width and the height, each on its own.

That is all. There is no "slant" tool and no "twist" tool. Yet here is a surprising fact: every matrix is just rotate, resize, rotate. Three taps in a photo editor.

Remember from Unit 1: a matrix is a machine that moves space. Its numbers mix the turning and the stretching together, so you cannot see them. Look at $\begin{bmatrix}3&0\\4&5\end{bmatrix}$ . Does it turn things? By how much? The four numbers do not say.

Numbers have the same problem. Is 5040 divisible by 48? Hard to tell. Now write both in pieces: $5040=2^4\cdot3^2\cdot5\cdot7$ and $48=2^4\cdot3$ . Suddenly the answer is an easy yes. The number did not change. We only wrote it in a form that shows what it is made of.

A decomposition does this for a matrix. It is factoring, for matrices. It rewrites a matrix $A$ as a few simple moves, done one after another. Watch it happen to a photo:

Try: press ▶ play. Then pick the shear and play again.

drag the picture to orbit

—

The dashed orange outline is where the matrix sends the photo in one go. The three simple moves land on it exactly.

Turn, resize, turn — that is where we are heading. We get there in three steps. Each step asks for less and works for more matrices:

Step 1 · SpectralA = QΛQᵀsymmetric A only — perpendicular axes, free inverse (just the transpose)

↓ now allow axes that lean

Step 2 · EigendecompositionA = PDP⁻¹any square A with enough eigenvectors — leaning axes, real inverse

↓ now allow any shape at all

Step 3 · SVDA = UΣVᵀEVERY matrix, any shape — two perpendicular frames, always works

Why this order? Step 1 is the perfect case: the matrix only resizes, along directions at right angles. Step 2 asks: what if those directions lean? The idea still works, but it costs more. Step 3 asks the big question: what if the matrix is not even square? The SVD answers it with one recipe that works for every matrix.

The realization

A matrix looks like a block of numbers. Underneath, it is a short list of simple moves. Writing $A=(\text{turn})\,(\text{resize})\,(\text{turn})$ does not change $A$ at all. It only lets you see what $A$ does.

Pause & predict

Pick the shear. It slides the top of the photo sideways. Yet the three moves are only turns and a resize. What does that tell you?

Pause & predict

When we write $12=2\times2\times3$ , the number does not change. What is the same idea for $A=U\Sigma V^{\top}$ ?

In one sentence: a decomposition rewrites a matrix as a few simple moves — turn, resize, turn — without changing what it does.

2

The goal — diagonal matrices are easy

Imagine this

In the photo editor, the resize tool has two handles. One sets the width. The other sets the height. Make the width ×2 and the height ×0.6.

The width handle never touches the height. The height handle never touches the width. Each handle minds its own business.

A matrix that works like the resize tool has numbers only on its diagonal — the line from top-left to bottom-right. Every other entry is zero. We call it a diagonal matrix:

D=\begin{bmatrix}2&0\\0&0.6\end{bmatrix}\qquad(\text{width}\times2,\ \text{height}\times0.6)

Diagonal matrices are the easiest matrices there are. Every hard question turns into easy arithmetic, one axis at a time:

The question	In everyday words	For this $D$
Do it 3 times, $D^3$	Width ×2 three times, height ×0.6 three times.	$\operatorname{diag}(8,\ 0.216)$
Undo it, $D^{-1}$	Divide by each handle instead.	$\operatorname{diag}(0.5,\ 1.667)$
Area change, $\det D$	Multiply the two handles.	$2\times0.6=1.2$
Solve $D\mathbf x=\mathbf b$	One division per axis.	$x_1=b_1/2,\ \ x_2=b_2/0.6$

In general we write $D=\operatorname{diag}(d_1,\dots,d_n)$ (read it: "the matrix with $d_1$ to $d_n$ down its diagonal, zeros everywhere else"). It is really $n$ separate one-number problems. Nothing mixes with anything.

So here is the plan for the whole unit. Take a messy matrix. Find a new point of view in which it becomes a resize tool. First, play with the two handles:

Try: press "set d₂ to 0" and read the undo line. Then try "flip d₁".

width handle d₁2

height handle d₂0.6

repeat k times1

—

Each handle owns one axis and cannot touch the other. A handle at 0 flattens its axis, and nothing can undo that.

The realization

A diagonal matrix is a resize tool: one handle per axis. Repeating, undoing and measuring area all work one number at a time: $D^k=\operatorname{diag}(d_1^k,\dots,d_n^k)$ . The only danger is a handle set to 0 — that axis is flattened for good.

Pause & predict

$D=\operatorname{diag}(5,-1)$ . What is $D^{3}$ , and how long did it take you?

In one sentence: a diagonal matrix is easy because each axis minds its own business — so this unit is a hunt for the diagonal hiding inside every matrix.

3

Diagonalizable — same machine, better glasses

Imagine this

A carpenter looks at a plank before cutting it. Along the grain, the wood splits cleanly. Across the grain, it fights back. The plank has its own favourite directions.

A good carpenter works along those directions, not along the edges of the table. Matrices are the same.

Take the lecture's matrix $A=\begin{bmatrix}1&4\\2&3\end{bmatrix}$ . In the usual x–y grid it looks messy: it turns and stretches at once. But it has two favourite directions, where it does nothing but resize:

Along $\mathbf p_1=(1,1)$ it stretches by 5: $A\mathbf p_1=(5,5)=5\,\mathbf p_1$ .
Along $\mathbf p_2=(-2,1)$ it just flips: $A\mathbf p_2=(2,-1)=-1\cdot\mathbf p_2$ .

You met these in Unit 4: they are the eigenvectors, and 5 and −1 are the eigenvalues. Now use the two favourite directions as your new axes. In those axes, $A$ is a resize tool: ×5 on one axis, ×(−1) on the other. That is what diagonalizable means. In symbols:

A=PDP^{-1},\qquad P=\begin{bmatrix}1&-2\\1&1\end{bmatrix},\quad D=\begin{bmatrix}5&0\\0&-1\end{bmatrix}

Read it right to left, like a sentence. $P^{-1}$ switches to the new axes. $D$ resizes along them. $P$ switches back. The columns of $P$ are the favourite directions. The diagonal of $D$ says how much each one is stretched.

Why must the columns be eigenvectors? Multiply $A=PDP^{-1}$ on the right by $P$ to get $AP=PD$ . Read it one column at a time and it says $A\mathbf p_i=\lambda_i\mathbf p_i$ : " $A$ only stretches $\mathbf p_i$ ." That is the definition of an eigenvector. So diagonalizing is Unit 4's eigen-hunt, packed into one formula.

$A=\begin{bmatrix}1&4\\2&3\end{bmatrix}$ : the columns of $P$ are the only directions that $A$ just resizes.

If you want the algebra · why AP = PD forces eigenvectors

Why AP = PD forces eigenvectors — derived

Claim. If $AP=PD$ with $P=[\mathbf p_1\;\cdots\;\mathbf p_n]$ and $D=\operatorname{diag}(\lambda_1,\dots,\lambda_n)$ , then $A\mathbf p_i=\lambda_i\mathbf p_i$ for every $i$ .

1

Column

i

of the left side:

(AP)\,\mathbf e_i = A\,(P\mathbf e_i) = A\mathbf p_i

Multiplying by

\mathbf e_i

picks out column

i

, and matrix products associate — so column

i

of

AP

is

A

applied to column

i

of

P

.

2

Column

i

of the right side:

(PD)\,\mathbf e_i = P\,(D\mathbf e_i) = P\,(\lambda_i\mathbf e_i) = \lambda_i\,P\mathbf e_i=\lambda_i\mathbf p_i

Column

i

of a diagonal matrix is

\lambda_i\mathbf e_i

— one number, in one slot. Scalars slide through a matrix product.

3

The two sides are the same matrix, so their

i

-th columns agree:

A\mathbf p_i=\lambda_i\mathbf p_i\qquad(i=1,\dots,n)

Every column of

P

is an eigenvector and its diagonal partner is the eigenvalue. Run the steps backwards and you get the converse: stack any

n

eigenvectors as columns and

AP=PD

holds automatically. When those columns are independent,

P^{-1}

exists and

A=PDP^{-1}

. ∎

One catch, straight from Unit 4. You need $n$ independent favourite directions to fill the $n$ columns of $P$ . Otherwise $P$ has no inverse, and the recipe breaks. Some matrices do not have enough — Section 6 shows who.

One more example, a symmetric one: $\begin{bmatrix}2.5&-1\\-1&2.5\end{bmatrix}$ stretches $(1,-1)$ by 3.5 and $(1,1)$ by 1.5. This time the two favourite directions are at right angles. That is no accident — it is the next section.

The realization

$A=PDP^{-1}$ says: in its own favourite directions, $A$ is just a resize tool. The columns of $P$ are those directions (the eigenvectors). The diagonal of $D$ says how much each is stretched (the eigenvalues).

In one sentence: $A=PDP^{-1}$ just says: put $A$ 's eigenvectors in the columns of $P$ and their eigenvalues in $D$ .

4

Step 1 · Spectral — the perfect case, read a new way

Imagine this

Open the equalizer in your music app. It splits the song into bass and treble. You turn the bass up ×3 and leave the treble at ×1. Then the app adds the two parts back together and plays the result.

Split, turn each part up or down, add back. Hold on to that. It is exactly how a symmetric matrix works.

A symmetric matrix equals its own mirror image across the diagonal: $A=A^{\top}$ (read it: "A equals A-transpose"). Our running example is $A=\begin{bmatrix}2&1\\1&2\end{bmatrix}$ .

Unit 4's Spectral Theorem promised two things about symmetric matrices. Their favourite directions are at right angles. And their stretch amounts are real numbers. For our $A$ :

$\mathbf q_1=\tfrac{1}{\sqrt2}(1,1)$ is stretched by $\lambda_1=3$ . Call it the "bass" channel.
$\mathbf q_2=\tfrac{1}{\sqrt2}(-1,1)$ is stretched by $\lambda_2=1$ . Call it the "treble" channel.

Now run the equalizer on the input $\mathbf x=(2,0)$ :

Split. The shadow of $\mathbf x$ on the $\mathbf q_1$ line is $(1,1)$ . Its shadow on the $\mathbf q_2$ line is $(1,-1)$ . Check: $(1,1)+(1,-1)=(2,0)$ ✓.
Turn each part up. Bass ×3 gives $(3,3)$ . Treble ×1 stays $(1,-1)$ .
Add back. $(3,3)+(1,-1)=(4,2)$ . And directly, $A\mathbf x=(2\cdot2+1\cdot0,\ 1\cdot2+2\cdot0)=(4,2)$ ✓.

In symbols, "the shadow on the line through $\mathbf q_i$ " is the small matrix $\mathbf q_i\mathbf q_i^{\top}$ . Unit 3 called it a projector. So the whole matrix is a sum of layers, one per channel:

A=\lambda_1\,\mathbf{q}_1\mathbf{q}_1^{\top}+\lambda_2\,\mathbf{q}_2\mathbf{q}_2^{\top}+\cdots+\lambda_n\,\mathbf{q}_n\mathbf{q}_n^{\top}

Stack the directions as the columns of a matrix $Q$ , and the stretches into a diagonal $\Lambda$ ("capital lambda"). Then the same sum reads $A=Q\Lambda Q^{\top}$ . This is the spectral decomposition.

Its bonus: the columns of $Q$ are at right angles and have length 1. So undoing $Q$ costs nothing — $Q^{-1}$ is just $Q^{\top}$ , the transpose. The biggest $\lambda$ is the loudest layer. Keep that thought; in Section 10 it becomes photo compression. Now play with the layers:

Try: press ▶ play. Then press "x on the q₂ line" and pick "λ₁ layer only".

drag the picture to orbit · drag the gold x on the floor

—

Each layer alone squashes the circle flat onto its own line. Added together, they rebuild the full oval — and the matrix.

The realization

A symmetric matrix is an equalizer. It splits the input along directions at right angles, turns each part up by its own $\lambda$ , and adds them back: $A=\sum_i\lambda_i\,\mathbf q_i\mathbf q_i^{\top}=Q\Lambda Q^{\top}$ . Undoing the split is free, because $Q^{-1}=Q^{\top}$ .

The lecture's 3 × 3 spectral workout — every step

Decompose $A=\begin{bmatrix}2&-1&0\\-1&2&-1\\0&-1&2\end{bmatrix}$ . It is symmetric, so the theorem applies and we know in advance the answer will have perpendicular axes.

Eigenvalues. $\det(A-\lambda I)=(2-\lambda)\big[(2-\lambda)^2-2\big]=0$ , so $\lambda_1=2+\sqrt2\approx3.414$ , $\lambda_2=2$ , $\lambda_3=2-\sqrt2\approx0.586$ — all real, as promised.
Eigenvectors. Solve each $(A-\lambda I)\mathbf v=\mathbf 0$ by Unit 1 elimination and normalise: $\mathbf q_1=\tfrac12(1,-\sqrt2,1)$ , $\mathbf q_2=\tfrac{1}{\sqrt2}(1,0,-1)$ , $\mathbf q_3=\tfrac12(1,\sqrt2,1)$ .
Free sanity check. $\mathbf q_1\cdot\mathbf q_2=0$ and $\mathbf q_1\cdot\mathbf q_3=\tfrac14(1-2+1)=0$ : orthogonality arrived without being asked — the Spectral Theorem at work.
Assemble. $A=Q\Lambda Q^{\top}$ with $\Lambda=\operatorname{diag}(2+\sqrt2,\,2,\,2-\sqrt2)$ ; as layers, $A=(2{+}\sqrt2)\,\mathbf q_1\mathbf q_1^{\top}+2\,\mathbf q_2\mathbf q_2^{\top}+(2{-}\sqrt2)\,\mathbf q_3\mathbf q_3^{\top}$ .

So what: the first layer does most of the work; the $0.586$ layer is a finishing touch. Drop it and you have a rank-2 matrix that is already close to $A$ — Section 10 turns that observation into compression.

If you want the algebra · why QΛQᵀ is a sum of layers

Why QΛQᵀ is a sum of layers — derived

Claim. If $Q=[\mathbf q_1\cdots\mathbf q_n]$ and $\Lambda=\operatorname{diag}(\lambda_1,\dots,\lambda_n)$ , then $Q\Lambda Q^{\top}=\sum_{i=1}^{n}\lambda_i\,\mathbf q_i\mathbf q_i^{\top}$ .

1

First the inner product

Q\Lambda

, column by column:

Q\Lambda=[\lambda_1\mathbf q_1\;\;\lambda_2\mathbf q_2\;\cdots\;\lambda_n\mathbf q_n]

Same fact as in Section 3: multiplying by a diagonal matrix on the right scales each column by its own diagonal entry.

2

Now multiply by

Q^{\top}

, whose rows are

\mathbf q_1^{\top},\dots,\mathbf q_n^{\top}

. Write the product entry-wise:

(Q\Lambda Q^{\top})_{jk}=\sum_{i=1}^{n}(Q\Lambda)_{ji}\,(Q^{\top})_{ik}=\sum_{i=1}^{n}\lambda_i\,(\mathbf q_i)_j\,(\mathbf q_i)_k

The definition of a matrix product — entry

jk

is a sum over the shared index

i

. Step 1 says

(Q\Lambda)_{ji}=\lambda_i(\mathbf q_i)_j

, and

(Q^{\top})_{ik}=(\mathbf q_i)_k

.

3

Recognise each summand as an entry of an outer product:

(\mathbf q_i\mathbf q_i^{\top})_{jk}=(\mathbf q_i)_j(\mathbf q_i)_k

. So

Q\Lambda Q^{\top}=\sum_{i=1}^{n}\lambda_i\,\mathbf q_i\mathbf q_i^{\top}

The sum over

i

of "column

i

times row

i

" is the column-times-row way of multiplying — it is always available, and here each term is a rank-1 layer.

4

Why each layer is a projector: for unit

\mathbf q_i

,

(\mathbf q_i\mathbf q_i^{\top})\mathbf x=\mathbf q_i(\mathbf q_i^{\top}\mathbf x)=(\mathbf q_i\cdot\mathbf x)\,\mathbf q_i

. That is the shadow of

\mathbf x

on the line through

\mathbf q_i

(Unit 3). So

A\mathbf x=\sum_i\lambda_i(\mathbf q_i\cdot\mathbf x)\mathbf q_i

: take each shadow, scale it by its eigenvalue, add. Exactly what the widget draws. ∎

Pause & predict

In $A=Q\Lambda Q^{\top}$ , undoing the outer factor costs only a transpose. In $A=PDP^{-1}$ it costs a real inverse. What gives symmetric matrices this discount?

In one sentence: a symmetric matrix is a set of perpendicular directions, each turned up by its own eigenvalue — nothing more.

5

Step 2 · Eigendecomposition — the matrix's own language

Imagine this

Your grandmother tells a joke in Marathi. Translated word by word into English, it sounds long and confusing. In Marathi it is short and simple.

The joke was never complicated. You were just hearing it in the wrong language. So: translate in, enjoy it there, translate back.

A general square matrix is the same. In the usual x–y grid it looks complicated. In its own language — its favourite directions — it only resizes.

Outside the symmetric world there is one price. The favourite directions lean: they are no longer at right angles. Take $A=\begin{bmatrix}1&4\\2&3\end{bmatrix}$ again. Its directions are $\mathbf p_1=(1,1)$ (stretch ×5) and $\mathbf p_2=(-2,1)$ (flip, ×−1). Their dot product is $1\cdot(-2)+1\cdot1=-1$ , not 0. So they lean.

Because they lean, the free transpose trick is gone. We need a real inverse: $P^{-1}=\tfrac13\begin{bmatrix}1&2\\-1&1\end{bmatrix}$ . The formula $A=PDP^{-1}$ is now a translator in three steps:

$P^{-1}$ translates $\mathbf x$ into the matrix's language: "how much of $\mathbf p_1$ , how much of $\mathbf p_2$ ?"
$D$ does the simple job there: ×5 and ×(−1).
$P$ translates the answer back to x–y.

Why bother? Because repeating the matrix becomes almost free. Doing $A$ three times is $A^3$ . Write each $A$ as a translator, and every $P^{-1}P$ in the middle cancels out:

A^{3}=(PDP^{-1})(PDP^{-1})(PDP^{-1})=P\,D^{3}\,P^{-1}

So you only cube two plain numbers: $5^3=125$ and $(-1)^3=-1$ . Translate back once, and $A^3=\begin{bmatrix}41&84\\42&83\end{bmatrix}$ . The same shortcut powers Google's PageRank, population models and Markov chains — anything that repeats one step many times. Watch the translator work:

Try: step through 1 → 4. Then drag the gold x onto the dashed p₂ line and watch step 3.

✋ drag the gold arrowhead to choose x

repeat k times1

—

The dashed axes lean, so x splits into a slanted parallelogram, not a rectangle. Slide k: $D^k$ is just $(5^k,(-1)^k)$ .

The realization

$A=PDP^{-1}$ is a translator: into the matrix's own directions, resize, and back. Its best trick is repetition: $A^k=PD^kP^{-1}$ . Powers of a matrix become powers of plain numbers.

If you want the algebra · why Aᵏ = PDᵏP⁻¹

Why Aᵏ = PDᵏP⁻¹ — derived

Claim. If $A=PDP^{-1}$ , then $A^{k}=PD^{k}P^{-1}$ for every whole number $k\ge1$ .

1

Do

k=2

by hand:

A^{2}=(PDP^{-1})(PDP^{-1})=PD\,(P^{-1}P)\,DP^{-1}=PD\,I\,DP^{-1}=PD^{2}P^{-1}

Matrix multiplication is associative, so the brackets can be regrouped freely; the only thing that happens is the

P^{-1}P

in the middle collapsing to

I

.

2

Suppose it holds for some

k

. Multiply once more by

A

:

A^{k+1}=A^{k}A=(PD^{k}P^{-1})(PDP^{-1})=PD^{k}(P^{-1}P)DP^{-1}=PD^{k+1}P^{-1}

The same collapse, one more time. Starting from step 1 and repeating step 2 reaches every

k

— that is induction.

3

And

D^{k}

costs nothing: for a diagonal matrix,

(D^{k})_{ii}=\lambda_i^{k}

and every off-diagonal entry stays

0

. A diagonal times a diagonal multiplies entry by entry (Section 2). For the lecture's

D=\operatorname{diag}(5,-1)

:

D^{3}=\operatorname{diag}(125,-1)

, then one product

PD^{3}P^{-1}

gives

\begin{bmatrix}41&84\\42&83\end{bmatrix}

. Two scalar cubes replaced two matrix multiplications. ∎

Pause & predict

With $D=\operatorname{diag}(5,-1)$ , what happens to $A^{k}\mathbf{x}$ when $k$ is large and even?

Pause & predict

Diagonalize $\begin{bmatrix}2&1\\0&3\end{bmatrix}$ in your head. What are the eigenvalues, and is this spectral or only eigen?

In one sentence: $P^{-1}$ translates into the matrix's own language, $D$ does a simple resize there, and $P$ translates back.

6

Where eigendecomposition fails — and the fix

Imagine this

Look at three everyday motions. A ceiling fan spins: every direction on its blades turns, none stays put. A deck of cards pushed sideways: only the direction along the table stays put — one direction, not two.

And a shadow on the wall: your 3-D hand becomes a flat 2-D shape. The input and the output do not even live in the same world.

Eigendecomposition needs enough favourite directions — directions the matrix does not turn. These three kinds of matrix do not have them:

The matrix	Everyday picture	What goes wrong
The shear $\begin{bmatrix}1&1\\0&1\end{bmatrix}$	a deck of cards pushed sideways	Only one direction stays unturned. A 2×2 matrix needs two. (Unit 4 called this "defective".)
The rotation $\begin{bmatrix}0&-1\\1&0\end{bmatrix}$	a spinning fan	Every direction turns. The eigenvalues are the imaginary $\pm i$ , so no real $P$ exists.
A $3\times2$ data matrix	2-D in, 3-D out	Not square. " $A\mathbf v=\lambda\mathbf v$ " makes no sense: input and output live in different spaces.

Three failures, one cause. Eigendecomposition insists on one set of axes for both the input and the output. The SVD drops that demand, and all three failures disappear at once.

See it for yourself first. Sweep a direction around the circle and watch for the moments when $A\mathbf v$ points the same way as $\mathbf v$ :

Try: press ▶ auto-sweep on each matrix and count the pauses.

✋ drag the dial — or press play and let it sweep

—

The strip shows how much every direction gets turned. Each place it touches zero is an eigenvector: symmetric 2, leaning 2, shear 1, rotation 0.

The realization

An eigenvector is a direction the matrix does not turn. Eigendecomposition needs $n$ independent ones for an $n\times n$ matrix. The shear has one, the rotation has none, and a rectangular matrix cannot even ask the question.

Pause & predict

On the strip, the shear's curve touches zero exactly once (along the x-axis). What does that say, in Unit 4's words?

In one sentence: eigendecomposition fails whenever one set of axes must serve both input and output — the shear, the rotation, and every rectangular matrix.

7

Step 3 · SVD — two frames, every matrix, no exceptions

Imagine this

Draw a circle on a flat sheet of rubber. Now pull, push and twist the sheet any way you like, keeping it flat. The circle always becomes an oval.

And every oval has a longest direction and a shortest direction. Those two are always at right angles. Always.

That one fact is the whole SVD. Eigendecomposition asked: "which directions does the matrix not turn?" Sometimes the answer is "none". The SVD asks a friendlier question that always has an answer: "which directions at right angles land on directions at right angles?"

Feed any matrix the unit circle and you get an oval (an ellipse). Its two axes are at right angles. Now walk backwards: which input directions landed on those axes? They turn out to be at right angles too. So we get two frames — one for the input, one for the output.

For the lecture's $A=\begin{bmatrix}3&0\\4&5\end{bmatrix}$ , the oval's long half-axis is $\sigma_1=3\sqrt5\approx6.71$ and its short half-axis is $\sigma_2=\sqrt5\approx2.24$ . These lengths are the singular values ( $\sigma$ is the Greek letter "sigma").

Here is the theorem. Every matrix $A$ , of any shape $m\times n$ , can be written as

A=U\,\Sigma\,V^{\top}

Piece	What it does	Photo editor
$V^{\top}$	Turns the input so the special input directions $\mathbf v_i$ sit on the axes.	rotate
$\Sigma$	Stretches axis $i$ by $\sigma_i$ . The $\sigma$ 's are never negative and are sorted biggest first.	resize
$U$	Turns the result into place, so the axes land on the output directions $\mathbf u_i$ .	rotate

The $\mathbf v_i$ are called right-singular vectors (the input frame). The $\mathbf u_i$ are left-singular vectors (the output frame). The whole story fits in one line: $A\mathbf v_i=\sigma_i\mathbf u_i$ — "input direction $i$ lands on output direction $i$ , stretched by $\sigma_i$ ." Watch it on a lit sphere, including the matrices that eigendecomposition turned away:

Try: pick the rotation and press ▶ play. The resize step does nothing (σ₁ = σ₂ = 1), yet the SVD still exists.

drag the picture to orbit · the matrix acts on the floor plane; the up-axis just rides along

σ₁ = — σ₂ = — σ₁/σ₂ = —

—

Watch the orange input frame ride the pipeline and land exactly on the blue axes $\sigma_i\mathbf{u}_i$ . That landing is $A\mathbf{v}_i=\sigma_i\mathbf{u}_i$ , acted out.

The realization

Every matrix is turn · resize · turn: $A=U\Sigma V^{\top}$ . There are two frames at right angles — $V$ for inputs, $U$ for outputs — and a list of stretches $\sigma_1\ge\sigma_2\ge\dots\ge0$ . No exceptions: not rotations, not shears, not rectangles.

Pause & predict

The rotation $\begin{bmatrix}0&-1\\1&0\end{bmatrix}$ had no real eigendecomposition. What about its SVD?

Pause & predict

$A=\begin{bmatrix}3&0\\4&5\end{bmatrix}$ has eigenvalues 3 and 5 (read off the diagonal of a triangular matrix). Are its singular values also 3 and 5?

In one sentence: every matrix is turn · resize · turn — $V^{\top}$ , then $\Sigma$ , then $U$ — no exceptions.

8

Building U, Σ, V — the symmetric-matrix bridge

Imagine this

Shout "hello" across a valley. Your voice travels out, hits the far hill, and comes back as an echo. From some spots the echo comes back loud and straight at you. From others it comes back faint.

Listening to the round trip tells you a lot about the valley. We will find the SVD the same way.

We do not attack $A$ head-on. $A$ sends a vector out; its transpose $A^{\top}$ brings it back. The round trip is the matrix $A^{\top}A$ . Whatever shape $A$ has, $A^{\top}A$ is always square and symmetric — exactly the easy case that Step 1 already solved.

The picture below shows why the round trip works. $A$ sends $\mathbf v_i$ to $\sigma_i\mathbf u_i$ . Then $A^{\top}$ sends that straight back along $\mathbf v_i$ , stretched by $\sigma_i$ again. So:

A^{\top}A\,\mathbf v_i=\sigma_i^{2}\,\mathbf v_i

Read it aloud: " $\mathbf v_i$ is an eigenvector of $A^{\top}A$ , and its eigenvalue is $\sigma_i^2$ ." The echo comes back in the same direction, $\sigma_i^2$ times as loud.

Why the detour works: $A$ carries $\mathbf v_i$ to $\sigma_i\mathbf u_i$ , and $A^{\top}$ carries $\sigma_i\mathbf u_i$ straight back to $\sigma_i^2\mathbf v_i$ . Round trip: $A^{\top}A\mathbf v_i=\sigma_i^2\mathbf v_i$ .

So the recipe writes itself:

Take the round trip. Form $A^{\top}A$ (or $AA^{\top}$ — whichever is smaller).
Use Step 1 on it. Find its eigenvalues $\lambda_i$ and its perpendicular eigenvectors. The eigenvectors are the input frame $\mathbf v_i$ .
Get the stretches. $\sigma_i=\sqrt{\lambda_i}$ , sorted biggest first. The $\lambda_i$ are never negative, so the square root always works.
Get the output frame for free. $\mathbf u_i=\tfrac{1}{\sigma_i}A\mathbf v_i$ : push each input direction through $A$ , then shrink it to length 1.
Assemble. $A=U\Sigma V^{\top}$ . Pad $\Sigma$ with zeros so it has exactly the shape of $A$ .

If you want the algebra · why AᵀA hands over V and the σ's, and why the uᵢ come out perpendicular

Why AᵀA hands over V and the σ's — derived

Claim. If $A=U\Sigma V^{\top}$ with orthonormal $U,V$ , then $A^{\top}A=V(\Sigma^{\top}\Sigma)V^{\top}$ ; hence each $\mathbf v_i$ is an eigenvector of $A^{\top}A$ with eigenvalue $\sigma_i^{2}\ge0$ .

1

Transpose the factorization:

A^{\top}=(U\Sigma V^{\top})^{\top}=(V^{\top})^{\top}\Sigma^{\top}U^{\top}=V\Sigma^{\top}U^{\top}

The transpose of a product is the product of the transposes in reverse order, and

(V^{\top})^{\top}=V

.

2

Multiply and let the middle collapse:

A^{\top}A=V\Sigma^{\top}\underbrace{U^{\top}U}_{=I}\Sigma V^{\top}=V\,(\Sigma^{\top}\Sigma)\,V^{\top}

U

has orthonormal columns, so

U^{\top}U=I

— the same free inverse that made Step 1 cheap.

3

Look at the middle factor.

\Sigma

is

m\times n

with

\sigma_i

in slot

(i,i)

, so

\Sigma^{\top}\Sigma

is

n\times n

and

(\Sigma^{\top}\Sigma)_{jk}=\sum_{i}\Sigma_{ij}\Sigma_{ik}=\begin{cases}\sigma_j^{2}&j=k\le r\\0&\text{otherwise}\end{cases}

Column

j

of

\Sigma

has at most one non-zero entry,

\sigma_j

; two different columns never share a row, so their dot product is 0. Result:

\Sigma^{\top}\Sigma=\operatorname{diag}(\sigma_1^{2},\dots,\sigma_r^{2},0,\dots,0)

.

4

Step 2 now reads

A^{\top}A=V\Lambda V^{\top}

with

\Lambda

diagonal and

V

orthonormal — a spectral decomposition. By Section 3, column

i

of

V

is an eigenvector:

A^{\top}A\,\mathbf v_i=\sigma_i^{2}\,\mathbf v_i

So

\lambda_i(A^{\top}A)=\sigma_i^{2}

and

\sigma_i=\sqrt{\lambda_i}

. Those eigenvalues can never be negative:

\lambda_i=\mathbf v_i^{\top}A^{\top}A\mathbf v_i=\|A\mathbf v_i\|^{2}\ge0

. Real, non-negative σ's — for every matrix. ∎

Why uᵢ = Avᵢ/σᵢ come out orthonormal — derived

Claim. Let $\mathbf v_1,\dots,\mathbf v_r$ be orthonormal eigenvectors of $A^{\top}A$ with eigenvalues $\sigma_i^{2}>0$ , and set $\mathbf u_i=A\mathbf v_i/\sigma_i$ . Then $\mathbf u_i\cdot\mathbf u_j=1$ if $i=j$ and $0$ otherwise.

1

Write the dot product as a matrix product and move

A

across:

\mathbf u_i\cdot\mathbf u_j=\frac{(A\mathbf v_i)^{\top}(A\mathbf v_j)}{\sigma_i\sigma_j}=\frac{\mathbf v_i^{\top}(A^{\top}A\,\mathbf v_j)}{\sigma_i\sigma_j}

(A\mathbf v_i)^{\top}=\mathbf v_i^{\top}A^{\top}

, then regroup the brackets — associativity again.

2

Use the eigen-equation

A^{\top}A\mathbf v_j=\sigma_j^{2}\mathbf v_j

:

\mathbf u_i\cdot\mathbf u_j=\frac{\sigma_j^{2}\,(\mathbf v_i\cdot\mathbf v_j)}{\sigma_i\sigma_j}=\frac{\sigma_j}{\sigma_i}\,(\mathbf v_i\cdot\mathbf v_j)

The scalar

\sigma_j^{2}

comes out in front, and one

\sigma_j

cancels against the denominator.

3

The

\mathbf v

's are orthonormal, so

\mathbf v_i\cdot\mathbf v_j

is

1

when

i=j

and

0

otherwise:

\mathbf u_i\cdot\mathbf u_i=\frac{\sigma_i}{\sigma_i}\cdot1=1,\qquad \mathbf u_i\cdot\mathbf u_j=\frac{\sigma_j}{\sigma_i}\cdot0=0\quad(i\ne j)

Unit length and mutually perpendicular — no Gram–Schmidt, no second eigen-problem. The outputs inherit orthogonality from the inputs through

A^{\top}A

. (If

r<m

, complete

U

with any orthonormal extra columns; they ride on σ = 0.) ∎

Let's run the recipe on the lecture's wide matrix $A=\begin{bmatrix}1&0&1\\-2&1&0\end{bmatrix}$ . It is 2×3 (2 rows, 3 columns): it eats 3-D vectors and returns 2-D ones. Its rank is 2, so expect two non-zero $\sigma$ 's and one input direction that gets flattened.

Round trip. $A^{\top}A=\begin{bmatrix}5&-2&1\\-2&1&0\\1&0&1\end{bmatrix}$ — 3×3 and symmetric, as promised.
Eigenvalues. $6,\ 1,\ 0$ . The 0 is expected: a 2×3 matrix squeezes 3-D into 2-D, so one input direction must be flattened.
Stretches. $\sigma_1=\sqrt6,\ \sigma_2=1$ . So $\Sigma=\begin{bmatrix}\sqrt6&0&0\\0&1&0\end{bmatrix}$ — 2×3 like $A$ , padded with a zero column.
Input frame. $\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)$ . The last one goes with $\sigma=0$ : it is the direction $A$ flattens to zero.
Output frame, free. $\mathbf{u}_1=\tfrac{1}{\sqrt6}A\mathbf{v}_1=\tfrac{1}{\sqrt5}(1,-2)$ and $\mathbf{u}_2=A\mathbf{v}_2=\tfrac{1}{\sqrt5}(2,1)$ . They come out perpendicular without being asked.

Multiply back and $A=U\Sigma V^{\top}$ exactly. The whole job cost one 3×3 eigen-problem and two quick products.

The tall twin: the SVD of a 3×2 matrix — featuring an old friend

$B$ is 3×2, so be smart and take the smaller Gram matrix: $B^{\top}B=\begin{bmatrix}2&1\\1&2\end{bmatrix}$ — the very matrix this unit keeps meeting. Its spectral data is familiar by now: $\lambda=3,1$ on $\tfrac{1}{\sqrt2}(1,1)$ , $\tfrac{1}{\sqrt2}(1,-1)$ . So $\sigma_1=\sqrt3,\ \sigma_2=1$ , $\mathbf{v}_{1,2}$ as above, and $\mathbf{u}_1=\tfrac{1}{\sqrt3}B\mathbf{v}_1=\tfrac{1}{\sqrt6}(2,1,1)$ , $\mathbf{u}_2=B\mathbf{v}_2=\tfrac{1}{\sqrt2}(0,-1,1)$ . A third vector $\mathbf{u}_3=\tfrac{1}{\sqrt3}(1,-1,-1)$ completes the 3×3 $U$ but rides on $\sigma_3=0$ : $\Sigma=\begin{bmatrix}\sqrt3&0\\0&1\\0&0\end{bmatrix}$ pads with a zero row, because $B$ sends 2-D into 3-D and the third output dimension receives nothing. Tall matrices pad with zero rows (unreachable outputs); wide ones with zero columns (flattened inputs). $\Sigma$ always has $A$ 's shape.

Tall: $\Sigma$ pads with a zero row. Wide: with a zero column. Count the non-zero σ's and you have read off the rank.

The realization

To find the SVD, take the round trip. The eigenvectors of $A^{\top}A$ are the input frame $V$ , and $\sigma_i=\sqrt{\lambda_i}$ . The output frame comes free: $\mathbf u_i=A\mathbf v_i/\sigma_i$ . $\Sigma$ always has the same shape as $A$ , padded with zeros.

Pause & predict

A data matrix is $500\times4$ (500 samples, 4 features) with rank 4. What does its $\Sigma$ look like?

Pause & predict

You need the SVD of a 1000×3 data matrix. Which round-trip matrix do you break down?

Pause & predict

In the wide example, $\mathbf{v}_3=\tfrac{1}{\sqrt6}(-1,-2,1)$ goes with $\sigma_3=0$ . What is this direction, in Unit 1's words?

In one sentence: to break down $A$ , break down the symmetric round trip $A^{\top}A$ instead: $V$ and the σ's fall out, and $\mathbf{u}_i=A\mathbf{v}_i/\sigma_i$ finishes the job.

9

Seeing a rectangular matrix — 2-D in, 3-D out

Imagine this

Hold a sheet of paper in the air and tilt it. The sheet is flat — it is 2-D. But it sits inside your 3-D room.

Anything drawn on the sheet stays on the sheet. And one direction, straight out of the paper, can never be reached by anything drawn on it.

A tall matrix does exactly this. $B=\begin{bmatrix}1&1\\0&1\\1&0\end{bmatrix}$ takes a flat 2-D vector and returns a point in 3-D. Feed it the whole unit circle. The output is an oval lying on a tilted sheet inside 3-D space.

The SVD names everything you see. The sheet is spanned by $\mathbf u_1$ and $\mathbf u_2$ . The oval's long half-axis is $\sigma_1\mathbf u_1$ with $\sigma_1=\sqrt3\approx1.73$ . Its short half-axis is $\mathbf u_2$ , since $\sigma_2=1$ . The third direction $\mathbf u_3$ points straight out of the sheet. No input ever lands there — it is the zero row of $\Sigma$ , made visible.

Drag the probe around the input circle and watch its image travel around the oval:

Try: press "look along the sheet". The oval flattens to a thin line, and u₃ stands straight up out of it.

✋ input space ℝ² — drag the probe

output space ℝ³ — drag to orbit

—

Put the probe on $\mathbf{v}_1$ and its image lands on $\sigma_1\mathbf{u}_1$ , length $\sqrt3$ . The grey $\mathbf{u}_3$ is the direction no input can ever reach.

The realization

A rectangular matrix maps one world into another. A $3\times2$ matrix can only fill a flat sheet inside 3-D space. The SVD's $\mathbf u_1,\mathbf u_2$ span that sheet, and $\mathbf u_3$ is the direction it can never reach.

In one sentence: a rectangular matrix maps one world into another: its image is a flat slice of the bigger world, and $\mathbf{u}_3$ is the direction it can never reach.

10

The layer cake — low-rank approximation, live

Imagine this

Watch an artist paint a face. First come a few big, rough shapes: the head, the hair, the dark side. Then the eyes and the nose. The tiny details come last.

Stop after the first few strokes and you can already tell who it is. The big strokes carry most of the picture.

The SVD paints a matrix the same way. Multiply $U\Sigma V^{\top}$ out one column at a time, and it becomes a stack of simple layers — just like the equalizer in Section 4, but now for every matrix:

\begin{aligned}A&=\sigma_1\mathbf{u}_1\mathbf{v}_1^{\top}+\sigma_2\mathbf{u}_2\mathbf{v}_2^{\top}+\cdots+\sigma_r\mathbf{u}_r\mathbf{v}_r^{\top}\\ &=\text{biggest stroke}+\text{next stroke}+\cdots+\text{finest detail}\end{aligned}

Each layer $\sigma_i\mathbf u_i\mathbf v_i^{\top}$ is one simple pattern: a column times a row (a "rank-1" matrix). The $\sigma$ 's are sorted, so the layers come biggest first. Real-world matrices keep most of their content in the first few layers.

So keep only the top $k$ layers. The result is the rank- $k$ approximation, written $\hat A(k)$ (read "A-hat of k"). A famous result, the Eckart–Young theorem, says no other rank- $k$ matrix gets closer to $A$ . And the error is exactly the first layer you dropped: $\|A-\hat A(k)\|_2=\sigma_{k+1}$ .

A tiny example. Keep only the biggest layer of the tall $B$ from Section 9: $\hat B(1)=\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}$ . The error is the dropped $\sigma_2=1$ .

Now scale up. A photo is a matrix: every pixel is one number. Below is a real photograph of a NASA astronaut, 36×36 pixels — 1,296 numbers. Watch her face appear, biggest layer first:

Try: slide k from 1 to 8. Watch the third panel: each new layer adds one stripe pattern.

drag the relief to orbit

keep k layers3

storage — energy — error σ₍k₊₁₎ = —

—

Watch out — the noise lesson

Switch the widget to pure noise and slide $k$ . The picture barely improves. Noise spreads itself evenly over all the layers, so there are no quiet layers to drop for free.

Turn that around and you get a superpower. Real content lives in the big early layers. Noise lives in the faint tail. So cutting the tail removes noise. Structure squeezes well; noise does not.

Pause & predict

You keep $k=3$ layers of a matrix whose singular values are $9,\,4,\,2,\,0.5,\,0.1$ . What is $\|A-\hat A(3)\|_2$ ?

Pause & predict

A $1000\times1000$ image is stored as 50 layers. Roughly what fraction of the original million numbers is that?

If you want the algebra · why the error is exactly σ_k+1

Why the truncation error is exactly σ_k+1 — derived

Claim. With $\hat A(k)=\sum_{i\le k}\sigma_i\mathbf u_i\mathbf v_i^{\top}$ , the leftover $A-\hat A(k)$ has spectral norm $\sigma_{k+1}$ . (That no other rank- $k$ matrix beats this is the Eckart–Young theorem; here we derive the size of the error you actually make.)

1

Subtract the kept layers from the full stack:

A-\hat A(k)=\sum_{i=1}^{r}\sigma_i\mathbf u_i\mathbf v_i^{\top}-\sum_{i=1}^{k}\sigma_i\mathbf u_i\mathbf v_i^{\top}=\sum_{i=k+1}^{r}\sigma_i\mathbf u_i\mathbf v_i^{\top}

The first

k

terms cancel exactly; what remains is the tail of the layer cake, loudest-dropped layer first.

2

Read the tail as its own SVD. Let

\Sigma'

be

\Sigma

with

\sigma_1,\dots,\sigma_k

replaced by

0

. Then

A-\hat A(k)=U\,\Sigma'\,V^{\top}

Multiply

U\Sigma'V^{\top}

out column-times-row (Section 4's derivation, same steps): the zeroed slots contribute nothing, and the surviving terms are exactly the tail in step 1.

U

and

V

are still orthonormal, so this is a genuine SVD of the leftover, with singular values

\sigma_{k+1}\ge\sigma_{k+2}\ge\cdots

.

3

Apply the spectral-norm rule (derived in Section 11): a matrix's

\|\cdot\|_2

is its largest singular value. The largest entry of

\Sigma'

is

\sigma_{k+1}

, so

\|A-\hat A(k)\|_2=\sigma_{k+1}

Check it in the widget: the "error" chip is always the first grey bar. And the direction that suffers most is

\mathbf v_{k+1}

:

(A-\hat A(k))\mathbf v_{k+1}=\sigma_{k+1}\mathbf u_{k+1}

, while every kept direction

\mathbf v_1,\dots,\mathbf v_k

is reproduced perfectly. The error is the loudest thing you threw away. ∎

One more disguise, because this is where the SVD earns its keep in machine learning. A matrix does not have to be a picture. A table is a matrix too. Below: six friends, five films, thirty star ratings. It looks like thirty separate opinions. It is not:

Try: press "hide 5 ratings". Guess them from the two taste patterns, then let the patterns fill them in.

—

Each pattern is a column of person-numbers times a row of film-numbers — one layer, like the photo's. Two layers rebuild all thirty ratings.

The realization

Sort the layers biggest first and keep the top $k$ : $\hat A(k)=\sum_{i\le k}\sigma_i\mathbf u_i\mathbf v_i^{\top}$ . No rank- $k$ matrix does better, and the error is $\sigma_{k+1}$ . Each layer costs only $m+n+1$ numbers — so this is compression, for photos and for tables of ratings alike.

Pause & predict

A streaming app has a million users and 10,000 films — ten billion possible ratings, almost all missing. Why does the layer idea rescue it?

In one sentence: sort the layers biggest first and keep the top few — the best possible summary of any matrix, whether it is a photograph or a table of tastes.

11

The spectral norm — and the family portrait

Imagine this

Speak into a megaphone. Point it straight at the crowd and your voice is at its loudest. Point it a little off, and it gets quieter.

Every megaphone has one direction of biggest boost. Every matrix has one too.

What is the most a matrix can ever stretch a vector? That biggest boost is called the spectral norm, written $\|A\|_2$ . The SVD answers it at once: it is the longest half-axis of the output oval.

\|A\|_2=\max_{\mathbf{x}\neq\mathbf{0}}\frac{\|A\mathbf{x}\|}{\|\mathbf{x}\|}=\sigma_1

Read it: "try every input direction, measure how much it grows, take the biggest — that is $\sigma_1$ ." The winning input is $\mathbf v_1$ .

The lecture's example: $A=\begin{bmatrix}1&2\\3&4\end{bmatrix}$ has $\sigma_1\approx5.465$ and $\sigma_2\approx0.366$ . So its biggest boost is ×5.465, and its smallest is ×0.366. The ratio $\sigma_1/\sigma_2\approx14.9$ is called the condition number. A big condition number means trouble — you will see why in a moment.

Hunt for the loudest direction yourself:

Try: turn the dial until the verdict says "peak found". Then pick nearly singular and find the quietest direction.

✋ drag the gold x to aim the input · drag empty space to orbit

aim θ29°

‖A‖₂ = σ₁ = — σ₂ = — σ₁/σ₂ = —

—

The orange curve shows the boost in every direction at once. Its farthest reach is $\sigma_1$ ; its nearest is $\sigma_2$ .

Why a big ratio is trouble. Solving $A\mathbf x=\mathbf b$ means undoing $A$ . Undoing a stretch means dividing by it. Along $\mathbf u_2$ you divide by the tiny $\sigma_2=0.366$ , so any small error in $\mathbf b$ grows about 2.7 times. Along $\mathbf u_1$ you divide by 5.465, so errors shrink. A round blob of noise becomes a long needle:

$A=\begin{bmatrix}1&2\\3&4\end{bmatrix}$ , $\sigma_1=5.465,\ \sigma_2=0.366$ . Solving divides each output component by its σ, so noise along $\mathbf u_2$ is amplified by $1/\sigma_2\approx2.7$ while noise along $\mathbf u_1$ is damped by $1/\sigma_1\approx0.18$ .

A matrix with a huge $\sigma_1/\sigma_2$ is called ill-conditioned, and numerical software fears it. The same number decides whether signals in a deep network blow up or fade away — and it gives "spectral normalization" its name.

If you want the algebra · why the biggest boost is exactly σ₁

Why the worst-case stretch is exactly σ₁ — derived

1

Rename the input in the

V

frame:

\mathbf y=V^{\top}\mathbf x

. Its length is unchanged:

\|\mathbf y\|^{2}=\mathbf x^{\top}VV^{\top}\mathbf x=\mathbf x^{\top}\mathbf x=\|\mathbf x\|^{2}

V

is square with orthonormal columns, so

VV^{\top}=I

— a rotation never changes length.

2

Apply

A

and drop the outer rotation:

\|A\mathbf x\|^{2}=\|U\Sigma\mathbf y\|^{2}=(\Sigma\mathbf y)^{\top}U^{\top}U(\Sigma\mathbf y)=\|\Sigma\mathbf y\|^{2}

A\mathbf x=U\Sigma V^{\top}\mathbf x=U\Sigma\mathbf y

, and

U^{\top}U=I

removes

U

. Only the stretch step can change length.

3

A diagonal stretch is easy to bound:

\|\Sigma\mathbf y\|^{2}=\sum_i\sigma_i^{2}y_i^{2}\;\le\;\sigma_1^{2}\sum_i y_i^{2}=\sigma_1^{2}\|\mathbf y\|^{2}=\sigma_1^{2}\|\mathbf x\|^{2}

Each

\sigma_i\le\sigma_1

because the σ's are sorted, and

y_i^{2}\ge0

, so replacing every

\sigma_i

by

\sigma_1

can only increase the sum. Step 1 turns

\|\mathbf y\|

back into

\|\mathbf x\|

.

4

The bound is reached. Take

\mathbf x=\mathbf v_1

: then

\mathbf y=V^{\top}\mathbf v_1=\mathbf e_1

and

\|A\mathbf v_1\|^{2}=\sigma_1^{2}\cdot1^{2}=\sigma_1^{2}

So the maximum of

\|A\mathbf x\|/\|\mathbf x\|

is at most

\sigma_1

(step 3) and at least

\sigma_1

(this step): it equals

\sigma_1

. The same argument with

\ge\sigma_r

gives the quietest response,

\sigma_r

— the valley in the widget. The spectral norm is the top singular value. ∎

And the family portrait — the whole ladder in one table:

	Eigen / Spectral	SVD
Formula	$A=PDP^{-1}$ (or $Q\Lambda Q^{\top}$ )	$A=U\Sigma V^{\top}$
Works on	square matrices with enough eigenvectors	every matrix, any shape
Frames	one set of axes, shared by input and output	two: $V$ for input, $U$ for output
At right angles?	$P$ : usually not ( $Q$ : yes)	$U$ and $V$ : always
The stretches	eigenvalues — can be negative or imaginary	singular values — always real, $\ge0$ , sorted
The link	$V$ = eigenvectors of $A^{\top}A$ · $U$ = eigenvectors of $AA^{\top}$ · $\sigma_i=\sqrt{\lambda_i(A^{\top}A)}$

The realization

$\sigma_1$ is the biggest boost a matrix can give: $\|A\|_2=\sigma_1$ . The ratio $\sigma_1/\sigma_2$ says how uneven the boosts are. When it is huge, undoing the matrix blows up tiny errors.

Pause & predict

On nearly singular, the orange curve is long one way and pinched almost to zero the other. What does that mean for solving $A\mathbf{x}=\mathbf{b}$ ?

Pause & predict

For $A=\begin{bmatrix}1&2\\3&4\end{bmatrix}$ , which number is $\|A\|_2$ ?

In one sentence: $\sigma_1$ is the loudest a matrix can ever be, and $\sigma_1/\sigma_2$ says how uneven its boosts are.

12

The whole story, in five lines

Imagine this

Back to the photo editor one last time. Rotate, resize, rotate. With just those two tools you can now rebuild any matrix — and you know how to find the three taps.

A matrix moves space. A decomposition rewrites it as simple moves — turn, resize, turn — without changing what it does.
The goal is always a diagonal middle, a resize tool, because it turns every question into arithmetic on separate numbers.
Spectral, $A=Q\Lambda Q^{\top}$ , is for symmetric matrices: perpendicular directions, a free inverse, and the equalizer view $A=\sum\lambda_i\mathbf{q}_i\mathbf{q}_i^{\top}$ . Eigen, $A=PDP^{-1}$ , keeps the idea on leaning directions and pays with a real inverse — earning $A^k=PD^kP^{-1}$ .
The SVD, $A=U\Sigma V^{\top}$ , works for every matrix. It uses two perpendicular frames, found through the round trip $A^{\top}A$ , with $\mathbf{u}_i=A\mathbf{v}_i/\sigma_i$ for free.
Sorted biggest first, the $\sigma$ 's turn any matrix into a stack of layers. Keep the top few for the best compression (Eckart–Young). Read $\sigma_1$ as the biggest boost (the spectral norm).

The realization

Every matrix is turn · resize · turn. Sort the stretches biggest first and keep the top few, and you have the best short summary a matrix can have. Photo compression, noise removal, PCA and recommenders are all that one move.

In one sentence: find the two frames and the sorted stretches, and any matrix becomes simple enough to read, repeat, undo and compress.

13

Practice arena — the unit's problem set, solved in full

These twelve problems come from the unit's problem set. That set covers this unit and Unit 4, so the pure eigenvalue problems live in Unit 4's arena. Try each one on paper first. Then open the solution — every step is shown.

Problem 1Easy

For each matrix, state the eigenvalue(s), their algebraic multiplicity $\operatorname{am}$ and geometric multiplicity $\operatorname{gm}$ , and decide whether the matrix is diagonalizable:

A=\begin{bmatrix}3&1\\0&3\end{bmatrix},\qquad B=\begin{bmatrix}3&0\\0&3\end{bmatrix},\qquad C=\begin{bmatrix}3&1&0\\0&3&1\\0&0&3\end{bmatrix}.

What this tests. Reading off $\operatorname{am}$ and $\operatorname{gm}$ quickly, and using them to decide diagonalizability.

Show the worked solution — every step

Step 1 · Matrix $A$ . Triangular, so the only eigenvalue is

\lambda=3

with

\operatorname{am}=2

. For the geometric multiplicity,

\operatorname{gm}=2-\operatorname{rank}(A-3I)=2-\operatorname{rank}\begin{bmatrix}0&1\\0&0\end{bmatrix}=2-1=1

. Since

\operatorname{gm}=1 < 2=\operatorname{am}

,

A

is not diagonalizable.

Step 2 · Matrix $B$ .

B=3I

: eigenvalue

\lambda=3

with

\operatorname{am}=2

, and

B-3I=0

has rank 0, so

\operatorname{gm}=2-0=2

. Here

\operatorname{gm}=\operatorname{am}

, so

B

is diagonalizable (it is already diagonal).

Step 3 · Matrix $C$ . Triangular, eigenvalue

\lambda=3

with

\operatorname{am}=3

. Now

C-3I=\begin{bmatrix}0&1&0\\0&0&1\\0&0&0\end{bmatrix}

has rank 2 (two independent nonzero rows), so

\operatorname{gm}=3-2=1 < 3

. Not diagonalizable — a single

3\times 3

Jordan block.

Answer.

A

:

\lambda=3

,

\operatorname{am}=2

,

\operatorname{gm}=1

— not diagonalizable.

B

:

\lambda=3

,

\operatorname{am}=\operatorname{gm}=2

— diagonalizable.

C

:

\lambda=3

,

\operatorname{am}=3

,

\operatorname{gm}=1

— not diagonalizable.

Watch out

$\operatorname{am}$ counts how often $\lambda$ is a root of $\det(A-\lambda I)$ ; $\operatorname{gm}$ counts independent eigenvectors, and the reliable formula is $\operatorname{gm}(\lambda)=n-\operatorname{rank}(A-\lambda I)$ . Never assume they match — compute the rank.

Key takeaway

Same eigenvalue, same $\operatorname{am}$ — but the number of independent eigenvectors ( $\operatorname{gm}$ ) is what decides diagonalizability: $A$ is diagonalizable $\iff \operatorname{gm}(\lambda)=\operatorname{am}(\lambda)$ for every eigenvalue.

Wait — really?

$A$ and $B$ have the identical characteristic polynomial $(\lambda-3)^2$ , yet opposite verdicts. The characteristic polynomial alone can never tell you whether a matrix diagonalizes — that information lives in the eigenspaces, not in the spectrum.

Problem 2Medium

Let $a,b,c\in\mathbb{R}$ with $b\neq 0$ and consider the upper-triangular matrix

A=\begin{bmatrix}a&b\\0&c\end{bmatrix}.

(a) Find the eigenvalues and an eigenvector for each (in terms of $a,b,c$ ). (b) State, with justification, exactly when $A$ is diagonalizable.

What this tests. Running the whole eigen-and-diagonalizability pipeline in symbols, and locating the exact parameter condition where it breaks.

Show the worked solution — every step

Part (a) · Eigenvalues. For a triangular matrix the eigenvalues are the diagonal entries:

\lambda_1=a

,

\lambda_2=c

.

Part (a) · Eigenvector for $\lambda_1=a$ .

A-aI=\begin{bmatrix}0&b\\0&c-a\end{bmatrix}.

The equations are

by=0

and

(c-a)y=0

; since

b\neq 0

we get

y=0

with

x

free, so

\mathbf{v}_1=(1,0)^{\top}

.

Part (a) · Eigenvector for $\lambda_2=c$ (assume $c\neq a$ ).

A-cI=\begin{bmatrix}a-c&b\\0&0\end{bmatrix}

gives

(a-c)x+by=0\Rightarrow x=-\dfrac{b}{a-c}\,y

. Taking

y=a-c

clears the fraction:

\mathbf{v}_2=(-b,\;a-c)^{\top}

. (Check:

A\mathbf{v}_2=\big(-ab+b(a-c),\;c(a-c)\big)^{\top}=(-bc,\;c(a-c))^{\top}=c\,\mathbf{v}_2

. ✓)

Part (b) · When is $A$ diagonalizable? Case $a\neq c$ : two distinct eigenvalues

\Rightarrow

two independent eigenvectors

\Rightarrow

diagonalizable. Case $a=c$ : then

\lambda=a

has

\operatorname{am}=2

, but

A-aI=\begin{bmatrix}0&b\\0&0\end{bmatrix}

has rank 1 (because

b\neq 0

), so the eigenspace is only 1-dimensional:

\operatorname{gm}=1 < 2

\Rightarrow

not diagonalizable (defective).

Answer.

\lambda_1=a

with

\mathbf{v}_1=(1,0)^{\top}

;

\lambda_2=c

with

\mathbf{v}_2=(-b,\,a-c)^{\top}

.

A

is diagonalizable

\iff a\neq c

(when

a=c

and

b\neq 0

it is defective).

Watch out

The hypothesis $b\neq 0$ is what kills the $a=c$ case — if $b=0$ the matrix would already be diagonal. And avoid dividing by $a-c$ blindly: scaling the eigenvector by $y=a-c$ sidesteps the fraction and stays valid right up to the boundary.

Key takeaway

Distinct eigenvalues $\Rightarrow$ diagonalizable, no further checks. A repeated eigenvalue forces you to compute $\operatorname{rank}(A-\lambda I)$ before you may conclude anything.

Wait — really?

Diagonalizability here fails only on the razor-thin set $a=c$ : nudge $a$ by any $\varepsilon\neq 0$ and the matrix instantly diagonalizes again. Defective matrices live on a knife-edge — which is exactly why numerical libraries treat "nearly repeated" eigenvalues with such care.

Problem 3Easy

Decide whether

A=\begin{bmatrix}2&1&0\\0&2&0\\0&0&3\end{bmatrix}

is diagonalizable. Justify using eigenvalues, algebraic and geometric multiplicities.

What this tests. The multiplicity test on a $3\times 3$ : spotting a defective eigenvalue hidden in a triangular matrix.

Show the worked solution — every step

Step 1 · Eigenvalues.

A

is upper-triangular, so the eigenvalues are the diagonal entries:

\lambda=2

(algebraic multiplicity 2) and

\lambda=3

(algebraic multiplicity 1).

Step 2 · Eigenspace of the repeated eigenvalue.

A-2I=\begin{bmatrix}0&1&0\\0&0&0\\0&0&1\end{bmatrix}.

This has rank 2, so its null space has dimension

3-2=1

: the equations force

y=0

and

z=0

with

x

free, i.e. eigenspace

\operatorname{span}\{(1,0,0)^{\top}\}

. Geometric multiplicity 1.

Step 3 · Compare. For

\lambda=2

the geometric multiplicity (1) is less than the algebraic multiplicity (2). Only two independent eigenvectors exist in total — not enough for a basis of

\mathbb{R}^3

, so

A

cannot be diagonalized.

Answer.

A

is not diagonalizable: for

\lambda=2

, geometric multiplicity

1 <

algebraic multiplicity

2

(only one independent eigenvector,

(1,0,0)^{\top}

). The block

\begin{bmatrix}2&1\\0&2\end{bmatrix}

is a defective Jordan block.

Watch out

It is not the repeated eigenvalue itself that blocks diagonalization — it is the missing second eigenvector. Compute $\operatorname{rank}(A-2I)$ ; do not guess from the diagonal.

Key takeaway

One defective eigenvalue sinks the whole matrix: if any $\lambda$ has $\operatorname{gm} < \operatorname{am}$ , no eigenbasis exists and no invertible $P$ can ever diagonalize $A$ .

Wait — really?

The eigenvalue $3$ is perfectly healthy, and $A$ is just one entry away from diagonal — yet the tiny $2\times2$ shear block $\begin{bmatrix}2&1\\0&2\end{bmatrix}$ tucked in the corner is enough to make the entire $3\times 3$ matrix undiagonalizable.

Problem 4Medium

Find an eigendecomposition $A=PDP^{-1}$ of the non-symmetric matrix

A=\begin{bmatrix}5&-1\\2&2\end{bmatrix},

giving $P,\,D,\,P^{-1}$ explicitly, and verify the factorization.

What this tests. Building $P$ and $D$ for a non-symmetric matrix — where $P^{-1}$ must be computed, not transposed — and verifying the product.

Show the worked solution — every step

Step 1 · Eigenvalues.

\det(A-\lambda I)=(5-\lambda)(2-\lambda)+2=\lambda^{2}-7\lambda+12=(\lambda-3)(\lambda-4)=0,

so

\lambda_1=3

,

\lambda_2=4

.

Step 2 · Eigenvectors.

\lambda_1=3

:

A-3I=\begin{bmatrix}2&-1\\2&-1\end{bmatrix}\Rightarrow 2x=y

, so

\mathbf{p}_1=(1,2)^{\top}

.

\lambda_2=4

:

A-4I=\begin{bmatrix}1&-1\\2&-2\end{bmatrix}\Rightarrow x=y

, so

\mathbf{p}_2=(1,1)^{\top}

.

Step 3 · Assemble $P$ , $D$ , and invert $P$ .

P=\begin{bmatrix}1&1\\2&1\end{bmatrix},\qquad D=\begin{bmatrix}3&0\\0&4\end{bmatrix},\qquad \det P=1\cdot 1-1\cdot 2=-1,\qquad P^{-1}=\frac{1}{-1}\begin{bmatrix}1&-1\\-2&1\end{bmatrix}=\begin{bmatrix}-1&1\\2&-1\end{bmatrix}.

Step 4 · Verify, entry by entry. First

PD=\begin{bmatrix}1\cdot 3&1\cdot 4\\2\cdot 3&1\cdot 4\end{bmatrix}=\begin{bmatrix}3&4\\6&4\end{bmatrix}

. Then

PDP^{-1}=\begin{bmatrix}3&4\\6&4\end{bmatrix}\begin{bmatrix}-1&1\\2&-1\end{bmatrix}=\begin{bmatrix}3(-1)+4(2)&3(1)+4(-1)\\6(-1)+4(2)&6(1)+4(-1)\end{bmatrix}=\begin{bmatrix}5&-1\\2&2\end{bmatrix}=A.\ \checkmark

Answer.

A=PDP^{-1}

with

P=\begin{bmatrix}1&1\\2&1\end{bmatrix}

,

D=\begin{bmatrix}3&0\\0&4\end{bmatrix}

,

P^{-1}=\begin{bmatrix}-1&1\\2&-1\end{bmatrix}

.

Watch out

Column order must match: $\mathbf{p}_1$ under $\lambda_1$ , $\mathbf{p}_2$ under $\lambda_2$ — swap one and not the other, and the "decomposition" silently produces a different matrix. And since $A$ is not symmetric, $P^{-1}\neq P^{\top}$ : the eigenvectors $(1,2)^{\top},(1,1)^{\top}$ are not orthogonal, so the inverse must be computed the usual way.

Key takeaway

The $PDP^{-1}$ recipe: eigenvalues $\to$ eigenvectors $\to$ stack into $P$ , $D$ $\to$ invert $P$ $\to$ multiply back and check. The verification costs two small multiplications and catches nearly every bookkeeping error.

Wait — really?

A non-symmetric matrix can still diagonalize perfectly — but on a slanted basis. $A$ acts as pure stretching (by 3 and by 4) along the directions $(1,2)$ and $(1,1)$ , axes that are not perpendicular. Orthogonal eigenvectors are a luxury reserved for symmetric matrices.

Problem 5Medium

Using diagonalization, derive a closed form for $A^{n}$ and evaluate $A^{4}$ , where

A=\begin{bmatrix}2&-1\\-1&2\end{bmatrix}.

What this tests. The workhorse pattern $A^{n}=PD^{n}P^{\top}$ : diagonalize once, then raise only the diagonal.

Show the worked solution — every step

Step 1 · Diagonalize (orthogonally).

\det(A-\lambda I)=(2-\lambda)^{2}-1=(\lambda-1)(\lambda-3)=0\Rightarrow\lambda_1=1,\ \lambda_2=3

. Eigenvectors: for

\lambda=1

,

A\mathbf{v}=(2x-y,\,-x+2y)^{\top}=\mathbf{v}

forces

x=y

; for

\lambda=3

,

x=-y

. Orthonormal eigenvectors

\tfrac{1}{\sqrt2}(1,1)^{\top}

and

\tfrac{1}{\sqrt2}(1,-1)^{\top}

give

P=\frac{1}{\sqrt2}\begin{bmatrix}1&1\\1&-1\end{bmatrix},\qquad D=\begin{bmatrix}1&0\\0&3\end{bmatrix},\qquad A=PDP^{\top}.

Step 2 · Power formula. Since

A=PDP^{\top}

with

P

orthogonal,

A^{n}=PD^{n}P^{\top}

, and only the diagonal is raised:

A^{n}=\frac12\begin{bmatrix}1&1\\1&-1\end{bmatrix}\begin{bmatrix}1&0\\0&3^{n}\end{bmatrix}\begin{bmatrix}1&1\\1&-1\end{bmatrix}=\frac12\begin{bmatrix}1+3^{n}&1-3^{n}\\1-3^{n}&1+3^{n}\end{bmatrix}.

(Middle step:

PD^{n}=\tfrac{1}{\sqrt2}\begin{bmatrix}1&3^{n}\\1&-3^{n}\end{bmatrix}

, then multiply by

P^{\top}

: the

(1,1)

entry is

\tfrac12(1+3^{n})

, the

(1,2)

entry

\tfrac12(1-3^{n})

, and symmetrically below.)

Step 3 · Evaluate $n=4$ .

3^{4}=81

, so

A^{4}=\frac12\begin{bmatrix}1+81&1-81\\1-81&1+81\end{bmatrix}=\frac12\begin{bmatrix}82&-80\\-80&82\end{bmatrix}=\begin{bmatrix}41&-40\\-40&41\end{bmatrix}.

Answer.

A^{n}=\dfrac12\begin{bmatrix}1+3^{n}&1-3^{n}\\1-3^{n}&1+3^{n}\end{bmatrix}

, and

A^{4}=\begin{bmatrix}41&-40\\-40&41\end{bmatrix}

.

Watch out

Only $D$ gets raised to the $n$ : $P$ and $P^{\top}$ appear once each, at the ends. And $1^{n}$ stays $1$ — a surprisingly common slip is powering only the larger eigenvalue.

Key takeaway

$A^{n}=PD^{n}P^{\top}$ turns $n-1$ matrix multiplications into $n$ -th powers of two scalars. Diagonalize once; reuse forever.

Wait — really?

The closed form works for every $n$ simultaneously — $n=0$ gives $I$ , $n=1$ gives $A$ back, and since no eigenvalue is zero, $n=-1$ even produces $A^{-1}$ . One formula quietly encodes the entire orbit of $A$ .

Problem 6Hard

Find a full singular value decomposition $A=U\Sigma V^{\top}$ of

A=\begin{bmatrix}1&1\\1&0\\0&1\end{bmatrix},

including the third column of $U$ obtained by orthogonal completion.

What this tests. The full SVD pipeline — $A^{\top}A$ , singular values, $\mathbf{u}_i=\frac{1}{\sigma_i}A\mathbf{v}_i$ — plus completing $U$ to a genuine $3\times 3$ orthogonal matrix.

Show the worked solution — every step

Step 1 · $A^{\top}A$ , singular values, right singular vectors.

A^{\top}A=\begin{bmatrix}1&1&0\\1&0&1\end{bmatrix}\begin{bmatrix}1&1\\1&0\\0&1\end{bmatrix}=\begin{bmatrix}2&1\\1&2\end{bmatrix}

(entries:

(1,1)\!: 1^2+1^2+0^2=2

;

(1,2)\!: 1\cdot1+1\cdot0+0\cdot1=1

;

(2,2)\!: 1+0+1=2

). Eigenvalues:

\det\begin{bmatrix}2-\lambda&1\\1&2-\lambda\end{bmatrix}=(2-\lambda)^{2}-1=0\Rightarrow\lambda=3,\,1

. Thus

\sigma_1=\sqrt3

,

\sigma_2=1

, with

\mathbf{v}_1=\tfrac{1}{\sqrt2}(1,1)^{\top}\ (\lambda=3),\qquad \mathbf{v}_2=\tfrac{1}{\sqrt2}(1,-1)^{\top}\ (\lambda=1).

Step 2 · Left singular vectors $\mathbf{u}_i=\frac{1}{\sigma_i}A\mathbf{v}_i$ . Entry by entry,

A\mathbf{v}_1=\tfrac{1}{\sqrt2}(1{+}1,\,1{+}0,\,0{+}1)^{\top}=\tfrac{1}{\sqrt2}(2,1,1)^{\top}

, so

\mathbf{u}_1=\frac{1}{\sqrt3}\cdot\frac{1}{\sqrt2}\begin{bmatrix}2\\1\\1\end{bmatrix}=\frac{1}{\sqrt6}\begin{bmatrix}2\\1\\1\end{bmatrix};\qquad \mathbf{u}_2=\frac{1}{1}\cdot\frac{1}{\sqrt2}\begin{bmatrix}1-1\\1-0\\0-1\end{bmatrix}=\frac{1}{\sqrt2}\begin{bmatrix}0\\1\\-1\end{bmatrix}.

Step 3 · Orthogonal completion $\mathbf{u}_3$ . We need a unit vector with

\mathbf{u}_3\perp\mathbf{u}_1

and

\mathbf{u}_3\perp\mathbf{u}_2

. Writing

\mathbf{u}_3=(p,q,r)^{\top}

: from

\mathbf{u}_2

,

q-r=0\Rightarrow q=r

; from

\mathbf{u}_1

,

2p+q+r=0\Rightarrow 2p+2q=0\Rightarrow p=-q

. Normalising:

\mathbf{u}_3=\tfrac{1}{\sqrt3}(-1,1,1)^{\top}

.

Step 4 · Assemble.

U=\begin{bmatrix}2/\sqrt6&0&-1/\sqrt3\\1/\sqrt6&1/\sqrt2&1/\sqrt3\\1/\sqrt6&-1/\sqrt2&1/\sqrt3\end{bmatrix},\qquad \Sigma=\begin{bmatrix}\sqrt3&0\\0&1\\0&0\end{bmatrix},\qquad V^{\top}=\frac{1}{\sqrt2}\begin{bmatrix}1&1\\1&-1\end{bmatrix}.

\Sigma

has the same

3\times 2

shape as

A

; its zero third row is what

\mathbf{u}_3

multiplies.

Answer.

\sigma_1=\sqrt3

,

\sigma_2=1

;

\mathbf{v}_1=\tfrac{1}{\sqrt2}(1,1)^{\top}

,

\mathbf{v}_2=\tfrac{1}{\sqrt2}(1,-1)^{\top}

;

\mathbf{u}_1=\tfrac{1}{\sqrt6}(2,1,1)^{\top}

,

\mathbf{u}_2=\tfrac{1}{\sqrt2}(0,1,-1)^{\top}

,

\mathbf{u}_3=\tfrac{1}{\sqrt3}(-1,1,1)^{\top}

;

\Sigma=\begin{bmatrix}\sqrt3&0\\0&1\\0&0\end{bmatrix}

.

Watch out

$\Sigma$ must have the shape of $A$ ( $3\times 2$ ) — forgetting the zero row makes $U\Sigma V^{\top}$ undefined. Keep the normalisations straight: $\mathbf{u}_1$ picks up $\frac{1}{\sqrt3}\cdot\frac{1}{\sqrt2}=\frac{1}{\sqrt6}$ , not $\frac{1}{\sqrt3}$ .

Key takeaway

Full-SVD recipe: eigen-decompose $A^{\top}A$ for $V$ and the $\sigma_i=\sqrt{\lambda_i}$ , push through $\mathbf{u}_i=\frac{1}{\sigma_i}A\mathbf{v}_i$ , then complete $U$ to an orthonormal basis of the output space.

Wait — really?

The completed column $\mathbf{u}_3=\tfrac{1}{\sqrt3}(-1,1,1)^{\top}$ satisfies $A^{\top}\mathbf{u}_3=\mathbf{0}$ : it spans the part of $\mathbb{R}^3$ that $A$ 's columns can never reach. The "filler" column is actually a precise description of what the matrix cannot do.

Problem 7Hard

Find the SVD of

A=\begin{bmatrix}1&1&0\\0&1&1\end{bmatrix}.

(Hint: it is quicker to get $U$ and the singular values from the $2\times 2$ matrix $AA^{\top}$ , then recover $V$ from $\mathbf{v}_i=\frac{1}{\sigma_i}A^{\top}\mathbf{u}_i$ ; the missing right vector spans $\ker(A^{\top}A)$ .)

What this tests. Choosing the smaller Gram matrix ( $AA^{\top}$ instead of a $3\times 3$ $A^{\top}A$ with a zero eigenvalue), and fetching the last right vector from the null space.

Show the worked solution — every step

Step 1 · $AA^{\top}$ , singular values, left singular vectors.

AA^{\top}=\begin{bmatrix}1&1&0\\0&1&1\end{bmatrix}\begin{bmatrix}1&0\\1&1\\0&1\end{bmatrix}=\begin{bmatrix}2&1\\1&2\end{bmatrix}

(entries: row 1 · row 1

=1+1+0=2

; row 1 · row 2

=0+1+0=1

; row 2 · row 2

=0+1+1=2

). Its eigenvalues are

\lambda=3,\,1

, so

\sigma_1=\sqrt3

,

\sigma_2=1

, with

\mathbf{u}_1=\tfrac{1}{\sqrt2}(1,1)^{\top}\ (\lambda=3),\qquad \mathbf{u}_2=\tfrac{1}{\sqrt2}(1,-1)^{\top}\ (\lambda=1).

Step 2 · Right singular vectors $\mathbf{v}_i=\frac{1}{\sigma_i}A^{\top}\mathbf{u}_i$ . With

A^{\top}=\begin{bmatrix}1&0\\1&1\\0&1\end{bmatrix}

: entry by entry,

A^{\top}\mathbf{u}_1=\tfrac{1}{\sqrt2}(1,\,1{+}1,\,1)^{\top}=\tfrac{1}{\sqrt2}(1,2,1)^{\top}

, so

\mathbf{v}_1=\frac{1}{\sqrt3}\cdot\frac{1}{\sqrt2}\begin{bmatrix}1\\2\\1\end{bmatrix}=\frac{1}{\sqrt6}\begin{bmatrix}1\\2\\1\end{bmatrix};\qquad \mathbf{v}_2=\frac{1}{1}\cdot\frac{1}{\sqrt2}\begin{bmatrix}1\\1-1\\-1\end{bmatrix}=\frac{1}{\sqrt2}\begin{bmatrix}1\\0\\-1\end{bmatrix}.

Step 3 · Third right vector from the null space.

A

is

2\times 3

, so

V

needs a third column

\mathbf{v}_3

with singular value 0, spanning

\ker(A)

(equivalently

\ker A^{\top}A

). Solving

A\mathbf{v}=\mathbf{0}

:

x+y=0

and

y+z=0

give

y=-x,\ z=x

, so

\mathbf{v}_3=\tfrac{1}{\sqrt3}(1,-1,1)^{\top}

.

Step 4 · Assemble.

U=\frac{1}{\sqrt2}\begin{bmatrix}1&1\\1&-1\end{bmatrix},\qquad \Sigma=\begin{bmatrix}\sqrt3&0&0\\0&1&0\end{bmatrix},\qquad V=\begin{bmatrix}1/\sqrt6&1/\sqrt2&1/\sqrt3\\2/\sqrt6&0&-1/\sqrt3\\1/\sqrt6&-1/\sqrt2&1/\sqrt3\end{bmatrix}.

The single zero column of

\Sigma

reflects that

A

has rank 2 but 3 columns.

Answer.

\sigma_1=\sqrt3

,

\sigma_2=1

;

U=\tfrac{1}{\sqrt2}\begin{bmatrix}1&1\\1&-1\end{bmatrix}

,

\Sigma=\begin{bmatrix}\sqrt3&0&0\\0&1&0\end{bmatrix}

,

\mathbf{v}_1=\tfrac{1}{\sqrt6}(1,2,1)^{\top}

,

\mathbf{v}_2=\tfrac{1}{\sqrt2}(1,0,-1)^{\top}

,

\mathbf{v}_3=\tfrac{1}{\sqrt3}(1,-1,1)^{\top}

.

Watch out

$\mathbf{v}_3$ cannot come from $\mathbf{v}_3=\frac{1}{\sigma_3}A^{\top}\mathbf{u}_3$ — that would divide by $\sigma_3=0$ . Vectors paired with zero singular values must be fetched from the null space directly.

Key takeaway

Always eigen-decompose the smaller of $A^{\top}A$ and $AA^{\top}$ — they share their nonzero eigenvalues — then transfer across with $\frac{1}{\sigma_i}A\mathbf{v}_i$ or $\frac{1}{\sigma_i}A^{\top}\mathbf{u}_i$ . For a wide matrix, that is $AA^{\top}$ .

Wait — really?

An entire line of inputs — every multiple of $(1,-1,1)^{\top}$ — is crushed to zero: check $A\mathbf{v}_3 = (1-1+0,\;0-1+1)^{\top}=\mathbf{0}$ . "Rank 2 out of 3 columns" is not an abstraction; it is a concrete direction the matrix simply deletes.

Problem 8Hard

(a) Find the SVD of $\;A=\begin{bmatrix}1&1\\-1&-1\end{bmatrix}$ . (b) Show that $A$ is not diagonalizable, yet its SVD still exists, and explain why.

What this tests. A rank-deficient SVD (zero singular value), and the sharp contrast between diagonalizability and the always-available SVD.

Show the worked solution — every step

Part (a), Step 1 · Singular values.

A^{\top}A=\begin{bmatrix}1&-1\\1&-1\end{bmatrix}\begin{bmatrix}1&1\\-1&-1\end{bmatrix}=\begin{bmatrix}2&2\\2&2\end{bmatrix}

(entries:

(1,1)\!: 1^2+(-1)^2=2

;

(1,2)\!: 1\cdot 1+(-1)(-1)=2

;

(2,2)\!: 1+1=2

). Eigenvalues:

(2-\lambda)^2-4=0\Rightarrow\lambda=4,\,0

, so

\sigma_1=2,\ \sigma_2=0

. The single nonzero singular value shows

\operatorname{rank}A=1

.

Part (a), Step 2 · Right and left vectors. Eigenvectors of

A^{\top}A

:

\mathbf{v}_1=\tfrac{1}{\sqrt2}(1,1)^{\top}

(for 4),

\mathbf{v}_2=\tfrac{1}{\sqrt2}(1,-1)^{\top}

(for 0). Then

\mathbf{u}_1=\frac{1}{\sigma_1}A\mathbf{v}_1=\frac12\cdot\frac{1}{\sqrt2}\begin{bmatrix}2\\-2\end{bmatrix}=\frac{1}{\sqrt2}\begin{bmatrix}1\\-1\end{bmatrix},\qquad \mathbf{u}_2\perp\mathbf{u}_1:\ \mathbf{u}_2=\frac{1}{\sqrt2}\begin{bmatrix}1\\1\end{bmatrix}.

U=\frac{1}{\sqrt2}\begin{bmatrix}1&1\\-1&1\end{bmatrix},\qquad \Sigma=\begin{bmatrix}2&0\\0&0\end{bmatrix},\qquad V=\frac{1}{\sqrt2}\begin{bmatrix}1&1\\1&-1\end{bmatrix}.

Part (b) · Not diagonalizable, but the SVD exists. The eigenvalues of

A

itself satisfy

\det(A-\lambda I)=(1-\lambda)(-1-\lambda)+1=\lambda^{2}=0

, so

\lambda=0

has algebraic multiplicity 2 — while

A\mathbf{v}=\mathbf{0}

has the single solution direction

(1,-1)^{\top}

, geometric multiplicity 1. Since

1 < 2

,

A

has no eigenbasis and is not diagonalizable. Nevertheless the SVD is built from the symmetric matrices

A^{\top}A

and

AA^{\top}

, which are always orthogonally diagonalizable — this is exactly why an SVD exists for every matrix, diagonalizable or not.

Answer.

\sigma_1=2

,

\sigma_2=0

;

U=\tfrac{1}{\sqrt2}\begin{bmatrix}1&1\\-1&1\end{bmatrix}

,

\Sigma=\begin{bmatrix}2&0\\0&0\end{bmatrix}

,

V=\tfrac{1}{\sqrt2}\begin{bmatrix}1&1\\1&-1\end{bmatrix}

.

A

is not diagonalizable (

\lambda=0

: algebraic multiplicity 2, geometric multiplicity 1).

Watch out

Do not read rank off the eigenvalues: here both eigenvalues are 0, yet $A\neq 0$ and $\operatorname{rank}A=1$ . It is the count of nonzero singular values that equals the rank — eigenvalues of a non-symmetric matrix can lie about size and rank.

Key takeaway

Diagonalization can fail (defective matrices); the SVD cannot. It inherits its existence from the spectral theorem applied to $A^{\top}A$ and $AA^{\top}$ , which are symmetric no matter what $A$ is.

Wait — really?

A matrix with no eigen-decomposition has a perfectly clean SVD. The trick is freedom: diagonalization must use one basis for input and output, while the SVD is allowed two different orthonormal frames ( $U\neq V$ ) — and that extra freedom never runs out.

Problem 9Medium

For $\;A=\begin{bmatrix}2&2\\-1&1\end{bmatrix}$ , find the singular values and the best rank-1 approximation $A_1=\sigma_1\mathbf{u}_1\mathbf{v}_1^{\top}$ .

What this tests. Extracting $\sigma_1\mathbf{u}_1\mathbf{v}_1^{\top}$ from a computed SVD and knowing (Eckart–Young) that it is the closest rank-1 matrix.

Show the worked solution — every step

Step 1 · Singular values and top right vector.

A^{\top}A=\begin{bmatrix}2&-1\\2&1\end{bmatrix}\begin{bmatrix}2&2\\-1&1\end{bmatrix}=\begin{bmatrix}5&3\\3&5\end{bmatrix}

(entries:

(1,1)\!: 4+1=5

;

(1,2)\!: 4-1=3

;

(2,2)\!: 4+1=5

). Then

\det\begin{bmatrix}5-\lambda&3\\3&5-\lambda\end{bmatrix}=(5-\lambda)^2-9=(\lambda-8)(\lambda-2)=0

, so

\sigma_1=\sqrt8=2\sqrt2,\qquad \sigma_2=\sqrt2,\qquad \mathbf{v}_1=\tfrac{1}{\sqrt2}(1,1)^{\top}\ \text{(for }\lambda=8\text{)}.

Step 2 · Top left vector.

\mathbf{u}_1=\frac{1}{\sigma_1}A\mathbf{v}_1=\frac{1}{2\sqrt2}\cdot\frac{1}{\sqrt2}\begin{bmatrix}2+2\\-1+1\end{bmatrix}=\frac{1}{4}\begin{bmatrix}4\\0\end{bmatrix}=\begin{bmatrix}1\\0\end{bmatrix}.

Step 3 · Rank-1 approximation.

A_1=\sigma_1\mathbf{u}_1\mathbf{v}_1^{\top}=2\sqrt2\begin{bmatrix}1\\0\end{bmatrix}\cdot\frac{1}{\sqrt2}\begin{bmatrix}1&1\end{bmatrix}=2\begin{bmatrix}1&1\\0&0\end{bmatrix}=\begin{bmatrix}2&2\\0&0\end{bmatrix}.

By the Eckart–Young theorem this is the closest rank-1 matrix to

A

; the discarded part corresponds to the dropped singular value

\sigma_2=\sqrt2

, and indeed

\lVert A-A_1\rVert_2=\sigma_2=\sqrt2

.

Answer.

\sigma_1=2\sqrt2

,

\sigma_2=\sqrt2

;

A_1=\sigma_1\mathbf{u}_1\mathbf{v}_1^{\top}=\begin{bmatrix}2&2\\0&0\end{bmatrix}

with

\mathbf{u}_1=(1,0)^{\top}

,

\mathbf{v}_1=\tfrac{1}{\sqrt2}(1,1)^{\top}

.

Watch out

$A_1$ needs all three ingredients — $\sigma_1$ out front and unit vectors $\mathbf{u}_1,\mathbf{v}_1$ . Forgetting a normalisation rescales the whole approximation and silently breaks Eckart–Young optimality.

Key takeaway

Truncating the SVD after $k$ terms gives the best rank- $k$ approximation, and the error is exactly the first dropped singular value: $\lVert A-A_k\rVert_2=\sigma_{k+1}$ .

Wait — really?

The best rank-1 stand-in keeps the top row $(2,2)$ exactly and zeroes the bottom row — the SVD judged the row of size $2\sqrt2$ worth keeping and the orthogonal remainder of size $\sqrt2$ expendable. Approximation by importance, not by position.

Problem 10Easy

A matrix has the SVD data

\sigma_1=3,\ \mathbf{u}_1=\tfrac{1}{\sqrt2}(1,1)^{\top},\ \mathbf{v}_1=\tfrac{1}{\sqrt2}(1,1)^{\top};\qquad \sigma_2=1,\ \mathbf{u}_2=\tfrac{1}{\sqrt2}(1,-1)^{\top},\ \mathbf{v}_2=\tfrac{1}{\sqrt2}(1,-1)^{\top}.

(a) Reconstruct $A=\sigma_1\mathbf{u}_1\mathbf{v}_1^{\top}+\sigma_2\mathbf{u}_2\mathbf{v}_2^{\top}$ . (b) Write down the best rank-1 approximation and the relative weight it keeps.

What this tests. Reading the SVD as $A=\sum_i\sigma_i\mathbf{u}_i\mathbf{v}_i^{\top}$ — a weighted stack of rank-1 layers — and measuring a truncation's kept energy.

Show the worked solution — every step

Part (a) · Two rank-1 layers.

\sigma_1\mathbf{u}_1\mathbf{v}_1^{\top}=3\cdot\frac{1}{\sqrt2}\begin{bmatrix}1\\1\end{bmatrix}\cdot\frac{1}{\sqrt2}\begin{bmatrix}1&1\end{bmatrix}=\frac32\begin{bmatrix}1&1\\1&1\end{bmatrix},\qquad \sigma_2\mathbf{u}_2\mathbf{v}_2^{\top}=\frac12\begin{bmatrix}1&-1\\-1&1\end{bmatrix}.

Adding, entry by entry:

(1,1)\!:\tfrac32+\tfrac12=2

;

(1,2)\!:\tfrac32-\tfrac12=1

;

(2,1)\!:1

;

(2,2)\!:2

:

A=\frac12\begin{bmatrix}3&3\\3&3\end{bmatrix}+\frac12\begin{bmatrix}1&-1\\-1&1\end{bmatrix}=\begin{bmatrix}2&1\\1&2\end{bmatrix}.

Part (b) · Best rank-1 approximation and its weight. Keep the largest singular value only:

A_1=\sigma_1\mathbf{u}_1\mathbf{v}_1^{\top}=\frac32\begin{bmatrix}1&1\\1&1\end{bmatrix}.

This is the rank-

k

truncation

\hat A^{(k)}=\sum_{i=1}^{k}\sigma_i\mathbf{u}_i\mathbf{v}_i^{\top}

with

k=1

. The energy kept is

\frac{\sigma_1^{2}}{\sigma_1^{2}+\sigma_2^{2}}=\frac{9}{10}=90\%.

Answer.

A=\begin{bmatrix}2&1\\1&2\end{bmatrix}

; best rank-1 approximation

A_1=\frac32\begin{bmatrix}1&1\\1&1\end{bmatrix}

, keeping

\sigma_1^{2}/(\sigma_1^{2}+\sigma_2^{2})=90\%

of the energy.

Watch out

Energy is measured in $\sigma^{2}$ , not $\sigma$ : the weights here are $9\!:\!1$ , not $3\!:\!1$ . Squaring is what makes truncation so effective — and forgetting it understates how much the top layer carries.

Key takeaway

The SVD writes any matrix as a sum of rank-1 layers $\sigma_i\mathbf{u}_i\mathbf{v}_i^{\top}$ , sorted by importance. Compression = keep the top $k$ layers, drop the rest.

Wait — really?

Half the singular values carry 90% of the energy. This uneven split is the entire business model of image compression and PCA: real-world matrices almost always hide a steep $\sigma$ -decay, and the squares make it steeper.

Problem 11Medium

Compute the spectral norm $\lVert A\rVert_2$ of

A=\begin{bmatrix}4&3\\0&5\end{bmatrix},

and state the corresponding right singular vector.

What this tests. The definition $\lVert A\rVert_2=\sigma_{\max}=\sqrt{\lambda_{\max}(A^{\top}A)}$ — the largest stretch factor of the matrix.

Show the worked solution — every step

Step 1 · Form $A^{\top}A$ .

A^{\top}A=\begin{bmatrix}4&0\\3&5\end{bmatrix}\begin{bmatrix}4&3\\0&5\end{bmatrix}=\begin{bmatrix}16&12\\12&34\end{bmatrix}

(entries:

(1,1)\!: 16+0=16

;

(1,2)\!: 4\cdot 3+0\cdot 5=12

;

(2,2)\!: 9+25=34

).

Step 2 · Largest eigenvalue of $A^{\top}A$ . Trace

=50

and determinant

=16\cdot 34-12^{2}=544-144=400

, so

\det(A^{\top}A-\lambda I)=\lambda^{2}-50\lambda+400=0

and

\lambda=\frac{50\pm\sqrt{2500-1600}}{2}=\frac{50\pm 30}{2}=40\ \text{or}\ 10.

Hence

\sigma_{\max}=\sqrt{40}=2\sqrt{10}

and

\sigma_{\min}=\sqrt{10}

.

Step 3 · Right singular vector for $\sigma_{\max}$ .

(A^{\top}A-40I)\mathbf{v}=\begin{bmatrix}-24&12\\12&-6\end{bmatrix}\mathbf{v}=\mathbf{0}\ \Rightarrow\ 2x=y,

so

\mathbf{v}_1=\tfrac{1}{\sqrt5}(1,2)^{\top}

, and

\lVert A\rVert_2=2\sqrt{10}\approx 6.32.

(Consistency check:

\sigma_1\sigma_2=\sqrt{40}\sqrt{10}=\sqrt{400}=20=\lvert\det A\rvert

. ✓)

Answer.

\lVert A\rVert_2=\sigma_{\max}=2\sqrt{10}\approx 6.32

, attained along

\mathbf{v}_1=\tfrac{1}{\sqrt5}(1,2)^{\top}

(the other singular value is

\sqrt{10}

).

Watch out

Do not take the largest $\lvert\text{eigenvalue of }A\rvert$ — that would give 5 here, and it is wrong. The spectral norm always comes from $A^{\top}A$ : $\lVert A\rVert_2=\sqrt{\lambda_{\max}(A^{\top}A)}$ . Eigenvalues equal singular values only for symmetric matrices (up to sign).

Key takeaway

$\lVert A\rVert_2=\sigma_{\max}$ is the largest factor by which $A$ can stretch any vector, and the top right singular vector is the direction that achieves it.

Wait — really?

$A$ 's eigenvalues are 4 and 5, yet $A$ stretches the direction $(1,2)/\sqrt5$ by $2\sqrt{10}\approx 6.32$ — more than any eigenvalue suggests. Non-symmetric matrices can out-stretch their own spectrum; that hidden extra gain is exactly what the spectral norm measures.

Problem 12Hard

Capstone. For $\;A=\begin{bmatrix}1&2\\2&1\end{bmatrix}$ : (a) find its eigendecomposition (note the negative eigenvalue); (b) find its SVD; (c) explain precisely how the two are related.

What this tests. How the eigendecomposition and the SVD of one symmetric matrix line up — and exactly where a negative eigenvalue forces them apart.

Show the worked solution — every step

Part (a) · Eigendecomposition.

\det(A-\lambda I)=(1-\lambda)^{2}-4=(\lambda-3)(\lambda+1)=0\Rightarrow\lambda_1=3,\ \lambda_2=-1

. Orthonormal eigenvectors

\mathbf{q}_1=\tfrac{1}{\sqrt2}(1,1)^{\top}

(for 3) and

\mathbf{q}_2=\tfrac{1}{\sqrt2}(1,-1)^{\top}

(for

-1

). With

Q=\tfrac{1}{\sqrt2}\begin{bmatrix}1&1\\1&-1\end{bmatrix}

,

A=Q\begin{bmatrix}3&0\\0&-1\end{bmatrix}Q^{\top}.

Part (b) · SVD.

A^{\top}A=A^{2}=\begin{bmatrix}5&4\\4&5\end{bmatrix}

has eigenvalues

9

and

1

, so

\sigma_1=3,\ \sigma_2=1

— note

\sigma_i=\lvert\lambda_i\rvert

. The right singular vectors are the same eigenvectors

\mathbf{v}_1=\tfrac{1}{\sqrt2}(1,1)^{\top}

,

\mathbf{v}_2=\tfrac{1}{\sqrt2}(1,-1)^{\top}

, and

\mathbf{u}_1=\frac{1}{3}A\mathbf{v}_1=\frac{1}{\sqrt2}\begin{bmatrix}1\\1\end{bmatrix}=\mathbf{v}_1,\qquad \mathbf{u}_2=\frac{1}{1}A\mathbf{v}_2=\frac{1}{\sqrt2}\begin{bmatrix}-1\\1\end{bmatrix}=-\mathbf{v}_2.

U=\frac{1}{\sqrt2}\begin{bmatrix}1&-1\\1&1\end{bmatrix},\qquad \Sigma=\begin{bmatrix}3&0\\0&1\end{bmatrix},\qquad V=\frac{1}{\sqrt2}\begin{bmatrix}1&1\\1&-1\end{bmatrix}.

Part (c) · The relationship. For a symmetric matrix the singular values are the absolute values of the eigenvalues,

\sigma_i=\lvert\lambda_i\rvert

, and the right singular vectors are the eigenvectors. Where an eigenvalue is positive,

\mathbf{u}_i=\mathbf{v}_i

; where it is negative (here

\lambda_2=-1

), the minus sign is absorbed into the left vector,

\mathbf{u}_i=-\mathbf{v}_i

. Thus EVD and SVD coincide exactly when every eigenvalue is non-negative (a positive-semidefinite matrix); otherwise they differ only by these sign flips between

U

and

V

.

Answer. EVD:

A=Q\operatorname{diag}(3,-1)Q^{\top}

with

Q=\tfrac{1}{\sqrt2}\begin{bmatrix}1&1\\1&-1\end{bmatrix}

. SVD:

\Sigma=\operatorname{diag}(3,1)=\operatorname{diag}(\lvert\lambda_i\rvert)

,

V=Q

,

U=\tfrac{1}{\sqrt2}\begin{bmatrix}1&-1\\1&1\end{bmatrix}

(the negative eigenvalue flips the sign of

\mathbf{u}_2

relative to

\mathbf{v}_2

).

Watch out

$\sigma_i=\lvert\lambda_i\rvert$ holds only for symmetric matrices — Problem 11 just showed a triangular matrix where no singular value matches any eigenvalue. And even here, symmetric or not, $U\neq V$ : the sign bookkeeping is part of the decomposition.

Key takeaway

Symmetric $A$ : singular values $=\lvert\text{eigenvalues}\rvert$ , $V=$ eigenvectors, and EVD $=$ SVD precisely when $A$ is positive semidefinite. The SVD is the eigendecomposition with all stretches forced non-negative.

Wait — really?

Compare $D=\operatorname{diag}(3,-1)$ with $\Sigma=\operatorname{diag}(3,1)$ : the SVD refuses negative stretches. It rewrites "stretch by $-1$ " as "stretch by $1$ , then flip", and hides the flip inside $U$ . Same matrix, same action — two bookkeeping conventions for a reflection.

Next up

Unit 6 · Differentiation →

Part I is complete: you can move, measure, and decompose space. Part II asks how things change. Unit 6 builds the derivative from a shrinking secant up to the Jacobian matrices behind backpropagation — and answers the question every model is really asking: which way is down?

← All units