Factorizations express complicated matrices as products of simpler ones, exposing structure and enabling efficient computation. The LU decomposition writes a square matrix as \(A = LU\) with \(L\) lower triangular and \(U\) upper triangular, useful for solving linear systems by sequential substitution. It exists without row pivoting precisely when every leading principal minor of \(A\) is nonzero. The Cholesky decomposition strengthens this for symmetric positive-definite matrices, writing \(A = LL^T\) with \(L\) lower triangular having positive diagonal entries.
The singular value decomposition (SVD) applies to every matrix, regardless of shape. Any \(m \times n\) matrix \(A\) can be written \(A = U \Sigma V^T\) with \(U\) and \(V\) orthogonal and \(\Sigma\) a rectangular diagonal matrix whose entries, the singular values, are the square roots of the eigenvalues of \(A^T A\), arranged in non-increasing order. The number of nonzero singular values equals the rank of \(A\). Associated with the SVD is the Moore–Penrose pseudoinverse \(A^+\), defined by the four Penrose conditions; for a full-rank \(A\) it equals \((A^T A)^{-1} A^T\).
These decompositions provide the foundation for least squares. The least-squares solution to \(Ax = b\) is the vector \(x\) that minimizes \(\|Ax - b\|^2\); it satisfies the normal equations \(A^T A x = A^T b\), whose unique solution (when \(A^T A\) is invertible) is \(x = (A^T A)^{-1} A^T b = A^+ b\). Projections also play a key role: a projection matrix \(P\) satisfies \(P^2 = P\), and its image is precisely the subspace onto which it projects. An orthogonal projection matrix additionally satisfies \(P = P^T\), projecting onto its column space along the orthogonal complement.