A condition number scaling cannot move

The units the matrix is measured in used the componentwise condition number as a foil — a second number, flat, drawn beside a first number that climbs. This essay takes it seriously as an object: what it is, what it bounds, why the invariance is exact rather than approximate, and what its ratio to κ is worth as a diagnostic.

Its definition is one line, and the only thing in it that is unusual is where the absolute values go.

$$\operatorname{cond}(A) = \bigl\|\, |A^{-1}| \cdot |A| \,\bigr\|_\infty$$

Take the inverse. Take the absolute value of every entry of both matrices. Then multiply, and then take a norm. The normwise condition number is ‖A⁻¹‖·‖A‖, where the norms are taken first and the entries never meet.

Why the absolute values matter #

The absolute values are the whole of the difference, and they are what makes the number a statement about entrywise relative perturbation.

A normwise bound answers: move A by a matrix of norm ε‖A‖ — how far can x move? The perturbation is described by one number for the whole matrix, and it is free to put all of its weight anywhere.

A componentwise bound answers: move every entry aᵢⱼ by at most ε|aᵢⱼ| — how far can x move? This constrains the perturbation entry by entry — the perturbation of a tiny entry is tiny — and the constant that comes out is cond(A, x) = ‖ |A⁻¹| |A| |x| ‖_∞ / ‖x‖_∞, with the solution in it.

Rounding a matrix into a floating-point format is exactly the second kind of perturbation. So is storing it in a narrower one, and so is a measurement whose error is a percentage. The first kind is a mathematical convenience.

The invariance, in three lines #

Write A = D·A₀ with D diagonal and positive. Then A⁻¹ = A₀⁻¹D⁻¹ and

|A⁻¹| |A|  =  (|A₀⁻¹| |D⁻¹|)(|D| |A₀|)  =  |A₀⁻¹| (|D⁻¹| |D|) |A₀|  =  |A₀⁻¹| |A₀|

because |D⁻¹||D| is exactly the identity — a diagonal matrix times its own inverse, entry by entry, no cancellation of unequal quantities anywhere. The product is the same matrix, not merely the same norm, so the equality survives whichever norm is taken afterwards.

That is a stronger statement than a bound, and it is worth noticing what it rules out. It says the componentwise number cannot be improved by scaling either: there is no diagonal D that makes it smaller, because there is no diagonal D that changes it. Equilibration takes κ down by eight orders of magnitude and takes cond down by exactly nothing, and the second sentence is the reason the first one is not a repair for every problem.

Measured, because the arithmetic is not the algebra #

assertSkeelIsInvariantUnderRowScaling computes the number twice, by inverting two different matrices, and checks agreement at 10⁻⁸ relative. The algebra above is exact; the two inversions round, and the scaled matrix’s inversion rounds worse because its entries span eight decades.

Measured on the site’s test matrix the two come out 6.976397983091772 and 6.976397983091762 — agreement to fourteen digits, on a matrix whose κ₂ has moved by 3.7·10⁷ between the two computations. The two digits that differ are the arithmetic’s, and they are exactly where the site expects to find them.

The assertion also runs a third scaling, drawn at random over twelve decades and unrelated to the one the test matrix was built with. An invariance checked only against the construction that produced it is an invariance checked against itself, and this site has recorded that mistake in another library already.

The invariance is visible rather than only provable, and the way to see it is to draw the same figure at six spreads and read the same four numbers off each one.

Across spreads of 0, 2, 4, 6, 8 and 10 decades the normwise condition number reads 9.8, 223, 2·10⁴, 1.9·10⁶, 1.9·10⁸ and 1.9·10¹⁰ — ten orders — while cond(A, x) reads 4.8 at every one of them, the componentwise bound reads 4.8·10⁻⁹ at every one, and the perturbation actually moves the answer by 2.1·10⁻⁹ at every one. Three of those four columns are constant to the digits printed, and the one that moves is the one nobody perturbed anything to change.

