Three orders and one last entry

Gaussian elimination in floating point chooses a pivot at every step and every stability property it has comes from making that choice well. Over the integers the arithmetic is exact, a small pivot amplifies nothing, and the fraction-free elimination therefore swaps rows only when it must — when the pivot is zero and the column has to be searched for a nonzero one.

That is the published algorithm and it is correct. It also leaves a decision unexamined, because there is a second thing a pivot choice could be for. Every intermediate is a minor and the minors are bounded by the rows they come from, so a different pivot order is a different sequence of minors — and minors have sizes.

Choosing the pivot for size is therefore a real option with a real mechanism behind it. It changes the profile by a few per cent and it cannot change the peak at all.

Three rules that genuinely differ #

An answer with no error in it is where the exact route’s economics are set out, and nothing in them mentions a pivot. The rules are: swap only when the pivot is zero; take the largest available entry in the column, which is partial pivoting; and take the smallest nonzero, which is what a bit-length argument would suggest, since a smaller pivot is a smaller factor in the minors that follow.

They are not variants of one rule. Over twenty random 10×10 integer matrices with entries between −6 and 6 the three make a median of 0, 7 and 7 row exchanges, and their step-by-step profiles differ:

The smallest-nonzero rule is one to three bits below the natural order from step three onward, and the largest-pivot rule is one bit above it at two steps. Summed over the run, the area under the three profiles is 156, 162 and 167 bit-steps — a spread of seven per cent, with the smallest rule the lowest and the largest rule the highest, in exactly the direction the mechanism predicts.

And one number they cannot move #

The last column is the same under all three, and not approximately.

The final entry of a fraction-free elimination is the determinant, up to the sign the row exchanges introduce. The determinant of an integer matrix is an integer that the matrix has, not something an algorithm produces — so its length is a property of the input and no ordering can shorten it. Twenty-nine bits, under every rule, on every draw.

Since the profiles rise monotonically and the last entry is the largest, the peak of each profile is the determinant’s own length. Three rules, three sequences of minors, one peak — because the peak is not a minor of intermediate size, it is the one minor that is the whole matrix.

That settles the practical question and settles it against the idea. A code allocating for the worst case allocates for the determinant, and no pivot rule reduces what it has to allocate. What a rule can do is keep the intermediates shorter while they are intermediate, which is worth something only to an implementation whose cost depends on the lengths it is holding rather than on the longest one it will hold.

An option that had to be written before it could be measured #

The published routine has no pivot rule to choose. Its swap is inside a conditional on the pivot being zero, and there is no argument, no branch and no record that a choice exists — which is the ordinary condition of a decision nobody has had a reason to question.

Adding a pivot-rule argument to the elimination, and checking that all three settings return the same determinant up to sign and that every division is exact under each, is what turns an edit into a measurement. The same arrangement this phase has needed three times: a constant becomes a parameter, the parameter becomes a sweep, and the sweep says what the constant was worth.

Here it was worth nothing, which is the answer that could not have been assumed either way. The mechanism — minors are bounded by the rows they are built from, so a smaller pivot row means smaller minors — is sound and predicts a saving. What it does not predict, and what only the measurement supplies, is that the saving is bounded above by zero at the one point that matters.

Why the smallest pivot is the right direction #

The mechanism is worth stating because it is the opposite of the floating-point one and the reasoning is short.

At step k the entry in position (i, j) is a (k+1)×(k+1) minor whose rows are the k pivot rows used so far plus row i. Its size is governed by the product of those rows’ norms — Hadamard again — so a pivot row with a small norm contributes a small factor to every minor built on it.

Choosing the smallest nonzero entry is not the same as choosing the smallest-norm row, which is the first thing to say about the measurement: the rule implemented picks on the entry in the pivot column, which is a proxy. That it moves the profile in the right direction at all is therefore mild evidence that the proxy correlates with the row norm on random matrices, and no evidence that it is the right proxy.

The floating-point rule is the opposite for a reason that has nothing to do with size. Partial pivoting takes the largest entry because the multiplier is the ratio of the entry to the pivot and a bound of one on it is what keeps the growth factor controlled. Over the integers there is no multiplier — the elimination is a cross-product followed by an exact division — so the quantity partial pivoting protects does not exist, and the quantity a rule could protect is the one it makes worse.

