Mathematical Immaturity

2.21 Miscellaneous review exercises on matrices

10. $\quad$ Hadamard matrices, named for Jacques Hadamard (1865-1963), are those $n \times n$ matrices with the following properties:

I. $\quad$ Each entry is 1 or $-1.$
II. $\quad$ Each row, considered as a vector in $V_n,$ has length $\sqrt{n}.$
III. $\quad$The dot product of any two distinct rows is 0.

$\quad$ Hadamard matrices arise in certain problems in geometry and the theory of numbers, and they have been applied recently to the construction of optimum code words in space communication. In spite of their apparent simplicity, they present many unsolved problems. The main unsolved problem at this time is to determine all $n$ for which an $n \times n$ Hadamard matrix exists. This exercise outlines a partial solution.

(a) $\quad$ Determine all $2 \times 2$ Hadamard matrices (there are exactly 8).
(b) $\quad$ This part of the exercise outlines a simple proof of the following theorem: If $A$ is an $n \times n$ Hadamard matrix, where $n > 2,$ then $n$ is a multiple of 4. The proof is based on two very simple lemmas concerning vectors in $n$-space. Prove each of these lemmas and apply them to the rows of Hadamard matrix to prove the theorem.

$\quad$ Lemma 1. $\quad$ If $X,$ $Y,$ $Z$ are orthogonal vectors in $V_n,$ then we have $$(X + Y) \cdot (X + Z) = \|X\|^2.$$ $\quad$ Lemma 2. $\quad$ Write $X = (x_1, \ldots, x_n),$ $Y = (y_1, \ldots, y_n),$ $Z = (z_1, \ldots, z_n).$ If each component $x_i,$ $y_i,$ $z_i$ is either 1 or $-1,$ then the product $(x_i + y_i)(x_i + z_i)$ is either 0 or 4.

(a) $\quad$ Determine all $2 \times 2$ Hadamard matrices (there are exactly 8).

Solution. $\quad$ The eight $2 \times 2$ Hadamard matrices are: \begin{align*} \begin{bmatrix}-1 & 1 \\ 1 & 1 \end{bmatrix}, \quad \begin{bmatrix}1 & -1 \\ 1 & 1 \end{bmatrix}, \quad \begin{bmatrix}1 & 1 \\ -1 & 1 \end{bmatrix}, \quad \begin{bmatrix}1 & 1 \\ 1 & -1 \end{bmatrix}, \quad \begin{bmatrix}1 & -1 \\ -1 & -1 \end{bmatrix}, \quad \begin{bmatrix}-1 & 1 \\ -1 & -1 \end{bmatrix}, \quad \begin{bmatrix}-1 & -1 \\ 1 & -1 \end{bmatrix}, \quad \begin{bmatrix}-1 & -1 \\ -1 & 1 \end{bmatrix} \quad \blacksquare \end{align*}

(b) $\quad$ Lemma 1. $\quad$ If $X,$ $Y,$ $Z$ are orthogonal vectors in $V_n,$ then we have $$(X + Y) \cdot (X + Z) = \|X\|^2.$$ $\quad$ Proof. $\quad$ We can use the distributive property of the dot product, noting that $X \cdot X = \|X\|^2,$ to write $(X + Y) \cdot (X + Z)$ as \begin{align*} \\ (X + Y) \cdot (X + Z) &= \|X\|^2 + X \cdot Z + Y \cdot X + Y \cdot Z \end{align*} But since $X, Y,$ and $Z$ are orthogonal vectors, $$X \cdot Z = Y \cdot X = Y \cdot Z = 0,$$ giving us $(X + Y) \cdot (X + Z) = \|X\|^2. \quad \blacksquare$

$\quad$ Lemma 2. $\quad$ Write $X = (x_1, \ldots, x_n),$ $Y = (y_1, \ldots, y_n),$ $Z = (z_1, \ldots, z_n).$ If each component $x_i,$ $y_i,$ $z_i$ is either 1 or $-1,$ then the product $(x_i + y_i)(x_i + z_i)$ is either 0 or 4.

$\quad$ Proof. $\quad$ This proof breaks down into two main cases, each with four sub-cases. First, $x_i$ can either be $1$ or $-1,$ giving our two main cases

(1) $\quad$ $x_i = 1,$ $\quad$ from which we reach four sub-cases:
$\quad$ (1.1) $\quad$ $y_i = 1, z_i = 1. \quad$ Then $(x_i + y_i)(x_i + z_i) = (1 + 1)(1 + 1) = 4.$
$\quad$ (1.2) $\quad$ $y_i = 1, z_i = -1. \quad$ Then $(x_i + y_i)(x_i + z_i) = (1 + 1)(1 - 1) = 0.$
$\quad$ (1.3) $\quad$ $y_i = -1, z_i = 1. \quad$ Then $(x_i + y_i)(x_i + z_i) = (1 - 1)(1 + 1) = 0.$
$\quad$ (1.4) $\quad$ $y_i = -1, z_i = -1. \quad$ Then $(x_i + y_i)(x_i + z_i) = (1 - 1)(1 - 1) = 0.$

(2) $\quad$ $x_i = -1,$ $\quad$ from which we reach four sub-cases:
$\quad$ (2.1) $\quad$ $y_i = 1, z_i = 1. \quad$ Then $(x_i + y_i)(x_i + z_i) = (-1 + 1)(1 + 1) = 0.$
$\quad$ (2.2) $\quad$ $y_i = 1, z_i = -1. \quad$ Then $(x_i + y_i)(x_i + z_i) = (-1 + 1)(-1 - 1) = 0.$
$\quad$ (2.3) $\quad$ $y_i = -1, z_i = 1. \quad$ Then $(x_i + y_i)(x_i + z_i) = (-1 - 1)(-1 + 1) = 0.$
$\quad$ (2.4) $\quad$ $y_i = -1, z_i = -1. \quad$ Then $(x_i + y_i)(x_i + z_i) = (-1 - 1)(-1 - 1) = 4.$
Having exhausted every case, we have shown that if each component $x_i, y_i, z_i$ is either $1$ or $-1,$ the product $(x_i + y_i)(x_i + z_i)$ is either $0$ or $4.$ Now, we will use these results to prove the following theorem:

$\quad$ Theorem. $\quad$ If $A$ is an $n \times n$ Hadamard matrix, where $n > 2,$ then $n$ is a multiple of 4.

$\quad$ Proof. $\quad$ Let $A$ be an $n \times n$ Hadamard matrix, where $n > 2.$ Then, let $X, Y$ and $Z$ be any three distinct rows of $A,$ where \begin{align*} X &= (x_1, \dots, x_n), \quad Y = (y_1, \dots, y_n), \quad Z = (z_1, \dots, z_n) \end{align*} As a result of Lemma, we know that \begin{align*} \|X\|^2 &= (X + Y) \cdot (X + Z) = \sum_{k=1}^n (x_k + y_k)(x_k + z_k) \end{align*} But by definition, each row of $A$ has length $\sqrt{n},$ which means $\|X\|^2 = n.$ And as we proved in Lemma 2, each term of the sum on the right-hand side is either $0$ or $4.$ But because $n \gt 0,$ there is at least one $k$ in $(1, 2, \dots, n)$ such that $(x_k + y_k)(x_k + z_k) = 4.$ As such, for some integer $m \geq 1,$ we have $n = 4m. \quad \blacksquare$