The Hadamard conjecture: existence of a Hadamard matrix of every order divisible by 4

The Hadamard conjecture admits a graph-theoretic reformulation in the language of oriented hypergraphs and signed graphs. The reformulation is an exact equivalence: a Hadamard matrix of order $n$ exists if and only if there are $n$ signed complete graphs, each switching-equivalent to $-K_n$ , whose adjacency matrices sum to zero. Because the equivalence is exact, the open core is the Hadamard conjecture itself: whether an $n\times n$ $\{+1,-1\}$ -matrix with orthogonal rows exists for every $n$ divisible by 4. The Hadamard conjecture remains open; the smallest order for which no Hadamard matrix is known is 668.

Background

A Hadamard matrix of order $n$ is an $n\times n$ matrix $H$ with entries in $\{+1,-1\}$ whose rows are mutually orthogonal, that is, $H H^{\mathrm T} = n I_n$ . Such matrices attain Hadamard's determinant bound $|\det M| \le n^{n/2}$ for matrices whose entries have modulus at most 1, and a standard orthogonality argument shows that a Hadamard matrix of order $n > 2$ can exist only when $n$ is divisible by 4. The Hadamard conjecture, open for over 130 years, asserts the converse: a Hadamard matrix exists for every order $n = 1$ , $2$ , or $4k$ . Known constructions cover wide but structured classes of orders — the doubling (tensor-product) construction yields all powers of 2, and constructions from quadratic residues in finite fields yield an infinite but number-theoretically restricted family of orders — while computational searches have exhibited matrices for all multiples of 4 up to 664, and the systematic SageMath reimplementation and verification of all published constructions by Cati and Pasechnik confirms that, within orders up to 1208, the only ones for which no Hadamard matrix is known are 668, 716, 892, and 1132 (the next unknown order is 1244). No uniform argument covering every multiple of 4 is known.

The source work reformulates the existence problem in the language of signed graphs. A signed graph is a graph in which every edge carries a sign $+1$ or $-1$ ; its adjacency matrix $A(\Sigma)$ has entry $\pm 1$ in position $(u,v)$ when $u$ and $v$ are joined by an edge of that sign, and $0$ otherwise. Switching a signed graph at a vertex negates the signs of all edges incident with it, and two signed graphs are switching-equivalent when one is obtained from the other by such switchings, equivalently when $A(\Sigma') = D A(\Sigma) D$ for a diagonal matrix $D$ with diagonal entries in $\{+1,-1\}$ . Write $-K_n$ for the complete graph on $n$ vertices with every edge negative, so $A(-K_n) = I - J$ , where $J$ is the all-ones matrix. Working through oriented hypergraphs — hypergraphs in which each vertex-edge incidence carries a sign $\pm 1$ , so that the incidence matrix is a $\{0,\pm1\}$ -matrix — Reff and Skogman (2017) proved the exact equivalence: an $n\times n$ matrix $H$ with entries in $\{+1,-1\}$ is a Hadamard matrix if and only if there exist $n$ signed graphs $\Sigma_1,\ldots,\Sigma_n$ on a common set of $n$ vertices, each switching-equivalent to $-K_n$ , whose adjacency matrices sum to zero, $\sum_{i=1}^{n} A(\Sigma_i) = \mathbf{0}$ ; concretely, one may take $A(\Sigma_i) = D_i (I-J) D_i$ where $D_i = \operatorname{diag}(\zeta_i)$ and $\zeta_1,\ldots,\zeta_n$ are the rows of $H$ , for which $\sum_i A(\Sigma_i) = nI - H^{\mathrm T}H$ . They also showed that the classical doubling construction is recovered naturally from this principle, and stated explicitly that whether the reformulation can lead to a proof of the conjecture or to new infinite families of Hadamard matrices remains open. Since the equivalence is exact rather than an implication, the open content of the source question is precisely the Hadamard conjecture itself, now phrased as a purely signed-graph-theoretic existence problem.

Problem Statement

Prove or disprove the Hadamard conjecture: for every positive integer $n$ divisible by 4 there exists an $n\times n$ matrix $H$ with entries in $\{+1,-1\}$ whose rows are mutually orthogonal, i.e. $H H^{\mathrm T} = n I_n$ .

Equivalently, in the exact reformulation established by the source work: for every $n \equiv 0 \pmod 4$ , $n \ge 4$ , there exist $n$ signed complete graphs $\Sigma_1,\ldots,\Sigma_n$ on a common set of $n$ vertices, each switching-equivalent to $-K_n$ (so that $A(\Sigma_i) = D_i (I-J) D_i$ for a diagonal sign matrix $D_i$ , where $I$ is the identity matrix and $J$ the all-ones matrix), whose adjacency matrices sum to zero:

$\sum_{i=1}^{n} A(\Sigma_i) = \mathbf{0}.$

No restriction to particular orders, congruence classes, construction methods, or answer forms is intended: the target is existence for every multiple of 4, and the smallest order currently undecided is $n = 668$ .

References

Nathan Reff and Howard Skogman, "A connection between Hadamard matrices, oriented hypergraphs and signed graphs", Linear Algebra and its Applications 529 (2017) 115–125. DOI: 10.1016/j.laa.2017.04.012, https://doi.org/10.1016/j.laa.2017.04.012 (zbMATH Open record Zbl 1365.05184).
Matteo Cati and Dmitrii V. Pasechnik, "A database of constructions of Hadamard matrices", arXiv:2411.18897 (v1 November 2024, v2 revised 30 August 2025), https://arxiv.org/abs/2411.18897
Cheng Du and Yi Jiang, "Golay Complementary Sequences of Arbitrary Length and Asymptotic Existence of Hadamard Matrices", arXiv:2401.15381 (January 2024), https://arxiv.org/abs/2401.15381
Lucas J. Rusnak, Josephine Reynes, Russell Li, Eric Yan, and Justin Yu, "The determinant of {±1}-matrices and oriented hypergraphs", Linear Algebra and its Applications 702 (2024) 161–178. DOI: 10.1016/j.laa.2024.08.013, https://doi.org/10.1016/j.laa.2024.08.013 (preprint: arXiv:2101.05420, https://arxiv.org/abs/2101.05420)