Orthogonality & Matrix Decompositions

Factorising matrices is how computers solve linear algebra. Learn inner products and orthogonality, projections and least squares, Gram–Schmidt and QR, LU and Cholesky factorisations, the singular value decomposition (SVD), low-rank approximation, pseudo-inverse and condition number.

Behind every call to a linear-algebra library is a decomposition: LU for general systems, Cholesky for symmetric positive-definite FEM matrices, QR for least squares, SVD for rank, noise reduction and image compression.

An analogy

A decomposition is like disassembling a complex machine into simple standard parts (triangular, orthogonal, diagonal) that are easy to work with individually.

Orthogonality

Orthogonal vectors have zero inner product; orthonormal bases make coordinates trivial (dot products). Gram–Schmidt turns any basis into an orthonormal one.

Least squares

Overdetermined systems (more equations than unknowns — noisy measurements) have no exact solution; the least-squares solution projects b onto the column space. QR is more stable than forming AᵀA.

LU and Cholesky

LU (with pivoting) solves general systems in O(n³/3) once, then O(n²) per right-hand side. Cholesky is twice as fast for symmetric positive-definite matrices (stiffness, covariance).

SVD

Every matrix factors as UΣVᵀ. Singular values reveal rank, conditioning and the most important directions; truncating small ones compresses images, denoises data, and gives the pseudo-inverse for rank-deficient problems.

Formulas

• Projection onto u: proj_u v = (⟨v, u⟩/⟨u, u⟩) u
• Least squares: min ‖Ax − b‖ ⇒ AᵀA x = Aᵀb (or QR: Rx = Qᵀb)
• Factorisations: PA = LU; A = LLᵀ (Cholesky, SPD); A = QR; A = UΣVᵀ
• Condition number: κ₂(A) = σ_max/σ_min
• Best rank-k approximation: A_k = Σ_{i≤k} σᵢ uᵢ vᵢᵀ (Eckart–Young)

Worked example: Least-squares line

Given: Points (0, 1), (1, 3), (2, 4), (3, 4)

Find: y = a + bx.

• AᵀA = [[4, 6], [6, 14]], Aᵀy = [12, 23]
• Solve → a = 1.5, b = 1.0

Answer: y = 1.5 + x

Worked example: Gram–Schmidt

Given: v₁ = (1, 1, 0), v₂ = (1, 0, 1)

Find: Orthogonal u₂.

• u₂ = v₂ − (v₂·v₁/v₁·v₁)v₁ = (1, 0, 1) − ½(1, 1, 0)

Answer: u₂ = (0.5, −0.5, 1) (u₂·v₁ = 0 ✓)

Common mistakes

• Wrong: Solving least squares via AᵀA for ill-conditioned A. — Right: Use QR or SVD (κ(AᵀA) = κ(A)²).
• Wrong: Cholesky on non-SPD matrices. — Right: Check symmetry and positive definiteness.

Applications

• Curve fitting & calibration: Least squares with QR.
• FEM solvers: Cholesky for SPD stiffness matrices.
• Data compression: SVD for images and signals.

Key takeaways

• Orthogonal bases simplify everything.
• Least squares: project onto column space (QR).
• LU, Cholesky, QR, SVD for different jobs.
• κ = σ_max/σ_min measures reliability.

Going further

• Randomised SVD: Fast low-rank approximations.
• Tikhonov regularisation: Stabilising ill-posed problems.
• Sparse direct solvers: Fill-reducing orderings.