Jump to main content
Circulant Hadamard

The circulant Hadamard conjecture

Steven Creech and Tomas Ortega

Full overview · The circulant Hadamard conjecture
Show the proof map

Definitions and main theorem

A Hadamard matrix of order is an matrix all of whose entries are and whose distinct rows are orthogonal. Since every row has squared length , this condition is equivalent to

where denotes the identity matrix.

A matrix is circulant if each row is obtained from the preceding row by shifting its entries one position cyclically to the right. Thus it is completely determined by its first row. A circulant Hadamard matrix is a Hadamard matrix with this cyclic structure.

Example. The following is a circulant Hadamard matrix of order :

Its rows are successive cyclic shifts of . Any two distinct rows agree in two positions and disagree in two, so their inner product is zero. Each row has squared length , and hence . This gives a circulant Hadamard matrix of order ; the matrix supplies the order- example. The following theorem states that there are no other orders.

Theorem 1 (Circulant Hadamard). Let be a positive integer. A real circulant Hadamard matrix of order exists if and only if .

We give a high-level overview of the proof presented in The circulant Hadamard conjecture. At this level, the order restriction and the Δ-theorem are used as inputs to the main argument.

The main overviews use the case as a guiding example to explain the idea of each lemma. As we open a node and explore its smaller steps, we develop the general statements and proofs. The example shows the shape of the argument; those general steps establish the result for every order.

The final three steps move from picture to calculation: Node 6 shows the common rotation and equality of the normalized evaluations, Node 7 gives the algebraic contradiction for , and Node 8 completes the argument for general odd and states the conclusion.

The dependency graph above organizes the proof into eight main steps and shows how they fit together. Click any node to explore its statement and the idea behind it, then go deeper into the mathematical details. This lets you follow the overall argument first and explore individual steps in more detail as you go.


1. Group-Ring Encoding

Dig in deeper

5 child nodes

Let be an circulant matrix with entries , and encode its first row by

Define , which reverses cyclic positions.

Lemma (Circulant Hadamard Dictionary). The matrix is Hadamard if and only if

Equivalently, if and only if .

Conversely, any polynomial with all coefficients satisfying this identity determines a circulant Hadamard matrix by taking its coefficient list and successive cyclic right shifts as the rows.

The right-hand side is the constant polynomial . This identity translates row orthogonality into a single equation in the group ring.

Cut from the overview · 1:34–1:45


2. Restriction on the Order

Dig in deeper

6 child nodes

Lemma (Order restriction, Proposition 2.2). If a real circulant Hadamard matrix has order , then for an odd positive integer .

The first two restrictions follow directly from what we already know. Evaluating the group-ring identity at gives

since . The row sum is an integer, so is a square.

Orthogonality tells us that is even. The dot product of two distinct rows is a sum of terms, each or , that equals zero. There must be equally many positive and negative terms, hence an even number of terms. Thus, is an even square, so divides it. Writing its even square root as , we obtain .

Lastly, is odd. The smaller nodes develop the proof of this part of the order restriction.

Since gives the known order-four case, it remains to rule out . We therefore proceed by contradiction: assume that a circulant Hadamard matrix exists with for an odd integer , and seek a contradiction.

Cut from the overview · 1:45–1:56


3. The Three Evaluations

Dig in deeper

5 child nodes

We first use the Chinese remainder theorem to separate the two factors of the order . Since is odd, and are coprime, so

This means that a position in the original cycle can be described by two coordinates: and . Every pair identifies exactly one original position. We are reorganizing the same coefficients, each still or .

In the group ring, introduce for the four-position coordinate and for the -position coordinate. Replacing by sends to , with the two exponents reduced separately. Thus our one-variable polynomial becomes a two-variable polynomial in

The relation makes fourth roots of unity the natural choices to substitute for . Evaluating at leaves three polynomials in ; the lemma normalizes them by dividing by .

Lemma (The three normalized evaluations). Suppose has coefficients and satisfies . Group its terms by their power of :

Each collects the coefficients with -exponent . Define by

Then have integer coefficients, has Gaussian-integer coefficients, and

Here the identities are in , and conjugates coefficients and inverts .

For our guiding case , this splits the hypothetical order- polynomial into coordinates with and . Grouping by the four powers of gives four polynomials with nine sign coefficients each. At these four parts add; at they alternate in sign; at they combine into real and imaginary differences.

