4
$\begingroup$

Definitions: A weighing matrix $W = W(n,k)$ with weight $k$ is a square matrix of order $n$ and entries $w_{ij}$ in $\{0, \pm 1\}$ such that $WW^T=kI$, where $I$ is the identity matrix. A circulant weighing matrix $CW(n,k)$ is a special type of weighing matrix in which every row except for the first is a right cyclic shift of the previous row.

Background: A $CW(512, 16^2)$ does not exist.

Questions: How many ways are there to prove this nonexistence result? Where can I find a complete proof? Thanks!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

The posed question is very close to questions on the existence of circulant Hadamard matrices and the nonexistence techniques of that theory should suffice.

Suppose $W$ is a circulant weighing matrix $CW(512, 16^2).$ Then we may view $W$ as an element of the group ring $\mathbb{Z}[G]$ where $G$ is the cyclic group of order 512. The coefficients of $W$ are in the set $\{-1,0,1\}.$

Any character $\chi$ of the cyclic group of order 512 gives the equation $$ \chi(W)\overline{\chi(W)} = 16^2.$$ Now $\chi(W)$ is an element of $\mathbb{Z}[\zeta]$ where $\zeta$ is a primitive 512-th root of unity. In the algebraic number ring $\mathbb{Z}[\zeta]$, the ideal (2) factors as $(1-\zeta)^{256}$ and so $(16^2)=(2^8)$ factors as $(1-\zeta)^{256\cdot 8}$. But these ideals are fixed by conjugation, so $(\chi(W))$ is the ideal $(1-\zeta)^{256\cdot 4} = (2)^4.$

One can show that with respect to the standard integer basis of $\mathbb{Z}[\zeta]$, all the elements of $(2)^4$ have coefficients divisible by 2 (indeed by 16.) Since the minimal polynomial of $\zeta$ is $x^{256}+1$, one can then write $W$ in the form $a(x^{256}-1)+2b$ where $a, b \in \mathbb{Z}[G]$ and get a contradiction to the claim that the coefficients of $W$ are just from $\{-1,0,1\}.$

A comment: I always find the algebraic number theory a little tricky (and have made several edits to tighten the explanation) but the number theory is relatively "easy" if we are in a group of order $2^k$. The algebraic number theory quickly gets complicated if several primes divide the order of the group.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ One accessible reference for circulant Hadamard matrices is [link] ocw.mit.edu/courses/… (See Theorem 1.) $\endgroup$
    – Ken W. Smith
    Commented Aug 10 at 21:34
  • 2
    $\begingroup$ It might be quicker to note that $\chi(W) = 16 \theta$ for some element $\theta \in \mathbb{Z}[\zeta]$, and then that all algebraic conjugates of $\theta$ have absolute value $1$, so that $\theta$ is a root of unity by Kronecker's theorem mentioned in the linked notes. $\endgroup$
    – Geoff Robinson
    Commented Aug 13 at 10:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .