Each column divides by the prime

The field decides it, usually counted how often a matrix’s rank depends on the field it is read over. Random 0/1 matrices showed it at almost every size: at twenty rows 99.8% are invertible over the rationals, 29% modulo two and 56% modulo three, and modulo two they obey, corank by corank, the law for uniformly random matrices over that field — invertible with probability $\prod_{k=1}^{n}(1 - q^{-k})$, which for $q = 2$ never rises above 0.289.

Its last section turned to rectangular matrices. An $n \times (n+k)$ matrix over a field with $q$ elements has full row rank with probability $\prod_{i=k+1}^{n+k}(1 - q^{-i})$, which is much nearer one, and “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.” It added a second prediction, with a sign: that the square matrices’ gap to the law “closes geometrically in $n$, at a rate set by how far the entry distribution is from uniform modulo the prime”.

The first half of the first prediction holds, and more generally than stated. The second half holds and turns out to be the explanation. The second prediction was looking at the wrong field.

Six columns to spare #

The matrices are 0/1 with each entry a fair coin, 3,000 of them at each of eight, twelve, sixteen and twenty rows, each drawn with six columns more than rows. Every prefix is read — the square matrix, then one column more, then two — so the comparison across column counts is on the same matrices. Each prefix is ranked modulo 2, 3, 5 and 7 by elimination in small integers, and over the rationals as the larger of its ranks modulo two primes near $2^{31}$, which equals the rational rank unless both primes divide every maximal minor; the earlier essay checked that construction against exact rational elimination.

The figure at the top of the page is the field-dependence the prediction was about: of the matrices the rationals call full rank, the share some prime does not. Square, it is 71.8% modulo two, 44.6% modulo three, 24.0% modulo five and 15.4% modulo seven. One extra column takes those to 43.1, 16.2, 4.9 and 2.5 per cent; two to 24.1, 5.6, 1.0 and 0.5; four to 6.5, 0.7, under 0.1 and under 0.1. Every line is straight on the logarithmic axis, and every line sits on its dashed law.

The prediction said three and five. It holds for every prime, two included, and the rate is the same rule for each: each column divides the shortfall by about $q$. Modulo two the ratios from one column count to the next are 1.7, 1.8 and 2.0; modulo three 2.8, 2.9 and 2.9. With $k$ extra columns the law’s shortfall is dominated by its first factor, $1 - (1 - q^{-(k+1)}) = q^{-(k+1)}$, so the chance of falling short is about $q^{-(k+1)}$ divided by $1 - 1/q$, and each extra column removes one power of $q$.

Why a column is worth a power of the prime #

Over a field, an $n \times (n+k)$ matrix falls short of full row rank exactly when its rows are dependent, and a fixed nonzero combination of the rows vanishes on each new column with probability $1/q$ when the column is uniform. Adding a column is one more independent chance to break every dependence the first $n + k - 1$ columns allowed; the chance that the smallest one survives is divided by $q$.

Over the integers the same statement reads differently, and the difference is the essay’s second half. A rectangular integer matrix has full rank modulo $p$ unless $p$ divides every one of its maximal minors — every $n \times n$ determinant that a choice of $n$ columns makes. A square matrix has one maximal minor, its determinant; an $n \times (n+k)$ matrix has $\binom{n+k}{n}$ of them. The rank modulo $p$ is full when $p$ fails to divide the greatest common divisor of all of them, which is a much weaker demand than that $p$ fail to divide any particular one. The prediction’s phrase, “the determinant’s divisibility, which is a square-matrix question”, is exactly right, and it is the mechanism: the leading square block’s determinant goes on being divisible by $p$ at the square rate, and the rank stops caring.

The figure shows it on the same matrices. The leading block is nonsingular modulo two on 28.1% of them, the square law’s 28.9% within sampling error; the whole matrix of which it is the first twenty columns is full rank modulo two on 93.5%. Modulo three, 55.2% against 99.3%; modulo five and seven, 75.7% and 84.3% against all of them. Adding columns did not make any minor less divisible by the prime. It added minors, and the rank needs only one of them not to be.

