The Matrix Condition Number and LU Decomposition

Inventing Modern Numerical Linear Algebra to Measure Round-Off Error

Designing aircraft wings, artillery trajectories, or structural trusses in the late 1940s required solving systems of $n$ linear algebraic equations in $n$ unknowns, written in matrix form as $Ax = b$. Since the time of Carl Friedrich Gauss in the early nineteenth century, human computers had solved small linear systems of five or ten variables by Gaussian elimination. The clerk subtracted multiples of the first row from lower rows to eliminate one variable at a time until the matrix became triangular. Executing Gaussian elimination on an $n \times n$ matrix requires roughly $\frac{1}{3}n^3$ multiplications and additions.

As soon as electronic computers promised to solve systems of $n = 50$ or $n = 100$ equations—requiring hundreds of thousands of sequential arithmetic steps—mathematicians raised an alarm over cumulative round-off error. Because a digital computer stores each real number in a fixed register of $t$ binary digits, such as thirty-two or forty bits, every multiplication rounds off the tail of the fraction. In 1943, statistician Harold Hotelling calculated a worst-case bound suggesting that rounding errors in elimination could amplify by a factor of $4^{n-1}$. That rate would wipe out forty bits of precision by $n = 21$. Even when John von Neumann and Herman Goldstine published a landmark 1947 analysis at the Institute for Advanced Study, they remained pessimistic about applying standard unsymmetric Gaussian elimination to large matrices.

Working at the National Physical Laboratory in Teddington in 1947 alongside numerical analyst James Hardy Wilkinson, Alan Turing suspected that the catastrophic $4^{n-1}$ error growth was an artifact of overly pessimistic worst-case assumptions. In his 1948 paper Rounding-Off Errors in Matrix Processes, published in the Quarterly Journal of Mechanics and Applied Mathematics, Turing laid the mathematical foundations of modern numerical linear algebra.

First, Turing proved that every variant of Gaussian elimination is simply a disguised way of factoring the original matrix $A$. Specifically, it decomposes $A$ into the product of a unit lower-triangular matrix $L$ (with ones on the diagonal) and an upper-triangular matrix $U$. To prevent a tiny number on the diagonal from dividing a row and blowing up rounding errors, Turing formalized partial pivoting. At each column step, the computer searches down the column for the entry of largest absolute magnitude. It then swaps rows via a permutation matrix $P$ before eliminating, yielding the canonical factorization $PA = LU$. With partial pivoting enforced, every multiplier in $L$ has magnitude at most unity, choking off exponential error amplification.

Second, Turing recognized that analysts were confusing two completely different sources of numerical inaccuracy: instability in the elimination algorithm versus intrinsic sensitivity in the matrix $A$ itself. Suppose the right-hand side vector $b$ is perturbed by a tiny measurement error $\delta b$. That input nudge causes the true mathematical solution $x = A^{-1}b$ to shift by $\delta x = A^{-1}\delta b$ even under infinitely precise arithmetic. Taking matrix norms $\|A\|$ and vector norms $\|x\|$, Turing showed that the relative amplification of input errors is governed by a single dimensionless invariant. He defined the matrix condition number $\kappa(A)$ (introduced in his paper via his $M$-condition number $M(A) = n \max_{i,j}|a_{ij}| \max_{i,j}|(A^{-1})_{ij}|$ and root-mean-square $N$-condition number $N(A)$):

When $\kappa(A) \approx 1$, the matrix is well-conditioned and small perturbations produce small changes in $x$. When $\kappa(A) = 10^{10}$, the matrix is nearly singular (ill-conditioned). Any representation of $A$ rounded to ten decimal digits already loses almost all accuracy before the algorithm performs a single subtraction. By proving that statistical round-off errors in pivoted Gaussian elimination grow mildly while the condition number $\kappa(A)$ dictates precision loss, Turing exonerated direct matrix elimination. Every modern scientific computing library that solves linear equations—from LAPACK and MATLAB to tensor accelerators—executes Turing's 1948 pivoted LU factorization and monitors his condition number to separate matrix ill-conditioning from hardware rounding noise.