That is the sentence the algebra above proves, but the fourth column is the one worth having drawn: the measurement is flat too. The invariance of cond is a statement about a formula, and a reader is entitled to ask whether the matrix has genuinely not become harder. Forty random componentwise perturbations at each spread say it has not.

What the ratio says #

cond(A) ≤ κ_∞(A) always, and the gap can be anything. So the ratio is information, and it is the most useful thing in this essay — the same kind of reading an estimate that can be fooled is about, except that this one cannot be, because it is computed rather than sampled:

κ_∞ ≫ cond. The matrix is badly described. Its rows differ enormously in size, a normwise perturbation is a bad model of what will happen to it, and a diagonal scaling will bring κ down to near cond. Measured here: 2.7·10⁷ for the eight-decade matrix.

κ_∞ ≈ cond. The matrix is badly conditioned, or well conditioned, and either way the normwise number is telling the truth and no scaling will help. Measured here: 2.9 for the Hilbert matrix at n = 8, with both numbers near 10¹⁰.

The Hilbert row is the one that makes the diagnostic usable. Without it a reader has a rule that says compute both and scale if they differ, which is fine and expensive; with it there is a second rule that says if they do not differ, stop looking for a repair.

The bound, and how tight it is #

The componentwise perturbation theorem says: if |ΔA| ≤ ε|A| and |Δb| ≤ ε|b|, then to first order

$$\frac{\|\Delta x\|_\infty}{\|x\|_\infty} \le \frac{2\varepsilon \cdot \operatorname{cond}(A, x)}{1 - \varepsilon \cdot \operatorname{cond}(A)}$$

and for the sizes of ε that matter the denominator is 1. The hero figure is that bound against a measurement, and the measurement is the worst of forty random perturbations at each of six sizes.

At ε = 10⁻⁹ the numbers are: measured worst 2.1·10⁻⁹, componentwise bound 4.8·10⁻⁹, normwise bound 0.19. The componentwise bound is within a factor of 2.3 of what actually happened. The normwise bound is a valid statement that predicts nothing.

Both directions are asserted, and it matters that they are. A single assertion saying “the componentwise bound is better” would pass on a matrix where both were hopeless. What is checked is that the normwise bound holds, that the componentwise bound holds, that they are orders apart, and that the componentwise one is nearly attained — which is the claim that it is a prediction rather than a smaller number.

And there is a point on that axis where the normwise bound stops being a statement at all. It reads 9.8·10⁻⁹, 2.2·10⁻⁷, 2·10⁻⁵, 1.9·10⁻³, 0.19 and 19 across the six spreads. The last of those is a relative error of nineteen hundred per cent: true, since the componentwise bound of 4.8·10⁻⁹ is below it, and empty, since any answer whatever satisfies it. The crossing is between eight and ten decades of units, and it is the point at which a solver reporting only κ can no longer distinguish a correct answer from a wrong one — on a matrix whose actual sensitivity has not changed since the first figure in this essay.

The version with x in it #

cond(A, x) is smaller still than cond(A), and the difference is worth a paragraph because it carries an idea this site has met before.

cond(A) takes a norm over all right-hand sides. cond(A, x) is about the solution in hand. A matrix can be very sensitive for some b and not for others — the sensitivity lives in the direction of x relative to the small singular directions — and cond(A) reports the worst case over all of them.

That is the same relationship as between κ(A) and the amplification a particular perturbation achieves, which the condition number is an amplifier measured: a random perturbation direction is amplified by 0.29 of κ at the median and 0.76 at the worst of 200. A condition number is a supremum, and a supremum is attained by one direction out of infinitely many.

The backward error it pairs with #

A condition number is only half of the site’s identity. The other half is the backward error, and it has a componentwise form too, which is where the pairing becomes an argument rather than a definition.

The normwise backward error of a computed x has a closed form — ‖Ax − b‖ / (‖A‖‖x‖ + ‖b‖) — and this site has printed it on figures since its first commit. The componentwise one, due to Oettli and Prager, is

$$\omega = \max_i \frac{|r_i|}{\bigl(|A|\,|x| + |b|\bigr)_i}$$

