Jump to main content
Circulant Hadamard

Hadamard Dictionary

Full overview · Hadamard Dictionary
Show the proof map

The polynomial identity and the circulant Hadamard condition imply one another.

The dictionary lemma

Let and let be the circulant matrix formed by their successive cyclic right shifts. Set in and define .

Lemma (Circulant Hadamard Dictionary). The matrix is Hadamard if and only if in this group ring. Equivalently,

Forward implication

Suppose . The first row is orthogonal to each nontrivial cyclic shift. By the coefficient identity, every nonconstant coefficient of is zero. The constant coefficient is

because each is a sign. Hence .

Reverse implication

Suppose has all coefficients and satisfies in this group ring. Form from the coefficient list and its successive cyclic right shifts. Uniqueness of the degree-less-than- representative makes every nonconstant coefficient zero. Therefore the first row is orthogonal to each nontrivial cyclic shift.

To compare any two rows, number rows and columns from zero. The cyclic-shift formula gives

where the exponent and subscripts are interpreted modulo . This is zero when and when . Consequently . Every entry of is by the coefficient assumption, so is a circulant Hadamard matrix.

Why the hypotheses matter

The coefficient formula works for arbitrary integers. Signs guarantee that the row norm squared is in the forward direction and that the constructed matrix has entries in the converse. The polynomial identity alone does not force sign coefficients: satisfies in , but its coefficient list gives , which is not Hadamard.

Signs and cyclic structure alone do not imply orthogonality either. For example, the all-ones row at order four gives

in .

Output. Both directions of the equivalence are established. The next main node uses the resulting equation to restrict the order.

Back to Group-Ring Encoding