Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Graph automorphism — where it appears

A relabelling of a graph's vertices that maps it to itself. Its permutation matrix commutes with the Laplacian, so a symmetry group with a two-dimensional representation forces a repeated eigenvalue and an eigenvector that is not determined.

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

Also named here as sweep cut — the same set of essays touches all of them, so they are one junction rather than several.

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 14710131619110¹indexeigenvalue of Lan eigenvalue with no vectorλ₂0.35λ₃0.35gap1.7·10⁻¹⁵partitions found3best conductance0.045worst0.045two eigenvalues, one valueand the answer is not a function of the graph

A partition decided in the last digit

On a graph with a symmetry there is no Fiedler vector — there is a plane, and every vector in it is an exact eigenvector. Twenty-four runs with the edge weights nudged by 10⁻¹² return ten different partitions of a cycle and, on a hypercube, two different qualities of answer.

graph · spectral partition

Named alongside it

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

ConductanceFiedler vectorSpectral partitionSweep cutAlgebraic connectivityCheeger inequalityCombinatorial optimumInvariant subspaceRank is a decisionRelaxationRepeated eigenvalueRun-to-run variation

All concepts