4
$\begingroup$

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 ??)

$\endgroup$
1

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ It is clear for me that if columns are orthogonal, so are the rows. But I can't see how this relates to the number of the columns of those types. $\endgroup$
    – NumberFour
    Apr 14, 2014 at 20:42
  • $\begingroup$ 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... $\endgroup$ Apr 14, 2014 at 20:44
  • $\begingroup$ Ok, even though I knew this and you didn't actually answer my question, you forced me to write it down again and now I see it really works! Thank you :) $\endgroup$
    – NumberFour
    Apr 14, 2014 at 20:59
  • $\begingroup$ 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.$ $\endgroup$
    – Will Jagy
    Apr 14, 2014 at 21:01
  • 2
    $\begingroup$ Glad to hear that you figured it out, @NumberFour. Well done! I have this habit of dropping hints rather than spelling it all out if at all feasible. I believe that this approach has some pedagogical merit :-) $\endgroup$ Apr 14, 2014 at 21:13

You must log in to answer this question.

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