A graph is alternating modulo two

Each column divides by the prime found that random 0/1 matrices are invertible modulo a small prime at the rate of the law for uniformly random matrices over that field, $\prod_{k=1}^{n}(1 - q^{-k})$, which modulo two is 0.289 at every size worth measuring, and that each extra column divides the shortfall by about the prime. Its matrices had independent entries everywhere. Its closing question was about matrices that do not: “A random graph’s adjacency matrix is symmetric, and symmetric matrices over a field follow a different law — modulo two, a symmetric matrix’s corank distribution differs from a general one’s at every size. The prediction with a sign is that random graphs on twenty vertices with edge probability one half are nonsingular modulo two at the symmetric law’s rate, about 0.42, not the general law’s 0.29, and that modulo three they approach the symmetric law from below as these approached the general one.”

At twenty vertices both halves hold. At twenty-one the first fails completely, and the reason it fails is a fact about graphs that the symmetric law does not know.

Three kinds of matrix at every order #

The graphs are the Erdős–Rényi kind: on $n$ vertices, each of the $\binom{n}{2}$ possible edges present by a fair coin, and the matrix is the adjacency matrix, with a one wherever two vertices are joined and zeros on the diagonal, since no vertex is joined to itself. Three thousand at each order from 8 to 21. Beside them, two controls of the same order and the same count: the same kind of graph with a loop on each vertex, also by a fair coin — a symmetric 0/1 matrix whose diagonal is as random as the rest of it — and a general 0/1 matrix, symmetric in nothing, which is the kind the earlier essays measured.

Every matrix is ranked exactly modulo 2, 3 and 5 by elimination in small integers, and over the rationals as the larger of its ranks modulo two primes near $2^{31}$, the construction the field decides it, usually checked against exact rational elimination. Nothing here is rounded, so every share is a count.

The general matrices sit on the uniform law, 0.276 to 0.306 at every order, as before. The graphs with loops sit on the symmetric law, 0.389 to 0.439, at every order. The graphs sit on the symmetric law at every even order — 0.409 to 0.434 — and at zero at every odd order: not one graph of 21,000 with an odd number of vertices has an adjacency matrix that is invertible modulo two.

The diagonal decides the parity #

Modulo two, a symmetric matrix with a zero diagonal is alternating: for every vector $x$ over the field,

$$x^{\mathsf T} A x = \sum_i a_{ii} x_i^2 + 2 \sum_{i<j} a_{ij} x_i x_j \equiv 0 \pmod 2,$$

because the diagonal terms are zero and every off-diagonal pair appears twice. Alternating forms are the most rigid kind of bilinear form there is. Their rank is always even — the matrix can be brought by a change of basis to a block diagonal of $2 \times 2$ blocks $\left(\begin{smallmatrix} 0 & 1 \\ 1 & 0 \end{smallmatrix}\right)$ and zeros — so an alternating matrix of odd order always has a null vector, whatever its entries.

Over the rationals and modulo odd primes the same matrix is not alternating, because $2 \ne 0$ there: the identity above says only that $x^{\mathsf T}Ax$ is even, which is no constraint on rank. So the zero diagonal is a fact about the graph that only the field with two elements turns into a law.

The figure shows the parity in full. At twenty vertices every graph has an even corank modulo two and none an odd one: 40.9% at zero, 57.1% at two and 2.1% at four, against the alternating law’s 41.9%, 55.9% and 2.1%. Turn the dial to twenty-one and every corank is odd: 84.1% at one, 15.7% at three, 0.2% at five, against the law’s 83.9%, 16.0% and 0.1%. The law here is MacWilliams’s count of alternating matrices of each rank over a finite field, divided by the number of alternating matrices; it agrees with the measurement within four standard errors at every corank from twelve vertices up. The graphs with loops, whose diagonal is a coin, fill both parities — 42.7% invertible at twenty-one vertices — and follow the symmetric law at every order.

The prediction’s number was right for a reason it did not give. The symmetric and alternating laws for invertibility are the same product, $\prod_{i=1}^{m}(1 - q^{1-2i})$, at even order $n = 2m$; at odd order the symmetric law takes one factor more and the alternating law is zero. A prediction stated at twenty vertices could not tell them apart. One vertex more could.

What a determinant modulo two counts #