A prime that divides the answer met the same distinction in a modular solve: a prime that divides the determinant is unlucky for the solve, whatever the other primes say. The rank of a rectangular matrix has more chances than a solve with a square one, and a prime has to be unlucky for all of them at once.

The invariant factor that has to be prime to p #

The same fact has a cleaner statement in the language the rank depends on the ring opened the subject with. Every integer matrix has a Smith normal form: unimodular row and column operations — the ones that can be undone over the integers — reduce it to a diagonal of invariant factors $d_1 \mid d_2 \mid \cdots \mid d_n$, each dividing the next. For an $n \times (n+k)$ matrix of full rational rank there are $n$ of them, and their product is the greatest common divisor of all the maximal minors. Unimodular operations survive reduction modulo any prime, so the rank modulo $p$ is $n$ minus the number of invariant factors $p$ divides — and since they divide each other in order, it is full exactly when $p$ does not divide the last one, $d_n$.

For a square matrix, $d_n$ carries most of the determinant: what a determinant does not determine and the swell was one-sided both found random square integer matrices to have Smith forms of all ones and then the determinant, so a prime that divides the determinant divides $d_n$, and the rank modulo $p$ drops. A rectangular matrix’s $d_n$ is a common divisor of many determinants, and a common divisor of many random-looking integers is almost always one. Each extra column multiplies the number of maximal minors and leaves fewer integers for which a given prime divides all of them. The law’s factor of $1/q$ per column is that dilution, counted.

Nothing in this requires the field at all, which is the point of reading it this way. The rank over $\mathbb{F}_p$ is a question about one prime and the matrix’s last invariant factor, and the integers decide it before any reduction is made. Every entry under the determinant worked modulo the determinant because the determinant bounds everything the lattice can say; here the last invariant factor is the smaller number that bounds what every field can say about the rank.

The law holds from sixteen rows #

At sixteen and twenty rows every prime’s measured share sits on its law at every column count, within four standard errors on all fifty-six comparisons — four primes, seven column counts, two row counts. The rationals sit at the top, above 0.97 square and above 0.999 with two columns to spare. The law was derived for matrices whose entries are uniform over the field, and 0/1 matrices are uniform only modulo two; modulo three, five and seven their entries never take most of the field’s values. At these sizes it does not matter. Twenty rows of coin flips have forgotten, modulo every small prime, that they were coin flips.

Turn the dial to eight rows and that stops being true for every prime but two. Modulo two the eight-row matrices are still on the law — 0.292 square against 0.290 — because their entries are uniform modulo two at every size. Modulo three, five and seven they fall below their laws, and the dial at twelve rows shows the shortfall shrinking.

Why a law derived for uniform entries should hold for coin flips modulo seven is worth a sentence. A determinant is a sum of $n!$ signed products, and its residue modulo a small prime is a sum of so many nearly independent terms that the entries’ own distribution is washed out — the same reason a sum of many dice is close to uniform modulo a small number whatever the die. The washing-out needs enough terms, and at eight rows it is incomplete for every odd prime; at sixteen it is complete to within sampling error. An answer with no error in it began this field with exact arithmetic as a guarantee; this is exact arithmetic as a census, and the census says that small primes treat integer matrices of moderate size as random over their field, whatever the integers’ own distribution.

At eight rows the rationals set the ceiling #

The shortfall is not modulo the prime at all. A matrix that is rank deficient over the rationals is rank deficient over every field, because a rational dependence among its rows clears denominators into an integer dependence that survives reduction modulo anything. At eight rows, 44% of square 0/1 matrices are singular over the rationals — two equal rows, a zero row, a row that is the sum of two others are all common when there are only $2^8$ possible rows — and every one of them is singular modulo every prime, which the measurement checks matrix by matrix.

So the eight-row share modulo five and seven is the rational share — 0.542 and 0.555 against the rationals’ 0.558 — and the uniform laws, 0.760 and 0.837, are not reachable. Modulo three, 0.465, the field’s own shortfall adds a little to the rationals’. The same holds with columns to spare: the rational share climbs to 0.996 with six extra columns and every odd prime climbs with it, step for step.

