Singular Value Decomposition
1. The one idea: rotate → stretch → rotate
\(V^\top\) rotates into the right basis, \(\Sigma\) stretches by \(\sigma_i\), \(U\) rotates into the left basis. Unlike eigendecomposition, this works for every rectangular \(A\) — because we never diagonalize \(A\) itself. We diagonalize the symmetric \(A^TA\).
2. Square it, then use the spectral theorem
From \(A\) build the symmetric, positive semidefinite \(A^TA \in \mathbb{R}^{n\times n}\). By the spectral theorem some orthogonal \(P\) diagonalizes it:
Now assume \(A = U\Sigma V^\top\) and substitute:
\(U,V\) orthogonal, so \(U^\top U=I\), leaving:
Compare (11) and (13):
So the eigenvectors of \(A^TA\) (columns of \(P\)) are the right-singular vectors \(V\), and eigenvalues are squared singular values.
3. Mirror it for \(U\)
Columns of \(U\) are an orthonormal eigenbasis of \(AA^\top\). \(A^TA\) and \(AA^\top\) share nonzero eigenvalues, so the nonzero \(\sigma\)’s coincide.
Orthogonality check — for \(i\neq j\):
The images \(Av_i\) stay orthogonal. Normalize them for \(i=1,\dots,r=\mathrm{rank}(A)\):
Rearranged, the singular value equation:
This completes the construction: \(v_i\) plus \(u_i\) are two orthonormal bases linked by \(\Sigma\).
3b. Slow version: where do the \(u_i\) come from? (18)–(20)
At this point we have orthonormal \(v_1,\dots,v_n\) and \(\lambda_i \ge 0\) with \(\sigma_i=\sqrt{\lambda_i}\). We still need \(u_i\). Idea: push \(v_i\) through \(A\), then normalize. Each sub-step says what to write and how to read it aloud.
aOutputs stay orthogonal — (18)
Say ► “A-v-i transpose A-v-j equals v-i transpose A-transpose A v-j, which equals lambda-j times v-i transpose v-j, which is zero because v-i and v-j are orthonormal.”
Why it works: \(v_j\) is an eigenvector of \(A^TA\), so \((A^TA)v_j=\lambda_j v_j\). This is special to our \(v\)’s — arbitrary vectors would not stay orthogonal after \(A\).
bLength of each output is \(\sigma_i\)
Say ► “Norm A-v-i squared equals v-i transpose A-transpose A v-i, which equals lambda-i, which is sigma-i squared. So norm A-v-i equals sigma-i.”
Hop 1 — length-squared is dot-with-self: “Norm A-v-i squared equals A-v-i transpose A-v-i.” That is \(‖x‖^2=x^\top x\) with \(x=Av_i\).
Hop 2 — transpose reverses: “A-v-i transpose equals v-i transpose A-transpose.” That is \((Av_i)^\top=v_i^\top A^\top\), so \(‖Av_i‖^2=v_i^\top(A^\top A)v_i\).
Hop 3 — \(v_i\) is an eigenvector: “A-transpose-A v-i equals lambda-i v-i.” So \(v_i^\top(\lambda_i v_i)=\lambda_i(v_i^\top v_i)\).
Hop 4 — \(v_i\) is unit length: “v-i transpose v-i equals 1.” Hence \(‖Av_i‖^2=\lambda_i\), and square-rooting gives \(‖Av_i‖=\sqrt{\lambda_i}=\sigma_i\). Numbers: \(Av_1=[3,4]^\top\), squared length \(9+16=25=\lambda_1\), length \(5=\sqrt{25}=\sigma_1\).
cNormalize to get \(u_i\) — (19)
Say ► “Define u-i as A v-i over norm A v-i, which is A v-i over sigma-i.”
The \(Av_i\) already point in orthogonal directions by (a); dividing by their length makes them unit vectors. Hence the \(u_i\) are orthonormal, and they turn out to be eigenvectors of \(AA^\top\).
dRearrange — (20), and the rank cutoff
Say ► “Rearranged, A v-i equals sigma-i u-i, for i equals 1 through r, where r is the rank of A.”
Meaning: \(A\) takes input direction \(v_i\), stretches by \(\sigma_i\), lands on output direction \(u_i\). We stop at \(r\) because if \(\sigma_i=0\) then \(Av_i=0\) — nothing to normalize, division by zero. Example below: \(v_2=[0,1]^T\) maps to \([0,0]^T\), so \(u_2\) is just any unit vector orthogonal to \(u_1\).
3c. Dumb version with numbers (same thing, no jargon)
Players. \(v_1=[1,0]^T\) is “arrow right”, \(v_2=[0,1]^T\) is “arrow up”. Unit length, 90° apart — that is all “orthonormal” means. \(A=\begin{bmatrix}3&0\\4&0\end{bmatrix}\) eats an arrow and spits out an arrow.
Step 1 — push them through. \(Av_1=[3,4]^T\) (column 1 of \(A\)). Length: \(3^2+4^2=25\), so length 5. \(Av_2=[0,0]^T\) (column 2 is zeros). It dies. Length 0.
Step 2 — still 90° apart? Dot product \(3\cdot 0+4\cdot 0=0\). Yes. That check is equation (18). Normally \(A\) wrecks the 90° — here it does not, because we picked the \(v\)’s cleverly (eigenvectors of \(A^\top A\)).
Step 3 — shrink the survivor to length 1. \([3,4]^T\) has length 5, so \(u_1=[3/5,4/5]^T=[0.6,0.8]^T\). That is equation (19): “u-one is A-v-one shrunk to length 1”. The dead \([0,0]^T\) cannot be shrunk (division by zero), so we stop at \(r=\mathrm{rank}=1\) and pick \(u_2=[-0.8,0.6]^T\), anything 90° from \(u_1\).
Punchline. \(Av_1=5u_1\). Input arrow, stretched 5×, lands on output arrow. That is equation (20): \(Av_i=\sigma_i u_i\) with \(\sigma_1=5\) just the measured length from Step 1. So \(V\) = input compass, \(\Sigma\) = zooms (5 and 0), \(U\) = output compass.
3d. Whole theorem in dumb words (start to finish)
You have a matrix \(A\). It scrambles arrows. Goal: find a clean input compass (\(V\)), zooms (\(\Sigma\)), and a clean output compass (\(U\)) so \(A\) stops looking scrambled. Nothing below is new — it is sections 2–3b rewritten like the “dumb version”.
1Square it — because \(A\) itself is not symmetric
Say ► “A is rectangular and scrambled, so I square it: A-transpose A is square and symmetric, so the spectral theorem gives me a clean compass P with A-transpose A equals P D P-transpose and lambda-i greater or equal zero.”
Dumb: \(A^\top A\) measures “length after \(A\)”: \(x^\top A^\top A x = \|Ax\|^2\), and a squared length can never be negative — that is why \(\lambda_i \ge 0\). Numbers: \(A^\top A=\begin{bmatrix}25&0\\0&0\end{bmatrix}\), compass = arrows right/up, zooms-squared = 25 and 0.
Why do this? ► We cannot diagonalize \(A\) directly — it is rectangular and not symmetric, so the spectral theorem does not apply. \(A^\top A\) is square + symmetric by construction, so it is the only thing we are guaranteed to split into a clean compass. Without this detour we have no \(V\).
2Pretend the answer exists, plug it in
Say ► “Pretend A equals U Sigma V-transpose. Then A-transpose A equals V Sigma-transpose U-transpose U Sigma V-transpose, and U-transpose U is the identity, so this is V times diag sigma-i-squared times V-transpose.”
Dumb: the middle \(U\) cancels itself (\(U^\top U=I\) — unit perpendicular arrows undo each other). All that survives is \(V\) with squared zooms.
Why do this? ► Reverse-engineering. We do not know \(V,\Sigma\) yet, so we ask: if the SVD were true, what would \(A^\top A\) have to look like? The \(U\) in the middle cancels, so the answer must already be in \(V\)-form. That tells us what to look for in Step 1.
3Match — so \(V\) was the compass all along
Say ► “Comparing with step 1, V-transpose equals P-transpose and sigma-i-squared equals lambda-i. So the right-singular vectors are just the eigenvectors of A-transpose A, and the singular values are root lambda-i.”
Dumb: two recipes for the same thing (\(P\) from step 1, \(V\) from step 2) must agree. Numbers: \(\sigma_1=\sqrt{25}=5\), \(\sigma_2=\sqrt{0}=0\).
Why do this? ► Steps 1 and 2 both diagonalize the same matrix \(A^\top A\). There is only one such diagonalization (up to order/signs), so \(V\) must equal \(P\) and \(\sigma_i^2\) must equal \(\lambda_i\). This is the free win: we get the input compass + zooms without solving SVD directly.
4Mirror — same trick on the other side
Say ► “The same calculation for A A-transpose gives U times diag sigma-i-squared times U-transpose, so the columns of U are the eigenvectors of A A-transpose.”
Dumb: input compass came from \(A^\top A\); output compass comes from \(AA^\top\). Same zooms (nonzero ones coincide).
Why do this? ► So far we only have the input side. \(A\) maps input space \(\mathbb{R}^n\) to a different output space \(\mathbb{R}^m\), so we need a second compass for where answers land. \(AA^\top\) is the mirror version that lives in output space — same argument, gives \(U\).
5Make \(U\) out of \(V\) — push, check, shrink
Say ► “A-v-i transpose A-v-j is zero, so the pushed arrows stay perpendicular. Define u-i as A-v-i over its length, which is A-v-i over sigma-i. If sigma-i is zero the arrow died, so stop at r equals rank.”
Dumb: \(Av_1=[3,4]^T\) (length 5 → \(u_1=[0.6,0.8]^T\)); \(Av_2=[0,0]^T\) (dead → skip, complete \(u_2\) by hand).
Why do this? ► We have the input compass \(V\) but still no output compass \(U\) that matches it. Step 4 only says “some \(U\) exists” from \(AA^\top\) — if we computed it separately, we would get some orthonormal basis, but with no guarantee that \(v_1\) pairs with \(u_1\): order could be shuffled, sign could flip (\(+u_1\) vs \(-u_1\) are both eigenvectors). SVD needs the paired rule \(Av_i=\sigma_i u_i\) with the same \(i\). So instead of finding \(U\) independently, we derive it: push \(v_i\) through \(A\) (it stays ⊥ by step a, length is \(\sigma_i\) by step b), then shrink to length 1. Pairing then holds by construction, including the sign. Numbers: \(AA^\top\) alone would hand you \([0.6,0.8]^T\) and \([-0.8,0.6]^T\) without labels; pushing forces it — \(Av_1=[3,4]^T\) can only shrink to \(+[0.6,0.8]^T\), so \(u_1\) must be that one.
∎Done — glue reads \(Av_i=\sigma_i u_i\)
Say ► “Rearranged, A v-i equals sigma-i u-i. Stacked side by side for all i, that is A V equals U Sigma, i.e. A equals U Sigma V-transpose.”
Dumb: input compass → zoom → output compass. \(V\) un-mixes, \(\Sigma\) stretches, \(U\) re-orients. That is the whole SVD.
Why do this? ► Steps 1–5 gave per-arrow rules \(Av_i=\sigma_i u_i\). Stacking them side-by-side as \(AV=U\Sigma\) and right-multiplying by \(V^\top\) turns \(n\) separate facts into one matrix factorization. That final glue is what you quote as \(A=U\Sigma V^\top\).
4. Concrete example you can recompute
Let \(A=\begin{bmatrix}3&0\\4&0\end{bmatrix}\), rank 1.
\(A^TA=\begin{bmatrix}25&0\\0&0\end{bmatrix}\): eigenvalues \(\lambda_1=25,\lambda_2=0\), so \(\sigma_1=5,\sigma_2=0\). Right vectors \(v_1=\begin{bmatrix}1\\0\end{bmatrix}, v_2=\begin{bmatrix}0\\1\end{bmatrix}\), \(V=I\).
By (19): \(u_1 = Av_1/5 = \begin{bmatrix}3\\4\end{bmatrix}/5 = \begin{bmatrix}0.6\\0.8\end{bmatrix}\). Complete to orthonormal \(U=\begin{bmatrix}0.6&-0.8\\0.8&0.6\end{bmatrix}\), \(\Sigma=\begin{bmatrix}5&0\\0&0\end{bmatrix}\). Check \(U\Sigma V^\top=A\).
5. If the professor says: “Prove it” — follow this flow
This is the proof you should memorize. Do not try to memorize every sentence. Memorize the six jobs:
Make a square matrix, diagonalize it, take square-roots, push the right arrows through A, fill in the missing arrows, then stack the results.
One-line version: “ATA gives V and σ²; push V through A to get U; stack Avᵢ = σᵢuᵢ.”
find input arrows \(v_i\) → measure their output lengths \(\sigma_i\) → turn their outputs into unit arrows \(u_i\) → put every arrow equation into one matrix equation.
1SQUARE — make a symmetric matrix
Say ► “Start with the square matrix B equals A-transpose A. It is symmetric and positive semidefinite.”
Why? ► A may be rectangular, but AᵀA is square. Also, for any x, \(x^TA^TAx=\|Ax\|^2\ge0\).
2SPECTRAL THEOREM — find the input arrows
Say ► “Because B is symmetric, the spectral theorem gives an orthonormal eigenbasis v-one through v-n. Put those vectors into V. Order the positive eigenvalues first. There are r of them, where r is the rank of A.”
Why? ► The columns \(v_i\) of V are the special input directions. They are the directions we will send through A.
3SQUARE-ROOT — define the stretches
Say ► “Define sigma-i to be the nonnegative square-root of lambda-i. Put these numbers down the diagonal of the m-by-n matrix Sigma and put zero everywhere else.”
Why? ► \(A^TA\) measures the squared length of \(Av_i\), but SVD records the length itself.
4PUSH — make the output arrows
Say ► “For each positive sigma-i, send v-i through A. Its squared length is v-i-transpose A-transpose A v-i. Because v-i is an eigenvector, this equals lambda-i, which equals sigma-i-squared. Therefore Av-i has length sigma-i. Divide by that length and call the resulting unit vector u-i.”
Why? ► This is the pairing: \(v_i\) is the input direction, \(u_i\) is where that input comes out, and \(\sigma_i\) is how much it was stretched.
In words: output = length × output direction.
5COMPLETE — prove U is allowed
Say ► “I must check that the u-vectors are orthonormal. If i is different from j, then”
Continue ► “They are perpendicular because the v-vectors are perpendicular. Each u-i has length one because I divided Av-i by its length. Thus u-one through u-r are orthonormal. Add any perpendicular unit vectors needed to obtain an orthonormal basis u-one through u-m, and put them into U.”
Why? ► SVD requires U to be orthogonal. The zero directions produce \(Av_i=0\), so they cannot be normalized; those unused columns are filled in by hand.
6STACK — turn the arrows into the factorization
Say ► “For i up to r, Av-i equals sigma-i u-i by construction. For i greater than r, lambda-i is zero, so norm Av-i squared is zero and therefore Av-i is zero. Sigma-i is also zero. Thus every column of AV equals the matching column of U Sigma, so AV equals U Sigma.”
Continue ► “Multiply on the right by V-transpose. Since V V-transpose is the identity, A equals U Sigma V-transpose.”
Finish ► “Thus A equals U Sigma V-transpose, with U and V orthogonal and Sigma diagonal with nonnegative entries. This proves the SVD.”
If grilled: “Why \(\lambda_i\ge0\)?” → \(x^TA^TAx=\|Ax\|^2\ge0\). “Why divide by \(\sigma_i\)?” → \(\|Av_i\|=\sigma_i\), so division makes a unit vector. “Why not divide when \(\sigma_i=0\)?” → \(Av_i=0\), and zero has no direction to normalize.
Questions the professor may use to grill you
Cover the answer with your hand, answer aloud, and then check yourself. The bold sentence is the shortest acceptable answer.
Because \(A\) may be rectangular or nonsymmetric, while \(A^TA\) is always square and symmetric. Therefore the spectral theorem always applies to \(A^TA\).
Transpose it: \((A^TA)^T=A^T(A^T)^T=A^TA\).
If \(A^TAv_i=\lambda_i v_i\) and \(\|v_i\|=1\), then \[\lambda_i=v_i^TA^TAv_i=\|Av_i\|^2\ge0.\] An eigenvalue is a squared length, so it cannot be negative.
The spectral theorem gives an orthonormal eigenbasis for every real symmetric matrix. Since \(A^TA\) is symmetric, its eigenvectors can be chosen orthonormally—even when an eigenvalue is repeated.
Because \(\lambda_i=\|Av_i\|^2\) is the squared stretch. The singular value \(\sigma_i=\|Av_i\|=\sqrt{\lambda_i}\) is the actual stretch.
They represent lengths. We choose the nonnegative square-root \(\sigma_i=\sqrt{\lambda_i}\). Any sign belongs to the direction of \(u_i\) or \(v_i\), not to the amount of stretch.
Because \(\|Av_i\|=\sigma_i\). Therefore \[\|u_i\|=\left\|\frac{Av_i}{\sigma_i}\right\|=\frac{\|Av_i\|}{\sigma_i}=1.\]
For \(i\ne j\), \[(Av_i)^T(Av_j)=v_i^TA^TAv_j=\lambda_jv_i^Tv_j=0.\] Dividing by \(\sigma_i\sigma_j\) gives \(u_i^Tu_j=0\). The special eigenvector inputs remain perpendicular after being pushed through \(A\).
Then \(\|Av_i\|=0\), so \(Av_i=0\). The zero vector has no direction and division by zero is impossible. Complete the remaining columns of \(U\) using any orthonormal vectors perpendicular to those already constructed.
Because \(\ker(A^TA)=\ker(A)\), so \(A^TA\) and \(A\) have the same rank. Thus \(A^TA\) has exactly \(r\) positive eigenvalues, and their square-roots are the positive singular values.
Starting from \(Av_i=\sigma_i u_i\), \[AA^Tu_i=A(A^Tu_i)=\sigma_i^2u_i.\] More explicitly, \(A^Tu_i=A^TAv_i/\sigma_i=\sigma_i v_i\), so \(AA^Tu_i=\sigma_i Av_i=\sigma_i^2u_i\). Thus \(u_i\) has eigenvalue \(\sigma_i^2\).
If \(A^TAv=\lambda v\) with \(\lambda>0\), then \(Av\ne0\), and \[AA^T(Av)=A(A^TAv)=\lambda(Av).\] So \(Av\) is an eigenvector of \(AA^T\) with the same \(\lambda\). The reverse direction uses \(A^Tu\). The nonzero eigenvalues pair across the two matrices.
The \(i\)-th column of \(AV\) is \(Av_i\), and the \(i\)-th column of \(U\Sigma\) is \(\sigma_i u_i\) (or zero when \(\sigma_i=0\)). The two matrices have the same columns, so they are equal.
Because \(V\) is orthogonal, \(VV^T=I\). Therefore \[AV=U\Sigma \quad\Longrightarrow\quad AVV^T=U\Sigma V^T \quad\Longrightarrow\quad A=U\Sigma V^T.\]
Not completely. Singular vectors may be multiplied by matching signs, vectors belonging to repeated singular values may be rotated within their shared subspace, and zero-singular-value columns can be completed in different ways. The singular values themselves are fixed, usually listed from largest to smallest.
Because \(A\) is \(m\times n\), while \(U\) is \(m\times m\) and \(V^T\) is \(n\times n\). For \(U\Sigma V^T\) to have the same shape as \(A\), \(\Sigma\) must be \(m\times n\).
30-second rescue version — write this if your mind goes blank:
Say it from memory: “Eigenvectors of ATA give V. Square-roots of its eigenvalues give Sigma. Normalized Av-i give U. Stack the equations.”
6. Check yourself
Pick an answer — feedback is immediate. Answers matched in length so formatting gives no hints.
7. Go to the source
Primary source: Strang, Introduction to Linear Algebra, §7.1 “Singular Values and Singular Vectors” — or MIT 18.06 Lecture 29 (Singular Value Decomposition). Same \(A^TA \to V,\sigma^2\) route, plus why \(Av_i=\sigma_i u_i\) is the payoff.
Prev: 0001 — diagonalization · Next: 0003 — orthogonality in one page (small things).