What is a matrix decomposition?

A matrix decomposition expresses a matrix as a product of simpler matrices — typically triangular, diagonal, or orthogonal — whose structure makes solving systems, computing eigenvalues, and approximating data dramatically cheaper. The factors reproduce the original matrix exactly.

What are the main matrix decompositions?

The five core decompositions are LU (triangular factors from Gaussian elimination), QR (orthogonal times triangular from Gram-Schmidt), Cholesky (symmetric positive definite square root), spectral (orthogonal eigendecomposition for symmetric matrices), and SVD (universal factorization for any matrix).

Which matrix decomposition should I use?

Use LU for general square systems, Cholesky for symmetric positive definite systems (twice as fast), QR for least squares and overdetermined systems, spectral decomposition for symmetric eigenvalue problems, and SVD for rank determination, pseudoinverse, low-rank approximation, or any rectangular or rank-deficient matrix.

Why are matrix decompositions important?

Decompositions convert hard problems into sequences of easy ones. They enable efficient system solving, numerically stable least squares, eigenvalue computation without characteristic polynomials, dimensionality reduction, and low-rank approximation. They are the computational backbone of applied linear algebra.

Decompositions

Q: How are the decompositions related to each other?

Cholesky is the symmetric positive definite specialization of LU. QR is Gram-Schmidt in matrix form. The spectral decomposition is eigendecomposition restricted to symmetric matrices with orthogonal eigenvectors. The SVD generalizes the spectral decomposition to all matrices regardless of shape or symmetry.

What a Decomposition Is

Why Decompositions Matter

LU Decomposition

QR Decomposition

Cholesky Decomposition

Spectral Decomposition

Singular Value Decomposition

Choosing the Right Decomposition

Relationships Between Decompositions

Summary: The Five Decompositions Side by Side

Factoring Matrices into Simpler Pieces

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 matrix

A

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

A\mathbf{x} = \mathbf{b}

reduces to two triangular substitutions — forward (

L\mathbf{y} = \mathbf{b}

) then backward (

U\mathbf{x} = \mathbf{y}

) — each costing

O(n^2)

. The factorization itself costs

\frac{2}{3}n^3

, but each additional right-hand side costs only

O(n^2)

. 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 \times 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

A^TA\hat{\mathbf{x}} = A^T\mathbf{b}

simplify to the triangular system

R\hat{\mathbf{x}} = Q^T\mathbf{b}

, avoiding the condition-number-squaring that comes from forming

A^TA

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 = LL^T

, 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 = A^T

.

Cholesky exploits symmetry to achieve half the cost of LU:

\frac{1}{3}n^3

versus

\frac{2}{3}n^3

. Only the lower triangle of

A

is read, and only

L

is computed — the upper factor

L^T

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 = QDQ^T

, 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 = \lambda_1 \mathbf{q}_1\mathbf{q}_1^T + \lambda_2 \mathbf{q}_2\mathbf{q}_2^T + \cdots + \lambda_n \mathbf{q}_n\mathbf{q}_n^T

. 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 \times n

matrix as

A = U\Sigma V^T

, where

U

and

V

are orthogonal and

\Sigma

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\Sigma^+ U^T

. The best rank-

k

approximation to

A

is obtained by truncating the SVD at

k

terms. The condition number is

\sigma_1/\sigma_r

.

Geometrically, every linear transformation is a rotation (

V^T

), followed by a coordinate-axis scaling (

\Sigma

), 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.

The decision compresses into a single lookup keyed on the type of problem at hand.

Problem / Matrix context	Best decomposition	Why
General square system, one or many right-hand sides	LU (with pivoting if needed)	factor once, then cheap forward/back substitution per right-hand side
Symmetric positive definite system	Cholesky	half the cost of LU, no pivoting required, doubles as a definiteness test
Least squares / overdetermined system	QR	avoids the condition-number squaring of the normal equations
Symmetric eigenvalue problem	Spectral	guarantees real eigenvalues and an orthogonal eigenvector basis
Rectangular, rank-deficient, or unknown structure	SVD	universal — exists for every matrix; reveals rank, pseudoinverse, low-rank approximation, and condition number

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 = A^T

with positive eigenvalues, the factorization

A = LDL^T

compresses into

A = LL^T

by absorbing

\sqrt{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.

Summary: The Five Decompositions Side by Side

The five decompositions covered above admit a single side-by-side comparison along four structural attributes: the algebraic form, the kind of matrix each one accepts, the structure of the factors it produces, and the primary application it enables. The table below collects this comparison as one reference card — useful both for orienting a new problem to the right factorization and for seeing how the family of decompositions is organized as a whole.

Decomposition	Form	Matrix requirement	Factor structure	Key application
LU	A = LU (or PA = LU)	square; pivoting handles general invertible	L lower triangular, U upper triangular	solving linear systems, especially with multiple right-hand sides
QR	A = QR	any m × n with linearly independent columns	Q with orthonormal columns, R upper triangular	least squares; iterative algorithm for eigenvalues
Cholesky	A = LL^T	symmetric positive definite	L lower triangular with positive diagonal	SPD systems at half LU cost; positive-definiteness test
Spectral	A = QDQ^T	real symmetric	Q orthogonal (eigenvectors), D diagonal of eigenvalues	symmetric eigenproblems, quadratic forms, PCA
SVD	A = UΣV^T	any m × n — no restriction	U, V orthogonal; Σ diagonal of non-negative singular values	rank, pseudoinverse, low-rank approximation, condition number