How often a table of random signs is flat

The number that says how much room is left introduced the determinant as a volume: the factor by which a matrix stretches space, and nought exactly when it squashes space flat into fewer dimensions. The biggest box built from signs then asked how large that volume can be when every entry is $+1$ or $-1$, and found the answer in tables whose rows are perpendicular — Hadamard’s matrices, which are as far from flat as a table of signs can be.

This essay asks the opposite question about the same tables, and asks it of a typical table rather than the best one. Fill an $n \times n$ table with signs chosen by fair coins. How likely is it to be flat?

The answer, drawn above, is not small at first. For four rows, two tables in three are flat. For six rows it is still five in eight. Only past seven or eight does the chance start to fall, and it then falls by roughly half for each row added. The figure also carries a second curve, the chance that two rows or two columns of the table are equal or are negatives of each other. That accident obviously makes a table flat, and the question this essay is about is how much of the flatness it explains.

Sixteen tables of two rows #

The smallest case shows the whole mechanism at once. A $2 \times 2$ table of signs has two rows, each one of four arrows from the origin — $(1, 1)$, $(1, -1)$, $(-1, 1)$, $(-1, -1)$ — and its determinant is the signed area of the parallelogram the two arrows span.

The four arrows point at the corners of a square, so two of them either are perpendicular, giving a square of area 2, or lie on one line, giving nothing. Eight of the sixteen tables are flat, and every one of them is flat because its second row equals its first or is its negative. There is no other way to fail with two rows, so at $n = 2$ the chance of a flat table is exactly one half and the dull accident explains all of it.

With more rows there are more ways to be flat. A table is singular whenever some combination of its rows, with coefficients not all nought, adds up to the zero row. Two equal rows are the combination $r_1 - r_2$. But $r_1 + r_2 - r_3 - r_4$ can vanish too, without any two rows being equal, and so can longer combinations with larger coefficients. How the chance of singularity behaves is a contest between the one cheap accident, which has a fixed small number of ways to happen, and the expensive ones, which are individually rarer but far more numerous.

Every table up to six rows #

For small tables the chance can be found by checking every table, and a symmetry makes the check much cheaper than it looks. Changing the sign of a whole row, or of a whole column, multiplies the determinant by $-1$ and so does not change whether it is nought. Every table can therefore be brought to a normal form whose first row and first column are all plus signs, and each normal form stands for exactly $2^{2n-1}$ tables. Subtracting the first row from each of the others then turns every entry below it into $0$ or $-2$, and pulling out the factor $-2$ from each of those $n - 1$ rows leaves a table of noughts and ones of size $n - 1$. So the determinant of an $n \times n$ table of signs is always a multiple of $2^{n-1}$, and the singular tables of signs correspond exactly to the singular $(n - 1) \times (n - 1)$ tables of noughts and ones.

For six rows that is $2^{25}$, a little over 33 million, determinants of $5 \times 5$ tables of bits, which a machine computes in seconds.

The counts are $10$ of $16$ normal forms for three rows, $338$ of $512$ for four, $42{,}976$ of $65{,}536$ for five and $21{,}040{,}112$ of $33{,}554{,}432$ for six — shares of 62.5, 66.0, 65.6 and 62.7 per cent. At every size nought is the single most likely value of the determinant, more likely than all the others together.

The same enumeration checks a classical identity that holds at every size: the average of the squared determinant over all tables of signs is exactly $n!$. Expanding the determinant as a signed sum over permutations and squaring, every cross term between two different permutations averages to nought, because some entry appears in one and not the other and its sign is a fair coin; what survives is one term of size one for each of the $n!$ permutations. The table of counts reproduces $2$, $6$, $24$, $120$ and $720$ exactly. So the determinant is large on average and nought most of the time — a distribution with a spike at nought and a long, wide spread of large values, which is what the shaded bars show at small sizes and what the last figure below shows at large ones.

Why four rows is the worst size #

The peak at four rows has a plain explanation, and it is a counting argument rather than anything about determinants. A row of $n$ signs is one of only $2^n$ possible rows, and up to sign one of $2^{n-1}$. With two rows there are two classes of row up to sign, so two random rows land in the same class half the time. With four rows there are eight classes and four rows to place among them, and by the arithmetic of more things than boxes and its probabilistic cousin, the chance that some two land in the same class — or that some two columns do — is already well over a half. The tables are small enough that coincidences between rows are the rule rather than the exception, and every coincidence is a flat table.

As $n$ grows the number of classes, $2^{n-1}$, grows exponentially while the number of rows grows only linearly, so the coincidences thin out. That is why the curve turns over between four and eight rows and then falls. Each further row halves the room available for a coincidence while adding only about $n$ new pairs that might coincide.

