Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Bipartite — where it appears

A graph whose vertices split in two so that every edge crosses between them, equivalently one with no odd cycle. The normalised Laplacian has an eigenvalue of exactly two precisely then, and the combinatorial one cannot tell.

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

0173451688510211910⁻⁶10⁻⁵10⁻⁴10⁻³10⁻²10⁻¹1steps of the walkdistance from stationarya rate read as a timeλ₂ of the walk0.9steps measured122steps predicted131ratio0.93the dashed line is the eigenvaluethe curve is the walk

The rate is the second eigenvalue

A walk forgets where it started at a rate the graph's second eigenvalue names exactly. Across three orders of magnitude in the step count the prediction is five per cent high — and the published rate for PageRank is right for a reason nobody states, which is that a link graph is in pieces.

graph · random walk a triangle and a square, joinedK₂,₃ with a pendant edge1234560123456indexeigenvaluethe same, and not the samevertices each6edges each7spanning trees12spectra differ by5.3·10⁻¹⁵highest degree, left4highest degree, right3one has a trianglethe other is bipartite

The spectrum is not the graph

Two graphs on six vertices with the same Laplacian characteristic polynomial — as integer polynomials, not to fourteen digits. One contains a triangle; the other is bipartite. Every method in this field that reads only the spectrum is answering about the class.

graph · graph invariant

Named alongside it

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

Normalised laplacianCharacteristic polynomialConductanceCospectral graphsExact ground truthGraph invariantGraph laplacianMixing timePagerankPower iterationRandom walkSpanning tree

All concepts