Jump to main content
Circulant Hadamard

Correlation Identity

Full overview · Correlation Identity
Show the proof map

Each coefficient of h(X)h*(X) is a dot product with a cyclic shift of the original row.

The coefficient identity

Let be arbitrary integers and set in . For , write for the coefficient of in the unique representative of of degree less than .

Proposition. With all coefficient subscripts taken modulo ,

Proof. Expand in this group ring:

A term contributes to exactly when . Thus , which gives the formula. The list is the original list shifted places to the right, so the sum is its dot product with the first row.

Equivalently, the complete product is

The order-four calculation

For the first row :

Shift Right-shifted row

Thus . The coefficient identity itself does not require sign coefficients; signs will enter when the constant coefficient is set equal to .

Output. One product records all cyclic dot products, for arbitrary integer rows.

Back to Group-Ring Encoding