The field decides it, usually

The rank depends on the ring showed a six-by-six integer matrix of rank six over the rationals, five modulo three and four modulo two, and was candid about how it got there. The first attempt took a random integer matrix, made two rows dependent, and hoped a small prime would drop the rank further; it did not, because a dependency built with integer coefficients holds modulo everything at once. So the matrix was built from its invariant factors — $\mathrm{diag}(1,1,1,1,2,6)$, hidden by two unimodular conjugations — and the ranks at every prime were known before anything was computed. The essay drew the moral that “a counterexample built from the property is evidence about the property.”

A built counterexample is evidence the property exists. It says nothing about how often a matrix nobody built has it, and the story of the first attempt reads as a hint that the answer is rarely. This essay measures the answer, on the simplest random integer matrices there are.

Five ranks for every matrix #

The matrices are square, with every entry 0 or 1, each 1 with probability one half, three thousand seeded draws at each size from 2 to 20. Each one’s rank is computed exactly over the rationals and modulo 2, 3, 5 and 7. The rational rank comes from elimination modulo two primes near $2^{31}$: a rank computed modulo a prime can fall below the rational rank only if the prime divides every maximal minor, and for two primes of that size that is not a case the sample will meet. Nothing is rounded and nothing is thresholded; rank is a decision is about the other way a rank stops being a property of the array, and it does not apply here.

The yardstick is a closed form. An $n \times n$ matrix whose entries are uniformly random over the field with $q$ elements is invertible with probability $\prod_{k=1}^n (1 - q^{-k})$ — the chance that each new row avoids the span of the ones before it, multiplied out — which for large $n$ is 0.289 for $q = 2$, 0.560 for $q = 3$, 0.760 for $q = 5$ and 0.837 for $q = 7$. A fair 0/1 matrix is exactly such a matrix over the field of two elements. Over the field of three it is not: no entry is ever 2.

The fields part company #

At two rows every field agrees: 38% of the matrices are invertible, which is the six of sixteen two-by-two 0/1 matrices with nonzero determinant, and a determinant of 1 or −1 is nonzero modulo everything. From there the fields separate. Over the rationals the invertible share rises — 0.42 at six rows, 0.71 at ten, 0.93 at fourteen, 0.998 at twenty. Modulo two it falls to the uniform law at once and stays on it: 0.33 at three rows against 0.328, 0.29 from six rows on against 0.289, at every size within the sampling error. Modulo three and five it starts on the rational curve and climbs away from it more slowly, towards the uniform law of its own field: modulo three 0.55 at twelve rows and 0.565 at twenty against 0.560; modulo five 0.72 at twelve and 0.74 at twenty against 0.760.

Two things were not obvious in advance. The share modulo two is exactly the uniform law, not approximately: over the field of two elements a fair 0/1 matrix is a uniformly random matrix, so a theorem about the second applies word for word. And the share modulo three arrives at the uniform law of the field of three, although the matrices have entries only 0 and 1. The distribution of the rank has forgotten which residues the entries could take.

Invertible over the rationals, singular modulo p #

The question the earlier essay’s construction answered is whether a matrix can be invertible over the rationals and singular over a prime field. For a random 0/1 matrix, the question is how often it is not. A matrix invertible over the rationals is singular modulo $p$ exactly when $p$ divides its determinant, and the shares climb with the size: modulo two, 3% at three rows, 47% at eight, 70% at sixteen and 71% at twenty; modulo three 17% at eight and 43% at twenty; modulo five 26% and modulo seven 17% at twenty. At twenty rows a rationally invertible 0/1 matrix is more likely than not to have an even determinant, and nearly half have a determinant divisible by three.

The dashed lines are what a uniform determinant would give, and the measured shares approach them. At twenty rows the chance that two divides the determinant of a rationally invertible matrix is 0.709, and one minus the uniform invertible share is 0.711: conditioning on invertibility over the rationals has not changed the determinant’s residue modulo two at all. A prime that divides the answer met this case as a hazard of modular elimination — an elimination modulo $p$ that reports a singular matrix and is telling the truth about the wrong field. On this evidence it is not an edge case at small primes. It is the typical case, and it is why modular algorithms use primes near $2^{31}$ and not primes near ten.

A law that no 0/1 matrix was built to obey #

