Matrix Decomposition and SVD: The Swiss Army Knife of Linear Algebra

Here is a strange fact about matrices. Take almost any grid of numbers you care about — exam marks of 500 students across 8 subjects, pixel brightness values of a photograph, a table of which of 10,000 users liked which of 3,000 movies — and you will usually find that the matrix is carrying far less real information than its size suggests. A 500×8 marks matrix looks like 4,000 independent numbers, but in reality a student's marks across subjects are correlated (a student strong in Physics is usually strong in Maths too), so the effective number of independent "directions of variation" in that data might be closer to 2 or 3. The question this chapter answers is: given a matrix, how do you find those hidden directions, rank them by importance, and use them to compress, understand, or approximate the matrix? The tool that does this — for absolutely any matrix, square or not, invertible or not — is called the Singular Value Decomposition, or SVD. It is the one factorization every other matrix decomposition wishes it could be, which is why it earns the "Swiss Army knife" name: eigendecomposition jams on non-square or non-diagonalizable matrices; SVD never does.

What a matrix actually does to space

Before decomposing anything, you need the right mental picture of what a matrix is. Forget "a matrix is a grid of numbers" for a moment. A 2×2 matrix A is a function that takes every point (x, y) in the plane and sends it to a new point A(x, y). Apply A to every point on the unit circle simultaneously, and the circle gets warped into some new shape.

Here is the one geometric fact that the entire theory of SVD is built on, stated informally first: no matter how weird the matrix, the unit circle always warps into an ellipse (in higher dimensions, a "hyperellipsoid"), never into some lumpy asymmetric blob. That ellipse has two special perpendicular directions — its major and minor axes. If you can find (a) which two perpendicular directions on the original circle land exactly on those axes, and (b) how long the axes end up being, you have completely described what the matrix does. Those two pieces of information are exactly the singular vectors and singular values. Everything below is the algebra needed to actually compute them, and a proof that this always works.

Eigenvalues and eigenvectors: the tool we borrow

SVD is built from a more basic idea you likely met with square matrices: an eigenvector of a square matrix M is a nonzero vector v whose direction M does not change — it only gets stretched or flipped: Mv = λv. The scalar λ is the corresponding eigenvalue. To find eigenvalues, rearrange to (M − λI)v = 0; for a nonzero v to exist, M − λI must be singular, i.e. det(M − λI) = 0. This is the characteristic equation.

Example: M = [4 2; 2 4]  (a symmetric matrix)

det(M - λI) = det([4-λ, 2; 2, 4-λ])
            = (4-λ)^2 - 4
            = λ^2 - 8λ + 12 = 0
            = (λ-6)(λ-2) = 0
            → λ = 6 or λ = 2

For λ = 6:  (4-6)v1 + 2v2 = 0  →  -2v1 + 2v2 = 0  →  v1 = v2
            eigenvector direction (1, 1)

For λ = 2:  (4-2)v1 + 2v2 = 0  →  2v1 + 2v2 = 0  →  v1 = -v2
            eigenvector direction (1, -1)

Notice the eigenvectors (1,1) and (1,-1) came out perpendicular. That is not a coincidence — it is a theorem: any real symmetric matrix has real eigenvalues and a full set of mutually perpendicular (orthogonal) eigenvectors. This is the Spectral Theorem, and you can treat it as a known, provable result. It is the single fact that makes SVD possible, because we are about to manufacture a symmetric matrix out of any matrix at all, even a non-square one that has no eigenvectors of its own.

Why eigendecomposition alone is not enough

Eigendecomposition writes a square matrix as M = PDP⁻¹, where D is diagonal and the columns of P are eigenvectors. This is powerful, but it fails in two common situations: (1) M is not square — a 500×8 marks matrix has no eigenvectors at all, because Mv = λv only makes sense when M maps a space to itself; (2) even for square matrices, M might not have enough independent eigenvectors to diagonalize (a "defective" matrix), or its eigenvectors might not be perpendicular, which breaks a lot of the geometric intuition we want. SVD sidesteps both problems entirely, for every real matrix, of every shape. Here is how.

The construction: turning any matrix into a symmetric one