Each evaluated polynomial still has product with its star equal to . Dividing the polynomial by also divides its star by , so the product is divided by : becomes . The coefficients remain integral because sums of four signs and differences of two signs are even. Thus have integer coefficients and has Gaussian-integer coefficients, with

The takeaway is geometric. Choose any ninth root of unity , so , and substitute . Star becomes complex conjugation, giving . Therefore

Whichever value of we choose subject to , all three output values lie on the circle of radius centered at the origin. Their distance from the origin is fixed; the next question is how their phases compare, especially at and .

Cut from the overview · 1:56–2:11


4. The Δ-Theorem

Dig in deeper

6 child nodes

Let be odd, and let be the set of distinct primes dividing . Choose a primitive th root of unity for each . For every subset , put

For a polynomial whose evaluations at these roots are nonzero, define

In other words, subsets containing an even number of primes contribute factors to the numerator, and subsets containing an odd number of primes contribute factors to the denominator. The empty subset counts as even, so it contributes to the numerator.

Guiding example: . There is only one prime in , so the subsets are and . Writing , the entire product becomes the simple quotient

The Δ-theorem tells us what this comparison can be when satisfies the norm identity:

Theorem (The Δ-theorem). Let be odd. If satisfies

then is a root of unity of odd order.

For , the norm identity puts both and on the circle of radius . Their quotient lies on the unit circle and records the rotation from to . The theorem restricts this phase to

Why should this be true? The norm identity makes every evaluation have absolute value . Since there are equally many even and odd subsets, these magnitudes cancel, giving . The same reasoning puts all its algebraic conjugates on the unit circle. An arithmetic comparison of the evaluations also shows that is an algebraic integer. We can therefore apply Kronecker's theorem: an algebraic integer whose conjugates all have absolute value one is a root of unity. A further congruence argument using the odd primes dividing shows that its order is odd.

The polynomials from Node 3 satisfy this norm identity, inherited from the Hadamard condition. Thus the theorem gives three phases of odd order, ready to compare in Node 6.

Cut from the overview · 2:11–2:25


5. Signs Become All Ones

Dig in deeper

3 child nodes

We now build a polynomial from the differences and , so that later comparisons among also give information about . We choose the combination so that, modulo , it becomes the all-ones polynomial

Lemma (Signs become all ones). Let be a positive odd integer, and let be the normalized evaluations from the same four sign polynomials in Node 3. Then

has Gaussian-integer coefficients, belongs to , and satisfies

Substituting the definitions of gives the exact identity

Every coefficient of is a sum of two signs, so the half-sum has integer coefficients. This proves that has Gaussian-integer coefficients. Since , the second term vanishes modulo . The remaining coefficients of are all or , and both reduce to because

Thus every coefficient becomes one. In our guiding case , this says

Finally, evaluating at gives . Since is odd, so is , and therefore

Cut from the overview · 2:25–2:36


6. Odd-Order Rigidity

Dig in deeper

5 child nodes

The key idea is to combine the two branches of the proof. The Δ-theorem makes our comparison products roots of unity of odd order, while the arithmetic of their common signs forces them to have residue modulo . Odd-order rigidity rules out every nontrivial root with these properties: the order must be one, so both comparison products equal .

Lemma (Odd-order rigidity). Let be odd, and let be the normalized norm solutions from the common sign array in Node 3. Define

Then

To obtain the residue condition, evaluate the sign divisibilities from Node 5 and divide by the invertible evaluations, giving . The smaller nodes inside Node 6 give the full arithmetic argument and the proof of odd-order rigidity.

In our guiding case , put . The identities mean exactly

Each ratio stays the same at the two inputs; need not equal . The six evaluations lie on circles of radius three. Set . Since , we obtain the common rotation

Thus the three points rotate together, keeping their relative angles. Now substitute the definition

For or , the value is a unit in . Dividing the evaluated identity by gives

The divisions by and are the exact divisions established in Node 5, before any modular reduction. Both ratios on the right stay the same when changes from to , so

Equivalently, : the value of picks up the same rotation. Node 7 compares this exact equality with the residues required by to obtain the contradiction for .

The general case requires more care. With several distinct prime divisors of , the identities compare alternating products; we cannot assume one shared rotation between every pair of evaluation points. The smaller nodes in Node 7 turn those product identities into a vanishing alternating-sum congruence, which Node 8 uses to finish the general argument.