The invertible share is one number; the full distribution of the corank is a sharper test. For large uniform matrices over the field with $q$ elements, the chance that the corank is $r$ is $q^{-r^2}\prod_{i>r}(1-q^{-i})/\prod_{i\le r}(1-q^{-i})$ — for $q = 2$, 0.289 for corank zero, 0.578 for one, 0.128 for two and 0.005 for three. The twenty-row 0/1 matrices modulo two give 0.290, 0.578, 0.128 and 0.003. Modulo three the law is 0.560, 0.420, 0.020, and the measurement is 0.565, 0.417, 0.018; turn the dial to five and the bars fall on that law too. A matrix with corank two modulo three is a matrix with two independent relations among its rows that hold modulo three and fail over the rationals, the very object the earlier essay built by hand; one in fifty-six random 0/1 matrices of this size has one.

This convergence is not a coincidence of the sample. That the corank of a random integer matrix modulo a prime approaches the uniform law of that field, whatever the distribution of the entries so long as it is not concentrated modulo the prime, is a theorem of recent random matrix theory; what the figure shows is how early it takes hold — by twelve rows modulo three the invertible share is within a per cent of the law — and that the one prime for which 0/1 entries are already uniform is the one where it holds from the start.

Why the entries are forgotten #

The convergence modulo three can be understood without the theorem, by building the matrix a row at a time. A square matrix is invertible over a field when each new row falls outside the span of the rows before it. When $k$ rows are in place and span a subspace of dimension $k$, a uniformly random new row lands inside that subspace with probability $q^{k-n}$, and multiplying the chances of missing it gives the product formula. Everything depends on how a new row sits relative to a subspace, not on its entries one by one.

A 0/1 row modulo two is uniform, so the formula holds exactly. A 0/1 row modulo three is not — it can never have a 2 in it — but the only thing that matters is which coset of the current subspace it lands in, and a subspace of dimension $k$ has $3^{n-k}$ cosets. When $n - k$ is large the cosets are many and each is hit by a 0/1 row with nearly the same probability, because the row has $n$ independent coordinates and the coset is decided by $n - k$ linear combinations of them, each of which mixes many coordinates. Only in the last few rows, where $n - k$ is small and the cosets are few, could the missing residue show — and those rows are also the ones where the subspace is large and generic, and its linear combinations mix every coordinate. The product formula is built from exactly the quantities that averaging over many coordinates makes uniform, which is why the law is reached from matrices that cannot fill the field.

The same account says why small sizes stay on the rational curve. With three rows, a subspace of dimension one or two has only three or nine cosets, the 0/1 rows are far from uniform over them, and the matrices that happen to be singular modulo three are almost exactly those that are singular over the rationals: the determinant of a three-by-three 0/1 matrix lies between −2 and 2, and only zero is divisible by three. Modulo three nothing is lost until the determinants are large enough to be multiples of three by accident: at four rows, where a 0/1 determinant can first reach 3, 0.8% of the invertible matrices are singular modulo three, and at six rows 6%.

Density, and what it does not change #

At any density other than one half, a 0/1 matrix is not uniform over the field of two, and the law has to be earned. With a quarter of the entries 1, the invertible share modulo two is 0.06 at four rows and 0.08 at eight, far under the law, because sparse rows are often zero or equal; it then climbs, 0.12 at twelve, 0.21 at sixteen, 0.24 at twenty, closing on 0.289 from below. With three quarters it is 0.19 at eight and 0.289 at twenty, on the law. The density sets how long the approach takes, not where it ends.

Over the rationals the same densities show the opposite end state. The singular share falls towards zero at every density, from 65% at four rows to 3.2% at sixteen and 0.2% at twenty for fair matrices, from 93% to 19% over the same range for sparse ones, and from 73% to 6% for dense ones — the dense matrices are close to the all-ones matrix, which has rank one, and pay for it at small sizes. That the rational singular share goes to zero is the old theorem of Komlós; that it does so exponentially, roughly halving every row, is the modern sharpening. Two limits, then, pulling apart: over the rationals invertibility becomes certain, over a small prime field it settles at a constant well below one, and the gap between them is the share of invertible matrices whose determinant the prime divides.

One matrix, drawn #

