Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Algebraic connectivity — where it appears

The second-smallest eigenvalue of a graph Laplacian, zero exactly when the graph is disconnected. It falls as a graph becomes easier to cut, and it is simultaneously the rate at which a random walk on the graph forgets where it started.

Named by 4 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 in these essays whose kernel is known before anything runs.

graph · Graph laplacian 10⁻³10⁻²10⁻¹110¹12345678910conductance, and the two bounds on itpathcyclegridbarbelltwo blockshypercubepreferentialstarcompletethe bar is the inequalitythe dot is the graph

Two Laplacians of one graph

The combinatorial Laplacian D − A and the normalised one, which conjugates it by the inverse square roots of the degrees, are built from the same object, are not similar to each other, and answer different questions. On a graph whose degrees are equal they coincide. On one whose degrees span an order of magnitude their second eigenvalues are sixteen times apart.

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 10⁻³10⁻²10⁻¹110¹12345678910conductance, and the two bounds on itpathcyclegridbarbelltwo blockshypercubepreferentialstarcompletethe bar is the inequalitythe dot is the graph

A bound with a square root in it

Cheeger's inequality brackets a graph's best cut between λ₂/2 and √(2λ₂). The lower bound is attained exactly. The upper one is loose by a factor of fourteen — on the one graph in the census with a real bottleneck, which is the shape it is always quoted about.

graph · Spectral partition

Named alongside it

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

ConductanceCheeger inequalityFiedler vectorGraph laplacianNormalised laplacianQuadratic formRank is a decisionRelaxationSpectral partitionAdjacency matrixBound tightnessCombinatorial optimum

All concepts