There is a combinatorial reading of the same fact, and it says what the determinant of a graph is, modulo two. An alternating matrix of even order has a Pfaffian, a polynomial in its entries whose square is its determinant. For an adjacency matrix the Pfaffian is a signed sum over the graph’s perfect matchings — the ways of pairing every vertex with a neighbour — and modulo two the signs disappear. So the adjacency matrix is invertible modulo two exactly when the graph has an odd number of perfect matchings.

That is checkable by brute force on small graphs, and it holds on every one of 1,200 checked — 300 at each of eight, nine, ten and twelve vertices, matchings counted by enumeration. A graph with an odd number of vertices has no perfect matching at all, zero is even, and the determinant of every odd-order graph is an even integer. At even order the count is a large number whose last bit is a coin: on 300 graphs with twelve vertices the number of perfect matchings runs from 2 to 1,300 with a median of 115, and it is odd on 133 of them — 44%, against the alternating law’s 42% and inside its noise. How many primes the answer needs reconstructs a determinant from its residues; for these matrices the residue modulo two is known before anything is computed.

One loop is enough #

If the zero diagonal is what makes the law alternating, the obvious question is how much of the diagonal has to be filled in to undo it, and the answer is one entry. Put a loop on a single vertex chosen at random — one diagonal entry equal to one, the rest zero — and at twenty-one vertices the share invertible modulo two goes from zero to 0.408. Two loops give 0.432, three give 0.408, a loop on every vertex gives 0.425, and the symmetric law says 0.419: every one of them within the noise of 3,000 draws, and none of them distinguishable from a diagonal of fair coins. At twenty vertices the same counts give 0.418, 0.429, 0.415 and 0.409, all on the same law, which there is also the alternating one.

The algebra says why one is enough. With a single loop at vertex $v$, the form becomes $x^{\mathsf T}Ax \equiv x_v$ modulo two — no longer identically zero, so the matrix is no longer alternating, and nothing forces its rank to be even. The symmetric law, as a law, does not care what the diagonal is; it cares only whether the diagonal is identically zero, because that is the one case in which the form is alternating and a different law applies. Every other diagonal, including one with a single one in it and including the all-ones diagonal of a graph with a loop at every vertex, leaves a matrix that a random change of basis makes look like any other symmetric matrix. So the law a graph follows modulo two is set by one bit of information about it — whether it has any loop at all — and that bit is fixed, for a simple graph, before any edge is drawn.

There is a practical edge to this. Adjacency matrices of simple graphs are the ones most often handed to a solver modulo two — in coding theory, in counting problems, in the matching algorithms that the Pfaffian identity above underlies — and the parity rule means that a randomised method which hopes for an invertible matrix modulo two on an odd number of vertices will never get one. The common repair, adding the identity, works for exactly the reason a single loop does, and costs nothing in the law.

The figure shows what that does to the question the earlier essays asked: of the matrices that are invertible over the rationals, what share become singular modulo a prime. For general 0/1 matrices modulo two it climbs to 0.71 and stays — the uniform law’s 1 − 0.289. For graphs it is exactly one at every odd order and 0.55 to 0.59 at every even order from fourteen, lower than the general matrices’ share because the alternating law’s 0.42 is higher than the uniform law’s 0.29. Modulo three the graphs lose 0.34 to 0.36 from fifteen vertices, against 0.41 to 0.45 for general matrices: the symmetric law is kinder than the uniform one modulo three as well, by about the same margin.

Modulo three the zero diagonal is only a constraint #

At an odd prime there is nothing alternating about an adjacency matrix. It is a symmetric matrix with a constraint on its diagonal and with entries that are not uniform over the field: each entry is 0 or 1, never 2. Both are departures from the hypotheses of the symmetric law, and the earlier essays found that a departure of the second kind — entries confined to 0 and 1 — costs a general matrix something at small sizes and nothing from about sixteen rows.

The prediction holds here as stated. Modulo three the graphs start at 0.498 at eight vertices, against the symmetric law’s 0.639, and reach it from below: 0.586 at twelve, 0.628 at fourteen, and 0.622 to 0.643 from sixteen on, inside the noise of 3,000 draws. Modulo five they start at 0.563 and reach the law’s 0.793 at the same size. The graphs with loops get there a little sooner, and the general matrices reach their own, lower, uniform law at about the same order.

At eight vertices nearly all of the shortfall below the symmetric law is the rationals’. A matrix that is singular over the rationals is singular over every field, and at eight vertices 41% of the graphs are singular over the rationals; the share invertible modulo three, 0.498, is 85% of the share invertible over the rationals, 0.588, which is close to the law’s 0.639 as a fraction of one. That is the shape the earlier essay found for general matrices at eight rows: the rationals set the ceiling and each field takes its law’s share of what is under it.

