A matrix decomposition writes a matrix as a product of simpler matrices — triangular, diagonal, orthogonal, or some combination — whose structure makes subsequent computation cheap. The upfront cost of factoring is repaid every time the factors are used to solve a system, compute eigenvalues, approximate data, or analyze stability. Decompositions are the computational backbone of applied linear algebra.
What a Decomposition Is
A matrix decomposition (or factorization) expresses a matrixA as a product of two or more matrices with known, exploitable structure. The factors are typically triangular, diagonal, or orthogonal — matrices for which solving systems, computing determinants, and extracting eigenvalues are either trivial or dramatically simplified.
A decomposition does not change the matrix. It reveals the internal structure of A by splitting it into interpretable components. The product of the factors always reproduces A exactly — the information is rearranged, not altered.
Every decomposition represents a trade: an upfront cost to compute the factors, followed by cheap operations that use them. The factorization is done once; the payoff is reaped every time the factors are applied.
Why Decompositions Matter
Decompositions transform hard problems into sequences of easy ones.
Solving linear systems: the LU decomposition converts a single factorization into cheap triangular solves for any number of right-hand sides. The Cholesky decomposition does the same at half the cost when the matrix is symmetric positive definite.
Least squares: the QR decomposition avoids squaring the condition number, providing a numerically stable solution to overdetermined systems.
Eigenvalue computation: the QR algorithm — an iterative process built on repeated QR factorizations — is the standard method for finding eigenvalues of general matrices, entirely avoiding the characteristic polynomial.
Dimensionality reduction: the singular value decomposition identifies the most important directions in the data and discards the rest, enabling compression, noise removal, and low-rank approximation.
Numerical stability: orthogonal factors (Q in QR, U and V in SVD) preserve lengths and condition numbers, keeping rounding errors under control throughout the computation.
LU Decomposition
The LU decomposition factors a square matrix as A=LU (or PA=LU with row pivoting), where L is lower triangular and U is upper triangular. It captures the entire process of Gaussian elimination in matrix form: U is the echelon form, and L stores the multipliers used during elimination.
Solving Ax=b reduces to two triangular substitutions — forward (Ly=b) then backward (Ux=y) — each costing O(n2). The factorization itself costs 32n3, but each additional right-hand side costs only O(n2). For k systems sharing the same coefficient matrix, LU amortizes the dominant cost over all k solves.
QR Decomposition
The QR decomposition factors an m×n matrix as A=QR, where Q has orthonormal columns and R is upper triangular. It is produced by the Gram-Schmidt process, by Householder reflections, or by Givens rotations.
QR is the standard method for least-squares problems: the normal equations ATAx^=ATb simplify to the triangular system Rx^=QTb, avoiding the condition-number-squaring that comes from forming ATA directly.
The QR algorithm for eigenvalues — an iterative scheme that repeatedly factors and recombines — converges to the eigenvalues of a general matrix without computing the characteristic polynomial. It is the dominant eigenvalue algorithm in numerical software.
Cholesky Decomposition
The Cholesky decomposition factors a symmetric positive definite matrix as A=LLT, where L is lower triangular with positive diagonal entries. It exists if and only if A is symmetric positive definite — all eigenvalues strictly positive and A=AT.
Cholesky exploits symmetry to achieve half the cost of LU: 31n3 versus 32n3. Only the lower triangle of A is read, and only L is computed — the upper factor LT is just the transpose.
Cholesky requires no pivoting. Positive definiteness guarantees that every diagonal entry encountered during the algorithm is strictly positive, so no zero pivots can occur. If the algorithm breaks down (a non-positive value under the square root), the matrix is not positive definite — the decomposition doubles as a definiteness test.
Spectral Decomposition
The spectral decomposition factors a real symmetric matrix as A=QDQT, where Q is orthogonal and D is diagonal. This is the diagonalization of a symmetric matrix, with the additional guarantee that the diagonalizing matrix Q is orthogonal — not merely invertible.
In outer product form, A=λ1q1q1T+λ2q2q2T+⋯+λnqnqnT. Each term is the eigenvalue times the projection matrix onto the corresponding eigenvector direction. The matrix is decomposed into a sum of independent rank-one projections, weighted by eigenvalues.
The spectral decomposition is the foundation of quadratic form analysis, principal component analysis, and the classification of symmetric matrices as positive definite, positive semi-definite, or indefinite.
Singular Value Decomposition
The singular value decomposition factors any m×n matrix as A=UΣVT, where U and V are orthogonal and Σ is diagonal with non-negative entries (the singular values). It exists for every matrix of every shape and every rank.
The SVD is the most informative factorization in linear algebra. The number of nonzero singular values equals the rank. The columns of U and V provide orthonormal bases for all four fundamental subspaces. The pseudoinverse is A+=VΣ+UT. The best rank-k approximation to A is obtained by truncating the SVD at k terms. The condition number is σ1/σr.
Geometrically, every linear transformation is a rotation (VT), followed by a coordinate-axis scaling (Σ), followed by another rotation (U). The SVD makes this decomposition explicit.
Choosing the Right Decomposition
The choice of decomposition depends on the matrix structure and the question being asked.
For a square invertible system with one or many right-hand sides, LU is the standard choice — factor once, solve cheaply. For a symmetric positive definite system, Cholesky is faster and more stable. For a least-squares problem or an overdetermined system, QR avoids condition-number issues. For eigenvalues of a symmetric matrix, the spectral decomposition gives real eigenvalues and orthogonal eigenvectors. For rank determination, the pseudoinverse, low-rank approximation, or any problem where the matrix may be rectangular or rank-deficient, the SVD is the universal tool.
More specialized decompositions exist for more specialized structures. Banded matrices have banded LU factors. Sparse matrices benefit from fill-reducing permutations. Iterative methods (Krylov subspace methods) avoid explicit factorization entirely for very large systems. But the five decompositions on this page cover the vast majority of problems encountered in a standard linear algebra course and in applied work.
Relationships Between Decompositions
The five decompositions are not independent — each can be viewed as a refinement or generalization of another.
LU is Gaussian elimination recorded as a matrix product. QR is Gram-Schmidt recorded as a matrix product. Cholesky is the symmetric-positive-definite specialization of LU: when A=AT with positive eigenvalues, the factorization A=LDLT compresses into A=LLT by absorbing D into L.
The spectral decomposition is eigendecomposition restricted to symmetric matrices, where the eigenvector matrix is guaranteed to be orthogonal. The SVD generalizes the spectral decomposition to non-symmetric and non-square matrices: for a symmetric positive semi-definite matrix, the SVD and spectral decomposition coincide.
Each decomposition occupies a specific niche — defined by the matrix structure it requires and the information it provides — but they are all connected through the common themes of triangularity, orthogonality, and diagonality.