Numerical Linear Algebra
where the algebra stops being the arithmetic
Two errors, and whose fault they are

The condition number is an amplifier

κ is usually introduced as a definition and then quoted. It is a measurement: perturb the input by a known amount, look at how much the output moves, and the largest ratio you can find is the number.
15 min read 6 figures Whose fault is itMeasured, not assertedTwo routes to a numberPrecision as the knob

The condition number of a matrix is defined as ‖A‖·‖A⁻¹‖, or equivalently as the ratio of its largest singular value to its smallest. Both of those are correct and neither says what it is for.

What it is for: κ is the largest factor by which a relative change in the input can be amplified into a relative change in the output. Change b by one part in a million; the answer x can change by as much as κ parts in a million, and by no more. That is a statement about the map from b to x — about the problem — and it is true whether the solve is done in floating point, in exact rational arithmetic, or by hand on paper.

It can therefore be measured by doing what it describes.

How much a perturbation of the right-hand side is amplified, κ = 10⁶The cumulative distribution of the amplification factor over two hundred random perturbation directions, with the condition number marked as the upper limit.110¹10²10³10⁴10⁵10⁶10⁷00.250.50.751amplification of the input perturbationfraction of directions at or belowκ = 10·10⁵worst found 7.6·10⁵6×6, 200 directionsmedian reaches 0.29 of κ
Fig. 1 Two hundred random perturbation directions, each of a known relative size, applied to the right-hand side of a system and the amplification recorded. The distribution is drawn cumulatively, so the right-hand edge is the worst case found. Drag κ and the whole distribution slides one decade for each decade — its shape does not change.

What the measurement says that the definition does not

Two things, and the second is the useful one.

First, the perturbation route agrees with the singular-value route. That is a check rather than a discovery — the two share no arithmetic, one being a random sampling and the other a Jacobi iteration on the matrix — but it is the check that entitles the site to use κ as an axis. Across four condition numbers and ten seeds each, the constructed κ and the measured κ agree to within a tolerance that is itself bracketed against the noise the construction introduces.

Second, and this is the part a definition cannot supply: random directions get close to the worst case. The worst of two hundred random perturbations reaches about 0.76κ. The median reaches 0.29κ. Even the mildest of the two hundred is amplified by about 0.05κ.

Those numbers hold at κ = 10², 10⁴, 10⁶ and 10⁸ — the ratios are the same at every scale, which is what makes them worth quoting rather than being an accident of one matrix.

Why that matters

Because the usual mental model of the condition number is that it is a pessimistic bound: a worst-case figure describing what could happen in an unlucky case, not what will happen.

For a six-by-six system with logarithmically spread singular values, that model is wrong. A perturbation in a random direction — which is what rounding error looks like — is amplified by nearly a third of the worst case. Ill-conditioning is not a rare misfortune. It is the ordinary behaviour of the matrix, and the worst case is only a factor of three away from the typical one.

The reason is dimensional. A random direction in n dimensions has a component along every right singular vector, including the one belonging to the smallest singular value, and that component is of order 1/√n. So the amplification is of order κ/√n rather than of order 1, and for the sizes of matrices anyone actually inverts by hand, √n is small.

Backward and forward error against the condition numberA log–log plot over twelve decades of condition number. The backward error is a flat line at ten to the minus sixteen; the forward error rises in proportion to the condition number.110²10⁴10⁶10⁸10¹⁰10¹²10¹⁴10⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹condition number κ(A)relative errorforward errorbackward errorpredicted: κ · u8×8, 20 seeds per κ; dashed is the worstthe problem worsens, not the method
Fig. 2 The same fact from the other side, over twenty seeded matrices at each of eight condition numbers. The forward error tracks κ, with the worst of twenty drawn dashed just above the median. If the worst case were rarely approached, the dashed line would sit far above the solid one. It sits close.

κ is not a property of the arithmetic

This is the sentence worth repeating until it is automatic, because almost every misuse of the condition number comes from forgetting it.

The Hilbert matrix has κ(H₁₀) = 1.6·10¹³. That number contains no reference to floating point, to double precision, or to any algorithm. It says: there exist two right-hand sides differing by one part in 10¹³ whose exact solutions differ by a factor of order one. That is a fact about the Hilbert matrix, provable on paper, and it would be true in a universe with no computers.

