Matrix factorizations expose geometry: triangular factors encode elimination, orthogonal factors preserve lengths, and singular values reveal rank and conditioning.
QR factorization
Definition. A QR factorization writes \(A=QR\), where \(Q\) has orthonormal columns and \(R\) is upper triangular. Householder reflections and Givens rotations compute QR while preserving Euclidean norms.
Cholesky factorization
Proposition. If \(A\) is symmetric positive definite, then \(A=LL^\top\) with \(L\) lower triangular and positive diagonal. Cholesky is efficient and stable for positive definite systems, but it is not a remedy for indefiniteness.
Singular value decomposition
Theorem. Every real matrix has an SVD \(A=U\Sigma V^\top\), with orthogonal \(U,V\) and nonnegative singular values on the diagonal of \(\Sigma\). Singular values determine operator norm, rank, numerical rank, and least-squares sensitivity.
Rank-revealing factorizations
Definition. A rank-revealing factorization separates numerically large directions from small ones. The goal is not exact algebraic rank, which is unstable under perturbation, but a scale-dependent effective rank.
Orthogonality as stability
Remark. Algorithms built from orthogonal transformations are favored because they do not magnify Euclidean errors. This is why QR and SVD are preferred over normal equations in ill-conditioned least-squares problems.
QR factorization
For \(A\in\mathbb R^{m\times n}\), \(m\ge n\), a reduced QR factorization is \[ A=QR,\qquad Q^\top Q=I_n, \] with \(R\) upper triangular. Householder reflectors \[ H=I-2vv^\top/(v^\top v) \] zero a column tail while preserving Euclidean norms.
Proposition. If \(A\) has full column rank, the reduced QR factorization with positive diagonal entries of \(R\) is unique.
Proof. If \(Q_1R_1=Q_2R_2\), then \[ Q_2^\top Q_1=R_2R_1^{-1}. \] The left side is orthogonal and the right side upper triangular. An upper triangular orthogonal matrix is diagonal with entries \(\pm1\); positivity of both \(R\) diagonals forces the identity.
Householder QR is backward stable. Modified Gram--Schmidt is usually acceptable but loses orthogonality proportional to \(\kappa(A)u\); classical Gram--Schmidt can lose it proportional to \(\kappa(A)^2u\) unless reorthogonalized.
Singular value decomposition
Theorem (SVD). Every \(A\in\mathbb R^{m\times n}\) has \[ A=U\Sigma V^\top, \] where \(U,V\) are orthogonal and \(\sigma_1\ge\cdots\ge\sigma_r>0\) are singular values. Moreover, \[ \|A\|_2=\sigma_1,\qquad \|A^\dagger\|_2=\sigma_r^{-1}. \]
The SVD exposes rank, null spaces, conditioning, and least-squares geometry. It is more expensive than QR but is the reliable choice near rank deficiency.
Optimal low-rank approximation
Theorem (Eckart--Young--Mirsky). Let \[ A_k=\sum_{j=1}^k\sigma_ju_jv_j^\top. \] Then among matrices of rank at most \(k\), \[ \min_{\operatorname{rank}B\le k}\|A-B\|_2=\sigma_{k+1}, \] \[ \min_{\operatorname{rank}B\le k}\|A-B\|_{\mathrm F} =\left(\sum_{j>k}\sigma_j^2\right)^{1/2}. \]
Proof. \(A_k\) attains the displayed errors by orthogonality. For any rank-\(k\) \(B\), its null space intersects \(\operatorname{span}(v_1,\ldots,v_{k+1})\) nontrivially; for a unit vector \(x\) in that intersection, \[ \|(A-B)x\|=\|Ax\|\ge\sigma_{k+1}. \] The Frobenius claim follows from unitary invariance and the corresponding singular-value inequality.
Rank-revealing factorizations
Column-pivoted QR, \[ AP=QR, \] orders columns to expose numerical rank. Strong rank-revealing QR controls blocks of \(R\) relative to singular values. Randomized range finding computes \(Y=A\Omega\), orthonormalizes it, and factors \(Q^\top A\); oversampling and power iterations improve accuracy when singular values decay slowly.