Hadamard conjecture

A Hadamard matrix of order $n$ is an $n\times n$ matrix $H$ with entries in $\{-1,1\}$ whose rows are pairwise orthogonal. Writing $H^{\mathsf T}$ for the transpose and $I_n$ for the identity matrix, this means

$$H\in\{-1,1\}^{n\times n},\qquad HH^{\mathsf T}=nI_n .$$

If a Hadamard matrix of order $n$ exists, then $n=1$, $n=2$, or $n\equiv 0\pmod 4$. To see this, negate columns so that the first row is all ones. For $n\ge 3$, orthogonality among the first three rows forces the four possible sign patterns in rows two and three to occur equally often, so $4\mid n$.

Conjecture. For every positive integer $k$ there is a Hadamard matrix of order $4k$:

$$\forall k\in\mathbb Z_{>0}\ \ \exists H\in\{-1,1\}^{4k\times 4k}:\quad HH^{\mathsf T}=4k\,I_{4k}.$$

Hadamard matrices are known to exist for many infinite families of orders $4k$, but the statement for all $k$ is open. A proof must give a construction, or a nonconstructive existence argument, valid for every $k$. A disproof must exhibit a single $k$ for which no Hadamard matrix of order $4k$ exists. [1, 2, 3]

Background

Sylvester built $\pm1$ matrices with orthogonal rows of every order $2^s$ in 1867 [1]. Hadamard proved in 1893 that a real $n\times n$ matrix with entries of absolute value at most $1$ satisfies $|\det H|\le n^{n/2}$. Equality holds exactly for the matrices now named after him [2]. Paley constructed further families from quadratic residues in finite fields in 1933 and stated the expectation that every multiple of $4$ occurs [3].

Hadamard matrices are equivalent to several other combinatorial objects. A Hadamard matrix of order $4t$ exists if and only if a symmetric $2$-$(4t-1,2t-1,t-1)$ design exists. Hadamard matrices also give binary error-correcting codes meeting the Plotkin bound, and the Walsh–Hadamard transform used in signal processing and quantum computing. The monograph of Seberry and Yamada surveys the constructions [9].