Just as composite numbers can be factored into prime numbers (e.g., 12 = 2 × 2 × 3) to reveal their fundamental properties, matrices can be decomposed into products of simpler, structured matrices (triangular, diagonal, or orthogonal).
⚡ Computational Speedup
Solving Ax = b directly takes O(n³) arithmetic operations. Decomposing A into triangular or orthogonal factors reduces system solving to fast O(n²) forward/backward substitution.
🔍 Structural & Geometric Insights
Decompositions reveal intrinsic properties like matrix rank, determinant, null space, eigenvalues, and principal directions of geometric variance.
LU decomposition factors a square matrix A into the product of a lower triangular matrix L (with 1s on the diagonal) and an upper triangular matrix U.
Key Properties
- Requires square matrix A (n × n).
- Partial Pivoting (PA = LU): Permutation matrix P prevents division by zero and numerical instability by swapping rows.
- Determinant: det(A) = det(L) × det(U) = ∏ uᵢᵢ (product of upper diagonal entries).
Solving Ax = b
- Decompose A = LU (Cost: 2/3 n³ operations).
- Solve Ly = b for y using Forward Substitution (Cost: n²).
- Solve Ux = y for x using Back Substitution (Cost: n²).
Step-by-Step Worked Numerical Example (LU)
Given A =
Step 1: Elimination on Row 2 (multiplier l₂₁ = 4/2 = 2): Row₂ → Row₂ - 2×Row₁
Step 2: Elimination on Row 3 (multiplier l₃₁ = 8/2 = 4): Row₃ → Row₃ - 4×Row₁
Matrix becomes: [ [2, 1, 1], [0, 1, 1], [0, 3, 5] ]
Step 3: Elimination on Row 3 (multiplier l₃₂ = 3/1 = 3): Row₃ → Row₃ - 3×Row₂
Final U = [ [2, 1, 1], [0, 1, 1], [0, 0, 2] ] and L contains the recorded multipliers.
Cholesky decomposition is a specialized, highly efficient variant of LU decomposition for matrices that are both Symmetric (A = Aᵀ) and Positive-Definite (xᵀAx > 0 for all x ≠ 0).
where L is a lower triangular matrix with strictly positive diagonal elements.
• 2x Faster: Requires ~n³/3 flops (half the operations of LU).
• Half Memory: Only stores the lower triangular matrix L.
• Numerically Stable: Does not require pivoting!
🌱 Key Applications in Machine Learning & Science
- Multivariate Normal Sampling: Generate correlated Gaussian vectors x = μ + L z where z ~ N(0, I).
- Gaussian Process Regression: Inverting kernel covariance matrices K.
- Kalman Filtering & Optimization: Solving Newton-Raphson system steps.
QR decomposition factors any real m × n matrix A into an orthogonal matrix Q (QᵀQ = I) and an upper triangular matrix R.
🛠️ Methods of Computation
- Gram-Schmidt Orthogonalization: Conceptually simple, projects vectors sequentially. (Use Modified Gram-Schmidt for numerical precision).
- Householder Reflections: Uses reflection hyperplanes. Preferred method for general dense matrices.
- Givens Rotations: Rotates plane pairs. Excellent for sparse matrices or parallel hardware.
🎯 The Least Squares Solution
To solve overdetermined system Ax ≈ b:
Since QᵀQ = I, this simplifies directly to:
Solved instantly via back substitution without computing unstable matrix AᵀA!
Eigendecomposition decomposes a square matrix A into its eigenvectors and eigenvalues, expressing the linear transformation in its natural coordinate system.
where Q contains eigenvectors as columns, and Λ is a diagonal matrix of eigenvalues λᵢ.
If A is real and symmetric (A = Aᵀ), its eigenvectors are orthogonal (Q⁻¹ = Qᵀ), giving:
Matrix Powers & Differential Equations
Computing matrix powers Aᵏ directly takes O(k n³). With Eigendecomposition:
Since Λ is diagonal, raising Λ to power k requires raising only diagonal entries to power k in O(n) time!
Unlike Eigendecomposition, SVD applies to ANY rectangular matrix (m × n). It factors matrix A into two orthonormal matrices and a diagonal matrix of singular values.
📐 Component Roles
- U (m × m): Left singular vectors (orthonormal eigenvectors of AAᵀ). Represents output space basis.
- Σ (m × n): Singular values σ₁ ≥ σ₂ ≥ ... ≥ 0 (square roots of eigenvalues of AᵀA). Represents scaling factors.
- Vᵀ (n × n): Right singular vectors (orthonormal eigenvectors of AᵀA). Represents input space basis.
🎨 Geometric Interpretation
Any linear transformation can be broken down into 3 simple sequential operations:
- Vᵀ: Rotation/Reflection in domain.
- Σ: Scaling along coordinate axes.
- U: Rotation/Reflection in codomain.
Truncating SVD to the top k singular values gives the best possible rank-k matrix approximation in both Frobenius and Spectral norms:
| Decomposition | Formula | Required Matrix Properties | Time Complexity | Primary Application |
|---|---|---|---|---|
| LU | A = LU (or PA=LU) | Square (n × n), non-singular | O(2/3 n³) | Solving Ax=b, Determinants |
| Cholesky | A = LLᵀ | Symmetric Positive-Definite | O(1/3 n³) | Fast linear systems, Gaussian Sampling |
| QR | A = QR | Any Rectangular (m × n) | O(2mn² - 2/3n³) | Least Squares, QR Eigenvalue Algorithm |
| Eigendecomposition | A = Q Λ Q⁻¹ | Square, non-defective (n independent eigenvectors) | O(n³) | Spectral analysis, Matrix powers, PageRank |
| SVD | A = U Σ Vᵀ | Any Matrix (m × n) | O(mn² + n³) | PCA, Compression, Pseudoinverse, NLP |
Q1: Why is Cholesky decomposition preferred over LU for Symmetric Positive-Definite matrices?
Answer: Cholesky requires only half the arithmetic operations (~n³/3 vs 2n³/3), uses half the memory (storing only L), and is unconditionally numerically stable without needing row pivoting.
Q2: What happens if you run SVD on a real symmetric matrix A?
Answer: The singular values σᵢ will equal the absolute values of the eigenvalues |λᵢ|, and the left and right singular vectors U and V will align with the eigenvectors Q (up to sign flips depending on eigenvalue signs).
Q3: How does QR decomposition solve the Least Squares problem min ||Ax - b||₂?
Answer: Substituting A = QR transforms the normal equations to (QR)ᵀ(QR)x = (QR)ᵀb. Because QᵀQ = I, this simplifies directly to Rx = Qᵀb, which is solved directly via fast back-substitution.
Q4: Can every square matrix be diagonalized via Eigendecomposition?
Answer: No. Only matrices with n linearly independent eigenvectors (non-defective matrices) can be diagonalized. Defective matrices require the Jordan Canonical Form instead. SVD, however, works on all matrices without exception!