A rule that is correct and unusable

Cramer’s rule is the most satisfying formula in elementary linear algebra. Every component of the solution, in closed form, with no algorithm in it:

xⱼ  =  det(Aⱼ) / det(A),   where Aⱼ is A with its jth column replaced by b

It is correct. It is a theorem, it is proved in every first course, and it has no hypotheses beyond det A ≠ 0. It is also, at 2×2, four multiplications and two subtractions written out by hand, which is what makes it the version everybody actually uses — not at n = 10, where the objection is obvious, but inside a line intersection, a Newton step, a barycentric coordinate, a two-parameter fit.

This essay is about what that costs, and the usual objection is the wrong one.

The objection everybody knows, and its size #

The standard complaint is arithmetic. At n × n, Cramer’s rule computes n + 1 determinants; done by cofactor expansion that is n! terms each, and the number quoted is that solving a 20×20 system this way would take longer than the age of the universe.

It is true and it is not the objection, because nobody computes a determinant by cofactor expansion either. Compute each determinant by LU — the only sensible way, and the way the previous essay describes — and Cramer’s rule costs n + 1 factorisations against elimination’s one:

A factor of n + 1 is a bad constant and it is a constant. It would not stop anybody using Cramer’s rule at n = 2, where the factor is 3 and the whole computation is six operations.

The objection that matters #

Elimination with a row interchange is backward stable. That word has a precise meaning on this site and it is the meaning the site’s spine is built from: the computed x̂ is the exact solution of (A + ΔA)x̂ = b + Δb with ‖ΔA‖ a small multiple of u‖A‖. The algorithm answered a question next door to the one it was asked, and everything else that goes wrong is the problem’s fault and can be predicted from the condition number.

Cramer’s rule has no such bound, and it is not that the bound is worse — there is no theorem of that shape for it at all.

Measured: forty thousand 2×2 systems whose two rows are nearly parallel, at 24 significand bits. The normwise backward error

η(x̂)  =  ‖b − Ax̂‖ / (‖A‖ ‖x̂‖ + ‖b‖)

is what decides the question, and it is attained — there is a perturbation of exactly that size for which x̂ is the exact answer.

Elimination’s worst over the whole sweep is 1.3u. Cramer’s rule’s worst is 458u.

The system it fails on is not a hard system #

This is the part worth dwelling on, because the natural defence is that the sweep found a nasty matrix.

The worst case has a condition number of 3.2·10⁴. That is a mildly awkward matrix and nothing more — four or five digits of the answer are at risk from the conditioning, which is a perfectly ordinary situation.

Elimination solved that system to 1.3u.

So the difficulty is not in the matrix. Two algorithms, the same six numbers in, algebraically identical outputs, and one of them returns the exact answer to a nearby problem while the other returns something no nearby problem has as its answer. That is the site’s identical algebra, different arithmetic thread in its smallest available instance: a 2×2.

Nor is it in the precision, which is the other place a reader will look for it. The natural repair for a formula that loses digits is to give it more, and this site has a whole thread on precision as the knob for cases where that works. Here it does not.

Across 16, 24, 32, 43 and 53 bits Cramer’s worst backward error reads 63, 395, 229, 214 and 248 units of roundoff and elimination’s reads 1.1, 1.2, 1.2, 1.2 and 1.4. Thirty-seven bits of extra arithmetic — a factor of 1.4·10¹¹ in u — leave both columns where they were. The absolute error falls with u in both cases, of course; what does not change is that one method is a small constant times the representation’s accuracy and the other is a couple of hundred times it, with nothing bounding the second.

The sixteen-bit row is the one to read carefully, because its 63u looks like evidence that low precision is safer and it is not. The family is built by making two rows nearly parallel, and how nearly is bounded below by what the format can represent — so at sixteen bits the sweep cannot construct the systems that break the rule at twenty-four, and its worst system is fifty times better conditioned. Less precision did not make the formula better; it made the counterexample unrepresentable.

How often, which is the question a programmer has #

A worst case is the right statistic for the claim being made — that no backward-stability theorem exists — because one counterexample settles it. It is the wrong statistic for the decision anybody reading this actually faces, which is whether the 2×2 Cramer’s rule already in their code needs replacing.

Bucketing the same forty thousand systems by condition number:

between κ = 10 and 10² the worst Cramer backward error is 13.2u and the median is 0.37u. Between 10² and 10³, worst 103.0u, median 0.22u. Between 10³ and 10⁴, worst 144.2u, median 0.11u. Between 10⁴ and 10⁵, worst 458.2u, median 0.05u. Above 10⁵, worst 395.2u, median 0.03u. Elimination’s worst in every one of those bands is between 1.00u and 1.29u.

Two things fall out of that table and they point in opposite directions.

The worst case grows like κ^0.33. A cube root — not proportionally, which is what it would take for Cramer’s backward error to be elimination’s forward error inherited. So the instability is real, uncapped by any theorem, and much milder than the conditioning. At κ = 10⁵ a proportional law would predict 10⁵u and the measurement is 400u.

