Introduction

Fill a square grid with only two symbols, +1+1 and −1-1. Now ask for something demanding: every pair of rows must agree in exactly half of the positions and disagree in the other half. Multiply two different rows entry by entry, add up, and you get exactly 00 — the rows are orthogonal.

Such a grid is a Hadamard matrix. In matrix language, an n×nn \times n matrix HH with entries ±1\pm 1 is Hadamard when

HHT=nInHH^{T} = nI_{n}

The smallest interesting examples are easy to write down:

H2=(111−1),H4=(H2H2H2−H2)H_{2} = \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}, \qquad H_{4} = \begin{pmatrix} H_{2} & H_{2} \\ H_{2} & -H_{2} \end{pmatrix}

That doubling trick is James Joseph Sylvester's construction from 1867, and it gives Hadamard matrices of every order 2k2^{k}:

sylvester(k):
    H = [[1]]
    repeat k times:
        H = [[H,  H],
             [H, -H]]       # order doubles, rows stay orthogonal
    return H

The name comes from Jacques Hadamard, who in 1893 proved that a matrix with entries of absolute value at most 11 satisfies ∣det⁡H∣≤nn/2|\det H| \le n^{n/2}, with equality exactly for these ±1\pm 1 matrices with orthogonal rows — and who exhibited examples of orders 12 and 20, which are not powers of 2.

Why the order must be 1, 2 or a multiple of 4. Multiplying a column by −1-1 keeps all rows orthogonal, so we may assume the first row is all +1+1. Take n≥3n \ge 3 and look at rows 2 and 3. Each column shows one of four sign patterns in those rows, (+,+)(+,+), (+,−)(+,-), (−,+)(-,+), (−,−)(-,-), occurring a,b,c,da, b, c, d times. Orthogonality of rows 1–2, 1–3 and 2–3 gives

a+b−c−d=0,a−b+c−d=0,a−b−c+d=0a+b-c-d = 0, \quad a-b+c-d = 0, \quad a-b-c+d = 0

and of course a+b+c+d=na+b+c+d = n. Adding all four equations yields 4a=n4a = n. So nn must be divisible by 4.

The Hadamard conjecture is the converse: for every multiple of 4 there is a Hadamard matrix of that order. Hadamard raised the question in 1893; Raymond Paley stated it explicitly in 1933, when he found a powerful new way to build them. Over ninety years later, nobody has proved it.

What Is Actually Known

