A matrix with no numbers in it

Every matrix on this site so far has arrived as a matrix. It came from a discretisation, or from a measurement, or from a least-squares fit, and whatever produced it produced a rectangular array of numbers with a question attached: solve this, factorise this, tell me how sensitive it is.

A graph does not arrive that way. It arrives as a set of vertices and a set of pairs, with no arithmetic in it anywhere — a road network, a set of citations, the sparsity pattern of a matrix somebody else is trying to eliminate. There are no numbers to be sensitive about. The matrix is something built from the graph afterwards, by a rule, and there is more than one rule.

That is the first thing this field changes. The second is what comes out at the end: not a number but a partition, a ranking or a count. A rounding error in the middle of a solve makes an answer slightly wrong. A rounding error in the middle of a count makes it a different count, and there is no continuum between five and six for the error to be small in.

The rule, and the property it has that nothing else here does #

The Laplacian of a graph is L = D − A: the diagonal matrix of degrees, minus the adjacency matrix. Written out, its diagonal entry is how many edges meet at that vertex and its off-diagonal entry is minus one where there is an edge and zero where there is not.

Every row therefore sums to zero, and it does so exactly. Not to the rounding level — exactly. For an unweighted graph each row is a positive integer and a set of minus ones that count it, and the cancellation of integers in binary64 is exact because every one of those integers is representable and their sum is representable. The figure above measures it rather than asserting it, and the number printed is zero with no exponent after it.

This is worth stopping on, because nothing else in this collection has it. The Hilbert matrix’s inverse is known in closed form and its entries still have to be rounded to be stored. A null space computed from a factorisation is orthogonal to about 10⁻¹⁵. Here the kernel is the vector of ones, it is known before the matrix is built, and the matrix annihilates it in the arithmetic as well as in the algebra.

The quadratic form explains why. For any vector x,

xᵀLx = Σ over edges (i,j) of w(i,j) · (xᵢ − xⱼ)²

which is a sum over edges rather than over entries, is never negative, and is zero exactly when x is constant on every connected piece of the graph. That identity is the whole field in one line: L is positive semidefinite, its kernel is spanned by the indicator vectors of the connected components, and both facts are combinatorial statements wearing an algebraic coat.

The Laplacian is a Gram matrix, and its square root is free #

There is a second way to write L that says something the first does not. Give every edge an arbitrary orientation and build the incidence matrix B, one row per edge, with √w in the column of the edge’s head and −√w in the column of its tail. Then

L = BᵀB

and the quadratic form identity above is nothing more than ‖Bx‖² written out.

So the Laplacian is a Gram matrix. On this site that is normally an alarm: forming AᵀA squares the condition number, and the whole least-squares field is about not doing it. A matrix handed over as a Gram matrix has already paid that price before anybody saw it, and no algorithm applied to it afterwards can get the digits back.

The situation here is the reverse, and the reversal is worth being precise about. B is not something that was formed and then squared; B is available for free, in closed form, from the edge list, at no arithmetic cost and with no rounding. Every entry of it is ±√w and its sparsity is two nonzeros a row. A least-squares problem with this design matrix can therefore be solved through a QR factorisation of B rather than through a factorisation of L, and the condition number that governs it is κ(B) rather than κ(B)² — which is exactly the trade the least-squares field spends four essays on, available here by construction because the object was combinatorial to begin with.

That is a general shape and it is worth naming: a matrix that comes from a structure often comes with its own square root, and the square root is the thing to compute with. The site meets it again in the Gramian of a linear system, where the factored form is what makes a reduction affordable, and in Cholesky-QR, where the same choice is made the wrong way round on purpose to see what it costs.

Two routes to one integer #

If the kernel is spanned by component indicators then the number of zero eigenvalues is the number of connected components. That is a theorem, and it hands this site an unusually clean instance of a habit it runs on: the same integer, by two routes that share no arithmetic.

The first route is the spectrum. Diagonalise L, count the eigenvalues that are zero.

The second route is breadth-first search. Start at a vertex, walk to everything reachable, mark it, start again at the first unmarked vertex, and count how many times the outer loop ran. Nothing in that procedure adds, multiplies or compares two floating-point numbers. It reads the edge list. Its answer is not an approximation to the number of components; it is the number of components.

On the graphs this field builds, the two routes agree. A connected path of twenty gives one zero eigenvalue against one component, and the largest computed zero is 5.8·10⁻¹⁷ while the smallest eigenvalue above it is 0.0246 — a ratio of 4.2·10¹⁴. Two disjoint pieces give two and two, with a ratio of 3.1·10¹⁶. Three pieces give three and three at 5.9·10¹⁵.

