Jump to main content
Circulant Hadamard
Back to Proof map

Group-Ring Encoding

Full overview · Group-Ring Encoding
Show the proof map


1.1. Group Ring

Dig in deeper

Undergraduate foundation

Let . Its integer group ring is

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 ,

Cut from the overview · 0:16–0:45


1.2. Cyclic Shifts

Dig in deeper

Undergraduate foundation

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 .

Cut from the overview · 0:45–1:09


1.3. Star Operation

Dig in deeper

Undergraduate foundation

Define the star operation by

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

Cut from the overview · 1:09–1:39


1.4. Correlation Identity

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.

Cut from the overview · 1:39–2:15


1.5. Hadamard Dictionary

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.

Matrix language Polynomial language
First row
Shift right by one Multiply by
Row , numbered from
Reverse cyclic positions Replace by
Dot product with the -step shift
Orthogonal rows, each with squared length
Cut from the overview · 2:15–3:20
Back to Proof map