A matrix $H \in {\pm 1}^n $ is Hadamard matrix if $HH^T=nI_n$, where $I$ is $n\times n$ identity matrix. Hadamard's conjecture said that there exists Hadamard matrix of order 1,2 or $4n$, for every positive integer $n$.

My question is how to prove there does not exists a $6 \times 6$ Hadamard matrix?


Wlog (why?) the first row is $(1\,1\,1\,1\,1\,1)$ and all other rows have three $+1$ and three $-1$ entries. If the second and third row have $r$ entries $+1$ in common ($0\le r\le 3$), then they also have $r$ entries $-1$ in common and their scalar product is $r\cdot 1^2+r\cdot (-1)^2+(6-2r)\cdot(-1)=4r-6\ne0$, contradiction.

Upon closer look, this argument can be extended to show that $H_n$ can exist only when $4\mid n$ or $n<3$:

Assume $n\ge 3$. Again with the first row being wlog all-ones, every other row must have an equal amount of $+1$'s and $-1$'s, hence $n$ must be even. Then as above, if the second and third row have $r$ entries $+1$ in common, they also share $r$ entries $-1$, and their scalar product is $4r-n$. As this is $0$, it follows that $4\mid n$.

  • $\begingroup$ [+1] Very interesting proof $\endgroup$ – Jean Marie Feb 21 at 8:39

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.