Those ratios are what makes the agreement uninteresting. A quantity separated from its neighbour by fifteen orders of magnitude is not being decided by a threshold; it is being read off. Any cut anywhere in the empty fifteen decades returns the same integer.

Where it stops being a reading and becomes a decision #

The interesting case is the one where the empty decades are not empty.

Take the same two ten-vertex paths and join them with a single edge whose conductance is not one but something small. The graph is connected at every positive weight — the edge is there, breadth-first search walks along it, and the combinatorial answer is one component whatever the number attached to that edge happens to be. The second eigenvalue, though, is proportional to the conductance divided by the size of a half, and it slides down the axis as the conductance does.

That constant is worth stating properly, because it is not the one the shape of the argument suggests. Sweeping the joining weight w across four decades on these two ten-vertex paths:

The ratio λ₂/w is 0.189 at 10⁻², 0.1999 at 10⁻⁴ and 0.2 at 10⁻⁶. So the linear law is not an asymptotic statement that arrives slowly — it is accurate to three digits by the second stop. What breaks it is the joining edge being comparable to the edges inside the two halves, and by 10⁻² it is already two orders below them.

The ratio λ₂/w is 0.1891, 0.1999, 0.2000, 0.2000 at w = 10⁻², 10⁻⁴, 10⁻⁶ and 10⁻⁸. That is 2/n with n = 10 the vertices in a half, not 2 — so λ₂ ≈ 2w/n, and the size of the graph is in the constant. It matters because the whole point of the section is how far the eigenvalue slides: on two paths of a thousand vertices the same joining edge would put λ₂ three further decades down, and a tolerance chosen for the ten-vertex case would call the large graph disconnected at a weight the small one called joined. The deviation at 10⁻² — 0.1891 rather than 0.2000 — is the only stop where w is not small enough for the linear relation, which is itself the check that it is a limit rather than an identity.

At a conductance of 10⁻⁸ the second eigenvalue is 2·10⁻⁹ and the threshold — 10⁻¹⁰ times the norm of L — is nine orders below it. The count is one, correctly. At a conductance of 10⁻¹⁰ the second eigenvalue is 2·10⁻¹¹, the threshold has not moved, and the count is two. The graph is connected. Breadth-first search says one. The spectrum says two, and the spectrum is not wrong about anything: it is reporting that this matrix is within 2·10⁻¹¹ of a matrix with two components, which is true and is a different statement.

This is rank is a decision arriving in a field where the number decided describes the object rather than the matrix. There, the threshold sorted singular values and the answer was how many columns a model had. Here the threshold sorts eigenvalues and the answer is how many pieces a road network has. The mechanism is identical and the consequence is not, because nobody argues about whether a road network has one piece or two.

And note where the crossover happens: at a conductance of about 10⁻⁹, which is seven orders above the unit roundoff. The decision is not being made at the rounding level. It is being made at a threshold somebody chose, and the choice is the whole of it.

What a closed form is worth here #

Every family used in this field has a spectrum that is known, and the reason is a rule this site runs on rather than a convenience. A measurement taken on a random graph and checked against nothing is a measurement of the eigensolver.

The path on n vertices has eigenvalues 2 − 2cos(πk/n). The cycle has 2 − 2cos(2πk/n). The complete graph has one zero and n − 1 copies of n. The star has one zero, n − 2 copies of one, and a single n. Against the site’s own symmetric eigensolver these come back at worst 1.7·10⁻¹⁴, 2.6·10⁻¹⁴, 2.7·10⁻¹⁴ and 3.6·10⁻¹⁵ — which is what a Jacobi rotation sweep on a matrix of that norm should give, and is the check that the figures below are about graphs rather than about a routine.

The complete graph’s spectrum is worth a second look for what it says about the whole field. Every non-zero eigenvalue is n. There is no second-smallest eigenvalue distinct from the others, so there is no Fiedler vector and no preferred way to cut it — which is correct, because a complete graph has no preferred way to be cut. The algebra is not being coy; it is reporting a symmetry the object actually has, and a later essay in this anchor is about what a solver does when handed one.

The quadratic form is where the two halves meet #

There is a temptation, on first meeting the Laplacian, to treat it as a matrix that happens to encode a graph, and to reach for the tools that work on matrices. That reading survives contact with the quadratic form for about one line.

