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 on this site 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

D − A and D^{-1/2}(D − A)D^{-1/2} 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