Singular over the rationals #

So the rationals’ own law is the last thing the graphs have to show. The general 0/1 matrices’ singular share falls fast with the order, and the graphs’ falls almost exactly as fast.

At eight vertices 41% of the graphs are singular over the rationals and 43% of the general matrices; at twelve, 16% of both; at sixteen, 2.9% and 3.3%; at twenty, 0.17% and 0.37%; at twenty-one, two graphs of 3,000 and one general matrix. The two curves cross each other inside their noise at every order, so on this measure a graph’s symmetry costs nothing and buys nothing.

What changes with the order is the cause. A graph’s adjacency matrix has two equal rows when two vertices that are not joined to each other have exactly the same neighbours — twins — and a zero row when a vertex has no neighbours. Either makes it singular, and at eight vertices the two explain 57% of the singular graphs. By twelve they explain a quarter, by sixteen a tenth, by eighteen three graphs of twenty-four. The chance that a given pair of vertices are twins halves with each vertex added, since they must agree on one more neighbour, and the rest of the singularity — a dependence among three rows or more — is already the larger part from nine vertices on. It is the same shape the earlier essay predicted for general matrices, where two equal rows or columns account for a vanishing part of the rational shortfall at twenty rows.

What the symmetric law misses #

The symmetric law is a statement about uniformly random symmetric matrices over a field, and a graph is not one: its diagonal is fixed at zero and its entries are fixed at zero or one. The measurement says that the second departure is forgiven by sixteen vertices, modulo every prime measured, exactly as it was for general matrices — and that the first is forgiven everywhere except modulo two, where it is not a departure from the symmetric law at all but a change of law.

That distinction matters beyond the count. A matrix with no numbers in it built two matrices from a graph, and the adjacency matrix is the one with nothing on its diagonal; the Laplacian puts the degrees there. Modulo two the degrees are parities, and a Laplacian of a graph whose every degree is even is again alternating — and a parity condition of the same kind, a set’s indicator vector lying in the Laplacian’s kernel modulo two, is what the set has to be even outward found decides whether a switch is heard by the critical group modulo two. The same arithmetic, read off a different matrix of the same graph. The group hears a switch only at two found the prime two special for graph invariants as well; two is the one characteristic in which a symmetric matrix with an even diagonal cannot be told from an alternating one, and whether that is the whole of the reason there is not something these counts can show.

What 3,000 graphs at each order do not settle #

The edge probability is one half throughout. At a lower density the entries are farther from uniform over every field, the rationals’ singular share is larger — isolated vertices alone make a sparse random graph singular often — and the approach to each law would be slower; the field decides it, usually measured that cost for general matrices, and it was large at a quarter. The alternating law modulo two does not depend on density in the same way: the parity argument is exact at every density, and only the share at even order would move. With 3,000 draws each share has a standard error of about one point, so a departure from a law smaller than two points is invisible here, and the corank agreement from twelve vertices up is agreement to that resolution. The single-loop result is the one most exposed to that limit: three thousand draws can say that one loop puts an odd-order graph within a point or two of the symmetric law, not that it puts it exactly there, and a difference between one loop and a full diagonal of coins of a point or less — which the algebra does not rule out at these sizes — would need thirty times as many graphs to see.

Still open: sparse graphs, and the Laplacian modulo two #

A sparser graph. At edge probability one quarter a graph on twenty vertices has an isolated vertex about one time in twelve, and twins much more often than at one half. The prediction with a sign is that modulo two the graphs at even order fall below the alternating law’s 0.42 by at least the share singular over the rationals — more than five points at twenty vertices — while the odd orders stay at exactly zero, so that the parity survives any density and the even-order rate does not.

The Laplacian. A graph’s Laplacian always has the all-ones vector in its kernel, so it is singular over every field; the question is its corank. Modulo two it is alternating exactly when every degree is even, and otherwise it is a symmetric matrix with a diagonal fixed by the degrees. The prediction is that on random graphs with edge probability one half the Laplacian’s corank modulo two is one more than the symmetric law’s corank distribution for a matrix of one order less, with the parity of the order mattering only through the graphs whose degrees are all even — about $2^{-(n-1)}$ of them, too few to see in 3,000. Two Laplacians of one graph is the account of which Laplacian a reader should expect the next count to be about.