The Existence of Hadamard Matrices

Recall from the Hadamard Matrices page that a Hadamard matrix of order $n$ is an $n \times n$ matrix $H$ with the properties that $h_{ij} = \pm 1$ for all $i, j \in \{ 1, 2, ..., n \}$ and $HH^T = nI_n$.

On the Equivalent and Normalized Hadamard Matrices page we said two Hadamard matrices were equivalent if one can be obtained from the other by interchanging matrix rows and/or columns and multiplying rows and/or columns by $-1$. We also defined a Hadamard matrix to be normalized if the top row of that matrix consisted of only $1$s.

We now investigate the existence of Hadamard matrices. Thus far we have only given examples of such matrices, but, we would like to know whether or not a Hadamard matrix exists for every positive integer $m$ or not. We begin by proving a theorem which says that if $m = 3$ then no such Hadamard matrix exists.

Theorem 1: No $3 \times 3$ Hadamard matrix exists.

• Proof: Let $H$ be a $3 \times 3$ matrix such that $h_{ij} = \pm 1$ for all $i, j \in \{ 1, 2, 3 \}$:

(1)

\begin{align} \quad H = \begin{bmatrix} h_{1,1} & h_{1,2} & h_{1,3} \\ h_{2,1} & h_{2,2} & h_{2,3} \\ h_{3,1} & h_{3,2} & h_{3,3} \end{bmatrix} \end{align}

• Then $H^T$ assumes the following form:

(2)

\begin{align} \quad H^T = \begin{bmatrix} h_{1,1} & h_{2,1} & h_{3,1} \\ h_{1,2} & h_{2,2} & h_{3,2} \\ h_{1,3} & h_{2,3} & h_{3,3} \\ \end{bmatrix} \end{align}

• We take the product $HH^T$:

(3)

\begin{align} \quad HH^T = \begin{bmatrix} h_{1,1} & h_{1,2} & h_{1,3} \\ h_{2,1} & h_{2,2} & h_{2,3} \\ h_{3,1} & h_{3,2} & h_{3,3} \end{bmatrix} \begin{bmatrix} h_{1,1} & h_{2,1} & h_{3,1} \\ h_{1,2} & h_{2,2} & h_{3,2} \\ h_{1,3} & h_{2,3} & h_{3,3} \end{bmatrix} \end{align}

• Assume that $H$ is a Hadamard matrix. Then $h_{1,1}h_{2,1} + h_{1,2}h_{2,2} + h_{1,3}h_{2,3} = 0$, that is, the entry in row $1$ column $2$ of $HH^T$ is equal to $0$. But since $h_{ij} = \pm 1$ for all $i, j \in \{ 1, 2, 3 \}$, this means that $h_{1,1}h_{2,1}, h_{1,2}h_{2,2}, h_{1,3}h_{2,3} = \pm 1$, however, the equation $a + b + c = 0$ has no solutions if $a, b, c \in \{ 1, -1\}$ so the assumption that $H$ is a Hadamard matrix is false.

• Thus there exists no $3 \times 3$ Hadamard matrix. $\blacksquare$

We state an important corollary to Theorem 1 above.

Corollary 2: No $n \times n$ Hadamard matrix exists if $n > 1$ and $n$ is odd.

• ** Proof:** If $n > 1$ and $n$ is odd, the equation $a_{1} + a_{2} + ... + a_n = 0$ where $a_1, a_2, ..., a_n \in \{ 1, -1 \}$ has no solution. Thus, if $H$ is a matrix with $h_{ij} = \pm 1$ for all $i, j \in \{ 1, 2, ..., n \}$ then the entries off the main diagonal of $HH^T$ are nonzero, that is, $HH^T \neq nI_n$. [$ \blacksquare $]]

We now state a more substantial result regarding the order of Hadamard matrices.

Theorem 3: If $H$ is a Hadamard matrix of order $n$ then either $n = 1$, $n = 2$, or $n \equiv 0 \pmod 4$.

Note that if $n$ is odd and $n \neq 1, 2$ then $n \equiv 1 \pmod 4$ or $n \equiv 3 \pmod 4$ and no such Hadamard matrix exists by Corollary 2.