Explore the common rotation

For , compare the fixed inputs and . Choose a common rotation and watch all four evaluations turn together. The triangular markers are the values of .

Rotation from the left circle to the right

Values at P = 1The values c(1), d(1), and g(1) lie on a circle of radius three. The triangular E(1) marker lies outside it. All four values rotate by 120 degrees from left to right.ReIm
Reference values · circle radius 3

Values at P = ωThe values c(ω), d(ω), and g(ω) lie on a circle of radius three. The triangular E(ω) marker lies outside it. All four values rotate by 120 degrees from left to right.ReIm
All four values rotated · circle radius 3

All four evaluations turn by 120°. Their relative angles stay fixed.

The polynomial is built from by

Here . Its value rotates by the same angle as the values of , although it need not lie on their circle. The forward multiplier is ; the reverse rotation is .

This is an illustration: no circulant Hadamard matrix of order 36 exists.

The conflict suggested by the picture

Node 5 gives . At , the all-ones terms cancel, so the same coefficient condition requires .

Required at : a nonzero residue.

Required at : zero residue.

But and must share an invertible rotation multiplier. It remains invertible modulo , so it cannot carry a nonzero residue to zero. The angle changes; the conflict is between the common rotation and these two arithmetic requirements.

Node 7 uses the equality proved above to compare the two residues and finish the nine-position example.

Continue to Node 7 →

These are requirements of the Hadamard construction, not residues computed from the schematic points above. Changing an angle alone does not make a residue become zero.

Cut from the overview · 2:36–2:50


7. From Products to Sums

Dig in deeper

4 child nodes

For our guiding case , Node 6 established the exact equality

We compare the residues of its two sides modulo . Work in , where the evaluated denominators are units: for or , the norm identity gives . These inverses remain valid after reduction.

Now use the all-ones congruence from Node 5, . At the two inputs,

Consequently and modulo . Moreover, , while remains invertible. The two equal ratios therefore have incompatible residues:

This is a contradiction in the nonzero reduction ring. It rules out , and hence a circulant Hadamard matrix of order .

For general odd , the exact comparisons involve alternating products over more evaluations. The deeper nodes establish the following replacement for the vanishing difference in our example.

Lemma (From products to sums). Let be odd, and let be the normalized polynomials from the common sign array. Define

Write for the distinct prime divisors and , with empty product . The exact identities imply

The congruence is in ; every denominator is a unit there.

Expand the equal products, cancel their common factors before reducing, and add the resulting two sums to obtain . Node 8 combines this general conclusion with the all-ones polynomial to rule out every odd .

Cancel the common rotation

Divide by on the left and on the right. The two normalized evaluations of then line up.

Rotation from the left circle to the right

Values at P = 1The values c(1), d(1), and g(1) lie on a circle of radius three. The triangular E(1) marker lies outside it. All four values rotate by 120 degrees from left to right.ReIm
Reference values · circle radius 3

Values at P = ωThe values c(ω), d(ω), and g(ω) lie on a circle of radius three. The triangular E(ω) marker lies outside it. All four values rotate by 120 degrees from left to right.ReIm
All four values rotated · circle radius 3

All four evaluations turn by 120°. Their relative angles stay fixed.

This is an illustration: no circulant Hadamard matrix of order 36 exists.

Cut from the overview · 2:50–3:01


8. The Final Contradiction

Dig in deeper

5 child nodes

Node 7 completes the contradiction for and supplies its general replacement: for every odd , the alternating sum has residue zero. We now finish the argument for all such .

Final contradiction and theorem. For an odd , the polynomials from a hypothetical circulant Hadamard matrix of order would satisfy both

These are incompatible in the nonzero reduction ring. Combined with the order restriction and the examples, this proves that a real circulant Hadamard matrix exists if and only if its order is or .

Let be the set of distinct primes dividing , and write , with . The all-ones polynomial

vanishes at every nontrivial evaluation root . At , it has value . Since and all denominators are units, only the empty-subset term survives:

Here , and is odd. This contradicts from Node 7, so no odd is possible.

Finally, Node 2 gives for every order . The contradiction leaves , hence , alongside the separate order- case. Both occur: is an order- example, and the circulant matrix with first row is an order- example. Thus the only possible orders are exactly and .

Cut from the overview · 3:01–3:34