A Laplacian that is not symmetric

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.

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.

What survives #

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.

What does not #

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.

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.

Those two figures are the refusal and its sharpest form in one pair. If asymmetry measured how complex a spectrum can get, the second of them would be the more real one. Across the five graphs this essay draws, the asymmetry runs 1, 0.825, 0.68, 0.258 and 0.24 and the largest imaginary part runs 1, 1.505, 1.18, 0 and 0.186 — not monotone, and not even ordered the same way at the two ends. The directed cycle is as asymmetric as a matrix gets and its imaginary reach is 1; the balanced family at 0.825 reaches 1.505, half as much again, on a matrix a norm calls closer to symmetric.

So the norm and the spectrum are answering different questions, which is the more useful form of the refusal. ‖L − Lᵀ‖/‖L‖ is a distance in the space of matrices; how far the eigenvalues leave the axis is a property of where the arrows are rather than of how many are unreciprocated. A digraph can be entirely one-way and have a spectrum on a circle of radius one; it can be nearly symmetric and have one twice as far off the axis.

The two directions of the same graph #

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.

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.

The walk is the thing that has to be computed #

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.

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, because the obvious reason is two reasons: it is not sensitive, and 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. Both are true, they are about different things, and the first has a closed form that the section below measures. Everything about the zero survives; everything about the rest is now a numerical question.

What is left to build on #

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.

The one closed form the directed case supplies #

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.

The cheap null vector’s eigenvalue is priced by the expensive one #

The sensitivity of a simple eigenvalue is 1/|y*x| for its normalised left and right eigenvectors. Here x is the constant vector, which is free. The left null vector of D_out − A is not the stationary distribution itself but D_out⁻¹π, and it is the object this essay has just spent a section calling the expensive one. So

κ(0) = √n · ‖D⁻¹π‖ ⁄ |1ᵀD⁻¹π| ,

and checking it against the condition number taken directly from a decomposition of Lᵀ, at twenty-four vertices:

Four digits at every family, and the pattern is the field’s own distinction. It is exactly one on the three balanced families, because there D⁻¹π is constant and the left null vector is the right one; it is 1.29 and 1.30 where the graph is unbalanced. So the eigenvalue at the origin is insensitive because the graph is balanced, not because the vector is free — and on a graph that is not, its conditioning is a number nobody can write down without running the walk.

The other half of the claim is a different statement, and it is much stronger. A general perturbation of the matrix at relative size 10⁻⁸ moves the zero to between 1.4·10⁻⁹ and 7.9·10⁻⁹ — κ(0) times the perturbation, as ordinary theory says it should. A perturbation of the same size that preserves the row sums leaves it between 2.9·10⁻¹⁶ and 2.3·10⁻¹⁵, six to seven orders smaller and at the rounding level.

That gap is the sentence about the integers cancelling, made into a measurement. It is not a claim about the eigenvalue’s conditioning at all; it is a claim about which perturbations a code actually commits. A Laplacian assembled by subtracting the adjacency from the row sums cannot have a nonzero row sum however badly the arithmetic goes, so the perturbations available to it are exactly the ones the zero does not feel. Assemble it any other way — read the diagonal from a file, accumulate it in a different order, store it in a narrower format — and the perturbation is general again and the zero moves like every other eigenvalue.

There is a small irony in the arithmetic that is worth stating, since this essay opened by observing which of the two null vectors is cheap. The right null vector is free and carries no information about the graph. The left one costs a walk and describes the graph completely. And the eigenvalue that belongs to the free one has its accuracy decided by the expensive one — so a code that wanted to report how much to trust its computed zero would have to compute the very object it was avoiding. On a balanced graph the answer is one and nothing has to be computed; on an unbalanced one the answer is a number the graph has to be walked to find. Which is the field’s new fact once more, in its smallest form: the undirected case gave both vectors away at once and hid every question about which of them was doing the work.

assertTheZerosSensitivityIsTheLeftNullVector holds the closed form at five families, the exact one on the balanced ones, and the six orders between the two perturbation classes.