Three exact eliminations of the same random matrix, and the widest number each one forms
At its defaults it draws three exact eliminations of the same random matrix, and the widest number each one forms. Every route here returns the same determinant exactly, so there is no error to plot and the y-axis is the length of the intermediates in bits. At n = 11 the answer itself is 33 bits and Hadamard's bound allows 47. Fraction-free elimination never forms a number wider than 35 bits, because each of its intermediates is a minor of the original matrix. Rational elimination that reduces every fraction to lowest terms reaches 35 bits and pays a gcd on every arithmetic operation to stay there. Rational elimination that does not reduce reaches 341287 bits — 9750 times the width of the fraction-free route and 10300 times the width of the answer. All three are correct.
bit-swell 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.
Every route here returns the same determinant exactly, so there is no error to plot and the y-axis is the length of the intermediates in bits. At n = 11 the answer itself is 33 bits and Hadamard's bound allows 47. Fraction-free elimination never forms a number wider than 35 bits, because each of its intermediates is a minor of the original matrix. Rational elimination that reduces every fraction to lowest terms reaches 35 bits and pays a gcd on every arithmetic operation to stay there. Rational elimination that does not reduce reaches 341287 bits — 9750 times the width of the fraction-free route and 10300 times the width of the answer. All three are correct.
family: "random", upTo: 12
The arguments are the ones An answer with no error in it passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
Every route here returns the same determinant exactly, so there is no error to plot and the y-axis is the length of the intermediates in bits. At n = 12 the answer itself is 40 bits and Hadamard's bound allows 52. Fraction-free elimination never forms a number wider than 40 bits, because each of its intermediates is a minor of the original matrix. Rational elimination that reduces every fraction to lowest terms reaches 39 bits and pays a gcd on every arithmetic operation to stay there. Rational elimination that does not reduce reaches 1422165 bits — 35600 times the width of the fraction-free route and 35600 times the width of the answer. All three are correct.
family: "random", upTo: 5
The arguments are the ones An answer with no error in it passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
Every route here returns the same determinant exactly, so there is no error to plot and the y-axis is the length of the intermediates in bits. At n = 5 the answer itself is 15 bits and Hadamard's bound allows 18. Fraction-free elimination never forms a number wider than 15 bits, because each of its intermediates is a minor of the original matrix. Rational elimination that reduces every fraction to lowest terms reaches 15 bits and pays a gcd on every arithmetic operation to stay there. Rational elimination that does not reduce reaches 85 bits — 5.67 times the width of the fraction-free route and 5.67 times the width of the answer. All three are correct.
family: "random", upTo: 13
The arguments are the ones An answer with no error in it passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
Every route here returns the same determinant exactly, so there is no error to plot and the y-axis is the length of the intermediates in bits. At n = 13 the answer itself is 44 bits and Hadamard's bound allows 56. Fraction-free elimination never forms a number wider than 44 bits, because each of its intermediates is a minor of the original matrix. Rational elimination that reduces every fraction to lowest terms reaches 44 bits and pays a gcd on every arithmetic operation to stay there. Rational elimination that does not reduce reaches 1120288 bits — 25500 times the width of the fraction-free route and 25500 times the width of the answer. All three are correct.
family: "random", upTo: 8
The arguments are the ones An answer with no error in it passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
Every route here returns the same determinant exactly, so there is no error to plot and the y-axis is the length of the intermediates in bits. At n = 8 the answer itself is 24 bits and Hadamard's bound allows 32. Fraction-free elimination never forms a number wider than 24 bits, because each of its intermediates is a minor of the original matrix. Rational elimination that reduces every fraction to lowest terms reaches 23 bits and pays a gcd on every arithmetic operation to stay there. Rational elimination that does not reduce reaches 4938 bits — 206 times the width of the fraction-free route and 206 times the width of the answer. All three are correct.
family: "wide", upTo: 10
The arguments are the ones An answer with no error in it passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
Every route here returns the same determinant exactly, so there is no error to plot and the y-axis is the length of the intermediates in bits. At n = 10 the answer itself is 103 bits and Hadamard's bound allows 110. Fraction-free elimination never forms a number wider than 103 bits, because each of its intermediates is a minor of the original matrix. Rational elimination that reduces every fraction to lowest terms reaches 103 bits and pays a gcd on every arithmetic operation to stay there. Rational elimination that does not reduce reaches 754790 bits — 7330 times the width of the fraction-free route and 7330 times the width of the answer. All three are correct.
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.
6 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.
a family the library builds
a size the exact routes are run to
at least two sizes to draw
Bareiss's widest intermediate is inside Hadamard's bound on a minor
every Bareiss division is exact
fraction-free and rational elimination return the same integer determinant
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 answer with no error in it
An integer matrix eliminated over the rationals rounds nothing, so the forward error is zero, the residual is the zero vector, and the identity this site is built on has no terms left. The cost does not vanish with the error. It moves into the length of the numbers, where three correct routes differ by four orders of magnitude.
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 answer is longer than the question
An exact solution of an integer system is a vector of fractions, each of them a ratio of two determinants. So the output carries 2n long integers where the input carried n² short ones, and no algorithm can write it down more cheaply — the length of the answer is a floor under every exact solver rather than a property of one.
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.