This is where the second prediction went wrong. It expected the square matrices’ gap to the law to close “at a rate set by how far the entry distribution is from uniform modulo the prime”, and it read the gap as a property of the field — slower modulo five than modulo three, because 0/1 entries cover two-fifths of the field rather than two-thirds. At these sizes the gap is the rationals’ singularity probability, which is the same for every prime and falls with $n$ at its own rate: 44% at eight rows, 17% at twelve, 3% at sixteen, 0.4% at twenty. Modulo five the gap to the law is 0.22 at eight rows and 0.06 at twelve; modulo seven 0.28 and 0.08; modulo three, whose law is lowest and so least constrained by the rational ceiling, 0.10 and 0.02. Five does close more slowly than three, as predicted — but because its law sits higher under the same ceiling, not because its entries are further from uniform.

A column or two, prime by prime #

Read the other way, the law says how many columns a matrix needs before a prime stops mattering. Modulo two, 28% of twenty-row matrices need none, 29% need one, 19% two, and 1.7% still fall short with six; the mean, counted to six, is 1.51 columns. Modulo three the mean is 0.69 against the law’s 0.68; modulo five 0.30 against 0.30; modulo seven 0.19. A matrix that will be read modulo many primes — as how many primes the answer needs reads every exact solve — is limited by the smallest, and modulo two it takes about seven extra columns before fewer than one matrix in a hundred falls short.

The practical version is the one exact-rank algorithms use: to decide the rank of an integer matrix modulo a prime with high confidence, it is not the matrix that should be random but the reduction. Multiply by a random matrix with a few extra columns, or project to a few extra random combinations, and a prime that divided every maximal minor of the original would have to divide every minor of the projection. Rank is a decision made the floating-point version of that point; here the decision is exact and only the field is chosen, and choosing a large one is the same remedy as adding columns, since the shortfall is about $1/q$ either way.

The two remedies — more columns, or a larger field — price differently, and the measurement says by how much. Each extra column costs one more column of elimination, a fraction $1/n$ of the work, and buys a factor of $q$. A larger prime buys the same factor all at once: modulo a prime near $2^{31}$ the shortfall of a square matrix is about $2^{-31}$, and the arithmetic still fits in a machine word with room to multiply. For deciding a rank, the large prime is the better trade by far, which is why the rational ranks here are computed that way. The small primes are where the trade becomes visible, and they are also where it matters in practice, because a computation over $\mathbb{F}_2$ is not chosen for convenience — codes, graphs and parity problems live there — and in that field the only remedy is more columns or more equations, at one bit of confidence per column. Seven columns for a one-in-a-hundred chance of falling short, ten for one in a thousand: a rule of thumb that is exact enough to plan with, since the measured shares sit on the law to sampling error from sixteen rows up.

What the coin flips do not settle #

The entries here are fair coins. Sparse 0/1 matrices — the earlier essay measured density a quarter — are not uniform modulo two, and the law should then be approached from below at small sizes for every prime, two included; whether a column still divides the shortfall by two there is not measured. The rational rank is the larger of two large-prime ranks, which is exact unless both primes divide every maximal minor; on 0/1 matrices of these sizes that would need minors with two specific ten-digit prime factors, and it was not ruled out by an independent rational elimination on the rectangular ones. And the mean extra columns are counted to six; modulo two the 1.7% that need more pull the measured mean below the law’s 1.61.

Still open: symmetric matrices, and the rational ceiling’s own law #

Adjacency matrices. The earlier essay’s second question stands. 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.

The rationals’ own shortfall. At eight rows 44% of 0/1 matrices are singular over the rationals, then 17%, 2.8% and 0.4% at twelve, sixteen and twenty. Two equal rows or two equal columns account for about $2\binom{n}{2}2^{-n}$ of it, which is 0.04% at twenty rows against the 0.4% measured. The prediction with a sign is that the shortfall keeps falling by a factor of about seven every four rows, to about 0.06% at twenty-four, and that dependences among three or more rows carry at least nine-tenths of it at every size from sixteen up — so that the rational ceiling is not a matter of repeated rows at any size measured.