The determinant itself is doing something more refined than counting coincidences, though, and the refinement is the subject of the rest of the essay. The only function that behaves like a volume characterised it by three rules, and the one that matters here is that it is nought exactly when the rows are dependent — when one of them lies in the space spanned by the others, which is what a map throws away read in the other direction. A coincidence between two rows is the cheapest dependency, and a table with no coincidences at all can still have a dependency among three, four or more of its rows. Counting only coincidences gives the squares in the first figure. Counting dependencies of every kind gives the dots, and the space between them is the question.

Twenty rows, sampled #

Beyond six rows the tables cannot all be checked, but they can be sampled: forty thousand random tables at each size up to ten, a hundred and twenty thousand beyond, each tested for a nought determinant by elimination. That gives the open dots in the first figure. The chance peaks at four rows, passes one half between eight and nine, a tenth between fourteen and fifteen, and reaches 0.47 per cent at twenty.

The chance of the dull accident can be written down. Two given rows are equal with chance $2^{-n}$ and opposite with chance $2^{-n}$, so a given pair is parallel with chance $2^{1-n}$. There are $\binom{n}{2}$ pairs of rows and as many of columns, and when the chance is small these accidents rarely overlap, so the chance of some parallel pair is about

$$\frac{n(n - 1)}{2^{\,n-1}}.$$

This is the reasoning of twenty-three people, where a coincidence between some pair is likely long before a coincidence with any particular person is: with $n$ rows there are about $n^2$ pairs, each a coin-flip match in $n$ places. The squares in the first figure are the sampled share of tables with a parallel pair, and the dashed curve passes through them.

The sampled chance of singularity does not. At twenty rows it is 6.9 times the parallel-pair rate, and the gap at sixteen rows is about the same. Something other than parallel pairs is making most of these tables flat.

Flat with no two rows alike #

What else can do it is easiest to see in a single table.

The sum of two rows of signs has entries $0$, $2$ or $-2$ — nought where the rows disagree and twice the common sign where they agree. Two other rows that agree and disagree in exactly the same places, with the same signs where they agree, have the same sum, and then $r_1 + r_2 - r_3 - r_4 = 0$. In each column the four signs must satisfy $s_1 + s_2 = s_3 + s_4$, which six of the sixteen possible columns do, so a given quadruple of rows has this property with chance $(3/8)^n$ for one of its three pairings. That is smaller than $2^{1-n}$ for large $n$, but there are about $n^4/24$ quadruples against $n^2/2$ pairs, and at moderate sizes the count wins. Dependencies among six rows, among eight, and with unequal coefficients add further terms of the same shape: individually rarer, collectively numerous.

The census separates the two causes. At two and three rows every flat table has a parallel pair. At six rows 87 per cent do. Then the share falls steadily — a half at nine rows, a quarter at twelve, 14 per cent at twenty — and across every size a computer can comfortably sample, the dull accident explains less and less of the flatness.

A conjecture the measurements do not yet see #

The conjecture about these tables, folklore since Komlós’s work on them, says the opposite: that for large $n$ the chance of singularity is $(1 + o(1))\, n(n-1)\,2^{1-n}$, which is to say that almost every flat table is flat because of a parallel pair. The weaker statement that the chance decays like $(1/2)^n$, up to factors smaller than any exponential, was the subject of a long sequence of papers.

Komlós proved in 1967 that the chance tends to nought at all. Jeff Kahn, Komlós and Endre Szemerédi gave the first exponential bound in 1995, with the modest base $0.999$. Terence Tao and Van Vu brought it to $0.939$ and then to $3/4$; Jean Bourgain, Vu and Philip Matchett Wood to $1/\sqrt 2$; and Konstantin Tikhomirov, in 2020, to $1/2 + o(1)$, which is optimal. The exponential rate is therefore settled. The sharp form — that the chance of singularity is the chance of a parallel pair, up to a factor tending to one — has since been proved by Vishesh Jain, Ashwin Sah and Mehtaab Sawhney for tables whose entries are drawn from many other distributions, and it is expected for the fair signs here.

So the conjecture and the census disagree about every size in the census, and there is no contradiction. The extra dependencies cost a factor like $(3/4)^n$ relative to the parallel pairs — $(3/8)^n$ against $(1/2)^n$ — multiplied by a polynomial in $n$ that is large; the polynomial loses only when $n$ is large enough for the exponential to overwhelm it, and the figures say that is well past twenty. The ratio between the measured chance and the parallel-pair rate, 6.9 at twenty, must eventually come down to one, and nothing on this page shows it starting to. That is the shape of statement the earlier essays on small cases kept running into: an asymptotic law can be exactly right and describe no case anyone has ever looked at.

The same tables over a different arithmetic #

The correspondence between tables of signs and tables of bits gives a surprising comparison. A table of signs with $n$ rows is singular exactly when a certain table of noughts and ones with $n - 1$ rows is singular — singular over the ordinary numbers, where the determinant is a whole number that happens to be nought.

