Hadamard matrices of the unresolved orders below 1000: the smallest open cases of the Hadamard and skew Hadamard conjectures

The Hadamard conjecture asserts that a $(-1,+1)$ matrix with mutually orthogonal rows (a Hadamard matrix) exists for every order $n$ divisible by 4; the analogous skew Hadamard conjecture asserts the same for matrices of the form $H=S+I$ with $S$ skew-symmetric. Both remain open. A 2023 SageMath implementation paper surveyed the state of the art and recorded that, below order 1000, Hadamard matrices are known for every admissible order except 668, 716, and 892, while skew Hadamard matrices are unknown for 25 orders (356, 404, 428, 476, 596, 612, 668, 708, 712, 716, 764, 772, 804, 808, 820, 836, 856, 892, 900, 916, 932, 940, 952, 980, 996), a list that includes the three non-skew unknowns. Every one of these orders remains unresolved as of 2025–2026: a July 2026 arXiv paper states order 668 remains the smallest order not settled by the conjecture, and an August 2025 database paper by the same authors still lists 668, 716, 892 (and 1132) as unknown. The problem is to settle existence for these remaining orders — by explicit construction or proof of nonexistence — thereby completing the existence classification of (skew) Hadamard matrices for all orders up to 1000, the smallest open instances of the two conjectures.

Background

A Hadamard matrix of order $n$ is an $n\times n$ matrix $H$ with all entries in $\{-1,+1\}$ whose rows are mutually orthogonal, equivalently satisfying $HH^{\top}=nI$. By Hadamard's determinant bound ($|\det H|\le n^{n/2}$ for any matrix whose entries have modulus at most 1), such matrices maximize the determinant over all bounded-entry matrices, which is how they first arose: Sylvester constructed examples of every power-of-two order in 1867, and Hadamard proved the bound in 1893, showing that for $n>2$ a Hadamard matrix can exist only when $n$ is a multiple of 4. Hadamard matrices underpin error-correcting codes, signal-processing transforms (the Walsh–Hadamard transform), and the design of statistical experiments, so knowing which orders exist is of both theoretical and practical interest. The Hadamard conjecture asserts the converse of the necessary divisibility condition: a Hadamard matrix exists for every order $n=1$, $2$, or $4k$. It has been open since 1893.

A skew Hadamard matrix is a Hadamard matrix of the form $H=S+I$, where $I$ is the identity and the matrix $S$ is skew-symmetric ($S^{\top}=-S$), equivalently $H+H^{\top}=2I$. The skew Hadamard conjecture asserts that one exists for every order divisible by 4; it is strictly stronger in the sense that a skew matrix is automatically a Hadamard matrix, and it too remains open.

Known orders come from isolated constructions rather than a uniform method. Paley's 1933 constructions use quadratic residues in a finite field $GF(q)$: for a prime power $q\equiv 3\pmod 4$ they give a skew Hadamard matrix of order $q+1$, and for $q\equiv 1\pmod 4$ a Hadamard matrix of order $2(q+1)$. Doubling — taking the Kronecker product with Sylvester's $2\times 2$ Hadamard matrix, i.e. replacing each $+1$ entry of a known matrix by the small matrix and each $-1$ entry by its negation — turns any known order $n$ into a known order $2n$. Further families produce additional orders from combinatorial designs: Williamson's construction (four commuting symmetric circulant $\pm 1$ matrices of order $n$ — circulant meaning each row is the previous row shifted by one position — whose squares sum to $4nI$, arranged in a fixed block array), the Goethals–Seidel array (a block array combining four $\pm 1$ matrices of order $n$ whose squared sum is $4nI$), supplementary difference sets (collections of subsets of a group whose translated differences cover each non-identity element a constant number of times), and T-sequences (four $\{-1,0,1\}$ sequences of length $n$ with exactly one nonzero entry per position whose periodic autocorrelations sum to zero at every nonzero shift, from which Hadamard matrices of order $4n$ arise). None of these methods covers all multiples of 4. The orders that resist every known method are those of the form $4m$ or $8m$ with $m$ odd that no base construction reaches: doubling only produces even multiples of a smaller known order, and the Paley congruences do not apply. For the non-skew conjecture, the unresolved orders below 1000 are all of the shape $4p$ with $p$ prime and $p\equiv 3\pmod 4$: $668=4\cdot 167$, $716=4\cdot 179$, $892=4\cdot 223$; the unresolved skew orders below 1000 are likewise all of the form $4m$ or $8m$ with $m$ odd, whether $m$ is prime (e.g. $356=4\cdot 89$, $404=4\cdot 101$, $808=8\cdot 101$) or composite (e.g. $476=4\cdot 119$, $900=4\cdot 225$). A Legendre pair — two $\pm 1$ sequences of odd length $\ell$ whose periodic autocorrelations sum to $-2$ at every nonzero shift — yields a Hadamard matrix of order $2\ell+2$ (at $\ell=333$, order $668$).

