Numbers & Math

Matrix Decomposition Methods

LU, QR, SVD, eigendecomposition, Cholesky — what each does and when to use it.

Decompositions

NameFormApplies toUsed for
LUA = L · U (or P · L · U)Square, usually invertibleSolving Ax = b; determinant
CholeskyA = L · LᵀSymmetric positive-definiteFast Ax = b for SPD
QRA = Q · RAny (even rectangular)Least squares, numerical stability
EigendecompA = P · D · P⁻¹Diagonalizable squarePCA (via covariance), dynamics
SVDA = U · Σ · VᵀAny matrixPCA, pseudo-inverse, low-rank approx
SchurA = Q · T · Qᵀ (T triangular)SquareStable eigenvalue computation
HessenbergA = Q · H · QᵀSquareFirst step of QR eigenvalue algorithm
JordanA = P · J · P⁻¹Any square (defective okay)Theoretical; numerically unstable

Picking one

  • Solve Ax = b once: LU.
  • Solve Ax = b many times: factor once, forward/back-substitute per b.
  • Symmetric positive-definite (covariance, Gram matrices): Cholesky — ~2× faster than LU.
  • Least squares: QR (normal equations are less numerically stable).
  • Rank, null space, low-rank approx: SVD.
  • PCA: SVD of centered data, or eigendecomposition of covariance.

Worked examples

LU on a 2×2. For A = [[4, 3], [6, 3]], the multiplier is 6 / 4 = 1.5. Subtract 1.5 times row 1 from row 2: 3 − 1.5 × 3 = −1.5. So L = [[1, 0], [1.5, 1]] and U = [[4, 3], [0, −1.5]]. Multiplying back gives [[4, 3], [6, 4.5 − 1.5 = 3]], which equals A. The determinant is the product of the diagonal of U: 4 × (−1.5) = −6, matching 4×3 − 3×6.

To solve Ax = b with b = (10, 12), solve Ly = b first: y1 = 10, y2 = 12 − 1.5 × 10 = −3. Then Ux = y: x2 = −3 / −1.5 = 2 and x1 = (10 − 3 × 2) / 4 = 1. Check: 4 + 6 = 10 and 6 + 6 = 12. For a new b only the two cheap substitution steps repeat.

Cholesky. The symmetric positive-definite A = [[4, 2], [2, 3]] factors as L = [[2, 0], [1, √2]]: L11 = √4 = 2, L21 = 2 / 2 = 1, L22 = √(3 − 1²) = 1.414. Check: LLᵗ = [[4, 2], [2, 1 + 2 = 3]]. Cholesky needs about n³/3 operations versus about 2n³/3 for LU.

Common mistakes

  • Inverting to solve. Computing A⁻¹ and multiplying is slower and less accurate than factoring and substituting.
  • Skipping pivoting. LU without row swaps fails on a zero pivot and loses accuracy on small ones; libraries use partial pivoting (P·L·U).
  • Normal equations for least squares. Forming AᵗA squares the condition number; QR or SVD avoids this.
  • Applying Cholesky to a non-positive-definite matrix. It fails; a failed attempt is itself a quick test for positive definiteness.
Was this article helpful?