The biggest box built from signs

Take a square table and fill every cell with $+1$ or $-1$. There are finitely many such tables of each size, so one of them has the largest determinant, and the question is what that largest value is.

It sounds like a puzzle about signs. It is really a question about boxes. The determinant is the factor by which a map scales area, which is to say the volume of the box the columns span, and a column of $n$ signs has length $\sqrt n$ whatever the signs are — every entry squares to one. So every table of signs spans a box whose edges all have the same length, and the question becomes: how large can a box be when the lengths of its edges are fixed and only their directions can be chosen?

The figure below is the answer in two dimensions. Two edges of fixed length, turned to three different angles, and the area is largest when the angle is square. That much is true in every dimension, and it gives a ceiling. The whole interest is in whether signs can reach it.

A box is largest when its corners are square #

The area of a parallelogram is its base times its height, and the height is the part of the second edge that sticks out perpendicular to the first. The height can never be longer than the edge it is measured from. It equals that edge only when the edge is already perpendicular, and it is shorter by a factor of the sine of the angle otherwise. So the area is at most the product of the two lengths, and equals it exactly at a right angle.

In more dimensions the same argument runs one edge at a time. Removing shadows one direction at a time rebuilds the box as a stack of heights: the first edge, the part of the second perpendicular to the first, the part of the third perpendicular to both, and so on. The volume is the product of those heights, each height is at most the length of its edge, and so

$$|\det A| \;\le\; \|a_1\|\,\|a_2\| \cdots \|a_n\|.$$

That is Hadamard’s inequality, published in 1893. Equality holds exactly when every height is the whole edge — which is to say exactly when the columns are pairwise perpendicular.

For a table of signs every column has length $\sqrt n$, and the inequality becomes a single number:

$$|\det A| \;\le\; n^{n/2}.$$

At size two the ceiling is $2$, and $\begin{pmatrix}1&1\\1&-1\end{pmatrix}$ reaches it, since its two columns are perpendicular. At size three the ceiling is $3^{3/2} \approx 5.196$, and it cannot be reached — a determinant of whole numbers is a whole number, so the most it could be is five. Whether five is possible is the first real question, and it has a clean answer.

Nine signs, and the number four #

There are $2^9 = 512$ tables of signs of size three, few enough to compute every determinant.

Three values occur: $0$, $4$ and $-4$. Not one table has determinant one, two, three or five. The census shows it; an argument explains it, and the argument is two lines long.

Multiplying a column by $-1$ only changes the sign of the determinant, so any table can be turned into one whose first row is all plus signs without changing the size of its determinant. Now subtract the first row from every other row. That leaves the determinant exactly as it was — the operation the determinant is built to ignore — and every entry below the first row becomes $(\pm 1) - 1$, which is $0$ or $-2$. Each of those $n - 1$ rows is twice a row of whole numbers, so the determinant is $2^{n-1}$ times a whole number.

At size three that says every determinant is a multiple of four. The ceiling is $5.196$. The largest multiple of four beneath it is four, and ninety-six tables reach it, with ninety-six more at minus four. The two facts together — a volume ceiling from the geometry and a divisibility floor from the arithmetic — pin the answer exactly, with no search needed at all.

So the answer at size three is four, and the box cannot be made square. Three columns of three signs cannot be pairwise perpendicular: the dot product of two such columns is a sum of three terms each $\pm 1$, which is odd and so never nought.

Sixteen signs, and the ceiling met #

At size four there are $2^{16} = 65{,}536$ tables, which is still few enough to compute all of them.

Five values appear: $0$, $\pm 8$, $\pm 16$. The ceiling is $n^{n/2}$ with $n = 4$, which is $4^2 = 16$, the divisibility says multiples of eight, and this time the ceiling itself is a multiple of eight — and 768 tables sit on it. Their columns are pairwise perpendicular. The box is a cube.

It is worth setting that beside the same sum with its minus signs deleted. The permanent of a table of signs is largest, trivially, when every entry is $+1$: all $n!$ products are one, and nothing cancels. The determinant of that table is nought, because its columns coincide and the box is flat. The determinant’s maximum is the hard one precisely because the signs cancel — a table has to be arranged so that the cancellation works against as little of the sum as possible, and at size four the arrangement that does it is one where the columns point in four mutually square directions.

A table of signs whose rows are pairwise perpendicular is called a Hadamard matrix, and the size-four ones are the first non-trivial examples. Perpendicularity for rows of signs has a concrete meaning. The dot product of two rows counts $+1$ where they agree and $-1$ where they differ, so it is nought exactly when the two rows agree in half their places and disagree in the other half. A Hadamard matrix is a set of $n$ sign patterns every two of which agree exactly half the time.