Cati and Pasechnik implemented in SageMath (an open-source computer algebra system) all known constructions of Hadamard and skew Hadamard matrices up to order 1000 and recorded the orders that remain without any known construction; a 2024–2025 follow-up database paper by the same authors extended the covered range to 1208 and published updated existence tables for odd $n\le 2999$ (non-skew) and $n\le 999$ (skew).

Problem Statement

The general problem is the Hadamard conjecture in its standard form: prove or disprove that a Hadamard matrix of order $n$ exists for every $n\in\{1,2\}\cup\{4k:\ k\ge 1\}$, and the parallel skew Hadamard conjecture that a skew Hadamard matrix exists for every order divisible by 4. The concrete, source-derived completion target of this problem is to settle the existence question for every order up to 1000 that the source tables list as unresolved, in both variants, so that the existence classification of Hadamard and skew Hadamard matrices is complete for all orders $4n\le 1000$. Specifically: (i) determine, by explicit construction or proof of nonexistence, whether a Hadamard matrix exists for each of the orders 668, 716, and 892; and (ii) determine, by explicit construction or proof of nonexistence, whether a skew Hadamard matrix exists for each of the orders 356, 404, 428, 476, 596, 612, 668, 708, 712, 716, 764, 772, 804, 808, 820, 836, 856, 892, 900, 916, 932, 940, 952, 980, and 996. These two lists share one scientific objective — completing the smallest open instances of the two conjectures — and the overlapping orders (668, 716, 892 appear in both) couple the two variants: at a shared order, a skew Hadamard construction settles the non-skew existence question there as well, since a skew matrix is automatically a Hadamard matrix, whereas a non-skew construction does not settle the skew question, the skew condition $H+H^{\top}=2I$ being strictly additional. A full resolution of either conjecture would settle the corresponding list; conversely, completing the lists order-by-order is the derived finite core of the conjectures as posed by the source paper's future-work agenda. A nonexistence result for any single listed order would refute the corresponding conjecture and is a valid admissible answer for that order.

References

1. R. E. A. C. Paley, On Orthogonal Matrices, Journal of Mathematics and Physics 12 (1933) 311–320. DOI: 10.1002/sapm1933121311, https://doi.org/10.1002/sapm1933121311
2. Matteo Cati, Dmitrii V. Pasechnik, Implementing Hadamard Matrices in SageMath, arXiv:2306.16812 (2023). DOI: 10.48550/arXiv.2306.16812, https://arxiv.org/abs/2306.16812
3. Matteo Cati, Dmitrii V. Pasechnik, A database of constructions of Hadamard matrices, arXiv:2411.18897 (v1 2024, v2 30 Aug 2025). DOI: 10.48550/arXiv.2411.18897, https://arxiv.org/abs/2411.18897
4. Arthur F. Ramos, David B. Hulak, Ruy J. G. B. de Queiroz, Multiplier obstructions for Legendre pairs of length 333, arXiv:2607.20765 (2026). DOI: 10.48550/arXiv.2607.20765, https://arxiv.org/abs/2607.20765
5. Kean Fallon, Equiangular tight frames in real symplectic space: Zauner's conjecture and the skew Hadamard conjecture, arXiv:2509.14463 (2025). DOI: 10.48550/arXiv.2509.14463, https://arxiv.org/abs/2509.14463
6. Amira Karoui, An Explicit Skew-Hadamard Matrix of Order 1252 via Cyclotomic Unions, arXiv:2602.16089 (2026). DOI: 10.48550/arXiv.2602.16089, https://arxiv.org/abs/2602.16089
7. Vitor Araujo Garcia, On the non-existence of skew-Hadamard difference sets in certain non-abelian groups, arXiv:2606.13536 (2026). DOI: 10.48550/arXiv.2606.13536, https://arxiv.org/abs/2606.13536
8. Andriyan Bayu Suksmono, A Quantum Approximate Optimization Method For Finding Hadamard Matrices, arXiv:2408.07964 (2024). DOI: 10.48550/arXiv.2408.07964, https://arxiv.org/abs/2408.07964