The condition number is an amplifier

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.

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.

That is eight by eight. If κ is the amplifier then the size of the matrix should not be a second amplifier, and the slider is where that gets tested rather than assumed.

Four times the unknowns of the first frame, and the two quantities in the badge have moved by very different amounts. Half again as many, to see which of the two is doing the moving:

One of those two numbers is growing with the size and the other is not, and four sizes is not quite enough to be sure which — the forward column has bounced from 5.72 to 7.41 to 4.28 to 5.18 without settling. Two more sizes:

The backward error grows as √n and nothing else. Dividing it by √n gives 5.13, 3.65, 4.38, 4.26, 4.60 and 5.13 × 10⁻¹⁷ — constant to within 40% while n moves by a factor of ten, and about four tenths of the unit roundoff. That is the elimination accumulating rounding over its own operations, and it is the only place the size appears.

The forward error at the hard end does not depend on n at all. 5.72, 7.41, 4.28, 5.18, 7.59 and 7.84 × 10⁻⁵ across a tenfold range of size — six readings inside a factor of 1.8, with no trend. So the answer’s accuracy at κ = 10¹³ is decided by κ, and the matrix being ten times larger costs nothing in the quantity a caller cares about.

Which is the essay’s claim in the form that can be checked. “The condition number is an amplifier” is a statement that one number governs, and the way to test it is to move a different number and watch nothing happen. The backward error moves — by √n, as the arithmetic requires — and the amplification carries it to the same place regardless.

The last column is the noisiest thing on the page and worth reading with that in mind: the achieved amplification is 0.084 to 0.238 of κ, a factor of 2.8 of scatter across the six sizes, and no trend in n. It is a fraction of κ rather than κ itself — twenty seeded matrices find a fifth of the available amplification at the small sizes and a tenth at the middle ones — and the scatter is the seeds rather than the size.

κ 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.

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.

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. By how much is worth measuring, because a rule that is conservative by a predictable amount can be sharpened and one that is conservative by an unpredictable amount can only be distrusted.

Forward error divided by κu, against a reference solved exactly in rationals, 16×16, twenty-four seeds at each conditioning:

The bound holds at every one of the 144 solves. No ratio exceeds one, which is what makes it a bound rather than an estimate, and is the property worth keeping.

And it is pessimistic by ten to fifty-seven times, not by five — between one and one and three-quarters of a digit. The slack also settles: for κ ≥ 10⁴ the median ratio sits between 0.017 and 0.039 with no trend, so it is a constant rather than something that grows with the conditioning.

A constant slack is a rule that can be sharpened. The median error is about 0.025·κu = κ·2.8·10⁻¹⁸, so the digits to expect are 17.5 − k rather than 16 − k. That is a digit and a half the conservative form gives away, and giving it away matters here more than it usually would, because the whole value of the rule is that it turns a vague worry into a number — and a number that is a digit and a half out is a different answer to the same question.

Keep both. 16 − k is what can be promised, since nothing in the sweep beat it. 17.5 − k is what will be seen. The gap between them is the width of the band a reader should expect, rather than a source of surprise when the answer comes back better than the bound.

That the estimate is the right first calculation is unchanged by any of this: it turns “is this matrix badly conditioned?” into a question with an answer in digits, and now into one with an answer and an error bar.

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.

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.

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.

Two quantities that are not this one #

The determinant is the scalar most readers reach for before the condition number, and it answers a different question — badly. A tenth of the identity has a condition number of exactly one and a determinant of 10⁻⁶⁰.