Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Sylvesters identity — where it appears

A determinant identity relating the minors of a matrix to the minors of the matrix obtained by one elimination step. It is what makes fraction-free elimination exact: the numerator at each step has the previous pivot as a factor, so the division by it leaves no remainder.

Named by 4 essays across one field — each of them below, with the objects they name alongside it.

1-2-6-7-474-26-12-5-8-524-394151435A, the matrix as given1-2-6-7-401840552700112217207003943011710017279153after 2 fraction-free steps3 × 3 minors25 divisions, all exactthe intermediates are minorswhich is why the divisions come out whole

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.

exact · Fraction-free 10×10, ±6determinant, bits27Hadamard's bound36median slack10024680510152025303540elimination stepbitsHadamard, on the minorsthe intermediatesevery intermediate is a minor of the originalso a bound on the minors bounds the run

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 · Fraction-free 20 matricespeak, every rule29the determinant's own length29area, smallest ÷ natural0.9602468051015202530elimination stepbits, longest entrythe determinant: 29 bitsswap only on a zerolargest pivotsmallest nonzero pivotthree orders, three sequences of minorsand one last entry they all arrive at

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.

exact · Fraction-free largest pivot, area1.037largest pivot, cost1.293smallest pivot, area0.969smallest pivot, cost0.704shortest row, original, area0.966shortest row, original, cost0.841shortest row, current, area0.964shortest row, current, cost0.760over the natural order: below one is cheaperthe rules agree on area and part on cost

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.

exact · Fraction-free

Named alongside it

The objects these essays reach for when they reach for this one.

Bit lengthDeterminantExact arithmeticFraction-free eliminationHadamard boundMinorExact ground truthPermutationFlop countGaussian eliminationPartial pivoting

All concepts