And the median falls, from 0.37u to 0.03u. The typical Cramer solve on a badly conditioned system is better than on a mildly conditioned one by that measure — partly because ‖x̂‖ grows and the normalisation grows with it, and partly because the near-parallel systems that cancel catastrophically are a thin subset rather than the general case.

0.015 per cent of the forty thousand exceed 100u. Elimination’s share is exactly zero, at every band, which is what a backward-stability theorem buys.

One qualification on the median, because it is the number most easily over-read. η is normalised by ‖A‖‖x̂‖ + ‖b‖, and on a near-singular system ‖x̂‖ is large, so the denominator grows with the conditioning and the fraction falls for a reason that is partly arithmetic bookkeeping rather than improved behaviour. The componentwise backward error, which the same sweep computes, does not have that property and is the honest quantity to compare medians on.

What survives the qualification is the shape rather than the exact numbers: the distribution has a long tail and a well-behaved body, at every conditioning. That is what a rule with no bound looks like when it is sampled, and it is why the sweep needed forty thousand systems rather than forty. A hundred-system experiment on this family would, with probability about 0.985, have found nothing at all and concluded that Cramer’s rule is fine.

Which is why it is still in the code #

That number is the essay’s practical finding and it is worth stating as such, because it explains a survival that the worst case alone makes look inexplicable.

A method that failed on every ill-conditioned system would have been removed from production code decades ago. Somebody would have noticed. What Cramer’s rule does instead is fail about twice in ten thousand, on matrices that look entirely ordinary — the worst case in this sweep has a condition number of 3.2·10⁴, which is a matrix nobody would look at twice — with no diagnostic attached and no exception raised. A line-intersection routine called a million times returns two hundred wrong answers and nine hundred and ninety-nine thousand eight hundred right ones, and the two hundred are not distinguishable from the rest by anything the routine reports.

So the honest advice is not Cramer’s rule is inaccurate, which the median refutes, and it is not Cramer’s rule is fine at 2×2, which the worst case refutes. It is that the rule has no bound and a low failure rate, and those two together are the worst combination for anything that will be called many times: too rare to be found in testing, too unbounded to be reasoned about, and too cheap for anyone to have looked.

The replacement costs nothing. A 2×2 solve with a row interchange is the same six operations plus a comparison — pivoting is the whole of the difference — and it returns 1.3u in the worst case this sweep could find. There is no trade here to weigh, which is the one respect in which this is an easier decision than most on this site.

Where the digits go #

The mechanism is cancellation, and it is worth following through.

For a 2×2, Cramer’s rule computes

d  = a₁₁a₂₂ − a₁₂a₂₁
x₁ = (b₁a₂₂ − a₁₂b₂) / d
x₂ = (a₁₁b₂ − b₁a₂₁) / d

When the two rows are nearly parallel, a₁₁a₂₂ and a₁₂a₂₁ agree to several digits, and their difference loses those digits — cancellation, exactly as the arithmetic field describes it. The two products are computed correctly and the subtraction is correct; what is lost is that the inputs to the subtraction were rounded, and rounding them at a relative 10⁻⁷ perturbs a difference that is itself 10⁻⁵ of them by a relative 10⁻².

So far this is conditioning, and conditioning is nobody’s fault. The reason it becomes the algorithm’s fault is what happens next. The two numerators cancel too, independently, and the three errors do not have a common factor. If d were merely inaccurate by a relative δ, both components of x would be scaled by 1 + δ and the residual would be δ‖b‖ — which is small when ‖A‖‖x‖ is large, and the backward error would survive. What actually happens is that d and the two numerators are wrong by three unrelated amounts, so x̂ is not a scalar multiple of anything, and Ax̂ − b is a vector with nothing small about it.

Elimination avoids this because of the interchange. The largest entry becomes the pivot, the multiplier is at most one in magnitude, and no intermediate quantity grows relative to the data — the growth factor, which the elimination field is built around, is bounded by 2 for a 2×2.

That last clause is the structural difference and it is worth stating on its own. Elimination is an algorithm — it has choices, and the choice it makes at every step is precisely the one that keeps its intermediates from growing. Cramer’s rule is a formula: the products it forms are named in advance, there is no step at which anything is compared to anything, and there is therefore no place to put a safeguard. A closed form has nowhere to be careful.

The same sentence explains why the failure cannot be repaired by computing the three determinants more accurately. Each of them is already computed as accurately as its own inputs allow; the loss happens in the subtraction that defines a determinant, and there is no reformulation of ad − bc that does not subtract. What elimination does instead is never form ad − bc at all — it forms d − (c/a)·b and multiplies by a implicitly, which is the same number by a route whose intermediates are bounded by the data.

The control, which is the half that makes it a finding #

A sweep chosen to break a method will break it. The result above is worth having only because the same measurement, on a uniformly random 2×2 with entries spread over two decades, separates almost nothing: Cramer’s worst is 8.4u against elimination’s 1.4u.

