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.

cond(A)  =  ‖ |A⁻¹| · |A| ‖_∞

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_ij by at most ε|a_ij| — 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.

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:

κ_∞ ≫ 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

‖Δx‖_∞ / ‖x‖_∞   ≤   2ε · cond(A, x)  /  (1 − ε·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.

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

ω  =  max_i  |r_i|  /  ( |A||x| + |b| )_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. If the largest is within a couple of orders of the smallest, κ and cond are close and κ is honest. If they span eight decades, κ is mostly reporting that fact. That is not a substitute for computing the number, and it is available before any solve at all.

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.