A matrix that deserves a shortcut
By now you can solve A x = b for any square matrix by computing an LU factorization and running two triangular solves. That method is general — it asks nothing of A beyond invertibility — and generality has a price. This guide is about cashing in when A is special. The special structure is symmetric positive-definite (SPD): the matrix equals its own transpose, A = A^T, and for every nonzero vector x the number x^T A x is strictly positive. Such matrices are everywhere — they fall out of least-squares normal equations, of physical energy, of covariance, of stiffness in a beam — and they reward you handsomely for noticing them.
Two warnings up front, because both halves of SPD matter. Symmetry alone is not enough: the matrix with diagonal entries 1, 1 and off-diagonals 2 is symmetric but has x^T A x going negative for x = (1, -1), so it is not positive-definite. And positive-definiteness without symmetry is a different, murkier story that Cholesky does not cover. The condition that makes everything work is the two of them together. The cleanest mental picture of positive-definiteness: the bowl-shaped surface z = x^T A x curves strictly upward in every direction away from the origin, with a single lowest point — there are no flat valleys and no saddles.
Here is the promise that the rest of the guide delivers on. For an SPD matrix you can factor A into a single triangular matrix and its transpose, A = L L^T, instead of into two separate factors L and U. That symmetry of the factorization is not a coincidence; it is the matrix's own symmetry showing through. And because it halves the bookkeeping, it halves the cost.
Cholesky: LU folded in half
The Cholesky factorization writes an SPD matrix as A = L L^T, where L is lower-triangular with strictly positive entries on its diagonal. Compare that to the general A = L U from before: there the lower factor L held the elimination multipliers and the upper factor U held what was left after elimination. For an SPD matrix those two factors are no longer independent — U turns out to be exactly L^T (up to a diagonal scaling). So instead of storing and computing both L and U, you compute one triangular factor and get the other for free by transposing. You are doing the same elimination you already know, but recording only half of it.
general matrix : A = L U (two factors, L and U)
SPD matrix : A = L L^T (one factor, reused transposed)
2x2 worked example, A = [ 4 2 ]
[ 2 5 ]
L_11 = sqrt(4) = 2
L_21 = 2 / L_11 = 1
L_22 = sqrt(5 - 1^2) = sqrt(4) = 2
so L = [ 2 0 ] and L L^T = [ 4 2 ] = A (check)
[ 1 2 ] [ 2 5 ]Look at what the worked example is really doing. The diagonal entry L_11 is a square root, and the next diagonal entry L_22 is the square root of '5 minus what we already used'. That subtraction is the elimination step in disguise: it is the Schur complement, the same updating of the remaining submatrix you do in Gaussian elimination. Positive-definiteness is exactly the guarantee that every quantity under a square root stays strictly positive, so the algorithm never asks for the square root of a negative number and never divides by zero. That is the deep reason the method is safe.
No pivoting needed — and why that is remarkable
The previous guide hammered home that general Gaussian elimination needs partial pivoting: without it, a tiny or zero pivot can appear and the growth factor can explode, wrecking accuracy. Cholesky needs none of that. You can run it straight down the diagonal, no row swaps, no searching for the largest pivot, and it is still provably backward stable. This is genuinely surprising — pivoting felt mandatory just one guide ago — and it is worth understanding why SPD matrices get the exemption.
The reason is that positive-definiteness controls the size of every entry that ever appears during the factorization. There is a clean bound: each entry of L is no larger in magnitude than the square root of the corresponding diagonal entry of A, so nothing can grow out of control the way it can for a general matrix. The pivots — those square-rooted diagonal quantities — are bounded below by structure, not by luck. So the danger that pivoting exists to defuse simply cannot arise here. You skip pivoting not because you are being reckless, but because the matrix has already done the safety work for you.
The algorithm, and the cost you actually save
Here is the whole method for solving an SPD system A x = b, walked through end to end. Notice that once you have L, solving is just the two triangular solves you already mastered — forward substitution with L, then back substitution with L^T — so all the new work lives in the factorization step.
- Factor: compute L so that A = L L^T. For each column, take a square root for the diagonal entry and divide to fill the column below it, subtracting the contributions already accounted for (the Schur-complement update).
- Forward solve: solve L y = b for y by forward substitution — top to bottom, each unknown ready as soon as you reach it.
- Back solve: solve L^T x = y for x by back substitution — bottom to top — and x is your answer.
- Reuse: to solve A x = b for a new right-hand side b, keep the same L and rerun only steps 2 and 3 — the factor-once-solve-many trick, unchanged from LU.
Now the headline payoff in flop count. LU factorization of an n-by-n matrix costs about (2/3) n^3 floating-point operations. Cholesky costs about (1/3) n^3 — almost exactly half — because the symmetry lets you touch only the lower triangle and reuse it for the upper. It also needs only about half the storage, since you keep one triangle instead of two full factors. The triangular solves remain cheap at O(n^2) each, so for any n large enough to matter, the factorization dominates and Cholesky is the clear winner whenever it applies. The factor-once-solve-many economics carry over unchanged: pay the cubic cost once, then each new right-hand side is only quadratic.
Cholesky as a positive-definiteness test, and an honest caveat
Cholesky has a bonus career as the most practical test for whether a symmetric matrix is positive-definite. Just attempt the factorization. If every diagonal quantity stays strictly positive all the way through, the matrix is SPD and you walk away with L for free. If at some step the quantity under the square root drops to zero or goes negative, the matrix is NOT positive-definite, and you have found out cheaply, at the same O(n^3) cost as factoring. Checking eigenvalues directly would be more expensive and less reliable in finite precision — attempting Cholesky is the standard, recommended test.
Now the honest caveat, because square roots make some readers nervous and a near-singular SPD matrix lives right on the edge. The remedy is the close cousin LDL^T factorization, which writes A = L D L^T with L unit-lower-triangular and D diagonal. It computes the same information without ever taking a square root, sidestepping the cost and the round-off of the root and handling certain near-borderline cases more gracefully. It is the natural fallback when you want Cholesky's symmetry savings but the plain square-root form makes you uneasy.
What to carry forward
The lesson generalizes far beyond this one factorization: structure is money. The moment you recognize that a matrix is symmetric positive-definite, you trade general LU for Cholesky, halve the work and the storage, drop pivoting entirely, and gain a free positive-definiteness test — all because the matrix told you something true about itself. Numerical computing rewards the habit of asking 'what do I actually know about this matrix?' before reaching for the general-purpose hammer.
The final guide of this rung pulls these threads together. It revisits the cubic cost in earnest, shows what changes when the matrix is sparse or banded — where Cholesky's pivot-free freedom becomes a superpower for controlling fill-in — and explains the most-broken rule in applied linear algebra: that you almost never form a matrix inverse to solve A x = b. Cholesky will be the running example, because a sparse SPD system is the single most common large problem you will be handed.