Full overview · The circulant Hadamard conjectureShow 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.
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.
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.
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 .
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.
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
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 .
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.
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.
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.
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.
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 .