A bound on every intermediate at once

Every intermediate is a minor established the theorem the whole fraction-free construction rests on. At step k of Bareiss’s elimination each entry of the trailing submatrix is a (k+1)×(k+1) minor of the original matrix — not approximately, and not for these entries — and the division by the previous pivot is exact because Sylvester’s identity says the numerator has that pivot as a factor.

The essay used the theorem for what it is usually used for, which is exactness: the division leaves no remainder, so the elimination stays in the integers and the fractions that would otherwise appear never do. That is the whole reason the method exists.

It buys a second thing that the exactness argument does not mention. A minor is a determinant, determinants have a bound, and the bound applies to every intermediate the elimination will ever produce — before a single division is done.

The bound that applies is not the bound that is quoted #

The answer is longer than the question is where this field’s central quantity — the length of an exact answer — is measured, and the bound below is where it comes from. Hadamard’s inequality says $|\det A| \le \prod_i \|a_i\|$ over the rows. The standard statement about fraction-free elimination quotes it for the whole matrix and concludes that the intermediates cannot exceed the determinant’s length.

That is true and it is loose everywhere except the last step. At step k the entries are (k+1)×(k+1) minors, and the largest such minor is bounded by the product of the k+1 largest row norms — a shorter product, and a much smaller number. On a 10×10 with entries between −6 and 6 the two bounds read

and the elimination actually reaches 3, 6, 8, 11, 14, 17, 20, 22, 24 and 27 bits.

So the quoted bound is out by a factor of twelve at the first step and by ten bits at the last. The per-step bound is out by two to nine bits and is out in the same direction at every step, which is what a bound that is being approached rather than attained looks like.

It is worth separating three statements that the phrase “the intermediates are bounded” runs together.

The first is that they are bounded at all, which is the theorem: a minor of an integer matrix is an integer and Hadamard bounds it. Without the fraction-free step there is no such statement — the rational elimination’s entries are quotients of products of previous entries and nothing bounds them except by tracking the arithmetic.

The second is that the bound is computable before the run, which follows because it depends on the original matrix’s rows and nothing else. That is what makes it useful to an implementation rather than to a proof.

The third is that the bound applies per step rather than once, which is the part the standard statement drops. It drops it for a good reason — the theorem people want is about the worst case, and the worst case is the last step — and the consequence is a bound that is out by an order of magnitude for most of the run.

Both bounds are checked, at every step #

What is checked behind the figure is not that the growth looks bounded. It checks, for twelve random 10×10 matrices and for every one of the ten steps, that the longest intermediate is inside the bound on minors of that step’s size — one hundred and twenty comparisons — and separately that the determinant is inside Hadamard’s bound on the whole matrix.

It also checks that the second bound is never attained. The median slack between Hadamard’s bound on the whole matrix and the determinant’s actual length is ten bits, and the smallest over the twelve draws is positive. A bound attained by a random matrix would be a bound about the wrong thing: Hadamard’s is attained exactly when the rows are orthogonal, and random integer rows in ten dimensions are nearly orthogonal but not exactly, so the gap is small and never zero.

Why both curves are straight #

The shape is the easiest part of the picture to over-read, so it is worth saying where it comes from.

Hadamard’s bound on a (k+1)×(k+1) minor is a sum of k+1 row log-norms, so the bound is exactly linear in k with a slope equal to the typical row’s log-norm — 3.4 bits a step for rows of ten entries in ±6, which is ½·log₂(10·36) ≈ 4.2 minus the effect of taking the largest rows first.

The growth is also nearly linear, at 2.7 bits a step, and its linearity has a different cause. A (k+1)×(k+1) minor of a random matrix is a sum of (k+1)! signed products, and its typical size is governed by a central-limit cancellation rather than by the worst case — so it grows like the geometric mean of the rows rather than like the product of their norms, which is the same linear form with a smaller constant.

Two straight lines with different slopes: the bound rising 26 per cent faster than the thing it bounds, which is why the gap opens from two bits to nine over ten steps rather than staying fixed.