The effect the earlier essay built can now be found by drawing. The eight-by-eight matrix in the figure is the first of the seeded draws that is invertible over the rationals, loses two ranks modulo two and one modulo three. Its determinant is 12. Its rank is 8 over the rationals and modulo five and seven, 7 modulo three and 6 modulo two: three ranks from one array of zeros and ones, none of them wrong, none of them approximate. A determinant of 12 says that 2 and 3 divide it; that the rank modulo two falls by two and modulo three by one is the finer statement that the Smith form’s last two invariant factors are even and its last one is a multiple of three — the invariant-factor account of what a determinant does not determine, read off a matrix nobody designed.

The earlier essay’s first attempt failed for a different reason than rarity. It made a random matrix singular by making two rows dependent, and a dependency with integer coefficients survives reduction modulo every prime — so every field saw the same deficiency. What produces a field-dependent rank is not a dependency but a determinant with small prime factors, and random 0/1 matrices have those in abundance, because their determinants are sums of many ±1 products and land on multiples of small primes about as often as a random integer does.

What the construction still owes nothing to #

None of this weakens the earlier essay’s method; it changes what the method was for. The constructed matrix came with a guarantee — three exact ranks at every one of six sizes, known before anything was computed — and a construction that lost the structure would have been caught at once. A random draw cannot come with that kind of guarantee, because a random matrix has whatever ranks it has; what it can carry is a share with an error bar and a law to compare it with, which is the other kind of evidence and the one this essay needed. An answer with no error in it made the same division of labour for exact elimination: exactness settles what one computation is, and it takes many computations to say what is typical.

What changes is the reading of the first attempt’s failure. It was read, reasonably, as a sign that field-dependent rank has to be manufactured. It was a sign that a particular way of making a matrix singular — a dependency with integer coefficients — produces the one kind of singularity that every field agrees on. The kind the fields disagree on is the kind random matrices have by default: a nonzero determinant with small prime factors. The number that decides nothing found the determinant a poor guide to near-singularity over the reals; over the prime fields its factorisation is the whole guide.

What this changes for exact computation #

The prime is a choice with a failure rate, and the rate is not small for small primes. An exact rank computed modulo one prime is a lower bound on the rational rank, wrong with the probability that the prime divides the relevant minor. For these matrices that probability is about $1/p$ plus smaller terms — 71% modulo two only because two is where every term counts — and at $p \approx 2^{31}$ it is negligible. How many primes the answer needs counted primes for reconstructing an answer; the same arithmetic prices how many are needed to trust a rank. A count that comes out of a determinant computed spanning-tree counts, which are determinants of integer matrices, in floating point; the counts it measured are exactly the kind of integer whose small prime factors decide the ranks here, and a modular route to them would have to avoid primes that divide them.

The field is part of the question. A rank over $\mathbb{F}_2$ is the natural quantity in coding theory, in graph theory’s cycle spaces, and in any problem whose entries are parities; the rank over the rationals is the natural one for a linear system with integer data. For a random 0/1 matrix of moderate size they differ more often than they agree, so a statement of rank without its field is not an incomplete statement but, most of the time, a false one for one of the fields a reader might assume. A finer invariant that hears less found the Smith form’s factors deciding a graph question; here they decide which field sees which rank.

What three thousand draws do not show #

Three thousand draws a size, one entry distribution with three densities, primes up to seven, sizes to twenty. The shares carry a sampling error of about one per cent, which is the tolerance every comparison with a law is made at. The rational rank is exact only up to the two large primes dividing every maximal minor, which for these sizes is a chance far below one in a million. And nothing here says how the convergence modulo three depends on the entry distribution beyond the three densities measured.

Still open: rectangular matrices, structured ones, and the rate of forgetting #

Rectangular matrices. An $n \times (n + k)$ matrix over a field has full rank with probability $\prod_{i=k+1}^{n+k}(1-q^{-i})$, much closer to one. The prediction is that a few extra columns remove most of the field-dependence of full rank modulo three and five, and none of the field-dependence of the determinant’s divisibility, which is a square-matrix question.

Structured 0/1 matrices. Adjacency matrices of random graphs are symmetric, and symmetric matrices over $\mathbb{F}_2$ follow a different law. Whether a random graph’s adjacency matrix converges to the symmetric law modulo two and three as these converge to the general one is the measurement that connects this to the graph field.

How fast the entries are forgotten. Modulo three the invertible share reaches its law within a per cent by twelve rows at density one half, and more slowly at a quarter. The prediction with a sign is that the gap closes geometrically in $n$, at a rate set by how far the entry distribution is from uniform modulo the prime — which would make the approach modulo five slower than modulo three, as the figure’s twelve-row values suggest.