That already rules out every odd size above one, since half of an odd number is not a whole number. It rules out more than that, and the reason is the next section.

Why only multiples of four #

Suppose a Hadamard matrix of size $n$ exists, with $n$ at least three. Multiplying columns by $-1$ keeps the rows perpendicular, so the first row may be taken to be all plus signs. Now look at the second and third rows together. Each column shows one of four patterns in those two rows — $(+,+)$, $(+,-)$, $(-,+)$ or $(-,-)$ — and say there are $a$, $b$, $c$ and $d$ columns of each kind.

Four facts about those four counts follow from the rows being perpendicular and from there being $n$ columns:

• the second row is perpendicular to the first: $a + b - c - d = 0$;
• the third row is perpendicular to the first: $a - b + c - d = 0$;
• the second and third are perpendicular to each other: $a - b - c + d = 0$;
• and $a + b + c + d = n$.

Adding the four equations gives $4a = n$, and the others follow the same way: $a = b = c = d = n/4$. Every Hadamard matrix of size three or more has size divisible by four.

That is a genuine obstruction and a strange one. Nothing about boxes cares about the number four. The ceiling $n^{n/2}$ is a perfectly good number at size six and at size ten; what fails is the possibility of choosing directions among the corners of a cube so that they are all square to each other. The arithmetic of agreeing half the time, three rows at once, forbids it.

Whether the converse holds — whether every multiple of four has a Hadamard matrix — is the Hadamard conjecture, and it is open.

Doubling, and the squares modulo eleven #

Two constructions account for most of the known examples, and they are worth seeing because they could hardly be more different in spirit.

The first is Sylvester’s, from 1867, a quarter of a century before Hadamard. Given a Hadamard matrix $H$, the matrix

$$\begin{pmatrix} H & H \\ H & -H \end{pmatrix}$$

is one of twice the size. Two rows from the top half agree wherever the two copies of their rows agree, so they stay perpendicular; a top row and a bottom row agree on the left half and disagree on the right, so they are perpendicular by construction. Starting from the single entry $(1)$ and doubling three times gives size eight.

Doubling reaches every power of two and nothing else. For size twelve something else is needed, and the second construction, Raymond Paley’s of 1933, comes from number theory. Take a prime $q$ that leaves remainder three when divided by four — $q = 11$ will do. Label the rows and columns by the remainders $0, 1, \ldots, 10$, and put a plus sign in row $i$ and column $j$ when $j - i$ is a square modulo eleven, a minus sign when it is not. Border the result with one extra row and column and adjust the diagonal, and the rows come out perpendicular.

Why the squares should do this is a fact about how evenly they are spread: modulo a prime of this kind, every non-zero remainder arises as a difference of two non-zero squares the same number of times, which is exactly the “agree half the time” condition in disguise. It is the same evenness that makes the pattern of quadratic residues look random while obeying exact laws.

Between them, doubling and Paley’s residues — and products and variants of both — produce Hadamard matrices at every multiple of four up to several hundred. The first gap is not until 668.

Where the two ceilings stop being enough #

For sizes that are not multiples of four the box cannot be square, and the question becomes how close to square it can get. Here the two ceilings of the size-three argument — the volume bound and the divisibility — are the only tools on the table, and it is worth seeing how far they go.

At size five the ceiling is about $55.9$ and the determinant is a multiple of sixteen, so it is at most $48$ — and the search over all 65,536 normalised tables finds $48$ exactly. The two crude arguments are still enough.

At size six they are not. The ceiling is $216$, the multiples of thirty-two beneath it stop at $192$, and the truth is $160$. At size seven the arguments allow $896$ and the truth is $576$. Nothing in either argument knows about the gap, because both treat the columns one at a time or the entries one at a time, and the obstruction is about all the columns together.

Sharper ceilings exist. For sizes two more than a multiple of four, Ehlich and Wojtas showed in the 1960s that the best a matrix can do is governed by splitting it into two blocks of nearly perpendicular rows, and the ceiling they found is reached at size six. For sizes one or three more than a multiple of four there are further bounds of the same flavour. But the largest determinant is known exactly only at scattered sizes beyond the small ones, and for most sizes the best tables known are not proved best.

A table of bits one size smaller #

The row subtraction that proved divisibility does more than prove divisibility. Normalise a table of signs so its first row and first column are all plus, subtract the first row from the others, and what remains in the lower-right corner is $-2$ wherever the original had a minus sign and $0$ wherever it had a plus. Divide every entry of that corner by $-2$ and it is a table of zeros and ones.

Every table of zeros and ones of size $n - 1$ arises this way from exactly one normalised table of signs of size $n$, and the determinants differ by the fixed factor $(-2)^{n-1}$. So the largest determinant of a zero–one table of size $n-1$ is the largest determinant of a sign table of size $n$, divided by $2^{n-1}$. The two problems are one problem.

