The powers mark the positions in a cyclic row.
The relation makes the positions wrap around. Every element
has a unique representative of degree less than , so its
coefficient list is unambiguous.
Encode the first row by
Here is a formal position marker. For the order-four example
with first row ,
Multiplication by shifts the coefficient list one position to
the right. Reducing to gives
Thus the rows of a circulant matrix correspond to
. In our order-four example,
whose coefficients form the next row, .
With rows numbered from , row corresponds to .
With rows and columns numbered from , the same rule is
. All coefficient subscripts are reduced modulo .
This stays in the same group ring, since . Star reverses cyclic
positions while leaving the coefficient at position zero fixed.
It does not change the signs and is not the reciprocal .
For four arbitrary coefficients, the reversal is
Our fixed row is symmetric under this reversal, so
Multiplying by the reversed polynomial records all the cyclic dot
products at once. For ,
Here means the coefficient in the representative of degree
less than , and the subscripts are taken modulo . The sum is
the dot product of the first row with its -step right shift.
This coefficient identity holds for arbitrary integer coefficients.
For the first row :
Shift
Right-shifted row
Dot product
Therefore in : the constant coefficient is
and all other coefficients are zero.
Lemma (Circulant Hadamard Dictionary).Let
with every , and let be the circulant matrix whose first row is
.
Then
If the rows are orthogonal, the correlation identity makes every
nonconstant coefficient zero. The constant coefficient is
because the coefficients are signs. Thus the
product is the constant polynomial .
Conversely, that polynomial identity says the first row is
orthogonal to every nontrivial shift. Any pair of distinct rows
has the same dot product as the first row and one such shift, so
all distinct rows are orthogonal. Because every coefficient is
assumed to be , every matrix entry is as well. Thus is
Hadamard. The polynomial identity alone does not imply the sign condition.