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.
Every graph in this field so far has been undirected, and the reason the field stopped there rather
than continuing is a specific one: an arrow breaks two properties that all seventeen of those essays
rest on, and neither break is repaired by being careful.
Point the edges. The adjacency matrix stops being symmetric, so the Laplacian D_out − A does too, and
the first thing to go is not an approximation or an accuracy — it is a theorem.
Fig. 1 The Laplacian of a directed cycle on eighteen vertices. Its eigenvalues are 1 − exp(2πik/n), a circle
of radius one centred at one, so all but the zero have an imaginary part and no ordering of them
exists.
The picture is the first thing that changes and it is not a presentational choice. An undirected
Laplacian’s spectrum is a list of real numbers and every figure in this field has drawn it on an
axis — smallest to largest, with the gap after the zeros marked. There is no axis here. The
eigenvalues are points in a plane, and the closest thing to an ordering is a distance from the
origin, which is a choice rather than a fact.
One thing does, and it is the property the field’s first essay
is named for. Every row of D_out − A is the vertex’s out-degree minus the weights of the arcs leaving
it, so every row sums to exactly zero by cancellation of integers, and L·1 is the zero vector with
no rounding anywhere. 1 is still a right null vector, 0 is still an eigenvalue, and it is still known
before anything runs.
The columns do not. A column sums to the out-degree minus the in-degree, which is zero only when the
vertex is balanced, and the left null vector is therefore something else entirely — it is the
stationary distribution of the random walk, and computing it is a whole problem rather than a lookup.
That asymmetry between the two null vectors is the field’s new fact in its smallest form. In the
undirected case they are the same vector and nobody has to say which one is meant.
It is worth noticing which of the two is the cheap one, because it is the opposite of what an
application usually wants. The right null vector — the constant — is free and says nothing: every
digraph has it, it carries no information about the graph, and the only thing it certifies is that
the rows were built by subtraction. The left null vector is the one that describes the graph, and it
is the one that costs an iteration. The undirected case gave both away at once and hid which was
which.
The rest of the undirected apparatus goes together, because it is all one argument.
A symmetric Laplacian has a quadratic form xᵀLx = Σ over edges of (xᵢ − xⱼ)², which is what makes λ₂
the minimum of a Rayleigh quotient over vectors orthogonal to 1, which is what makes λ₂ a relaxed
cut, which is what makes a sweep over the second eigenvector a partitioning algorithm, which is what
Cheeger’s inequality is about. Remove the symmetry and the first link goes: there is no quadratic
form, because xᵀLx and xᵀLᵀx are different numbers and neither is a sum over anything.
The loss propagates further than it first looks. The sweep cut is not merely unjustified, it is
undefined: there is no real vector to sort. The spectral layout every picture in this field uses
places a vertex at its second and third eigenvector entries, and those entries are complex. The
component count reads the multiplicity of the zero eigenvalue, which survives — but the gap it is
read against is a distance in a plane rather than a difference on a line.
So there is no second-smallest eigenvalue either, and the reason is more basic than the loss of a
theorem. The eigenvalues are complex. There is no ordering of the complex numbers compatible with
arithmetic, so “the second smallest” is not a quantity that exists — and every ranking of them by
modulus or by real part is a choice somebody made rather than a fact about the matrix.
Fig. 2 A random strongly connected digraph, whose spectrum has no structure to it at all: the largest
imaginary part is 1.18, the matrix is 68 per cent asymmetric, and the eigenvalue at the origin is
computed at 1.5·10⁻¹⁵.
The claim that had to be dropped, and it improved the essay #
The natural pair of statements is that a symmetric digraph’s Laplacian has a real spectrum and an
asymmetric one’s does not. The first is a theorem. The second is false, and the measurement
refused it before any of this was written.
The two-block family at twelve vertices is 25.8 per cent asymmetric in the Frobenius norm and has
every eigenvalue real, to exactly zero. The graph is small enough that the few arcs crossing between
its two rings all happen to be reciprocated in the parts of the matrix that matter, and a
non-symmetric matrix is perfectly entitled to a real spectrum — every triangular matrix has one.
So asymmetry permits a complex spectrum and does not force one. What is asserted instead is the
closed form: the directed cycle’s eigenvalues are 1 − exp(2πik/n) exactly, computed by the real Schur
form and matching to 1.2·10⁻¹⁵, and its largest imaginary part is 0.985 at n = 9. That is a
construction rather than an observation, which is what lets it carry a refusal — and the refusal is
the one this essay publishes, fed a graph rather than a hope.
There is a second measurement worth taking before any theory, because it separates two words that get
used as though they were one.
A digraph is symmetric when every arc appears both ways with equal weight, which makes its
Laplacian the undirected Laplacian and its spectrum real. A digraph is balanced when every
vertex’s in-degree equals its out-degree, which is a much weaker condition — a directed cycle is
balanced and is as asymmetric as a matrix gets.
The measurement: the balanced family at twenty-four vertices is 82.5 per cent asymmetric and has a
largest imaginary part of 1.51. So balance is not a weak form of symmetry, and the fact that it
recovers some of the undirected theory — which the next essay is about — is not because it is
nearly symmetric. It is because it makes one particular vector, the stationary distribution, equal to
one particular other vector, the degrees.
Fig. 3 A balanced digraph: eighty-two per cent asymmetric, and its stationary distribution equal to its
degree distribution to 10⁻¹⁴. Two quantities that are the same object on an undirected graph, drawn
on one where the matrix is not symmetric and they still coincide.
Why this was left until the field’s eighteenth essay #
The graph field’s own record says it stopped at undirected graphs rather than running out of
material, and the reason is visible now: the directed case is not a variation on the undirected one,
it is a different subject that shares a picture.
Every result in the field so far factors through the quadratic form.
Two Laplacians of one graph is about which cut each of two
symmetric matrices minimises; a partition decided in the last
digit is about the eigenvector of a symmetric matrix
with a repeated eigenvalue; a graph with a tenth of the edges
is about preserving a quadratic form. None of those questions can even be asked here without first
building something new.
What is not lost is the field’s central claim, and it is worth checking that it survives: a discrete
answer computed by continuous arithmetic is still what a partition is, and a rounding still makes it a
different answer rather than a worse one. That part transfers unchanged. It is the machinery for
getting the answer that has to be rebuilt.
On an undirected graph the stationary distribution of the random walk is the degree distribution.
That is a one-line fact and it is why nothing in this field has ever had to compute one:
the ranking essay computes a Perron vector because
PageRank’s walk is not the graph’s walk, and every other essay reads a degree.
On a digraph the two are different, and the difference is not small. On the two-block family the
worst per-vertex gap between the stationary distribution and the out-degree share is 0.062 — six per
cent of the total probability mass sitting on the wrong vertex, on a graph with twenty-four of them.
That matters because everything the next essay needs is built from the stationary distribution, and
it has three properties the degree does not:
It is global. A vertex’s degree is a property of its own arcs. How often a walk visits it
depends on the whole graph, so a local change anywhere moves every entry.
It might not exist. A walk on a graph that is not strongly connected has more than one closed
communicating class and therefore more than one stationary distribution —
the essay on a chain with no stationary vector is
about exactly that failure, arrived at from the Markov side.
And it has to be computed to an accuracy. The degrees are integers, read off the graph with no
arithmetic in them at all. The stationary distribution is the fixed point of an iteration, and the
figure above reports 824 power iterations to reach 10⁻¹⁴ — so a normalised Laplacian built from it
carries an error the undirected one does not have, before any eigenvalue of it is computed.
The iteration is a power iteration rather than a call to an eigensolver, deliberately. Every step is
a probability vector times a stochastic matrix, so every entry is a sum of nonnegative terms and no
subtraction happens anywhere — which means a nonnegative vector cannot come back with a negative
entry. The Perron vector with four negative entries
is the measurement that made that a rule here rather than a preference.
Fig. 4 The unbalanced case: the walk’s distribution against the degree share, differing by up to six per
cent of the mass. These are the two candidate weights for a normalised Laplacian and only one of them
gives a theorem.
The eigenvectors go too, and that is the part with a cost #
The eigenvalues being complex is the visible loss. The eigenvectors being non-orthogonal is the
expensive one, and it is worth pricing because it decides which algorithms are available.
A symmetric matrix has an orthonormal eigenbasis. That is what makes the Jacobi sweep this field uses
possible, it is what makes an eigenvalue’s condition number exactly 1 — so
the essay on eigenvalue sensitivity has nothing to
report on a symmetric matrix — and it is what lets a subspace be described by a projector.
A directed Laplacian has none of that. Its eigenvectors are the columns of some invertible matrix,
that matrix has a condition number, and the eigenvalues inherit it: an eigenvalue’s sensitivity is
1/|yᵀx| for its left and right eigenvectors, which for a symmetric matrix is 1 and here is not. So a
computed directed spectrum carries a perturbation that a computed undirected spectrum does not, and
the essay on eigenvalues that are not there describes
what that does at its worst.
The eigenvalue at the origin is the exception and it is worth saying why. It is not sensitive,
because it is not computed from the matrix’s numerical structure at all: the right null vector is 1
by construction and the row sums cancel as integers. Everything about the zero survives; everything
about the rest is now a numerical question.
The situation after this essay is worth stating plainly, because it is unusually bare.
There is a matrix. It has an exact null vector on one side and an unknown one on the other. Its
eigenvalues are complex, unordered, and attached to eigenvectors that are not orthogonal. There is no
quadratic form, no variational characterisation, no Cheeger inequality, no sweep cut, and no
second-smallest eigenvalue.
What there is instead is a walk, which exists whenever the graph is strongly connected and which
carries all the information the degrees carried in the undirected case and more. Chung’s construction
symmetrises the Laplacian with respect to it and recovers the whole apparatus — a real spectrum in
[0, 2], a variational characterisation, a sweep cut and a Cheeger inequality. The price is that the
quantity the inequality is about is no longer the weight of the arcs crossing a cut, and that
substitution is the next essay.
Fig. 5 What the symmetrisation is checked against: on a balanced digraph it must reduce exactly to the
undirected normalised Laplacian, and it does, at 10⁻¹⁴ across every size.
Every field on this site needs at least one object whose answer is known in advance, because a
measurement checked only against another measurement is checked against nothing. The undirected field
had several — the path’s spectrum, the cycle’s, the hypercube’s, Foster’s identity, the exact
spanning-tree count. The directed field has one, and it is the cycle.
The Laplacian of a directed cycle on n vertices is I − S, with S the cyclic shift, and S’s
eigenvalues are the n-th roots of unity. So the spectrum is
λₖ = 1 − exp(2πik/n), k = 0 … n − 1
a circle of radius one centred at 1, passing through the origin. Every eigenvalue but λ₀ has a
nonzero imaginary part, the whole spectrum is determined by n, and there is nothing approximate about
it.
Measured against the real Schur form the agreement is 1.2·10⁻¹⁵ at n = 9, which is the rounding level
for a computation of that size. That is the ring in the hero and it is the only assertion in this
essay that compares a computed spectrum with a formula rather than with a property.
It is also the reason the cycle is the family the refusal uses. A claim that a graph Laplacian’s
eigenvalues are real has to be refused by an instance, and an instance whose spectrum is known is
worth more than one whose spectrum was computed — because if the computation were wrong, an instance
of the second kind would refuse the claim for the wrong reason.
Fig. 6 Twelve vertices, twelve eigenvalues, all of them on the ring the closed form draws.
Fig. 7 The degenerate case: every arc both ways, every eigenvalue real to exactly zero, and the picture is a
line inside a plane.Fig. 8 Balanced and 82 per cent asymmetric, which is the pair of words this field has to keep apart.Fig. 9 Two blocks with one arc back, where the imaginary parts are small and not zero.Fig. 10 The closed form at thirty-six vertices, filling in the same circle.Fig. 11 And at eight, where the eight eigenvalues are visibly the eighth roots of unity reflected.Fig. 12 A random strongly connected digraph, where the walk and the degrees disagree everywhere.Fig. 13 The directed cycle, where every vertex has one arc in and one out and the two distributions are both
uniform.Fig. 14 What the symmetrisation buys, and what it renames.Fig. 15 The undirected object this field spent seventeen essays on, for comparison.Fig. 16 An undirected Laplacian’s spectrum, which is a list of real numbers on a line.Fig. 17 The walk whose stationary distribution this essay needs, in the field’s undirected version of it.Fig. 18 The Perron vector whose negative entries made power iteration the rule here.Fig. 19 Twenty-six vertices on the ring the closed form draws.Fig. 20 A larger random strongly connected digraph, filling the plane.Fig. 21 Balanced at eighteen, still complex and still not symmetric.Fig. 22 Every arc both ways at thirty vertices, and a spectrum on a line.Fig. 23 The closed form at eighteen vertices, agreeing to 10⁻¹⁴.Fig. 24 The unbalanced case at thirty-two, where the gap does not shrink.Fig. 25 The check that the symmetrisation collapses when it should.Fig. 26 What the symmetrisation buys, at thirty vertices.Fig. 27 The undirected inequality this field has to rebuild.Fig. 28 The undirected sweep cut, which needs a real eigenvector.Fig. 29 Forty-eight vertices on the ring.Fig. 30 Two blocks at forty, where the imaginary parts are small and not zero.Fig. 31 A small random strongly connected digraph.Fig. 32 Balanced at thirty-six, and as asymmetric as ever.Fig. 33 The walk against the degrees on a random digraph.Fig. 34 And on a symmetric one, where they are the same object.Fig. 35 The closed-form check out to thirty-eight.Fig. 36 The quantity the symmetrisation renames.