5
$\begingroup$

Is there any proof that there doesn't exist an $8 \times 8$ circulant Hadamard matrix?


A matrix $H \in \{\pm 1\}^{n \times n}$ is Hadamard if $H H^T = n I$, where $I$ is the $n \times n$ identity matrix. Then, a Hadamard matrix $H$ such that $h_{i,~j}=h_{(i+1)~mod~n,~(j+1)~mod~n}$ is a circulant Hadamard matrix.


For example, let $\pi$ be a $4$-size matrix $[1, -1, -1, -1]$. Let

$$A = \text{circulant}(\pi)=\left[\begin{array}{rrrr}1&-1&-1&-1\\-1&1&-1&-1\\-1&-1&1&-1\\-1&-1&-1&1\end{array}\right]$$

Since

$$AA^T=4I=\text{circulant}(1,0,0,0)=\left[\begin{array}{rrrr}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\end{array}\right]$$

where $A$ is the $4 \times 4$ Hadamard matrix.


Now, my question is how to prove that there does not exist an $8 \times 8$ circulant Hadamard matrix. I can check all possible $8 \times 8$ circulant matrices using MATLAB. There are just $2^8$ possible cases; $\text{circulant}(\pm1, \pm1, \pm1, \pm1, \pm1, \pm1, \pm1, \pm1)$. However, I want to know mathematical proof not a proof via simulation.

$\endgroup$
  • $\begingroup$ Why don't you use MATLAB and brute force to find the answer? Once you know the answer, you know what you would like to prove. $\endgroup$ – Rodrigo de Azevedo Dec 18 '17 at 22:37
3
$\begingroup$

There is no $8$ by $8$ circulant Hadamard matrix. Write an $n$ by $n$ Hadamard matrix $H$ as $[v_1,\dots,v_n]$, where $v_k$ is the $k$-th row. The condition of being Hadamard means that all rows of $H$ are mutually orthogonal. The condition of being circulant means that $$v_{k+1} = \begin{bmatrix} 0 & 0 & 0 & \dots & 0 & 1 \\ 1 & 0 & 0 & \dots & 0 & 0 \\ 0 & 1 & 0 & \dots & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \dots & 1 & 0 \end{bmatrix} v_k $$

Call the matrix in the preceding expression $R$. For $H$ to be Hadarmard, $v_1 \cdot R^m v_1 = 0$ for $m=1,2,\dots,n-1$. Hence, $0 = v_1 \cdot (R+R^2 + \dots + R^{n-1})v_1$.

Now note that $$I + R+R^2 + \dots + R^{n-1} = \begin{bmatrix} 1 & 1 & \dots & 1 \\ 1 & 1 & \dots & 1 \\ \vdots & \vdots & \ddots & \vdots \\ 1 & 1 & \dots & 1 \end{bmatrix}$$ Where $I$ is the identity matrix.

On the one hand, $v_1 \cdot (I + R+R^2 + \dots + R^{n-1}) v_1 = v_1 \cdot I v_1 = ||v_1||^2 = n$. On the other hand, $$v_1\cdot \begin{bmatrix} 1 & 1 & \dots & 1 \\ 1 & 1 & \dots & 1 \\ \vdots & \vdots & \ddots & \vdots \\ 1 & 1 & \dots & 1 \end{bmatrix} v_1 = \left(\sum_k v_{1,k}\right)^2$$

Where $v_{1,k}$ is the $k$-th component of $v_1$. In order for this to not be a contradiction, we must have that $n$ is a perfect square. This is not the case for $n=8$, hence there is no such Hadamard matrix in this dimension.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.