What floating point adds is a guaranteed perturbation of the input, of size u, because the entries of A and b cannot be stored exactly. So a computation in double precision necessarily faces an input perturbation of about 10⁻¹⁶, and κ·u is what that becomes in the answer. For H₁₀ that is 1.6·10⁻³, and the measured forward error is 2.7·10⁻⁴ — within the bound, as the inequality requires.

The practical consequence: when κ·u exceeds the accuracy required, no algorithm will do. Not a better solver, not a more careful implementation, not a library written by cleverer people. The options are more precision, a different formulation of the problem, or accepting the answer is not determined.

Conditioning of other questions

A matrix does not have one condition number; a problem has one, and the same matrix appearing in two different questions can be easy in one and impossible in the other. This is worth spelling out because “the condition number of A” is used loosely everywhere, including on this site.

Solving Ax = b has condition number κ(A) = σ₁/σₙ, which is what has been discussed so far.

Least squares with A has a condition number that depends on the residual as well as on κ(A) — when the data lies close to the column space it behaves like κ(A), and when it does not there is a term in κ(A)² even for the honest QR route. The valley with no bottom is about the geometry underneath that.

Eigenvalues of A have nothing to do with κ(A) at all. A symmetric matrix with κ = 10¹⁵ still gives up its eigenvalues to full absolute accuracy, and a matrix with κ = 1 can have eigenvalues so sensitive that rounding moves them by a hundredth. Symmetry is worth more than precision is that case, and it is one of the sharpest surprises in the subject.

Matrix multiplication by A has condition number 1 in the norm — multiplying is always stable — which is precisely why the algorithms here are built out of multiplications by orthogonal matrices and never out of inverses.

How far a perturbation of size ε moves an eigenvalue, 8×8A log–log plot of eigenvalue movement against perturbation size. The symmetric case lies on a line of slope one; the non-symmetric case lies on a line of slope one eighth, and at a perturbation of ten to the minus sixteen it has already moved by a hundredth.10⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹10⁻¹⁶10⁻¹³10⁻¹⁰10⁻⁷10⁻⁴10⁻¹size of the perturbation ‖δA‖how far the eigenvalues moveJordan block, ε^(1/8)symmetric, ≤ ‖δA‖rounding error alone moves it to 10⁻²six seeds per symmetric point; Jordan is closed formsymmetry beats precision
Fig. 3 The same matrix, two questions, two answers. For a symmetric matrix an eigenvalue moves by at most the size of the perturbation, whatever the condition number of the matrix is. For an eight-by-eight Jordan block it moves by the eighth root of it. Neither line has anything to do with σ₁/σₙ.

What can be done about it

Three things, in increasing order of how much they help.

Scaling. A matrix whose rows differ wildly in magnitude often has a condition number dominated by that fact rather than by anything intrinsic. Equilibrating the rows and columns can reduce κ by many orders of magnitude and costs nothing. It is the first thing to try and the most frequently skipped.

Reformulating. The basis is part of the problem: fitting a degree-eleven polynomial in the monomial basis gives a design matrix with κ = 1.2·10⁸; the same fit to the same data in a Chebyshev basis gives κ = 2.5. Nothing about the question changed. The matrix is not handed down; it is constructed from a modelling choice, and the choice can be made differently.

Regularising. If the problem genuinely does not determine the answer, adding information does. That is what Tikhonov regularisation, ridge regression and truncated SVD all are: a decision to answer a nearby, better-conditioned question and say so. It is honest when the substitution is declared and dishonest when it is not.

What does not help is precision, except by a fixed number of digits. The order they are added in makes the same point about summation: an algorithmic change buys a rate, and a precision change buys a constant.

Forward error of a 6×6 Hilbert solve at eight precisionsA bar for each significand width from 12 to 53 bits showing the relative error in the computed solution, with the condition number times the unit roundoff marked as a prediction.κ = 1.5·10⁷ · the exact answer is (1, 2, …, 6)12 bits3.316 bits0.8620 bits4.324 bits0.09330 bits7.6·10⁻⁴36 bits6.2·10⁻⁶43 bits2·10⁻⁷53 bits4.5·10⁻¹¹dashed: κ · unit roundoffone matrix, eight arithmeticsmeasured against a known answer
Fig. 4 The constant, bought a bit at a time. The same Hilbert system solved at eight significand widths, with the error measured against the exact answer. Every 3.3 bits buys one decimal digit, and the prediction κ·u is marked. Nothing in this figure is a slope that precision can change.

Where κ comes from, structurally

The singular value decomposition makes it geometric. A = UΣVᵀ maps the unit sphere to an ellipsoid with semi-axes the singular values, so the map stretches by σ₁ in one direction and by σₙ in another. The inverse map does the reverse, and their product — the total distortion between the best- and worst-treated directions — is σ₁/σₙ, which is κ.

That is why κ ≥ 1 always, with equality exactly for orthogonal matrices scaled by a constant. An orthogonal matrix maps the sphere to itself, distorts nothing, and amplifies nothing: κ = 1.

And that is the deep reason orthogonal transformations are the backbone of every stable algorithm in this subject. It is not a preference or a convention. A reflection cannot stop being one is about the structural half of the argument — an orthogonal matrix that has been perturbed by rounding is still very nearly orthogonal — and this is the other half: an orthogonal step cannot amplify an existing error, because its condition number is one.

Compare with what forming AᵀA does. The singular values square, so κ squares, and an error that was being amplified by 10⁶ is now being amplified by 10¹². That is the road that squares the problem, and it is the clearest case on the site of a modelling decision converting a solvable problem into an unsolvable one.

The estimate that is affordable

Computing κ exactly requires the smallest singular value, which costs about as much as the solve itself and rather more code. In production nobody does it. What they do — or should — is estimate it.

The standard trick uses the factorisation already computed. Solving Az = y for a few cleverly chosen y gives a lower bound on ‖A⁻¹‖, and combined with ‖A‖, which is free, that gives a lower bound on κ. LAPACK’s gecon does exactly this and returns its reciprocal; the cost is a few triangular solves against an O(n³) factorisation, which is to say nothing.

A lower bound is the right thing to want. It cannot certify that a problem is well conditioned, but it can warn that it is not, and warning is the case that matters. An estimator that returns 10¹² has said something conclusive. One that returns 10² has said only that it did not find a bad direction, which is weaker, but the estimators are good and the false reassurance rate is low.

A worked estimate, done in the head

The arithmetic that matters in practice is a single subtraction, and it is worth having ready.

Write κ = 10ᵏ and the unit roundoff as 10⁻¹⁶ for double, 10⁻⁷ for single. Then the number of correct decimal digits to expect is about 16 − k in double and 7 − k in single.

That is it. A matrix with κ = 10⁶ leaves ten digits in double and one in single. A matrix with κ = 10¹² leaves four digits in double and nothing at all in single. A matrix with κ = 10¹⁷ leaves nothing in double.

The estimate is a bound rather than a promise, so it errs on the pessimistic side — the measured errors in the figures here typically come in a factor of five or so below it. But it is the right first calculation, and it turns “is this matrix badly conditioned?” from a vague worry into a question with an answer in digits.

The single-precision column is the surprising one. Seven digits of headroom sounds ample and it is consumed by a condition number of 10⁷, which is not a large number: a design matrix for a sixth-degree polynomial fit on equispaced points passes it. The road that squares the problem is where that becomes concrete, and where the same arithmetic explains why forming AᵀA is not a small change of plan — it takes k to 2k, so ten digits become four.

Loss of orthogonality against condition number, in binary64A log–log plot of the norm of Q-transpose-Q minus the identity against condition number. Classical Gram–Schmidt rises steeply, modified Gram–Schmidt rises gently, and Householder is flat.110²10⁴10⁶10⁸10¹⁰10¹²10⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹condition number κ(A)‖QᵀQ − I‖classicalmodifiedHouseholderκ²uκu8×8, eight seeds per κ, binary64all three reconstruct A
Fig. 5 The same subtraction, applied to a different quantity. Loss of orthogonality against condition number, for three factorisation methods, with the predictions κu and κ²u drawn as dashed lines. Classical Gram–Schmidt loses like κ², modified like κ, and Householder does not lose at all — three different answers to the same question about the same matrices.

What is asserted here

The claims in this essay are all measurements, and each is run on every build.

No perturbation is allowed to be amplified by more than κ — that is the definition, and if the measurement ever exceeded it, either the measurement or the κ would be wrong. Two hundred random directions must find at least a third of κ, which is the claim that the worst case is reachable. The median must exceed κ/10, which is the claim that random directions are typically close to it. And the mildest of the two hundred must still be amplified by κ/1000, which is the claim that no direction escapes.

Those four thresholds hold at every position of the slider, from κ = 10² to κ = 10⁸, because the frames are generated at build time by the same code that drew the static figure. A reader dragging the control is exploring the claim’s generality, and the build has already checked it there.

