# Is there any proof that there doesn't exist a circulant Hadamard matrix of size $8 \times 8$?

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.

• 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. – Rodrigo de Azevedo Dec 18 '17 at 22:37

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.