How can I prove using induction that the Hadamard matrices are orthogonal?

Question

I can't figure out how to prove using induction that the dot product of 2 rows in a Hadamard matrix is 0. I've always thought of it as just a property of the type of matrix.

Answer 1

Why use induction? The $2^n\times 2^n$ Hadamard matrix $H$, whose rows and columns are indexed by vectors $x,y \in \{0,1\}^n$, has entries $$ H(y,x) = (-1)^{\sum_i x_i y_i}. $$ Now suppose that $y,z$ are two different rows, say $y_j \neq z_j$. The inner product between the two rows is $$ \sum_x H(y,x) H(z,x) = \sum_x (-1)^{\sum_i x_i (y_i + z_i)}. $$ We can decompose $x$ as $x_j,x_{-j}$, where $x_{-j} \in \{0,1\}^{n-1}$. The inner product is then $$ \begin{align*} \sum_x H(y,x) H(z,x) &= \sum_{x_j,x_{-j}} (-1)^{x_j} (-1)^{\sum_{i \neq j} x_i (y_i + z_i)} \\ &= \sum_{x_{-j}} (-1)^{\sum_{i \neq j} x_i (y_i + z_i)} \sum_{x_j=0}^1 (-1)^{x_j} \\ &= 0. \end{align*} $$

A more sophisticated proof uses the fact that the $n$th Hadamard matrix is the $n$th tensor power of $$ \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}, $$ which has orthogonal rows. It is not too hard to check that the tensor product of two matrices with orthogonal rows also has orthogonal rows, and then induction yields the desired result.

Answer 2

Your doubts were justified: by definition, a Hadamard matrix is a matrix with elements $\pm1$ whose rows are pairwise mutually orthogonal. So there is nothing to prove.

Yuval Filmus's answer provides a proof that a family of $2^n\times 2^n$ matrices constructed by Sylvester are Hadamard matrices. But Hadamard's own main contribution to the field of Hadamard matrices was to find examples of sizes $12$ and $20$. These are not of Sylvester's form, and therefore that proof does not apply to them.