A grid of bits whose rank stops at the state asked the same question of tables of bits in the arithmetic modulo two, where $1 + 1 = 0$. There the chance that a random square table is singular does not tend to nought at all: it tends to $1 - \prod_{k \ge 1}(1 - 2^{-k}) \approx 0.711$. Modulo two, a table of bits is singular more often than not, at every size, for ever.

The tables are the same tables. What differs is what counts as a dependency. Modulo two, any set of rows whose sum has an even number of ones in every column is dependent, and with $n$ rows there are $2^n$ subsets, each with a chance of about $2^{-n}$ — so a dependency is close to certain. Over the ordinary numbers, the same subset sum must be exactly nought, not merely even, and a sum of many rows of noughts and ones is a vector of whole numbers that is very unlikely to vanish. The determinant over the integers is a large number, and its being nought is a genuine coincidence; its being even is not.

How large the determinant usually is #

When the determinant is not nought it is not small, and the contrast with the largest possible value finishes the comparison with Hadamard’s tables.

Hadamard’s ceiling grows like $n^{n/2}$; the root mean square, fixed exactly by the identity above, is $\sqrt{n!}$, which by Stirling’s formula is smaller by a factor of about $e^{n/2}$; and the median among non-singular tables sits just below the root mean square, at $2^{28.5}$ against $2^{30.5}$ for twenty rows. A random table is a box of reasonable size — its rows are long, $\sqrt n$ each, and only moderately far from perpendicular, as a matrix is a picture of what happens to the grid would draw it in two dimensions — and the event of the box being completely flat requires an exact cancellation in a sum of $n!$ signed terms of size one. That the cancellation happens two times in three at four rows is a fact about how few distinct rows there are when $n$ is small, not about cancellation being natural.

What a census of small tables can and cannot say #

Every number on this page up to six rows is an exact count. Every number beyond is an estimate with a sampling error: about two per cent of its value at sixteen rows and about seven at twenty, which is far too small to close a gap of a factor of seven. The trend of the measured ratio is therefore real across the measured range. What the census cannot do is say where the ratio turns, because the asymptotic statements say only that it does so for some large $n$, with no explicit size, and sampling a chance below one in a million needs tens of millions of determinants at each size.

The figures also cannot show the proof, and the proof is where the subject’s difficulty lives. The upper bounds work by showing that a random table is unlikely to have a null direction that is “unstructured” — a combination of rows with many different coefficients — so that only structured, nearly parallel dependencies remain to be counted. That reduction is the Littlewood–Offord problem of how often a sum $\pm a_1 \pm a_2 \pm \cdots \pm a_n$ can hit a given value, and the forty years of progress in the bounds figure are forty years of sharpening it.

The problem is easy to state in the language of coin tosses. Fix numbers $a_1, \ldots, a_n$, none of them nought, and toss a fair coin for each sign. If all the $a_i$ equal one, the sum $\pm 1 \pm 1 \cdots \pm 1$ is the walk of a bell curve assembled out of coin flips, and it hits nought with chance about $1/\sqrt n$ — the largest possible, as Paul Erdős showed in 1945. If the $a_i$ are generic, all different and unrelated, the sum almost never repeats a value and hits nought with chance close to $2^{-n}$. A null direction of a random table supplies the $a_i$, and the next row of signs is the coin. The proofs show that the null direction of a random table is, with overwhelming probability, generic — and that the non-generic ones, which make the coin sum likely to vanish, are so few and so structured that they can be counted. Parallel rows are the extreme non-generic case: a null direction with two non-zero coefficients, $1$ and $-1$, which every later row satisfies with chance one half.

Still open: the second term #

The exponential rate is known; the conjectured leading term is $(1 + o(1))\,n(n-1)\,2^{1-n}$. What is not known with comparable precision, even where that term is proved, is the correction — how the next family of dependencies, of which the four-row sums above are the first members, enters, and how large $n$ must be before the parallel pairs account for, say, nine-tenths of the flat tables. The census says that size is beyond twenty; heuristics based on counting the cheapest dependency types put it far beyond, since the four-row type alone outweighs the pairs until $n^2 (3/4)^n$ falls below a constant. An exact expansion of the chance in decreasing exponential rates, with each rate attached to a type of dependency, is believed to exist and has not been proved.

There is a parallel question about the other end of the spectrum. Hadamard’s tables are the boxes of maximal volume, and nobody knows whether they exist at every multiple of four. Random tables are flat with a known chance, and nobody knows exactly how that chance approaches its limit. Between the two lies the whole distribution of the determinant, whose bulk is understood — its logarithm is close to normally distributed around $\tfrac12 \log (n - 1)!$, by a theorem of Hoi Nguyen and Van Vu — and whose two extremes, nought and the ceiling, are where the open problems sit.