xᵀLx = Σ w(xᵢ − xⱼ)² is a sum over edges. It has no entries in it and no indices that range over the whole vertex set at once. Computing it costs one pass over the edge list, which for a sparse graph is a fraction of the cost of forming a matrix–vector product the ordinary way — and, more to the point, it is what every argument in this field is made of. A cut is a vector of zeros and ones and its quadratic form is the number of edges crossing it. A spectral partition is the minimiser of that form over vectors that are not constant. A spectral sparsifier is a graph whose form matches another’s to within a factor.

So the object the field manipulates is the form, and the matrix is a way of writing it down. The figure above draws the graph laid out at its own second and third eigenvectors, which is not decoration: those are the two vectors that make the form as small as they can while staying orthogonal to the constant, so the picture is literally the answer the algebra gives when asked where the graph is loose.

What the diagonal is, when the edges have weights #

Nothing above requires the edges to be unweighted, and most of the graphs in this field are not. A weight is a conductance rather than a count — larger means more strongly joined — and the degree on the diagonal is the sum of the conductances at that vertex rather than the number of edges. Every identity survives that generalisation unchanged, including the quadratic form and the kernel.

What does not survive is the exactness. A weighted Laplacian’s row sums are a cancellation of floating-point numbers rather than of integers, so they are zero to about one rounding of the largest weight rather than to zero. On the weighted graphs in this field that is 10⁻¹⁶ or so and nothing depends on the difference — but it is worth knowing which of the two situations a given figure is in, because the essays that use the exactness use it structurally. A solver that deflates the constant vector out of its iterates is relying on the constant vector being in the kernel; if it is only nearly in the kernel, the deflation leaks at the rate of the leak.

The other thing the weights change is what a threshold means. An unweighted graph’s Laplacian has integer entries and its norm is a small multiple of the largest degree, so a relative threshold is a threshold in units of “one edge”. A weighted graph can have conductances spanning ten orders, and then the relative threshold is measured against the largest of them and says nothing about the smallest — which is how the bridge above ends up on the wrong side of a cut nobody moved.

What is different about this field, stated once #

Every field before this one asks how wrong a number is. The error field separates that wrongness into the algorithm’s contribution and the problem’s; the machine field asks how many answers there are; the rank essays ask what a threshold decides.

This field asks a different question, and it is not a refinement of any of those: what does a continuous computation decide when the answer it is asked for is discrete?

The answers it will produce are a partition of the vertices, an order on them, a count of pieces, a count of spanning trees. None of those has a small perturbation. A partition that is wrong is a different partition. A count that is wrong is a different integer. So the question of how big the error is has no meaning, and the question that replaces it is whether the answer is a function of the graph at all — which, on the evidence assembled over the next several essays, is quite often no.

The Laplacian’s exactly zero row sums are the one thing in the field that is not like that. They are an identity that survives the arithmetic intact, and every construction here leans on them: the grounded solve that computes an effective resistance, the deflation that makes an iterative solver converge, the projection that removes the constant vector before a partition is read.

It survives on the graphs this field draws, and the reason is not the one the sentence suggests:

Exactly zero on unit and integer weights; merely tiny on real ones. And the mechanism has nothing to do with the Laplacian. The degree is accumulated in edge order and a row sum walks the same numbers in column order, so the identity holds bit-for-bit only when two summations of the same multiset agree. For small integers both partial sums are exact and the difference is exactly zero; for reals they round differently and the difference is a rounding. Forming the diagonal by the same traversal the row sum uses would restore exactness on any weights.

So this is the order they are added in wearing a graph’s clothes, and the identity is a property of a summation rather than of a matrix.

And on a badly scaled graph the comparison with the second Laplacian reverses. With weights spanning eight decades the combinatorial row sums are 1.92·10⁻¹³ and the normalised null-vector residual is 1.31·10⁻¹⁴ — the normalised Laplacian is the better behaved of the two there. Dividing by √(dᵢdⱼ) puts every row on one scale, and a row sum on one scale cancels better than a row sum spanning four decades.

None of that endangers the constructions. This field’s graphs are unweighted or integer-weighted and the identity is exact on them. What changes is the reason to believe it: not that a Laplacian’s rows sum to zero in floating point, but that a sum of small integers does.

That distinction is worth holding onto, because it says what to check when the field is applied outside its own examples. A graph whose edge weights are conductances, similarities, or transition rates has real weights, and on it every construction that treats the null vector as exact is treating a rounding as a zero. None of them breaks at 10⁻¹³ — the grounded solve, the deflation and the projection all tolerate that comfortably — but the guarantee they were resting on is gone, and what replaces it is an ordinary backward-error argument of the kind every other field here runs.

Which returns the field to the position the paragraph above claimed it was exempt from. The one piece of exact ground truth turns out to be exact on integers and approximate on measurements, and a graph built from measurements is the case the applications are about.