There is a second reason the smallest-entry rule cannot be the right rule and it is worth noticing because it is about the algorithm rather than about the proxy. The entry the rule chooses on is itself an intermediate — a k×k minor at step k — and a small one is not evidence of a small row so much as evidence of cancellation in that particular minor. Cancellation in one minor says nothing about the next, so the rule is reading a quantity whose correlation with what it wants decays as the elimination proceeds.

That is consistent with the profiles. The smallest rule’s advantage is largest in the middle — two to three bits at steps three to eight — and gone at the last step, which is where the peak is and also where the rule has the least information.

What is not affected either #

Two other quantities are worth checking because a reader would reasonably expect one of them to move.

An exact answer to a measured problem is the essay about whether any of this is worth paying for, and a pivot rule that changed the cost would be the first thing it would want. It does not. The number of divisions does not change. Bareiss does (n−k−1)² divisions at step k whatever the order, so all three rules do the same n(n−1)(2n−1)/6 exact divisions — and every one of them is exact under every rule, which is the thing each of the three eliminations checks and which would fail immediately if a reordering broke Sylvester’s identity.

It does not, and that is worth one sentence. Sylvester’s identity is stated for the leading principal minors, and a row exchange changes which minors are leading. The identity survives because a row permutation of an integer matrix is an integer matrix and the identity holds for it — so the elimination after a swap is the natural-order elimination of a different matrix, whose determinant differs by a sign. Every division being exact under all three rules is the check that the reasoning is right rather than plausible.

And the determinant’s value is identical, not merely its length. The three rules return the same integer up to the sign the exchange count implies, which is the strongest statement available that the three are the same computation differently ordered.

The contrast with the same question in floating point #

The order the greedy rule cannot choose measured the same question in floating point and got the opposite shape of answer. There the pivot order changes the growth factor by $2^{n-2}$ on the matrix built to defeat the rule, the greedy choice is wrong on a real share of random matrices, and an exhaustive search over orderings finds something the rule cannot.

Here the order changes the profile by seven per cent and the peak by nothing. The two measurements are about different quantities and the difference is instructive: floating-point growth is an accumulation that compounds, and a bad decision early is amplified by every later step. Integer growth is a fact about the minors, each one determined by the original matrix and the set of rows used so far — so an early decision changes which minors appear and not how large minors can be.

Put another way, the floating-point elimination has a state that a bad pivot corrupts, and the exact elimination has a state that is always a minor of the input whatever has been done to it. That is what Sylvester’s identity buys and it is why there is so little for a pivot rule to do.

What must fail for any of this to be wrong #

Four claims and a refusal. That every rule reaches the same peak, which is the finding. That the peak is at least the determinant’s own length, which is what makes the first claim an explanation rather than a coincidence. That the rules make different numbers of exchanges, which is what stops the comparison being vacuous. And that the smallest-pivot rule’s profile has less area under it than the natural order’s, with the largest-pivot rule’s no lower — which is the direction the mechanism predicts and is the only thing a rule buys.

The refusal is fed the claim that some rule reaches a smaller peak.

All three eliminations are one routine with a rule argument, and each verifies its own divisions are exact, so a reordering that broke the identity would fail rather than produce a wrong answer quietly.

What a pivot rule is for, in three fields #

Three fields now have a measurement of what a pivot choice buys, and putting them together is worth a paragraph because the three answers are different for three reasons.

In floating point the pivot bounds the multiplier, the multiplier bounds the growth, and growth compounds — so a single bad choice is amplified by every later step, and the order the greedy rule cannot choose finds $2^{n-2}$ between a rule’s answer and the best one.

In sparse elimination the pivot decides which edges the elimination creates, the fill compounds through the elimination graph, and the order decides the memory finds factors of nearly two between orderings on one matrix — with the least fill there is establishing what the best available order would have been.

Over the integers the pivot decides which minors appear, and minors do not compound — each is determined by the original matrix and a set of rows, and the last one is determined by the matrix alone. So the answer is seven per cent of an area and nothing at all of a peak.