The construction of the test matrices is itself checked against two routes. Two routes to a number is the thread; here it means that a matrix built to have κ = 10⁸ is required to measure as having κ = 10⁸, by a one-sided Jacobi SVD that shares only the matrix multiplication with the construction. The tolerance for that agreement is not a round number — it scales with κ, because the assembly’s own rounding limits how precisely the smallest singular value can be planted, and it is bracketed between the measured noise and a factor-of-two miss.

Where κ appears in the rest of the collection

It is the horizontal axis of nearly every figure here, so it is worth listing what it is measuring in each.

In a small residual is not a small error it separates the flat backward-error line from the rising forward-error one, and the vertical distance between them at any point is κ.

In orthogonal is a number it drives the loss of orthogonality, at a rate that identifies the algorithm: κ for modified Gram–Schmidt, κ² for classical, and nothing at all for Householder.

In the road that squares the problem it is the quantity that gets squared, and the essay is about a modelling choice that does the squaring.

In rank is a decision it is the reciprocal of the tolerance: a matrix is numerically rank deficient exactly when κ exceeds 1/tol, and the two vocabularies describe one fact.

Growth factor under partial pivoting: the bound, the worst case, and realityGrowth factor against matrix size on a logarithmic vertical axis. The two-to-the-n bound rises as a straight line; Wilkinson's matrix sits exactly on it; random matrices stay near one.0816243240110²10⁴10⁶10⁸10¹⁰10¹²10¹⁴matrix size ngrowth factor max|u| / max|a|the 2ⁿ⁻¹ boundworst of 30 randommedian randomWilkinson's matrix sits on the bound30 Gaussian matrices per sizeat n = 40: bound 5.5·10¹¹, worst 4.8
Fig. 6 And the one important quantity on this site that is not κ. The growth factor belongs to the algorithm rather than to the problem, which makes it the exception that shows what the rule is: a matrix’s conditioning is fixed, and how much of it an algorithm adds to is a separate question with a separate answer.

The estimate that gets skipped

A closing practical note, because everything above is only useful if the number is actually computed.

LAPACK returns a condition estimate on request from gecon, at a cost of a few triangular solves against a factorisation that already cost n³/3. In relative terms it is free. It is also, in most code that calls a linear solver, never asked for.

The consequence is a class of failures with a characteristic signature: results that are subtly wrong in a way that varies with the input data, discovered late, and attributed to a bug in the solver. The solver is fine. The one number that would have said so was available for the asking, and the asking did not happen.

The habit worth building is small. When a solve matters, request the estimate, print it, and know the arithmetic that turns it into digits: 16 − log₁₀κ in double, 7 − log₁₀κ in single. When it comes back at 10³ nothing further is needed. When it comes back at 10¹² the answer has four digits and the question is whether four is enough — which is a question about the application, and one that can now be answered rather than worried about.

Where this goes next

the problem you posedA = H10b = A·(1, 2, …, 10)the problem it answered exactlyA + δA, b + δb‖δ‖ / ‖A‖ = 2.3·10⁻¹⁷the answer you wantedx = (1, 2, …, 10), exactlythe answer you gotx̂, wrong by 2.7·10⁻⁴ relativebackward error 2.3·10⁻¹⁷forward error 2.7·10⁻⁴κ = 1.6·10¹³κ · η = 3.6·10⁻⁴, and the measured forward error is 2.7·10⁻⁴.The algorithm is not at fault. The problem is.H10, LU with partial pivotingresidual and error differ The exact answer to a nearby problem A good algorithm does not give an approximate answer to your problem. It gives the exact answer to a problem very close to yours — and once that is the definition, a wrong result has two possible authors and they can be measured apart. 110²10⁴10⁶10⁸10¹⁰10¹²10¹⁴10⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²10¹condition number κ(A)relative errorforward errorbackward errorpredicted: κ · u8×8, 20 seeds per κ; dashed is the worstthe problem worsens, not the method A small residual is not a small error Substituting the answer back and finding that it fits is the most natural check there is, and it verifies the wrong thing. A residual of 10⁻¹⁷ is entirely compatible with an answer whose second digit is wrong. 1234567891010⁻¹⁸10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³1indexsingular valuecutoff, σ₁ · 10⁻¹⁰numerical rank 10gap 8.2·10⁶an opiniontrue rank 410×10, built with 4 nonzero valuesrank is a decision Rank is a decision A floating-point matrix does not have a rank. It has a spectrum of singular values, and somewhere in that spectrum is a place where the values stop being signal and start being noise. Deciding where is a judgement, and the evidence for it is a gap.