The conjecture is a statement about infinitely many orders, and progress has come one family of constructions — and sometimes one stubborn order — at a time.

  • Sylvester (1867) gives every order 2k2^{k}. More generally, the Kronecker product of Hadamard matrices of orders aa and bb is Hadamard of order abab, so the set of achievable orders is closed under multiplication.
  • Paley (1933) used quadratic residues. If qq is a prime power with q≡3(mod4)q \equiv 3 \pmod 4, the Jacobsthal matrix Qij=χ(j−i)Q_{ij} = \chi(j-i) (where χ\chi is the quadratic character) yields a Hadamard matrix of order q+1q+1; if q≡1(mod4)q \equiv 1 \pmod 4, a block version yields order 2(q+1)2(q+1). Sylvester, Paley and products together reach every multiple of 4 up to 88; the first gap is 92.
  • Williamson (1944) reduced the problem to finding four small symmetric circulant ±1\pm 1 matrices A,B,C,DA, B, C, D with A2+B2+C2+D2=4mIA^{2}+B^{2}+C^{2}+D^{2} = 4mI. Using this idea, Baumert, Golomb and Hall found order 92 in 1962 with a computer search at JPL. Later machinery — Goethals–Seidel arrays, Turyn sequences, cyclotomy, difference sets — filled thousands more orders.
  • The smallest open case kept moving: 268 fell in 1985 (Sawade), and 428 in 2005, when Kharaghani and Tayfeh-Rezaie published a construction. From then on, 668 was the smallest multiple of 4 with no known Hadamard matrix, and twelve orders below 2000 stayed open: 668, 716, 892, 1132, 1244, 1388, 1436, 1676, 1772, 1916, 1948, 1964.
  • August 2026. Levent Alpöge, Philippe Voinov and Saul Reynolds-Haertle announced explicit Hadamard matrices for all twelve of those orders, found with the help of an AI model (Anthropic's Claude). Because verifying a candidate only requires computing HHTHH^{T} — about n3n^{3} operations, a fraction of a second for n=668n = 668 — the claim can be checked mechanically by anyone, unlike a long proof. Every multiple of 4 up to 2000 now has a known Hadamard matrix; the open orders lie above 2000.
  • Asymptotic results. Jennifer Seberry (1976) proved that for every odd qq there is a Hadamard matrix of order 2tq2^{t}q once tt is large enough (roughly t≥2log⁡2qt \ge 2\log_{2} q); later work by Craigen and others lowered the needed power of 2. So every odd number becomes a Hadamard order after multiplying by some power of 2 — but the conjecture asks for the power 44 alone.

Why it is hard. There are 2n22^{n^{2}} sign patterns of order nn; for n=668n = 668 that is about 10134 00010^{134\,000}, so blind search is hopeless. Every known approach imposes structure (circulant blocks, group symmetry, number-theoretic patterns) that shrinks the search space, but no single structure is known to work for all orders. The problem shares the shape of an NP search — a short certificate, easy to verify, hard to find — although each fixed order is a finite question, so this is not literally a P vs NP instance. Like the Goldbach conjecture, it has been confirmed far beyond any small case, yet a construction covering every multiple of 4 remains out of reach.

A related problem is wide open too: for nn not divisible by 4, what is the largest determinant of an n×nn \times n ±1\pm 1 matrix? Hadamard's bound nn/2n^{n/2} cannot be attained there, and the true maximum is known only for scattered orders.

Where It Matters

Perfectly balanced, perfectly orthogonal ±1\pm 1 patterns are exactly what engineers want whenever signals must be separated cleanly:

  • Walsh–Hadamard transform. Sylvester's matrices define a transform that, like the FFT, runs in O(nlog⁡n)O(n \log n) using only additions and subtractions. It is used in signal and image processing, compression, and in algorithms such as randomized dimensionality reduction.
  • Error-correcting codes. The rows of HH and −H-H form a code where any two codewords differ in at least n/2n/2 positions. In 1971 Mariner 9 sent its pictures of Mars using the (32,6)(32, 6) first-order Reed–Muller code — a Hadamard code — that corrects up to 7 bit errors in every 32-bit word. Compare it with the leaner Hamming codes, which correct a single error.
  • CDMA. In cellular systems like IS-95, each user's data is spread with a different row of a 64×6464 \times 64 Sylvester matrix (Walsh codes); orthogonality lets the receiver separate users sharing the same frequency.
  • Quantum computing. The one-qubit Hadamard gate 12(111−1)\tfrac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} is H2H_{2} normalized. It creates superpositions, and applying it to every qubit is the 2n2^{n}-dimensional Walsh–Hadamard transform — the first step of many algorithms, and the binary cousin of the quantum Fourier transform.
  • Experimental design. Plackett and Burman (1946) used Hadamard matrices to screen up to n−1n-1 factors in only nn experimental runs, with every factor estimated independently. That is why the existence of orders like 92 or 668 matters to statisticians, not just to combinatorialists.

Conclusion

The Hadamard conjecture is a rare open problem you can draw. A Hadamard matrix is a mosaic of black and white squares in which every pair of rows is in perfect balance. A three-line argument shows the order must be a multiple of 4; Sylvester, Paley, Williamson and generations of computer searches have built them for every multiple of 4 up to 2000, the last dozen announced only in 2026.

Yet no one knows a recipe that works for every multiple of 4. Each new order is still a separate victory, and an infinite list of victories is not a proof. The gap between "we can verify any example in a second" and "we can guarantee an example always exists" is the same gap that keeps P vs NP and the Goldbach conjecture open — easy to check, hard to find, and harder still to guarantee.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/hadamard-conjecture/Content licensed under CC BY-NC 4.0.