Let A be any real m×n matrix (not necessarily square). Look at A^TA, an n×n matrix. Two facts about A^TA make everything work.

Fact 1 — A^T A is always symmetric.
(A^T A)^T = A^T (A^T)^T = A^T A.   QED.

Fact 2 — every eigenvalue of A^T A is ≥ 0.
Let v be a unit eigenvector of A^T A with eigenvalue λ:
   A^T A v = λ v
Take the dot product of both sides with v:
   v · (A^T A v) = λ (v · v) = λ        (since v is a unit vector)
The left side is (Av) · (Av) = |Av|^2, a squared length, which
can never be negative. So λ = |Av|^2 ≥ 0.

Because A^TA is symmetric, the Spectral Theorem guarantees it has n real, mutually perpendicular unit eigenvectors v₁, v₂, …, v_n — call this orthonormal set V. Because of Fact 2, its eigenvalues λ₁ ≥ λ₂ ≥ … ≥ λ_n ≥ 0 are never negative, so we can safely take their square roots. Define the singular values:

σ_i = √(λ_i),   for i = 1, ..., n,   with σ_1 ≥ σ_2 ≥ ... ≥ σ_n ≥ 0

Now build the other side. For every v_i with σ_i > 0, define u_i = (1/σ_i) Av_i. Two things need checking: that these u_i are unit vectors, and that they are mutually perpendicular. Both follow from one short computation:

u_i · u_j = (1/σ_iσ_j) (Av_i)·(Av_j) = (1/σ_iσ_j) v_i^T (A^T A) v_j
          = (1/σ_iσ_j) v_i^T (λ_j v_j) = (λ_j / σ_iσ_j) (v_i · v_j)

If i ≠ j:  v_i · v_j = 0 (V is orthonormal)  →  u_i · u_j = 0
If i = j:  v_i · v_i = 1, and λ_i = σ_i^2     →  u_i · u_i = σ_i^2/σ_i^2 = 1

So the u_i are automatically orthonormal too — we did not have to search for them separately; they fall out of A and V for free. (If A's rank is less than n, some σ_i are zero and the corresponding u_i can't be built this way; you complete U to a full orthonormal set using any perpendicular directions, since those directions get erased by A anyway.) Collect the u_i as columns of an m×m matrix U and the v_i as columns of V, and put the σ_i down the diagonal of an m×n matrix Σ (padded with zero rows or columns if A is not square). The claim — which you can verify column-by-column using Av_i = σ_iu_i — is:

A = U Σ V^T          (Singular Value Decomposition)

U : m×m, orthogonal (columns are orthonormal "output" directions)
Σ : m×n, diagonal, entries σ_1 ≥ σ_2 ≥ ... ≥ 0
V : n×n, orthogonal (columns are orthonormal "input" directions)

This factorization exists for every real matrix, full stop — no squareness required, no diagonalizability required. That universality is the entire reason it is called the Swiss Army knife of linear algebra: eigendecomposition is a specialty tool that only opens certain bottles; SVD opens all of them.

Full worked example: decomposing A = [[2, 2], [-1, 1]] by hand

Let's run the machinery on a concrete matrix, start to finish.

Step 1: Compute A^T A.

A = [ 2  2]        A^T = [ 2 -1]
    [-1  1]               [ 2  1]

A^T A = [2 -1] [2  2]  =  [2·2+(-1)(-1),  2·2+(-1)(1)]  =  [5 3]
        [2  1] [-1 1]     [2·2+1·(-1),    2·2+1·1    ]     [3 5]

Step 2: Find eigenvalues of A^T A = [5 3; 3 5].

trace = 10, det = 25 - 9 = 16
λ^2 - 10λ + 16 = 0
λ = (10 ± √(100-64)) / 2 = (10 ± 6) / 2
λ_1 = 8,   λ_2 = 2

Step 3: Singular values.
σ_1 = √8 = 2√2 ≈ 2.828
σ_2 = √2       ≈ 1.414

Step 4: Eigenvectors of A^T A (these become columns of V).

λ_1 = 8:  (5-8)v1 + 3v2 = 0  →  -3v1 + 3v2 = 0  →  v1 = v2
          unit eigenvector: (1/√2, 1/√2)

