Decompositions
| Name | Form | Applies to | Used for |
|---|---|---|---|
| LU | A = L · U (or P · L · U) | Square, usually invertible | Solving Ax = b; determinant |
| Cholesky | A = L · Lᵀ | Symmetric positive-definite | Fast Ax = b for SPD |
| QR | A = Q · R | Any (even rectangular) | Least squares, numerical stability |
| Eigendecomp | A = P · D · P⁻¹ | Diagonalizable square | PCA (via covariance), dynamics |
| SVD | A = U · Σ · Vᵀ | Any matrix | PCA, pseudo-inverse, low-rank approx |
| Schur | A = Q · T · Qᵀ (T triangular) | Square | Stable eigenvalue computation |
| Hessenberg | A = Q · H · Qᵀ | Square | First step of QR eigenvalue algorithm |
| Jordan | A = 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.