Jump to main content
Circulant Hadamard

Cyclic Shifts

Full overview · Cyclic Shifts
Show the proof map

Multiplying by X moves the last coefficient to the first position: one right cyclic shift.

Multiplication implements a shift

Work in and encode a row by

Using ,

The coefficient list changes from to . This is exactly one cyclic shift to the right.

Any number of shifts

Proposition. For any integer , the coefficient of in is , with all subscripts reduced modulo .

Proof. A term contributes to position precisely when , or . This selects exactly one coefficient.

Consequently the -th row, when rows are numbered , corresponds to . In formulas we instead number rows and columns and write

For the fixed example, and , corresponding to the second row . After shifts, .

Output. Every row of the circulant matrix is represented by a power of times the same polynomial.

Back to Group-Ring Encoding