Singular Value Decomposition

The last lesson’s question asked for a decomposition that works on any matrix. Eigenvalues will not do — they only describe square matrices, and even then can come out negative or complex. The singular value decomposition minds none of that. It works for any matrix at all, square or rectangular, and produces a clean set of non-negative numbers, the singular values, measuring how much the matrix stretches space along its most important directions.

The factorisation reads A = UΣVᵀ, and geometrically it is three simple moves: an orthogonal V picks the input directions, the diagonal Σ stretches along each by a singular value, and an orthogonal U rotates the result into the output space. Rotate, stretch, rotate — and that is every linear map there is.

An orthogonal matrix is one whose columns are unit vectors at right angles to one another (equivalently QᵀQ = I), which is precisely the algebraic way of saying “this matrix rotates or reflects, but never stretches”. All the stretching in A is therefore quarantined inside the single diagonal matrix Σ — that is what makes the singular values worth so much.

A = UΣVᵀ

The exam’s central question is where the singular values come from. Form the matrix AᵀA — always symmetric and positive-semidefinite, so its eigenvalues are real and ≥ 0. The singular values are their square roots:

σᵢ = √( λᵢ(AᵀA) ),     σᵢ ≥ 0 always.

Three consequences are worth memorising:

• Always non-negative: even if A has negative or complex eigenvalues, each σᵢ is a real ≥ 0, being a square root of a non-negative eigenvalue of AᵀA.
• Symmetric PSD case: if A is symmetric positive-semidefinite, its singular values equal its eigenvalues (σᵢ = λᵢ) — the only general case where they coincide.
• Rank: the number of non-zero singular values equals rank(A).

That last bullet has a companion that people skip past, and it is where the shape of A enters. An m × n matrix has exactly min(m, n) singular values in total — that is simply how many diagonal slots Σ owns — and the non-zero ones among them count the rank. Zeros are still singular values; they just sit at the bottom of the sorted list. This is also why rank(A) ≤ min(m, n) can never be broken: you cannot have more non-zero σ’s than there are σ’s.

Watch both facts on one small rectangular matrix:

        ⎡1 1⎤             ⎡1 1⎤
A   =   ⎢0 0⎥      AᵀA =  ⎣1 1⎦      eigenvalues of AᵀA:  2 and 0
        ⎣0 0⎦                        σ = √2  and  0

A is 3×2, so min(3, 2) = 2 singular values in all.
Exactly one is non-zero, so rank(A) = 1 — and indeed both columns of A are the same vector.

The geometry is the same one PCA exploits. Reshape the cloud below: the principal arrows are the singular vectors of the (centred) data matrix, and their lengths track the singular values — the directions of largest spread are the top singular-value directions.

A worked example — real GATE DA 2024

Let u = (1, 2, 3, 4, 5)ᵀ and M = uuᵀ (a 5×5 matrix). Find the sum of the singular values of M.

M = uuᵀ is an outer product, so every column is a multiple of u — the column space is one line, rank(M) = 1. A rank-1 matrix has exactly one non-zero singular value. Applying M to u gives Mu = u(uᵀu) = ‖u‖²·u, so u is an eigenvector of M with eigenvalue ‖u‖²; the lone non-zero eigenvalue of MᵀM is (‖u‖²)², and its square root is

σ = √( (‖u‖²)² ) = ‖u‖² = 1² + 2² + 3² + 4² + 5² = 1 + 4 + 9 + 16 + 25 = 55

All other singular values are 0, so the sum of the singular values is 55. The shortcut: for a rank-1 uuᵀ, the one non-zero singular value is ‖u‖² (the squared length of u).

A question to carry forward

You now hold a whole web of always-true facts — the determinant test for singularity, the rank conditions on solutions, the eigenvalue and singular-value rules. GATE’s hardest Linear Algebra questions rarely test one in isolation; they stack several into a single “which of the following is always true?” and plant one plausible falsehood among them. Here is the thread onward: how do you reason through such a clustered statement quickly, knowing which facts are watertight and which are the classic traps?

In one breath

• SVD: every matrix (any shape) factors A = UΣVᵀ — orthogonal V (rotate), diagonal Σ of non-negative singular values (stretch), orthogonal U (rotate).
• Singular values σᵢ = √(eigenvalues of AᵀA), always real and ≥ 0 (even if A’s eigenvalues are negative/complex).
• Count: number of non-zero σ = rank(A).
• σ = λ only for symmetric PSD A; in general they differ ([[0,2],[0,0]]: σ = 2,0 but λ = 0,0).
• Rank-1 uuᵀ: one non-zero singular value = ‖u‖² (e.g. u=(1,2,3,4,5) → 55).

Practice