Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Connected components — where it appears

The maximal sets of vertices reachable from one another. Their number is both a breadth-first search away and equal to the count of zero eigenvalues of the Laplacian, and the two routes share no arithmetic at all.

Named by 2 essays across one field — 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 on this site whose kernel is known before anything runs.

graph · graph laplacian 1357911131510⁻¹⁸10⁻¹⁵10⁻¹²10⁻⁹10⁻⁶10⁻³1vertexrelative error against the exact answerthree routes, one numberworst, by elimination4.8·10⁻¹⁶worst, by spectrum10·10⁻¹⁶solve residual1.5·10⁻¹⁵Foster's sum15n − 115difference3.6·10⁻¹⁵the answer is a ratio of integersso the error is known

A distance computed by a solve

Effective resistance is the one quantity in this field with no combinatorial route to it — it is defined by a linear system. On a small unweighted graph the answer is a ratio of two integers, so for once the error is known rather than estimated, and every resistance in a graph has to add up to a number fixed in advance.

graph · effective resistance

Named alongside it

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

Exact ground truthGraph laplacianAdjacency matrixAlgebraic connectivityEffective resistanceFoster theoremGroundingImportance samplingMatrix tree theoremMetricNull spacePseudoinverse

All concepts