λ_2 = 2:  (5-2)v1 + 3v2 = 0  →   3v1 + 3v2 = 0  →  v1 = -v2
          unit eigenvector: (1/√2, -1/√2)

So  V = [1/√2   1/√2 ]
        [1/√2  -1/√2 ]

Step 5: Build U using u_i = A v_i / σ_i.

A v1 = [2 2][1/√2]  = [ (2+2)/√2 ]  = [4/√2] = [2√2]
       [-1 1][1/√2]    [(-1+1)/√2]    [0   ]   [0  ]

u1 = A v1 / σ1 = (2√2, 0) / (2√2) = (1, 0)

A v2 = [2 2][ 1/√2] = [(2-2)/√2 ]  = [0]
       [-1 1][-1/√2]  [(-1-1)/√2]    [-√2]

u2 = A v2 / σ2 = (0, -√2) / √2 = (0, -1)

So  U = [1  0]
        [0 -1]

Step 6: Assemble and verify.
A = U Σ V^T,  Σ = diag(2√2, √2)

Let's actually check this multiplies back to A, since a formula you can't verify is a formula you shouldn't trust:

U Σ = [1  0] [2√2  0 ] = [2√2   0 ]
      [0 -1] [0    √2]   [0   -√2]

U Σ V^T = [2√2   0 ] [1/√2   1/√2 ]
          [0   -√2] [1/√2  -1/√2 ]

Row 1: (2√2 · 1/√2 + 0 · 1/√2,  2√2 · 1/√2 + 0 · (-1/√2)) = (2, 2)
Row 2: (0 · 1/√2 + (-√2) · 1/√2,  0 · 1/√2 + (-√2)(-1/√2)) = (-1, 1)

Result: [2  2]  ✓ matches A exactly.
        [-1 1]

One more identity worth checking by hand, because it will matter for compression later: A can be rebuilt as a sum of two rank-1 pieces, one per singular value, using A = σ₁u₁v₁^T + σ₂u₂v₂^T.

σ1 u1 v1^T = 2√2 · [1] [1/√2  1/√2]  = [2  2]
                    [0]                 [0  0]

σ2 u2 v2^T = √2  · [ 0] [1/√2  -1/√2] = [ 0  0]
                    [-1]                [-1  1]

Sum = [2  2] + [ 0  0] = [ 2  2]  ✓ matches A again.
      [0  0]   [-1  1]    [-1  1]

The rank-1 term with the bigger singular value (σ₁ = 2√2) contributes almost all of A's "energy"; the second term is a smaller correction. This decomposition — a big term plus a shrinking correction — is exactly what makes SVD useful for compression, which we get to shortly.

Checking the answer with code

You should never trust a hand derivation blindly — verify it computationally. NumPy's linalg.svd computes exactly this factorization:

import numpy as np

A = np.array([[2, 2], [-1, 1]])
U, S, Vt = np.linalg.svd(A)

print(S)
# [2.82842712 1.41421356]   → matches 2√2 and √2 computed by hand

recon = U @ np.diag(S) @ Vt
print(np.allclose(recon, A))
# True

One caution: NumPy's U and Vt may not print with exactly the signs derived by hand above. SVD is unique up to simultaneously flipping the sign of a matched pair (u_i, v_i) — flipping both leaves σ_iu_iv_i^T unchanged, so (−u₁, −v₁) is an equally valid answer to (u₁, v₁). The singular values themselves, and the reconstruction UΣV^T, are never ambiguous.

Common misconception: "singular values are just eigenvalues by another name"

This is wrong, and it's worth seeing exactly where it breaks. Singular values of A are the square roots of the eigenvalues of A^TA — not eigenvalues of A itself. For a non-square matrix, A doesn't even have eigenvalues, so the question doesn't apply. But the misconception persists even for square matrices, so test it on one:

A = [1 1]     (a shear — squashes nothing, just tilts the plane)
    [0 1]

Eigenvalues of A: det(A - λI) = (1-λ)^2 = 0  →  λ = 1 (repeated)
So both eigenvalues of A equal 1.

But A^T A = [1 0][1 1] = [1 1]
            [1 1][0 1]   [1 2]

