Every boxed entry is a 2 × 2 minor of the matrix beside it
At its defaults it draws every boxed entry is a 2 × 2 minor of the matrix beside it. A 5 × 5 random matrix and its state after 1 step of fraction-free elimination. Each of the 16 boxed entries was formed as (pivot × entry − column × row) divided by the previous pivot, and every one of those 16 divisions came out exact. The reason is that the entry at (i, j) is exactly the 2 × 2 minor of the ORIGINAL matrix on rows 0…0 and i, columns 0…0 and j — checked here against a cofactor expansion of A rather than against a second elimination. The widest number anywhere in the picture is 6 bits.
bareiss-minors is one function in lib/figures/integer.js —
exact arithmetic — no residual to print, and a cost measured in the length of the numbers. Everything below came out of it during this build, at
arguments taken from the essays rather than invented for this page. A figure here is the
figure a reader meets in an essay, and if the generator changes, this page changes with it.
At its defaults
Drawn even though every essay passes arguments — which on this site is every essay, at 100% of placements since the standard pass. A default nothing exercises is a trap for the next essay to call this with none, and this is the page where a default that has drifted from the figures around it becomes visible.
A 5 × 5 random matrix and its state after 1 step of fraction-free elimination. Each of the 16 boxed entries was formed as (pivot × entry − column × row) divided by the previous pivot, and every one of those 16 divisions came out exact. The reason is that the entry at (i, j) is exactly the 2 × 2 minor of the ORIGINAL matrix on rows 0…0 and i, columns 0…0 and j — checked here against a cofactor expansion of A rather than against a second elimination. The widest number anywhere in the picture is 6 bits.
show: "bound"
The arguments are the ones A bound on every intermediate at once passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
Bit lengths against the elimination step, over 12 random 10×10 integer matrices with entries between −6 and 6. The lower curve is the longest intermediate after each step; the upper one is Hadamard's bound on a minor of that size, taken over the largest rows of the original. Every intermediate is a minor of the original, so the upper curve bounds the lower at every step and does. The last step's entry is the determinant, at 27 bits against Hadamard's 36 for the whole matrix — a median slack of 10 bits.
show: "bound", n: 6
The arguments are the ones A bound on every intermediate at once passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
Bit lengths against the elimination step, over 12 random 6×6 integer matrices with entries between −6 and 6. The lower curve is the longest intermediate after each step; the upper one is Hadamard's bound on a minor of that size, taken over the largest rows of the original. Every intermediate is a minor of the original, so the upper curve bounds the lower at every step and does. The last step's entry is the determinant, at 14 bits against Hadamard's 20 for the whole matrix — a median slack of 5 bits.
show: "profile"
The arguments are the ones A bound on every intermediate at once passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
The longest intermediate after each step, as a median over 20 random 10×10 integer matrices, for three pivot rules: swap only when the pivot is zero, take the largest available, take the smallest nonzero. The three make 0, 7 and 7 row exchanges and reach the same peak of 29 bits, because the last entry of the elimination is the determinant and the determinant does not depend on the order. The area under the three profiles is 162, 167 and 156 bit-steps.
show: "bound", n: 12
The arguments are the ones A bound on every intermediate at once passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
Bit lengths against the elimination step, over 12 random 12×12 integer matrices with entries between −6 and 6. The lower curve is the longest intermediate after each step; the upper one is Hadamard's bound on a minor of that size, taken over the largest rows of the original. Every intermediate is a minor of the original, so the upper curve bounds the lower at every step and does. The last step's entry is the determinant, at 33 bits against Hadamard's 45 for the whole matrix — a median slack of 9 bits.
show: "reuse-families"
The arguments are the ones An order found once knows what the rows know passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
Twelve members a family, entries from minus six to six, every one of the 40,320 row orders costed with each multiplication charged at the product of its operands' bit lengths. independent entries: natural order 1.600, the median order 1.717, another member's best 1.540, best over the other eleven 1.458, rows by their norms 1.495, smallest pivot entry 1.240. a shared zero pattern: natural order 1.652, the median order 1.716, another member's best 1.592, best over the other eleven 1.361, rows by their norms 1.349, smallest pivot entry 1.076. shared row scales: natural order 1.884, the median order 1.860, another member's best 1.126, best over the other eleven 1.156, rows by their norms 1.049, smallest pivot entry 1.014. one matrix, two entries redrawn: natural order 1.280, the median order 1.511, another member's best 1.155, best over the other eleven 1.070, rows by their norms 1.421, smallest pivot entry 1.136.
What it checked while drawing
Every figure above checked its own claims on the way to being drawn, and a claim that failed
would have stopped the picture rather than shipped a wrong one. Those checks used to leave
no trace at all: a passing one returned true and the only evidence the figure had
checked anything was that nothing crashed. The list below is what they actually said, collected
by running this generator with an observer installed — not a description of
what it is believed to check.
42 distinct claims across 6 sets of arguments, grouped below by shape — because most of them are one sentence with a different number in it, and how many separate times that sentence was put to the test is the informative part.
the step-0 intermediates are inside the bound on their own minors — checked 12 times
a family the dial draws
a family the library builds
a family this file draws
a growth view this figure draws
a look-ahead rule this elimination implements
a look-ahead rule this figure draws
a matrix small enough to print every minor of
a pivot rule this elimination implements
a size every row order can be run at
a size the exact elimination is affordable at
although the rules make different choices
an elimination step to display
and almost every draw is nonsingular
and so does the largest rule
and the determinant is inside Hadamard's bound on the whole matrix
and the smallest-pivot rule keeps the whole profile below the natural order's
every Bareiss division is exact
every Bareiss division is exact under the largest rule
every Bareiss division is exact under the none rule
every Bareiss division is exact under the smallest rule
every division in the step is exact
no pivot is zero at this step on this family
the family builds at this size
the intermediate is the minor Sylvester's identity names
the largest rule reaches the same peak as the natural order
the none rule reaches the same peak as the natural order
the smallest rule reaches the same peak as the natural order
which is at least the determinant's own length
with the bound never attained
with the largest-pivot rule no lower than it
Against the rule
The rule does not apply to it. It factorises nothing, so there is no residual it could be withholding. That is worth stating rather than leaving blank: a site that reported the rule as satisfied by every generator would be counting mostly generators the rule never reached.
Across the library: the rule bites on 217
of 397 generators —
199 print a residual and
18 are exempt with a published reason;
180 factorise nothing.
Read from lib/residual-rule.js, which is the same body the gate enforces from,
and the gate's last check fails the build if this page and it disagree about any generator.
Where it is called
Changing this generator changes every figure on this list. That is what makes the list worth publishing rather than keeping in a check script.
A bound on every intermediate at once
Fraction-free elimination's intermediates are minors of the original, which is a theorem about exactness. It is also a bound: Hadamard's inequality applies to every minor, so one inequality bounds the whole run before it starts. The bound on the k-th step is the one on (k+1)×(k+1) minors, not the one on the whole matrix — and on a 10×10 with entries in ±6 the difference is ten bits, with the run reaching 2.7 bits a step against the bound's 3.4.
Exact arithmetic, and what it costs insteadAn order found once knows what the rows know
Searching for a fraction-free elimination's least-cost row order costs forty to two hundred and sixty times the elimination, so it can only pay if one order serves a whole family. The prediction was that it cannot: the best order depends on which rows happen to have short entries, so a reused order should do no better than the natural one. On independent entries and on a shared zero pattern that holds — another member's best order is an ordinary order, at the middle of the 40,320. On a family that shares its row scales it fails completely: another member's order costs a median 1.13 of the least where the natural order costs 1.88. But on every family, including that one, the rule that just takes the smallest pivot entry is cheaper than any reused or trained order — 1.24, 1.08 and 1.01. What an order carries from one matrix to the next is what the family shares — and only when that is a particular matrix, not a visible structure, does an order trained on the family beat the rule.
Exact arithmetic, and what it costs insteadEvery intermediate is a minor
Fraction-free elimination divides by the previous pivot at every step and the division is always exact. Not usually, not for these entries — always, because the number being divided is a determinant with that pivot as a factor, which is a theorem and is checked here against the minors themselves.
Exact arithmetic, and what it costs insteadThe pivot is in every product
A fraction-free elimination's intermediates are minors, and Hadamard bounds a minor by the lengths of the rows it is made of — so the rule that picks the smallest pivot entry looked like a proxy for a rule that picks the shortest row. Measured, the two keep the bit-length profile equally low: 0.969 and 0.966 of the natural order's area. They part on what the arithmetic costs. Counting every multiplication and division at the product of its operands' lengths, the smallest-pivot rule costs 0.70 of the natural order and the shortest-row rule 0.84, because the pivot multiplies every entry of the step and divides every entry of the next. Three per cent of area is thirty per cent of arithmetic.
Exact arithmetic, and what it costs insteadThree orders and one last entry
Over the integers there is no stability to pivot for, so a fraction-free elimination swaps rows only when the pivot is zero. Choosing a pivot for length instead does change the sequence of minors — the smallest-nonzero rule makes seven exchanges where the natural order makes none and keeps the profile two bits lower through the middle. It cannot change the peak. The last entry of the elimination is the determinant, and the determinant does not know what order it was computed in.
Exact arithmetic, and what it costs insteadWhat reading the next pivot buys
In a fraction-free elimination every pivot is paid for twice — it multiplies every entry of its own step and divides every entry of the next — and the rule that picks the smallest pivot entry left a median 20 per cent above the least arithmetic any row order reaches. A rule that charges two steps ahead brings the median matrix to within 2.5 per cent, and on one matrix of twenty-four costs 1.87 times the least, worse than the smallest pivot ever does. Charging three steps ahead finds the least of all 40,320 orders on thirteen matrices and is never more than 27 per cent above it. And none of it pays: choosing that way costs forty to two hundred and sixty times the elimination it chooses.