That is not obvious from either side. A zero–one table looks like the more natural object — incidence tables, the adjacency of a graph, membership in sets — and nobody would guess that its extremal question lives one size up, among tables of signs with perpendicular rows. It also means that at size three the largest zero–one determinant is two, at size four it is three, and at size five it is five — the sign-table maxima sixteen, forty-eight and one hundred and sixty divided by eight, sixteen and thirty-two.

Weighing on a balance, and a code sent from Mars #

The question was asked in earnest for a reason that has nothing to do with boxes.

Suppose several small objects are to be weighed on a two-pan balance whose readings carry a random error. Weighing each object alone gives each weight with the full error of one reading. Harold Hotelling observed in 1944 that it is better to put every object on the balance in every weighing, some on the left pan and some on the right, and solve for the individual weights afterwards. A weighing plan is a table of signs — row for the weighing, column for the object, $+1$ for the left pan and $-1$ for the right — and the error in the recovered weights is smallest when the table’s rows are perpendicular. With a Hadamard plan, $n$ weighings give each of $n$ weights with an error variance $n$ times smaller than weighing it alone, for the same number of uses of the balance.

A small case shows the size of the gain. Four packets of unknown weights $w_1, \ldots, w_4$ and four weighings, each with a random error of the same spread. Weighed one at a time, each estimate carries the whole error of its one reading. Weighed by the size-four Hadamard plan — all four on the left pan; the first two left and the last two right; the first and third left; the first and fourth left — each reading is a signed sum of all four weights, and each weight is recovered as a signed average of all four readings, $w_j = \tfrac14 \sum_i h_{ij} y_i$. The four errors enter every estimate with weight a quarter each, so their variance is a quarter of one reading’s: half the spread, from the same four uses of the balance. Nothing was weighed more carefully. The plan simply stopped each weighing from repeating what another had already measured, which is what perpendicular rows mean.

The same tables are among the best codes there are. The rows of a Hadamard matrix of size $n$, together with their negatives, are $2n$ words of length $n$ any two of which differ in at least $n/2$ places — a code that meets the averaging bound Plotkin proved, and so one of the lengths where the best a code can be is known exactly. A code of exactly this kind, with thirty-two-letter words, carried the pictures Mariner 9 sent back from its orbit of Mars in 1971 and 1972.

They turn up once more, in a place further from boxes still. A table whose rows are perpendicular cannot be very lopsided in any large block of it: Lindsey’s lemma says the entries of any sub-rectangle of a Hadamard matrix nearly balance, and that is what lets two independent imperfect sources of randomness be combined into one fair bit.

The balance, the error-correcting code and the box are one condition read three ways. Perpendicular rows mean the volume is as large as edges of that length allow; they mean the weighings share no information and waste none; and they mean every two code words disagree as much as two words can while there are so many of them.

What a census of tables cannot reach #

Every figure here that finds a maximum finds it by computing every candidate, and that stops quickly. Normalised tables of size five number $2^{16}$; of size six, $2^{25}$, about thirty-three million; of size seven, $2^{36}$, which no picture could summarise. The maxima at six and seven in the table are quoted from the literature, and the table says so rather than hiding it.

Nor can a picture show the obstruction at sizes that are not multiples of four in the one place it is interesting. The three-row argument proves that sizes like six and ten cannot reach the ceiling; it does not say how far below they must fall, and no finite census of small sizes reveals the pattern of the gap. At size six the gap is from $216$ to $160$ — about a quarter — and at larger sizes the known best tables fall short by amounts that are bounded by theory but not settled by it.

And the grids of Sylvester and Paley show two tables that exist. The conjecture is about tables nobody has found, and there is no drawing of an absence. What the figures can do, and do, is check every claimed perpendicularity pair by pair, so that the examples are evidence rather than illustrations.

Still open: a table of signs of size 668 #

The Hadamard conjecture says that for every multiple of four there is a table of signs with pairwise perpendicular rows. Such a table is known at every multiple of four below 668; the last of those gaps to close was 428, filled by Hadi Kharaghani and Behruz Tayfeh-Rezaie in 2005 with a construction assembled from smaller pieces. No Hadamard matrix of size 668 is known, and no argument rules one out.

The difficulty is that the constructions are not a theory. Sylvester doubles, Paley uses the squares of a prime field, and the dozens of other methods combine smaller matrices in ways that work for particular arithmetic reasons at particular sizes. None of them is known to cover every multiple of four, and the only general obstruction — the three-row argument — says nothing against any of them.

Which is an unusual place for a question about determinants to end. The ceiling on the volume is a two-line argument. The condition for reaching it is a line of algebra. And whether the condition can be met at a size as modest as 668 is not known.