with r the residual, and it answers: what is the smallest ε such that x is the exact solution of some (A + ΔA)x = b + Δb with |ΔA| ≤ ε|A| and |Δb| ≤ ε|b|? It is a maximum over rows of a ratio of computed quantities, so it costs one matrix–vector product and no inverse at all.

The two halves then compose in the same shape as the site’s spine:

forward error  ⪅  cond(A, x) × ω

and both factors are componentwise. That inequality is the one whose right-hand side was nearly attained in the hero figure, and it is the reason the componentwise pair is worth carrying rather than merely noting: the normwise identity and the componentwise identity are both true, and only one of them predicts the number.

What Skeel’s theorem is actually about #

The componentwise condition number is usually called Skeel’s, and the paper it comes from is not about a condition number. It is about iterative refinement, and the result is startling enough to restate.

Gaussian elimination with partial pivoting is normwise backward stable and is not componentwise backward stable: the ΔA it is exact for can be small in norm and enormous relative to individual entries, which is exactly what happens on a badly scaled matrix. Skeel’s theorem says that one step of iterative refinement, with the residual computed in the working precision, repairs that — the refined solution has a componentwise backward error of order u, provided cond(A) is not too large.

The italics are the surprising part. Buying the accuracy back measured refinement in the setting it is usually presented in: a low-precision factorisation, a residual computed in a higher precision, and the reward is forward accuracy. Skeel’s version needs no extra precision anywhere and buys something different — not a more accurate answer, but an answer that is the exact solution of a problem whose every entry is within a rounding of the one that was handed over.

That is a different guarantee and it is the right one for a scaled problem, because a componentwise backward error is invariant under row scaling for the same reason cond is: the scaling divides out of the ratio row by row.

Two matrices with the same κ and different cond #

The clearest way to see that these are separate quantities is to hold one fixed and move the other.

Take the badly scaled matrix at eight decades: κ_∞ = 1.9·10⁸, cond = 6.98. Now take an ordinary random matrix and give it a genuine spread of singular values until its κ_∞ reaches 1.9·10⁸ as well. Its rows are all about the same size, so its cond is also near 10⁸.

Two matrices, the same normwise condition number, componentwise numbers seven orders apart. A solver handed either of them and told only κ would budget for the same loss of accuracy, and would be right about one of them. Equilibrating the first takes κ to about 7 and leaves the answer exactly where it was; equilibrating the second does nothing at all.

The site’s own Hilbert matrix is the second case at n = 8, and it is drawn in every figure in this essay for that reason.

Why nothing computes it #

cond(A) needs the entries of A⁻¹, not its action. Every other quantity in a solve — the answer, the residual, an estimate of κ — can be got from the factorisation by solving with it. This one needs n solves to form the inverse, which costs more than the factorisation did, and then an n×n product on top.

That is why it is not in the routine every library exposes, and why the number a reader has in hand is the normwise one. LAPACK’s expert drivers do return a componentwise error bound, computed by Skeel’s iterative-refinement argument rather than by forming the inverse, and it is the right thing to ask for when the answer matters. It is also three letters longer to type than the simple driver and correspondingly rare.

There is a cheaper diagnostic that costs nothing at all: look at the row norms. The claim is that their spread is what separates the two condition numbers, and since it is free it is worth knowing how good it is rather than only that it exists.

How good the free diagnostic is #

Take matrices at four intrinsic condition numbers, scale their rows over eight decades, and compare the measured κ_∞/cond against the row-norm spread. The table is the ratio of the two — what fraction of the row spread actually shows up as separation between the condition numbers:

                     row spread 1      10²      10⁴      10⁶      10⁸
κ₂ = 10¹                 0.52         0.37     0.27     0.23     0.21
κ₂ = 10³                 0.24         0.25     0.25     0.25     0.24
κ₂ = 10⁶                 0.14         0.11     0.15     0.16     0.14
κ₂ = 10⁹                 0.10         0.064    0.084    0.12     0.11

