# Proving that if $n\times n$ Hadamard matrix exists, then 4 divides $n$

Im looking for an explanation of the following: a standard way to prove that, if there exists Hadamard matrix of dimension $n > 2$, then $4|n$, is to suppose that without loss of generality every column of the matrix starts with +. (Otherwise, one can multiply the column by -1, which doesn't change the Hadamard property).

Then there are only 4 possibilities of how the first three entries of each column look like: +++, ++-, +-+ and +--. Let's say there's $a$ columns of the first type, $b$ of the second, $c$ and $d$ of third and fourth respectively.

Obviously, since the matrix is $n\times n$, we obtain $a+b+c+d=n$. But here comes the point of confusion: the final step says that because of the orthogonality relations we also obtain 3 more relations: $$a + b - c - d = 0$$ $$a + c - b - d = 0$$ $$a - b - c + d = 0$$
which all put together yields $4a=n$. Im not sure, how can "number of columns of some type" be mixed with the fact that every two columns are orthogonal? How do we obtain these 3 relations? This might be a stupid question, but I can't really see something that might be obvious.

(How come the orthogonal property of the columns can yield something like "number of type 1 columns + number of type 2 columns - number of type 3 columns - number of type 4 columns" = 0 ??)

Hint: A Hadamard matrix $H$ has the property $HH^T=nI_n$. This implies that $H^T$ is Hadamard whenever $H$ is. Therefore if the columns all are orthogonal to each other, then so are the rows. Guess what you get with the inner products of the first three rows.
• First and second row have the same sign on columns of types $a$ and $b$, and a different sign on columns of types $c$ and $d$. Therefore the inner product of the first and the second rows is $a+b-c-d$. Calculate the inner products of 1st & 3rd as well as 2nd and 3rd in the same way... Apr 14, 2014 at 20:44
• I get it. First row all $+1,$ second row demanded $(1,1,1,-1,-1,-1).$ Trial third row $(-1,-1,-1,1,1,1),$ inner product $-6 \equiv 2 \pmod 4.$ If I switch one $+1$ entry in the third row to $-1,$ and one $-1$ entry to $+1,$ I have changed the dot product by $\pm 4$ or by $0,$ so it is still $2 \pmod 4.$ Apr 14, 2014 at 21:01