trace = 3, det = 2-1 = 1
λ^2 - 3λ + 1 = 0  →  λ = (3 ± √5)/2  →  λ ≈ 2.618 or 0.382

σ1 = √2.618 ≈ 1.618,   σ2 = √0.382 ≈ 0.618

Both eigenvalues of A are 1, but the singular values are ≈ 1.618 and ≈ 0.618 — nowhere near 1. Geometrically, A's eigenvalues only tell you what happens along the one special direction that doesn't rotate under a shear; the singular values tell you the actual maximum and minimum stretch factors over every direction, which for a shear is genuinely more than 1 in the direction of the shear and genuinely less than 1 perpendicular to it. The two facts (eigenvalues = 1, but the shape clearly gets stretched) are not in conflict once you realize eigenvalues and singular values are answering different questions. The one case where they do coincide is when A is symmetric and positive semi-definite — there, singular values equal eigenvalues exactly, which is why our very first example, M = [[4,2],[2,4]], would give identical eigenvalues and singular values if you checked (try it: A^TA = M² in that case, whose eigenvalues are λ_i², so σ_i = |λ_i|).

Why this is the Swiss Army knife: best low-rank approximation

Go back to the rank-1 sum: A = σ₁u₁v₁^T + σ₂u₂v₂^T + … + σ_ru_rv_r^T, with terms sorted from largest to smallest singular value. Stop the sum early — keep only the first k terms — and you get a matrix A_k of rank at most k. A theorem called the Eckart–Young theorem states that this truncated sum is not just a decent rank-k approximation of A; it is provably the best possible rank-k approximation, in the sense of minimizing the total squared error between A_k and A, among every rank-k matrix that exists. No cleverer rank-k matrix can approximate A more closely. That is an extremely strong guarantee, and it's the reason SVD is the default tool whenever you need to compress or simplify a matrix while preserving as much of its structure as possible.

Here is why that matters in storage terms. A rank-k approximation of an m×n matrix needs k singular values plus k columns of length m (for U) plus k columns of length n (for V) — roughly k(m+n+1) numbers, instead of mn numbers for the full matrix. Take a 500×500 grayscale image patch (250,000 numbers). If its singular values decay fast enough that keeping the top k = 30 captures nearly all the visual detail — genuinely true for most natural photographs, because neighbouring pixels are highly correlated — you'd store roughly 30 × 1001 = 30,030 numbers: about 12% of the original. (Note this is not how the JPEG standard actually compresses images — JPEG uses a different transform, the Discrete Cosine Transform, on small blocks — but SVD-based compression works on the same underlying observation: most real image data is close to low-rank, and it is used in its own right in areas like hyperspectral image compression and medical imaging.)

The same idea, applied to a matrix of (user, movie) ratings instead of (row, column) pixels, is matrix factorization for recommendation. If a ratings matrix is approximately rank-k for a modest k, that means each user's taste and each movie's appeal can be summarized by just k numbers ("latent factors"), and a user's predicted rating for a movie is approximately the dot product of their two factor-vectors. Methods built on exactly this idea — approximating a huge, mostly-empty ratings matrix with a low-rank factorization — were central to the winning approaches in the Netflix Prize competition (2006–2009), most famously the gradient-descent variant popularized by Simon Funk and later refined by the BellKor team. It's also the mathematical engine behind Principal Component Analysis (PCA): the right singular vectors of a mean-centered data matrix are its principal components, and the squared singular values tell you how much variance each direction explains.

Practice: work these out yourself before checking the answers

1. Symmetric case. Find the eigenvalues and eigenvectors of M = [[4, 2], [2, 4]], and state what its singular values must be without recomputing M^TM from scratch.
2. Full SVD by hand. Let B = [[3, 0], [4, 5]]. Compute B^TB, its eigenvalues, and the two singular values of B.
3. Determinant check. For our worked example A = [[2,2],[-1,1]], verify that σ₁σ₂ = |det A|.
4. Conceptual. True or false, with a one-line justification: "If a 3×3 matrix has three equal singular values σ₁ = σ₂ = σ₃ = 5, its eigenvalues must also all equal 5."
5. Compression estimate. A 200×300 matrix is approximated at rank k = 10. Roughly how many numbers does the rank-10 SVD approximation need to store, versus the 60,000 entries of the full matrix?
6. Proof recall. In one or two lines, explain why every eigenvalue of A^TA must be ≥ 0 for any real matrix A, even a non-square one.

