Numerical Linear Algebra

Matrix decompositions factor a matrix into products of simpler matrices, each with special properties. The LU decomposition factors a square matrix into a lower triangular matrix L and an upper triangular matrix U, enabling efficient solving of linear systems and computation of determinants. The QR decomposition factors into an orthogonal matrix Q (Q transpose times Q equals the identity) and an upper triangular matrix R, essential for least squares and eigenvalue algorithms. The Cholesky decomposition is a specialized factorization for symmetric positive definite matrices: A equals L times L transpose, where L is lower triangular. It is twice as fast as LU.

The SVD is arguably the most important matrix decomposition in applied mathematics. It factors any matrix A (even rectangular or singular) into U times Sigma times V transpose. U and V are orthogonal matrices, and Sigma is a diagonal matrix of singular values (non-negative, sorted in descending order). The SVD reveals the fundamental structure of a matrix: the rank equals the number of non-zero singular values. Truncating to the largest k singular values gives the optimal rank-k approximation — the basis of Principal Component Analysis (PCA), latent semantic analysis, collaborative filtering, and image compression.

When matrices are very large (millions of rows) and sparse (mostly zeros), direct methods like Gaussian elimination become too expensive (O of n cubed). Iterative methods solve these efficiently. The Conjugate Gradient (CG) method is optimal for symmetric positive definite systems, converging in at most n iterations. GMRES (Generalized Minimal Residual) handles non-symmetric systems. Preconditioning transforms the system to improve convergence — a good preconditioner can reduce iterations from thousands to dozens. Multigrid methods achieve optimal O of n complexity by solving on multiple grid resolutions simultaneously, making them among the fastest solvers for elliptic PDEs.

See how the SVD decomposes a matrix transformation into rotation, scaling, and rotation. Adjust parameters to see the geometric interpretation.

The Singular Value Decomposition factors ANY matrix A (m×n) into A = UΣV^T. U (m×m) and V (n×n) are orthogonal matrices (U^T U = I, V^T V = I). Σ is a diagonal matrix of singular values σ_1 ≥ σ_2 ≥ ... ≥ σ_r > 0, where r is the rank. Geometrically: every matrix is a rotation (V^T), then axis-aligned scaling (Σ), then another rotation (U).

The SVD is the crown jewel of numerical linear algebra because: (1) it exists for EVERY matrix, even rectangular and singular, (2) it reveals rank (number of nonzero singular values), (3) it provides the optimal low-rank approximation (keep the largest k singular values — this is the Eckart-Young theorem and the math behind PCA), (4) the condition number κ = σ_max/σ_min measures sensitivity to errors, (5) the pseudoinverse A^+ = VΣ^+U^T solves least-squares problems for any matrix. Google's PageRank, Netflix's recommendation system, image compression (JPEG), and semantic search embeddings all rely on the SVD.