Matrix Rank & Low-Rank Approximation

How many independent directions a matrix encodes

Why

Not all rows and columns of a matrix are independent — some may be linear combinations of others. Rank tells you exactly how many truly independent directions exist. A matrix that looks large may carry far less information than its size suggests, and rank is how you measure that.

Intuition

The rank of a matrix is how many truly independent directions it has. A 1000×1000 matrix of rank 5 looks massive — but it's only doing 5 distinct things. Everything else is just echoes of those 5.

Explanation
What Rank Means
rank(A) = number of non-zero singular values in SVD rank(A) ≤ min(m, n) for an m×n matrix Full rank: rank = min(m, n) — no redundancy Rank deficient: rank < min(m, n) — some columns are linear combinations of others

A rank-r matrix can be written as a sum of r rank-1 outer products: A = u₁v₁ᵀ + u₂v₂ᵀ + … + uᵣvᵣᵀ. Each outer product contributes one independent direction. The column space has dimension r — all outputs live in an r-dimensional subspace.

Low-Rank Approximation
A ≈ A_k = U_k · Σ_k · V_kᵀ U_k: (m×k), Σ_k: (k×k), V_kᵀ: (k×n) Storage: m×n → m·k + k·n numbers

Keep only the top-k singular values to get the closest rank-k matrix to A. The Eckart-Young theorem proves A_k minimizes ‖A − B‖_F over all rank-k matrices B — no other rank-k matrix is closer.

Rank and Linear Systems
  • A square matrix is invertible if and only if it is full rank
  • A rank-deficient matrix maps multiple inputs to the same output — the transformation loses information
  • The null space of A has dimension n − rank(A): these are the directions A collapses to zero