Hadamard Matrix - The Hadamard Conjecture

The Hadamard Conjecture

The most important open question in the theory of Hadamard matrices is that of existence. The Hadamard conjecture proposes that a Hadamard matrix of order 4k exists for every positive integer k.

A generalization of Sylvester's construction proves that if and are Hadamard matrices of orders n and m respectively, then is an Hadamard matrix of order nm. This result is used to produce Hadamard matrices of higher order once those of smaller orders are known.

Sylvester's 1867 construction yields Hadamard matrices of order 1, 2, 4, 8, 16, 32, etc. Hadamard matrices of orders 12 and 20 were subsequently constructed by Hadamard (in 1893). In 1933 Raymond Paley discovered a construction that produces a Hadamard matrix of order q+1 when q is any prime power that is congruent to 3 modulo 4 and that produces a Hadamard matrix of order 2(q+1) when q is a prime power that is congruent to 1 modulo 4. His method uses finite fields. The Hadamard conjecture should probably be attributed to Paley.

The smallest order that cannot be constructed by a combination of Sylvester's and Paley's methods is 92. A Hadamard matrix of this order was found using a computer by Baumert, Golomb, and Hall in 1962. They used a construction, due to Williamson, that has yielded many additional orders. Many other methods for constructing Hadamard matrices are now known.

In 2005, Hadi Kharaghani and Behruz Tayfeh-Rezaie published their construction of a Hadamard matrix of order 428. As a result, the smallest order for which no Hadamard matrix is presently known is 668.

As of 2008, there are 13 multiples of 4 less than or equal to 2000 for which no Hadamard matrix of that order is known. They are: 668, 716, 892, 1004, 1132, 1244, 1388, 1436, 1676, 1772, 1916, 1948, 1964.