Hadamard Matrices

A matrix is a table of numbers. A Hadamard matrix is a square table filled with $+1$ and $-1$. Any two of its rows agree in exactly half of their positions. Here is one with 4 rows, written with plain signs:

Compare the first two rows. They agree in positions 1 and 3, and they differ in positions 2 and 4. Every other pair of rows also agrees in exactly two positions. Mathematicians call such rows orthogonal.

The number of rows is the order. Orders 1 and 2 exist, but after that the order must be a multiple of 4. To see why, take any three rows and call them $A$, $B$ and $C$. In each column, $B$ agrees or disagrees with $A$, and so does $C$. That gives four patterns, and the agreement rule makes each pattern appear in the same number of columns. So the number of columns can be divided by 4.

The Hadamard conjecture says that a Hadamard matrix exists for every multiple of 4. Some methods build many sizes. For example, four copies of a Hadamard matrix, placed in a square with the signs flipped in one copy, make one of twice the order. That takes 4 to 8 to 16 and so on. Other methods cover other sizes, but none covers all of them.

Checking a table is easy, because you only compare the rows. Finding one is hard. A table with 668 rows has 446,224 cells, and each cell has two choices. So there are $2^{446224}$ possible tables, a number with 134,327 digits. No computer could try them all.

For about 20 years, 668 was the smallest order with no known example. Alpöge, Voinov and Reynolds-Haertle, working with Claude, announced examples for all twelve open orders below 2000. These are 668, 716, 892, 1132, 1244, 1388, 1436, 1676, 1772, 1916, 1948 and 1964. Other mathematicians verified them by direct calculation.

The smallest order with no known example is now 2396. The conjecture itself stays open, because these are individual tables and not a rule that covers every size.

Separately, OpenAI reports a proof about a special shape. Suppose that each row is the row above, shifted one step to the right, with the last entry moved to the front. Such a table can be a Hadamard matrix only if the order is 1 or 4.