Why factor at all
Triangular systems are easy. The last equation has one unknown, so you solve it and substitute upwards. One pass, no searching.
General systems are not. Elimination is O(n³), and doing it again for every new right-hand side is wasteful when the matrix has not changed.
So: factor once, at O(n³), then every solve after that is two triangular substitutions at O(n²). With a hundred right-hand sides that is a very large saving, and it is exactly why numerical libraries factor rather than invert.
Each factorisation also exposes something. LU is elimination written down. QR produces an orthonormal basis. Cholesky proves positive definiteness on the way past.
LU and pivoting
LU is Gaussian elimination with the working kept. U is what elimination leaves behind; L holds the multipliers used to get there.
It is exact on this page, because elimination needs only addition, subtraction, multiplication and division — no square roots. A matrix of whole numbers has an LU with rational entries and nothing is rounded.
Not every matrix has one without pivoting. A zero in a pivot position stops the process, and the fix is to swap rows — which is why the general result is written PA = LU, with P recording the swaps.
In floating point, pivoting is done even when it is not strictly necessary: swapping the largest available entry into the pivot position keeps the multipliers small and the errors under control. On exact arithmetic that motivation disappears, and swaps are made only when a pivot is genuinely zero.
QR and the Gram-Schmidt trap
QR writes A as Q times R, where Q has orthonormal columns — each of length one, and each perpendicular to the others — and R is upper triangular.
Q being orthonormal is what makes it valuable: its inverse is simply its transpose, and multiplying by it neither stretches nor distorts, so it cannot amplify error.
The textbook construction is Gram-Schmidt: take each column, subtract off its projections onto the earlier ones, normalise. There are two versions of that, identical on paper.
Classical subtracts every projection from the original vector. Modified subtracts each projection from the running remainder. Algebraically the same; numerically not close. On nearly-dependent columns the classical version loses orthogonality badly, and Q comes back visibly not orthogonal.
This page uses the modified version and reports how far QᵀQ actually falls from the identity, so the quality of the result is visible rather than assumed.
QR is what least-squares solvers use. Forming the normal equations instead squares the condition number, which can throw away half the available precision on an awkward problem.
Cholesky, and what its failure tells you
For a symmetric positive-definite matrix, Cholesky writes A as L times its own transpose — one triangle, used twice.
Because the symmetry means only one triangle has to be computed, it is about half the work of a general LU. When it applies, it is the method to use.
The interesting part is what happens when it does not apply. The algorithm reaches a square root of a non-positive number and stops — and that failure is the definition. A symmetric matrix is positive definite exactly when Cholesky completes.
So attempting a Cholesky is the standard test for positive definiteness, and it is far cheaper than computing eigenvalues and checking their signs. A failure is a result rather than an error, which is why this page reports it as one.
It also has a neat guarantee behind it: AᵀA is positive definite for every A with independent columns, which is why Cholesky is what least-squares and simulation code reach for.
Which one to use
LU for solving square systems, especially with several right-hand sides. The general workhorse.
QR for least squares, for orthonormal bases, and whenever numerical stability matters more than speed. Also the basis of the standard eigenvalue algorithm.
Cholesky whenever the matrix is symmetric and positive definite — covariance matrices, stiffness matrices, normal equations. Half the work, and it proves the property while it runs.
SVD when nothing else applies: it exists for every matrix, square or not, and handles rank deficiency gracefully. It is the most expensive and the most informative, and it is beyond what this page shows.
Sources and methodology
The factorisations and their numerical behaviour are standard; these are the references.
Method. LU runs on exact rationals and stays exact, so multiplying the factors back reconstructs the original with nothing to round. QR and Cholesky take square roots and are therefore decimal, and the page marks them as such rather than presenting all three alike. The QR uses modified Gram-Schmidt rather than the classical version: the two are identical on paper, but the classical one subtracts every projection from the original vector and accumulates error, losing orthogonality badly on nearly-dependent columns. The page reports how far QᵀQ actually falls from the identity. That engine is verified on every change against 104 hand-written assertions, including that L times U reconstructs the row-permuted original exactly across three hundred generated matrices, and that Cholesky succeeds on AᵀA for every invertible A — which it must, since that product is always positive definite. The count and the per-case breakdown are published on the formula verification page.
Read the guide
Factoring once and substituting is why numerical libraries advise against inverting a matrix — the Matrix Inverse Calculator sets out that argument.