Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Directed graph — where it appears

A graph whose edges point, so its adjacency matrix is not symmetric and neither is the Laplacian built from it. The row sums are still exactly zero, so the constant vector is still a right null vector, and almost nothing else transfers: the eigenvalues are complex, there is no quadratic form to minimise, and the left null vector is the walk's stationary distribution rather than the degrees.

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

Re λIm λwhat survives the arrowsvertices18arcs18worst row sum0worst column sum0largest |Im λ|0.98asymmetry1the null vector is still exactand nothing else about the spectrum is real

A Laplacian that is not symmetric

Point the edges and the matrix stops being symmetric. Its row sums are still exactly zero, so the null vector survives; everything built on the quadratic form does not, and the eigenvalues need a plane rather than a line. Asymmetry permits that and does not force it, which the smallest case here demonstrates by being asymmetric and real.

graph · Directed laplacian Cheeger's band, for the circulationcirculation · arcsvertices on the smaller sidewhich of the two the theorem is aboutλ₂ of 𝓛0.066λ₂/20.033√(2λ₂)0.36circulation Φ0.12arc conductance0.04their ratio3.1the inequality holdsabout a quantity nobody counts

A conductance the arcs do not measure

Symmetrising a directed Laplacian with respect to its walk recovers everything the arrows took — a real spectrum, a sweep cut, a Cheeger inequality. What it does not recover is the quantity: the inequality bounds the probability that a step of the walk crosses the cut, which on one graph here is three times the weight of the arcs that do.

graph · Directed laplacian

Named alongside it

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

Graph laplacianQuadratic formStationary distributionCheeger inequalityComplex eigenvaluesConductanceNull spaceSpectral partitioningSymmetry

All concepts