An answer with no error in it is where this field’s economics are set out — an exact answer costs what it costs because the answer is longer than the question — and the per-step curve is that statement made continuous. The answer’s length is the last point of the curve; every earlier point is how much of it the elimination has accumulated by then.

What a bound before the run is for #

Knowing the length of the longest intermediate before doing the elimination is not a curiosity. It is what lets an exact code allocate.

A fraction-free elimination over the integers has entries whose length changes at every step, and an implementation either allocates for the worst case or grows its numbers dynamically. Growing dynamically costs an allocation and a copy at every promotion; allocating for the worst case costs memory proportional to the bound. The per-step bound makes a third option available — allocate per step, at the length that step’s minors can reach — which is a factor of the number of steps smaller than the worst case in total.

Whether that is worth doing is a question about an implementation this field does not have. What the measurement supplies is the number the decision would need: the per-step bound is tight to within two to nine bits, so an allocation made from it is never wrong and is never wasteful by more than a word.

And what the bound does not say #

The bound is about the intermediates and the intermediates are not the cost.

The answer is longer than the question is the standing measurement of what the growth costs, and the cost of an integer multiplication is not linear in the length of its arguments — so a run whose entries reach twenty-seven bits does not cost twenty-seven times a run whose entries reach one. The bound says how many bits, and a cost model says what a bit is worth, and the two are separate.

Nor does the bound distinguish the elimination from the alternatives. The determinant’s length is a property of the matrix: every exact method that computes it must produce an integer of that length, so 27 bits is a floor on the output of Bareiss, of the rational elimination, and of the modular route. What distinguishes the three is what they produce on the way there, and that is what the per-step curve is a statement about.

The bound that is a floor #

One thing the last point of the curve is, and the earlier points are not, is a floor as well as a ceiling.

The determinant of an integer matrix is an integer and its length is whatever it is. Any exact method that produces it must produce that many bits — Bareiss, the rational elimination, the modular route with enough primes — so 27 bits is not a cost the fraction-free algorithm incurs, it is a cost the problem has. An exact answer to a measured problem is the essay about when that cost is worth paying at all, and three orders and one last entry is the measurement that no pivot rule reduces it.

What the curve says is that Bareiss pays it gradually: 3 bits after one step, 14 after five, 27 at the end. A method whose intermediates jumped to 27 bits immediately would do the same total arithmetic on longer numbers, and a method whose intermediates exceeded 27 would be carrying length the answer does not need. The rational elimination is the second kind, which is what the field’s opening figure shows and why the middle curve is the interesting one.

So the per-step bound is not only an allocation aid. It is the statement that the fraction-free elimination’s intermediates are as short as any method’s could be at each stage, up to the gap between a minor’s typical size and its Hadamard bound — because they are minors, and a minor of that size is what any method must have in hand to produce the determinant.

What must fail for any of this to be wrong #

Three claims. That every step’s longest intermediate is inside the bound on minors of that step’s size, checked at every step of every draw. That the determinant is inside Hadamard’s bound on the whole matrix. And that the bound is never attained, with a median slack of ten bits, which is what makes it a bound about a worst case rather than a description.

The bound is computed by two routes that agree by construction: one sums the row log-norms of the whole matrix, and the per-step bound sums the largest $k+1$ of them. The second reduces to the first at k = n−1, which is the check that they are the same inequality applied to different sets.

Reading the two slopes as a prediction #

The gap between the two curves opens linearly, at 0.7 bits a step on the 10×10, and that is a number worth turning into a prediction because it is the one thing in the measurement that would fail loudly if the mechanism proposed above were wrong.

If the bound rises at the typical row’s log-norm and the growth rises at something smaller because of cancellation inside the minor, then both slopes should scale together with the entry range and neither should depend much on the size. Doubling the range of the entries adds one bit to every row’s log-norm, so both slopes should rise by about one, and the ratio 2.7 : 3.4 should stay where it is.

Changing the size should change neither slope, only the number of steps — which is what the 6×6 figure shows: the same two straight lines, cut short.

Neither prediction is swept here and both are one parameter away. What the figure does show is the second of them at two sizes, which is the cheaper half, and it holds.

