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.

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.