Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Rank is a decision — where it appears

The observation that a numerical rank is a threshold applied to singular values rather than a property a matrix has. The gap either side of the cut is what says whether the integer was read off or chosen, and it belongs beside the integer.

Named by 6 essays across 3 fields — each of them below, with the objects they name alongside it.

the matrix, measuredvertices40edges223‖L·1‖∞0zero eigenvalues1components, by search1λ₂1.5laid out at its own eigenvectorsand the row sums are exactly zero

A matrix with no numbers in it

A graph arrives as vertices and edges. Two different matrices can be built from it, they answer different questions, and one of them has a null vector that is exact — the only object in these essays whose kernel is known before anything runs.

graph · Graph laplacian 0481216202410⁻²10⁻¹1vertices on the smaller sideconductance of the prefix cut0.00752, the best prefixthe rounding stepλ₂0.14cuts considered23best conductance0.0075at k =12worst prefix1the dashed curve is the eigenvectorthe solid one is what it costs

The vector that has to be rounded

A spectral partition is an eigenvector, and an eigenvector is a real vector. The answer wanted is a subset. Something has to turn one into the other, and the something is a heuristic applied after the linear algebra has finished.

graph · Spectral partition det mod p, as a fraction of p3713a prime that divides the answerdet A3·10⁴primes swept25unlucky5rate0.2det, in bits15singular mod p is not singularand one residue cannot tell them apart

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 · Modular lift ℚ6𝔽24𝔽35𝔽56𝔽76𝔽116𝔽136𝔽1016𝔽655376rank, by the ring the entries are read inthe rank of one matrixover ℚ6over 𝔽24over 𝔽35over 𝔽56over 𝔽76nothing is rounded hereand the answer still is not a property of the matrix

The 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 · Exact rank 12345678910111210⁻¹³10⁻¹¹10⁻⁹10⁻⁷10⁻⁵10⁻³10⁻¹10¹order of the reduced modelworst relative errora model made of measurementssamples used24degree read6gap at the cut2·10⁸best model, order12its error2.7·10⁻¹¹states in the original40filled: at its own samplesopen: everywhere else

A model with no matrices behind it

Twenty-four numbers — values of a transfer function at twenty-four points — produce a sixth-order model of a forty-state system that passes through every sample to 10⁻¹² and matches the function it never saw to 10⁻⁹. Noise of 10⁻¹⁰ on those numbers takes the rank decision's gap from 10⁸ to 4.

reduction · Data-driven realisation 4914192429343900.20.40.60.81decimal digits of the numbers the lattice is givenshare of trials recovering the relationa double has about this many digitsnumbers that are exactthe same numbers, measureda window with two edgescoefficients up to30exact, at 12 digits1exact, at 401doubles, at 121doubles, at 250doubles, at 400.13one edge is the relationand the other is the data

A relation among digits that were not there

A lattice finds the exact integer combination of several numbers that vanishes, and it needs enough digits of them to do it. Give it more digits than the numbers have and it finds a relation anyway — among the rounding, with the same confidence and no warning. Recovery runs 8 of 8 at twelve digits and 1 of 8 at forty.

exact · Lattice reduction

Named alongside it

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

Exact arithmeticAlgebraic connectivityModular arithmeticUnlucky primeAdaptive interpolationAdjacency matrixCheeger inequalityChinese remainder theoremCombinatorial optimumConductanceConnected componentsData-driven realisation

All concepts