Determinant — where it appears
Named by 26 essays across 9 fields — each of them below, with the objects they name alongside it.
Every 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.
The 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.
How many primes the answer needs
Work modulo a word-sized prime and no intermediate can exceed twenty-six bits, whatever the matrix does. The catch is that the answer must be reassembled from several such computations, and the number of them has to be fixed before the first one runs — by a theorem about how large a determinant can be, not by trying more until it settles.
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.
A rule that is correct and unusable
Cramer's rule gives every component of the solution in closed form, in terms of determinants, and it is a theorem. On two-by-two systems whose rows are nearly parallel it returns an answer with a backward error of 458 units of roundoff where elimination returns 1.3 — on a matrix whose condition number is 32,000 and which elimination solved perfectly.
One multiply the compiler removed
A determinant whose value is exactly 1, computed as exactly 0 by the expression that is written down, and exactly 1 by the same expression with the multiply and the add fused. Both forms conform to IEEE-754, both are legal compilations of the same source, and nothing in the program says which one you have.
A rotation that comes back mirrored
Align twenty noisy points and the nearest orthogonal matrix to the answer is a reflection in 7.7 per cent of trials at noise three times the set's thickness and a third of them at ten — at thicknesses of 10⁻², 10⁻³ and 10⁻⁴ alike. The determinant fix is never a small correction. It moves the answer by exactly 2, it costs exactly 4σ₃ of residual, and it leaves the rotation's error at half the noise however thin the set becomes.
The number that decides nothing
The determinant is the first scalar anybody attaches to a matrix and the last one worth consulting. A tenth of the identity has a determinant of 10⁻⁶⁰ and a condition number of exactly one. The Hilbert matrix's determinant stops being right at n = 13 and stops being a number at n = 29, and nothing in between reports either.
What 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.
A basis that describes its lattice badly
The same set of points has infinitely many bases, they are all correct, and they are not equally useful. One measurement separates them — the product of the vectors' lengths over the lattice determinant — and the determinant is the invariant the reduction may not change, which is what makes the reduction checkable.
The knob and the rounding
The Lovász parameter is the number a lattice reduction is specified by, and moving it from 0.50 to 0.99 strengthens the proved bound from 16.00 to 1.83, costs 91 per cent more steps, and returns a basis with the same orthogonality defect. The one rounding nobody writes down decides everything: above 2⁵³ the reduction returns a basis 12,345 times worse than it should, with the determinant invariant equal to one throughout.
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.
Three 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.
Five precise points are five points
Weighting each sighting by its reliability is the standard form of an attitude or registration fit, and it changes how often the nearest orthogonal matrix comes back as a mirror. Measured, the rate is a function of two numbers: the weighted noise over thickness, and the effective count (Σw)²/Σw². Five points with a tenth of the noise, weighted by 1/σ², carry the information of 515 equal points and mirror like five — 7.9 per cent at a noise ratio where twenty points mirror 1.8 and five mirror 9.5. The √m the earlier measurement left unchecked is right, and it counts what carries the thin direction.
A count that comes out of a determinant
The number of spanning trees of a graph is the determinant of its grounded Laplacian, so it is a whole number known in advance. The elimination that computes it is backward stable at every size — and from sixteen vertices the answer is wrong, because the count has seventeen digits and a binary64 has sixteen.
A mirror decided in the thin directions
In n dimensions the nearest orthogonal matrix to a noisy alignment is still sometimes a reflection, and the rate at which it is does not depend on n. Three, five and ten dimensions with one thin direction mirror alike; two thin directions mirror like each other in five dimensions and in ten. The rate is the chance that a k × k matrix built from the k thin directions has a negative determinant — 21.7 per cent at a noise ratio of 0.7 for k = 2, measured at 23.0 — and it is well above k independent coin flips. With two or more thin directions the determinant correction still fires, and it no longer rescues the rotation: the answer is eleven noise-widths off whether or not it was mirrored.
The room a relation has to stand out
A lattice search for an integer relation returns its shortest vector, and the proposal was to return the gap to the next one as well, so a caller could tell a relation from an accident. Measured, the gap is a certificate with a budget: the digits the numbers really have, shared among all but one of them, less the size of the relation. A found relation's gap sits half a digit under that budget, accidents stay near zero, and a one-digit gap vouches for 81 of 96 relations among three numbers and for 1 of 35 among six. The test numbers the proposal came from turned out to have relations of their own.
The correction lost to its own two-by-two solve
Solving a band matrix through a circulant and a small correction was measured losing the answer to 10⁻⁴ where elimination kept it to 10⁻¹⁴, and a wrap that landed one sample on a zero was measured costing four orders more than one that landed a pair. Both measurements solved the two-by-two correction system by Cramer's rule. Solved with a row interchange, the corrected solve on the same matrix loses 2.9·10⁻¹⁰ — the cancellation, and nothing multiplied onto it — and the single landing costs what the pair costs. The loss was in the determinant.
Two precisions guard the other edge
Run a lattice relation search at N digits and again at N/10, and accept its answer only if both runs return the same vector. Among six measured numbers, where the gap between the shortest and next vector vouches for one found relation in 35, the two runs agree on 34. Past a double's sixteen digits they never once agree on an accident, 0 of 561. They do agree on 62 accidents at fifteen digits or fewer — approximate relations that really are the shortest vector there — and the gap, which cannot see a relation among six numbers, can see those.
One mass removed, and one eigenvalue gone
A coordinate with no inertia reads like a coordinate that has been deleted, and a chain of eight masses with one of them removed would then be a chain of seven, with fourteen eigenvalues. It has fifteen. The massless coordinate is still there, still carrying a damper, and it contributes a first-order equation rather than none.
The 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.
What 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.
The field decides it, usually
A matrix whose rank depends on the field it is read over was built, the first time, from its invariant factors outward, because random integer matrices never seemed to show the effect. Random 0/1 matrices show it at almost every size that is not tiny. At twenty rows, 99.8% of them are invertible over the rationals, 29% modulo two, 56% modulo three — and 71% of the ones the rationals call invertible are singular modulo two. Modulo two they obey, corank by corank, the law for uniformly random matrices over that field; modulo three and five, which their entries cannot fill, they converge to that field's law anyway.
An eigenvalue with no value
If the second matrix of a pencil is singular then some of the eigenvalues are infinite, and that is not a degeneracy — it is the algebraic constraints of the model, one per constraint. What survives is a pair of numbers rather than one, and on the line those pairs live on, infinity is an ordinary point with an ordinary residual.
A problem with no answer
If two matrices share a null vector then det(A − λB) is identically zero and every λ is an eigenvalue, which means none of them is. Perturb such a pencil by a ten-billionth and a solver returns six numbers with residuals below 10⁻⁹. Change the seed and it returns six different numbers, spread over forty-four, with residuals just as small.
The largest gap is inside the null space
The rule recommended for counting a pencil's infinite eigenvalues is to cut at the largest gap in the singular values of B. On integer pencils, with no perturbation anywhere and an exact answer available from the characteristic polynomial, it returns the wrong count on nine of twenty-five — because the singular values that are mathematically zero come back spread over a hundred and forty orders of magnitude, and the largest ratio in the list is between two of them.
Named alongside it
The objects these essays reach for when they reach for this one.
Exact arithmeticExact ground truthBit lengthFraction-free eliminationHadamard boundBackward errorMinorCondition numberLattice reductionOrthogonalityOrthogonality defectSingular values