That is the honest size of the everyday case. Cramer’s rule at 2×2 on ordinary data is a bad method — six times the backward error, consistently — and not a broken one. It becomes broken where the determinant cancels, which is exactly where a 2×2 solve is being asked to do something interesting: two lines that nearly coincide, two constraints that nearly agree, a Newton step near a fold.

The cases a 2×2 solver exists to handle are the cases the formula fails on, which is a worse property than failing at random.

Precision does not buy it back #

The axis of every one of those figures is in units of the arithmetic’s own roundoff, and that choice is the argument.

If Cramer’s rule were merely imprecise — if it needed a few more digits than elimination — then measuring both in units of u would collapse the two curves onto each other, because both would scale with the format. They do not. Elimination sits at a bounded multiple of u at 16, 24, 32, 43 and 53 bits; Cramer’s rule’s tail is at tens to hundreds of u wherever it is measured.

That is what backward stability is, stated as a measurement rather than as a definition: a stable method’s error, in units of the precision, does not depend on the precision. Doubling the mantissa buys a stable method eight more correct digits and buys an unstable one eight more digits of an answer that still does not solve any nearby problem.

Where it is still written #

Cramer’s rule survives in code, and mostly in three places.

Geometry kernels. A line–line intersection, a barycentric coordinate, the circumcentre of a triangle. These are 2×2 and 3×3, the data is often exact — integer or fixed-point coordinates — and where the data is exact the whole argument above is void. The exact-input case is the same exemption the determinant’s sign gets: an exact function of exact data is exact.

Symbolic and interval work. In exact rational arithmetic Cramer’s rule has no error at all, and in interval arithmetic it gives an enclosure. It is a poor choice for cost and a fine one for correctness.

Proofs and derivations. As an object it is indispensable — the adjugate, the closed form for the inverse, the derivative of a determinant. None of that is a computation.

What it is not is a solver, and the distinction is the same one the whole phase is about: a formula that is exact in the algebra is not thereby a computation of what it names.

Two rules that look alike and are not #

It is worth separating Cramer’s rule from a formula it is often filed beside: the 2×2 inverse,

A⁻¹ = (1/det A) [ a₂₂  −a₁₂ ; −a₂₁  a₁₁ ]

which is the same arithmetic wearing different clothes, and inherits the same defect exactly — as it must, since x = A⁻¹b computed this way is Cramer’s rule. The inverse that is never formed takes the general version of that apart, and finds the same shape of result at every size: the backward error separates and the forward error does not.

The difference between the two essays is where the loss comes from. There it is the assembly of n independently-perturbed columns; here it is a single division by a number that cancelled. Same conclusion, different mechanism, which is what makes them two essays.

Three by three, and where the rule is taught #

At n = 3 Cramer’s rule is still written by hand — in a graphics kernel, a barycentric coordinate, a plane–plane–plane intersection — and the arithmetic changes shape enough to be worth a paragraph.

The 3×3 determinant is a sum of six products of three entries, so a single evaluation has two subtractions of nearly equal quantities rather than one, and the cancellation compounds. The conditioning of a 3×3 solve is no worse than a 2×2’s for the same κ, and the number of independent roundings in the closed form is roughly three times larger. Everything this essay measures gets worse and nothing gets better.

What does change is the alternative. At n = 3 a pivoted elimination is 17 operations against Cramer’s rule’s 51, so the cost argument now points the same way as the stability one — which it did not at n = 2, where the two methods are six operations against six. The 2×2 case is the only one where the formula is genuinely cheaper, and it is the only one where anybody has a reason to defend it.

And the rule is taught for a reason that survives all of this. Cramer’s rule is how a first course proves that a solution exists and is unique when det A ≠ 0, and the proof is constructive and short. It is also how the inverse’s closed form is derived, how the derivative of a determinant is obtained, and how the adjugate is defined. None of those is a computation, and none of them is diminished by the measurement in this essay.

The failure is entirely in the transfer: a formula proved as an existence argument, carried into a setting where the question is how accurately, with no step in between at which anybody says the two questions are different. That is the same transfer this collection’s whole refutations index is built out of — a theorem, learnt properly, taken one field past the one it was proved over.

What is worth carrying #

Correct and stable are different properties, and only one of them is proved in the first course. Cramer’s rule is correct in the sense a theorem is correct. It is unstable in the sense a measurement is unstable, and no amount of care in stating the theorem changes the measurement.

The cost objection is the small one. A factor of n + 1 is a constant; a backward error with no bound on it is not. A reader who avoids Cramer’s rule because it is slow has the right conclusion for a reason that would not survive a 2×2.

And the cases it fails on are the cases it exists for. A uniformly random 2×2 separates the two methods by a factor of six. A pair of nearly parallel lines separates them by 350. The second is what a 2×2 solve is usually being asked about.

The next essay takes the same measurement to the object Cramer’s rule is a special case of: the inverse that is never formed.