5 × 5: the invariant factors, computed twice by routes with no algorithm in common
At its defaults it draws 5 × 5: the invariant factors, computed twice by routes with no algorithm in common. The Smith normal form of a random matrix of order 5 is the diagonal [1, 1, 1, 1, 22616], reached by unimodular row and column operations, with each entry dividing the next — a property the elimination does not give and which has to be enforced and asserted. The same numbers computed from the definition — the gcd of all k × k minors, over the gcd of all (k−1) × (k−1) minors — are [1, 1, 1, 1, 22616], and the two agree entry for entry. Their product is 22616, which is |det A| = 22616. The Hermite form of the same matrix reaches 24 bits against the Smith form's 15, and its transform has determinant -1, so the lattice the rows generate is unchanged.
normal-form 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.
The Smith normal form of a random matrix of order 5 is the diagonal [1, 1, 1, 1, 22616], reached by unimodular row and column operations, with each entry dividing the next — a property the elimination does not give and which has to be enforced and asserted. The same numbers computed from the definition — the gcd of all k × k minors, over the gcd of all (k−1) × (k−1) minors — are [1, 1, 1, 1, 22616], and the two agree entry for entry. Their product is 22616, which is |det A| = 22616. The Hermite form of the same matrix reaches 24 bits against the Smith form's 15, and its transform has determinant -1, so the lattice the rows generate is unchanged.
family: "random", n: 6
The arguments are the ones A prime that divides the answer passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
The Smith normal form of a random matrix of order 6 is the diagonal [1, 1, 1, 1, 1, 40098], reached by unimodular row and column operations, with each entry dividing the next — a property the elimination does not give and which has to be enforced and asserted. The same numbers computed from the definition — the gcd of all k × k minors, over the gcd of all (k−1) × (k−1) minors — are [1, 1, 1, 1, 1, 40098], and the two agree entry for entry. Their product is 40098, which is |det A| = 40098. The Hermite form of the same matrix reaches 27 bits against the Smith form's 16, and its transform has determinant -1, so the lattice the rows generate is unchanged.
show: "mod-bits"
The arguments are the ones Every entry under the determinant passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
n = 4: plain form 21, transform 18, finished transform 10; modular stored 13, unreduced 25; determinant 13 bits; n = 8: plain form 72, transform 69, finished transform 23; modular stored 26, unreduced 51; determinant 26 bits; n = 12: plain form 149, transform 145, finished transform 35; modular stored 44, unreduced 88; determinant 44 bits; n = 16: plain form 307, transform 304, finished transform 58; modular stored 60, unreduced 120; determinant 60 bits; n = 20: plain form 450, transform 445, finished transform 73; modular stored 78, unreduced 155; determinant 78 bits; n = 24: plain form 696, transform 693, finished transform 95; modular stored 98, unreduced 196; determinant 98 bits; n = 32: plain form 1328, transform 1327, finished transform 128; modular stored 132, unreduced 263; determinant 132 bits; n = 40: plain form 2233, transform 2230, finished transform 174; modular stored 177, unreduced 354; determinant 177 bits; n = 48: plain form 3371, transform 3366, finished transform 209; modular stored 219, unreduced 437; determinant 219 bits; n = 64: plain form 7382, transform 7379, finished transform 298; modular stored 302, unreduced 604; determinant 302 bits; n = 72: plain form 10132, transform 10129, finished transform 337; modular stored 343, unreduced 685; determinant 343 bits; n = 80: plain form 13835, transform 13832, finished transform 387; modular stored 390, unreduced 780; determinant 390 bits. Both routes return the same form at every size.
show: "mod-trace", n: 24
The arguments are the ones Every entry under the determinant passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
Plain form after each column: 7, 11, 13, 19, 31, 41, 51, 62, 84, 109, 128, 158, 185, 221, 259, 293, 329, 374, 428, 489, 540, 604, 696, 98 bits. Modular stored: 98, 98, 98, 98, 98, 98, 98, 98, 98, 98, 98, 98, 98, 98, 98, 98, 98, 98, 98, 98, 98, 98, 98, 98 bits. The determinant has 98 bits.
show: "mod-ratio"
The arguments are the ones Every entry under the determinant passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
entries to ±9, n = 4: 1.6; entries to ±9, n = 8: 2.8; entries to ±9, n = 12: 3.4; entries to ±9, n = 16: 5.1; entries to ±9, n = 20: 5.8; entries to ±9, n = 24: 7.1; entries to ±9, n = 32: 10.1; entries to ±9, n = 40: 12.6; entries to ±9, n = 48: 15.4; entries to ±9, n = 64: 24.4; entries to ±9, n = 72: 29.5; entries to ±9, n = 80: 35.5; entries to ±999, n = 4: 1.6; entries to ±999, n = 8: 2.9; entries to ±999, n = 12: 4.3; entries to ±999, n = 16: 5.4; entries to ±999, n = 20: 6.8; entries to ±999, n = 24: 7.9; entries to ±999, n = 32: 10.7. The determinant's width grows like n log n; the plain route's like n squared.
show: "mod-form"
The arguments are the ones Every entry under the determinant passes. A value nobody placed would be a picture no essay asked for and no claim was ever checked against.
Diagonal: 1, 1, 1, 1, 1, 1, 1, 1, 1, 2 bits, 5 bits, 39 bits. The determinant has 44 bits. Every column but the last holds entries of at most 5 bits; the last holds entries up to 39 bits, each below the last pivot.
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.
11 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 nonsingular matrix, whose lattice contains D·I
a size every minor can be enumerated at
a size the dial offers
a size the trace is drawn at
each Smith invariant divides the next
every Bareiss division is exact
the algorithmic Smith form agrees with the definition by minors
the diagonalisation finishes
the Hermite transform is unimodular
the invariant factors multiply to |det A|
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 prime that divides the answer
A modular elimination reports a singular matrix and is telling the truth — over the field with p elements the matrix is singular. Over the rationals it is not. Nothing in the residue distinguishes the two cases, no quantity is small enough to be suspicious, and the wrong answer is a correct computation of a different question.
Exact arithmetic, and what it costs insteadEvery entry under the determinant
The Hermite form's swell was put down to its transform — the record of how the answer was reached — while the form's own entries stayed bounded. Instrumented separately, the form's intermediates swell exactly as much: 3,371 bits against the transform's 3,366 for a random 48 × 48 matrix whose determinant has 219. Carried out modulo the determinant instead, every entry stays within the determinant's width, the answer is identical on every matrix to n = 80, and it is almost always the identity with the whole determinant in its last pivot and last column. What the bound does not buy is speed: counted in bit operations the modular route does more work until just past n = 72, because its steps multiply numbers the determinant's size where plain elimination multiplies wide numbers by small quotients.
Exact arithmetic, and what it costs insteadThe rank depends on the ring
A floating-point rank is a decision about a threshold. Remove the arithmetic error entirely and the threshold goes away — and the answer still is not a property of the array of numbers, because one integer matrix has rank six over the rationals, five modulo three and four modulo two, with nothing rounded and nothing decided.
Exact arithmetic, and what it costs insteadThe swell was one-sided
The Smith form can be computed modulo the determinant, and it was predicted to return the right invariant factors, to stay within twice the determinant's width, and to cost about what the modular Hermite form costs instead of the far larger count of the plain Smith routine. The first three hold. The comparison does not: the plain Smith routine never needed a far larger count. With column operations as well as row operations, its smallest-entry pivot is a unit after a step or two, every entry it holds is a minor of the matrix, and nothing it writes is wider than the determinant — at every size to sixty-four, at a fiftieth of the modular route's work. The swell the Hermite form suffered belonged to doing elimination with one hand.
Exact arithmetic, and what it costs insteadWhat a determinant does not determine
Two integer matrices can have the same determinant, the same rank and the same size, and define genuinely different maps. What separates them is a list of integers each dividing the next — computed here twice, once by unimodular elimination and once from the gcds of every minor, which share no algorithm at all.