Cholesky decomposition

When a matrix is symmetric positive definite, it has a special square-root-like factorization that is the workhorse of statistics, optimization, and physics. Cholesky writes A = L L^T, where L is lower triangular with positive diagonal entries. You can read it as: A is its own factor times that factor's mirror image.

Why it exists exactly when A is positive definite is the elegant part. Run symmetric Gaussian elimination; positive definiteness guarantees every pivot is strictly positive, so you can take the square root of each pivot and split it evenly between L and L^T. Conversely, if A = L L^T with L invertible, then for any nonzero x, x^T A x = ||L^T x||^2 > 0, so A must be positive definite. Existence and positive definiteness are the same statement.

Practically it costs about (1/3) n^3 flops, roughly half of LU, because symmetry lets you compute and store only the lower triangle and skip pivoting entirely. It is the standard solver for normal equations in least squares, for covariance matrices when sampling Gaussians, and for Newton steps in optimization.

It doubles as a cheap definiteness test. Attempt the factorization: if you ever hit a nonpositive pivot, the matrix is not positive definite and you stop. This is far more reliable than computing eigenvalues just to check signs.