The prediction that would be most informative is the negative one. A matrix family whose rows are nearly parallel has a Hadamard bound far above its determinant — the inequality is attained only for orthogonal rows — so the gap between the two curves should be much wider and the per-step bound correspondingly less useful. The scaled Hilbert family this library builds is exactly that, and running the same comparison on it is the measurement that would say whether “tight to within two to nine bits” is a property of the bound or of random matrices.

A note on measuring bits #

matBits returns the longest entry of a matrix in bits, and “bits” here means the number of binary digits the integer’s magnitude needs, which for a BigInt is what its string length in base two reports. It is not a memory figure: an implementation stores in words, so an entry of 27 bits and one of 32 occupy the same space and one of 65 occupies three words rather than two.

That matters for the allocation argument above and it does not matter for the bound. The bound is about the integers and the words are about a machine, and the conversion is a ceiling division by the word size — which is why the per-step curve’s usefulness to an allocator depends on the step at which it crosses a word boundary rather than on its value.

On the 10×10 measured, the curve crosses 32 bits nowhere: every intermediate fits in one 32-bit word and the whole question is moot. At 20×20 with the same entry range the determinant would be about 60 bits and the crossing would happen around step 11, which is where a per-step allocator would first differ from a worst-case one. Neither size is measured here and the arithmetic is the linear slope above.

What this does not settle #

Random integer matrices with entries in a fixed range, at four sizes. A matrix whose rows have very different norms would separate the per-step bound from a naive one more sharply, and a matrix whose rows are nearly parallel would make both loose.

The bound is on bit lengths and the measurement is of matBits, the longest entry of the whole trailing submatrix at each step. The typical entry is shorter, and an implementation allocating per entry rather than per step would want the distribution rather than the maximum.

No structured families: the Hilbert-like, Pascal and unitriangular families this field builds elsewhere have minors with very different behaviour, and the unitriangular one has no growth at all by construction.

And nothing here is about the rational route’s growth, which is the comparison the field opens on and is governed by a different mechanism — products of previous numerators and denominators rather than minors of the original.

What the exactness argument and the length argument share #

The two things the minor theorem buys are worth setting side by side, because they are the same fact read twice and only one of the two is ever put to work.

Exactness: the numerator at step k is a (k+1)×(k+1) minor and has the previous pivot — a k×k minor — as a factor, so the division leaves no remainder. That is Sylvester’s identity, it is what the first of these essays checks against cofactor expansion, and it is a statement about divisibility.

Length: the same entry is a (k+1)×(k+1) minor, so Hadamard bounds it. That is a statement about magnitude and it uses nothing about divisibility.

Both follow from one identification of the intermediate with a minor, and neither implies the other — an algorithm could produce minors without exact division, and an algorithm with exact division could produce quantities that are not minors. What Bareiss does is arrange for the intermediates to be minors, and then both statements arrive at once.

That is the shape of argument this field keeps meeting. A construction is justified by one property and turns out to carry a second, and the second is invisible because the first is what the construction was for. One number that has to be right is the same shape in the orthogonality field: one fact about a unit vector, two consequences, and only one of them in the derivation.

Still open: the distribution, the structured families, and what the bound is worth to an implementation #

The distribution rather than the maximum. Every number above is the longest entry at each step. An allocator would want the median and the tail, and the gap between them says whether per-step allocation is nearly free or mostly wasted.

The families with structure. A Hilbert-like matrix’s minors are tiny and its rational elimination’s are enormous, which is the opposite extreme from a random integer matrix. Running the same per-step comparison on the three families this library builds would say whether the 26 per cent slope gap is a property of random matrices or of the bound.

What the bound is worth in seconds. The per-step bound would let a code allocate exactly, and whether that beats growing dynamically depends on an allocator this field does not have. It is the one open question here that cannot be answered by a measurement of integers.

And whether the pivot order moves any of it. The elimination above swaps rows only when the pivot is zero. A different order produces a different sequence of minors, and whether the per-step bound is reached more or less closely under one is the next essay.