Every cell is between a sixteenth and a half. The gap itself runs from 1.6 to 1.9·10⁷ across this grid — seven orders — and the row-norm spread predicts it to within a factor of eight everywhere, while barely noticing the intrinsic conditioning: the drift down the columns is a factor of five over eight orders of κ₂, and the drift across the rows is nothing at all.

So the diagnostic is quantitative rather than qualitative. κ_∞/cond ≈ a quarter of the row-norm spread, and a reader with the row norms in hand knows the answer to within an order of magnitude before any solve.

That fixes a sentence this essay had wrong. The natural way to state the rule is if the row norms are within a couple of orders, κ and cond are close and κ is honest — and two orders of row spread puts κ twenty-four to thirty-six times above cond, which is not close. The essay’s own earlier sentence had it right: two decades of units is already two decades of gap. The threshold for “κ is honest” is row norms within a factor of a few, not within a couple of orders, and that is a much narrower condition than it sounds — almost any matrix assembled from quantities in different units fails it.

None of that is a substitute for computing the number when the answer matters. It is what to do before deciding whether to.

There is one more thing in the table and it is the reason the fraction is a quarter rather than one. A row spread of 10⁸ does not put eight full decades between the two numbers; it puts about 7.4. The missing part is that the row norms are the largest entries of each row, and κ_∞ is built from a sum along each row rather than from its maximum, so a row whose entries are all near its maximum contributes slightly less than a row with one large entry and the rest small. That is a detail about the ∞-norm and not about scaling, and it is why the diagnostic is an estimate of the gap rather than a computation of it.

The practical ordering that falls out is three steps and only the last of them is expensive. Read the row norms, which is free and says to within an order what κ is overstating by. Equilibrate if they are spread, which costs one pass and takes κ down to near cond — and changes the answer by nothing, which is what the units the matrix is measured in is about. And compute cond itself only when the answer matters enough to pay for n solves, because by then the first two steps have already said whether it can report anything they did not.

Where the two numbers come apart in practice #

Three places, and none of them is contrived.

Assembled physical models. A stiffness matrix couples displacements to rotations to forces, and the constants of the physics set the row scales. κ reports the constants; cond reports the geometry.

Least squares with a weighting. Weighted least squares multiplies each row of A and b by a weight, which is a row scaling performed deliberately and often over many orders of magnitude — a measurement trusted a thousand times more than another gets a weight a thousand times larger. The normwise condition number of the weighted matrix is then partly a report of the weights. The projection and the right angle has the unweighted version; the weighting is a diagonal on the left of it.

Interior-point steps. The linear system inside an interior-point iteration has a diagonal that goes to zero and to infinity as the iteration converges, which is a row scaling with an enormous and deliberately growing spread. Its κ blows up along the path by construction. Whether the steps are actually getting harder to compute is a question about cond, and the practical answer — that they are not, that these systems solve accurately right up to the boundary — is one of the reasons interior point methods work at all.

In each case a reader who watches κ sees a number that grows and concludes the problem is deteriorating. A reader who watches the ratio sees a number that does not.

What is worth carrying #

The componentwise condition number is exactly invariant under row scaling, and the exactness is structural — two diagonal matrices cancel entry by entry inside the absolute values, before any norm is taken. Nothing is being estimated.

It is the constant in the bound that models what a machine actually does to a matrix, which is a relative perturbation of each entry, and on a badly scaled matrix it is nearly attained where the normwise bound is loose by eight orders.

And the ratio of the two is a diagnostic that says which kind of trouble a matrix is in. Far apart: the units. Together: the matrix. The first is repairable by a diagonal and the second is not repairable at all.

The next essay is about the number a library actually prints in place of κ, and about the matrix on which that number is wrong by any factor at all: an estimate that can be fooled.

The other place these entries are the answer #

Skeel’s number needs the entries of A⁻¹ rather than its action, which is one of the two cases on this site where forming an inverse is right. The other is statistical, and it is the diagonal of a hat matrix.