Answers

1. trace=8, det=16-4=12 → λ^2-8λ+12=0 → λ=6 or λ=2
   λ=6: eigenvector (1,1);  λ=2: eigenvector (1,-1)
   M is symmetric, so its singular values equal |eigenvalues|: σ1=6, σ2=2.

2. B^T B = [3 4;0 5]·[3 0;4 5]... row1:(3,4)·(3,4)=25, (3,4)·(0,5)=20
                       row2:(0,5)·(3,4)=20, (0,5)·(0,5)=25
   B^T B = [25 20; 20 25], trace=50, det=625-400=225
   λ^2-50λ+225=0 → λ=(50±40)/2 = 45 or 5
   σ1 = √45 = 3√5 ≈ 6.708,  σ2 = √5 ≈ 2.236

3. det(A) = 2(1) - 2(-1) = 2+2 = 4
   σ1σ2 = 2√2 · √2 = 2·2 = 4.   Equal — confirmed.
   (General fact: the product of all singular values always equals |det A|
   for a square matrix, since U and V are orthogonal so |det U|=|det V|=1.)

4. False. Counterexample logic: equal singular values only force A to be a
   scaled orthogonal-type map (it sends every direction to length 5*something
   perpendicular-preserving), but A itself need not be symmetric, and a
   non-symmetric matrix's own eigenvalues can be complex or unequal even
   while its singular values are all equal.

5. k(m+n+1) = 10 × (200+300+1) = 10 × 501 = 5,010 numbers,
   versus 60,000 for the full matrix — about 8.4% of the storage.

6. For a unit eigenvector v of A^T A with eigenvalue λ: λ = v·(A^T A v)
   = (Av)·(Av) = |Av|^2, a squared length, which cannot be negative.
   This uses nothing about A being square — it holds for any real A.

Where this sits in your exams

CBSE's Class 12 Matrices & Determinants chapter stops at operations, inverses, and solving linear systems — it does not name eigenvalues or SVD. What this chapter gives you is the layer above that: the same matrices, but understood as geometric transformations with intrinsic stretch directions, which is exactly the intuition that makes matrix questions in JEE Advanced (where matrix-equation and characteristic-polynomial-flavoured problems do appear among the harder integer-type questions) much faster to reason about instead of grinding through algebra. The core skill this chapter builds — finding eigenvalues via the characteristic equation, and reasoning about a linear map through invariant directions rather than raw coordinates — is also good general preparation for the kind of structural, proof-oriented algebra problems that show up at INMO (Indian National Mathematical Olympiad) level, even though SVD itself is a numerical-linear-algebra tool that isn't directly examined there. Treat this chapter as depth beyond the board syllabus that pays off wherever "understand what a matrix does, not just how to multiply it" is being tested.

Summary

• Every real matrix A (any shape) can be written as A = UΣV^T, with U, V orthogonal and Σ diagonal with non-negative entries σ₁ ≥ σ₂ ≥ … ≥ 0 — this always exists, unlike eigendecomposition.
• The construction runs through A^TA: it's always symmetric (Fact 1) and always has eigenvalues ≥ 0 (Fact 2, proved via |Av|²), so the Spectral Theorem hands you an orthonormal eigenbasis V for free; singular values are σ_i = √λ_i, and U's columns u_i = Av_i/σ_i come out orthonormal automatically.
• Geometrically: V's columns are the perpendicular directions on the input unit sphere that map to the perpendicular axes of the output ellipsoid; U's columns are those axis directions; σ_i are the axis lengths.
• Singular values are not the same as eigenvalues of A in general — they coincide only when A is symmetric positive semi-definite.
• Truncating the rank-1 sum to the top k terms gives the Eckart–Young-optimal rank-k approximation of A, the basis for compression, PCA, and matrix-factorization-based recommendation.

Think About It

Think about this: How would you explain matrix decomposition and svd: the swiss army knife of linear algebra to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.