The common thread is that a pivot rule is worth whatever the quantity it controls compounds by. Where the state accumulates, the choice is everything; where the state is always a function of the input, there is nothing for a choice to accumulate into.

What a zero pivot is, and why it is the only forced swap #

The published rule swaps only on a zero pivot, and the zero deserves a sentence because over the integers it means something sharper than it does in floating point.

A floating-point elimination almost never meets an exact zero; what it meets is a pivot small enough that the multipliers formed against it are large, and “small enough” is a judgement about magnitudes. An integer elimination meets exact zeros routinely — a matrix with structure has them by construction — and a zero pivot is not a degree of difficulty but an arithmetic impossibility: the division by it does not exist.

So the swap in the published routine is not a stability measure that happens to be rare. It is the one case the algorithm cannot proceed through, and searching the column for a nonzero is the only decision Bareiss is obliged to make. Everything this essay sweeps is a decision it is not obliged to make, which is why the answer being “it changes nothing that matters” is the answer the published routine already assumed.

The one place the zero is more than an inconvenience is where the whole column is zero, which means the determinant is zero — and the routine returns it as such rather than skipping the step, which is a correction this library’s own ledger records as having been needed.

What this does not settle #

Random integer matrices with entries in a fixed range, at two sizes, twenty draws. A structured family — the scaled Hilbert, the Pascal, the unitriangular — would have very different minors and the unitriangular one has no growth at all by construction.

The pivot rules choose on the entry in the pivot column, which is a proxy for the row norm the mechanism is about. A rule choosing on the row norm directly is one line away and is not measured.

The measure is matBits, the longest entry of the trailing submatrix at each step, so the profile is a maximum and the area under it is an area under maxima. An implementation’s memory depends on all the entries, and the typical one is shorter.

And nothing here searches over orderings. The three rules are three heuristics; whether some ordering makes the middle of the profile dramatically shorter — the analogue of what the exhaustive search found in floating point — is unknown, and the peak is provably immovable either way.

What the peak being fixed is good for #

A quantity that no decision can move is usually reported as a limitation, and here it is a guarantee worth having.

An exact code that has to allocate knows, before it starts, exactly how long its longest intermediate will be: the determinant’s length, bounded by Hadamard’s inequality on the original rows. No reordering, no heuristic, no adversarial input can exceed it. That is a much stronger statement than anything available in floating point, where the growth factor’s bound is $2^{n-1}$ and the question of whether a matrix attains it is the subject of a whole field.

It also means an exact elimination has no bad cases in the sense the floating-point one does. There is no integer matrix on which a fraction-free elimination’s intermediates blow up relative to its determinant, because they are minors of the input and the input’s minors are what they are. The rational elimination has bad cases — its entries are quotients of products of previous entries and nothing ties them to the input — which is the whole reason the fraction-free step exists and is the field’s opening measurement.

So the finding reads two ways. As an answer to “should a pivot rule choose for length”, it is no. As a statement about the algorithm, it is that the quantity a pivot rule would have tried to control is already controlled, by the same theorem that makes the divisions exact.

Still open: the row-norm rule, the structured families, and whether the middle can be searched #

A rule that reads the row norm. The mechanism says the minors are bounded by the norms of the rows used, so the rule should pick the smallest-norm available row rather than the smallest entry. That is one line and would say whether the seven per cent is the proxy’s or the mechanism’s.

The families with structure. A matrix whose rows differ wildly in norm gives a pivot rule much more to work with, and the scaled Hilbert family this library builds is exactly that. The prediction is a larger separation in the middle and the same peak, and the second half of it is a theorem rather than a guess.

Searching the middle. The peak cannot move; the area can. Whether an exhaustive search over orderings at n = 8 finds a profile substantially below the smallest-pivot rule’s — the same instrument the sparsity field uses for fill — would say whether seven per cent is most of what is available or a small part of it.

And whether any of it is worth a second. The whole of the difference is in intermediate lengths, and the cost of an integer multiplication is superlinear in its arguments’ lengths. Seven per cent of the area is not seven per cent of the time, and which way the conversion goes depends on a cost model this field states and does not measure.