Hadamard Matrices

Definition: A Hadamard Matrix of order $n$ is an $n \times n$ matrix $H$ with the properties that $m_{ij} = \pm 1$ for all $i, j \in \{ 1, 2, ..., n \}$ and $H H^T = nI_n$.

Here the notation "$H^T$" denotes the transpose matrix of $H$ and $nI_n$ denotes the $n \times n$ matrix whose entries are all zero except for the entries on the main diagonal which are $n$.

Many such Hadamard matrices exist. For example, the following matrix is a $2 \times 2$ Hadamard matrix:

(1)

\begin{align} \quad H = \begin{bmatrix} 1 & 1\\ 1 & -1 \end{bmatrix} \end{align}

All of the entries in $H$ are $+1$ or $-1$ and:

(2)

\begin{align} \quad HH^T = \begin{bmatrix} 1 & 1\\ 1 & -1 \end{bmatrix} \begin{bmatrix} 1 & 1\\ 1 & -1 \end{bmatrix} = \begin{bmatrix} 2 & 0\\ 0 & -2 \end{bmatrix} = 2 \begin{bmatrix} 1 & 0\\ 0 & 1 \end{bmatrix} =2I_2 \end{align}

An example of a larger Hadamard matrix is the following $4 \times 4$ matrix:

(3)

\begin{align} \quad H = \begin{bmatrix} 1 & 1 & 1 & 1\\ 1 & -1 & 1 & -1\\ 1 & 1 & -1 & -1\\ 1 & -1 & -1 & 1 \end{bmatrix} \end{align}

All of the entries in $H$ are $+1$ or $-1$ and:

(4)

\begin{align} \quad HH^T = \begin{bmatrix} 1 & 1 & 1 & 1\\ 1 & -1 & 1 & -1\\ 1 & 1 & -1 & -1\\ 1 & -1 & -1 & 1 \end{bmatrix} \begin{bmatrix} 1 & 1 & 1 & 1\\ 1 & -1 & 1 & -1\\ 1 & 1 & -1 & -1\\ 1 & -1 & -1 & 1 \end{bmatrix} = \begin{bmatrix} 4 & 0 & 0 & 0\\ 0 & 4 & 0 & 0\\ 0 & 0 & 4 & 0\\ 0 & 0 & 0 & 4 \end{bmatrix} = 4 \begin{bmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 1 \end{bmatrix} = 4I_4 \end{align}

We now state some basic properties of Hadamard matrices.

Theorem 1: If two rows or two columns of a Hadamard matrix are interchanged then the resulting matrix is also a Hadamard matrix.

• Proof: Let $H$ be an $n \times n$ Hadamard matrix. Then $h_{ij} = \pm 1$ for all $i, j \in \{ 1, 2, ..., n \}$ and:

(5)

\begin{align} \quad HH^T = \begin{bmatrix} h_{1,1} & h_{1,2} & \cdots & h_{1,n}\\ h_{2,1} & h_{2,2} & \cdots & h_{2,n}\\ \vdots & \vdots & \ddots & \vdots\\ h_{n,1} & h_{n,2} & \cdots & h_{n,n} \end{bmatrix} \begin{bmatrix} h_{1,1} & h_{2,1}& \cdots & h_{n,1} \\ h_{1,2}& h_{2,2} & \cdots & h_{n,2} \\ \vdots & \vdots & \ddots & \vdots\\ h_{1,n} & h_{2,n} & \cdots & h_{n,n} \end{bmatrix} = nI_n \end{align}

• Let $H'$ be the matrix where row $s$ is interchanged with row $t$ where $s, t \in \{ 1, 2, ..., n \}$ and $s \neq t$. Then $H'$ and $H'^T$ assume the following forms:

(6)

\begin{align} H' = \begin{bmatrix} h_{1,1} & h_{1,2} & \cdots & & & & & h_{n,1}\\ h_{2,1} & h_{2,2} & \cdots & & & & & h_{2,n}\\ \vdots & \vdots & & & & & & \vdots\\ h_{t,1} & h_{t,2} & \cdots & & & & & h_{t, n}\\ \vdots & \vdots & & & & & & \vdots \\ h_{s, 1} & h_{s, 2} & \cdots & & & & & h_{s, n}\\ \vdots & \vdots& & & & & & \vdots \\ h_{n, 1} & h_{n,2} & \cdots& & & & & h_{n,n} \end{bmatrix} \quad , \quad H'^T = \begin{bmatrix} h_{1,1} & h_{2,1}& \cdots & h_{t,1} & \cdots & h_{s,1} & \cdots & h_{n,1}\\ h_{1,2} & h_{2,2} & \cdots & h_{t,2} & \cdots & h_{s,2} & \cdots & h_{n, 2}\\ \vdots & \vdots & & \vdots & & \vdots & & \vdots \\ & & & & & & & \\ & & & & & & & \\ & & & & & & & \\ & & & & & & & \\ h_{n,1} & h_{2,n} & \cdots & h_{t,n} & \cdots & h_{s,n} & \cdots & h_{n,n} \end{bmatrix} \end{align}

• When we multiply $H'$ with $H'^T$ we get:

(7)

\begin{align} \quad H'H^T = \begin{bmatrix} \sum_{k=1}^n h_{1,k} h_{1, k} & \sum_{k=1}^n h_{1,k} h_{2, k} & \cdots & \sum_{k=1}^n h_{1,k} h_{t, k} & \cdots & \sum_{k=1}^n h_{1,k} h_{s, k} & \cdots & \sum_{k=1}^n h_{1,k} h_{n, k}\\ \sum_{k=1}^n h_{2,k} h_{1, k} & \sum_{k=1}^n h_{2,k} h_{2, k} & \cdots & \sum_{k=1}^n h_{2,k} h_{t, k} & \cdots & \sum_{k=1}^n h_{1,k} h_{s, k} & \cdots & \sum_{k=1}^n h_{2,k} h_{n, k}\\ \vdots & \vdots & & \vdots & & \vdots & & \vdots\\ \sum_{k=1}^n h_{t,k} h_{1, k} & \sum_{k=1}^n h_{t,k} h_{2, k} & \cdots & \sum_{k=1}^n h_{t,k} h_{t, k} & \cdots & \sum_{k=1}^n h_{t,k} h_{s, k} & \cdots & \sum_{k=1}^n h_{t,k} h_{n, k}\\ \vdots & \vdots & & \vdots & & \vdots & & \vdots\\ \sum_{k=1}^n h_{s,k} h_{1, k} & \sum_{k=1}^n h_{s,k} h_{2, k} & \cdots & \sum_{k=1}^n h_{s,k} h_{t, k} & \cdots & \sum_{k=1}^n h_{s,k} h_{s, k} & \cdots & \sum_{k=1}^n h_{s,k} h_{n, k}\\ \vdots & \vdots & & \vdots & & \vdots & & \vdots \\ \sum_{k=1}^n h_{n,k} h_{1, k} & \sum_{k=1}^n h_{n,k} h_{2, k} & \cdots & \sum_{k=1}^n h_{n,k} h_{t, k} & \cdots & \sum_{k=1}^n h_{n,k} h_{s, k} & \cdots & \sum_{k=1}^n h_{n,k} h_{n, k}\\ \end{bmatrix} \end{align}

• Notice that $h'h'^T_{ij} = hh^T_{ij}$ whenever $i, j \not \in \{ s, t \}$, and otherwise, the entries on the main diagonal of $H'H'^T$ are a rearrangement of the main diagonal entries of $HH^T$ so $H'H'^T = nI_n$. $\blacksquare$

Theorem 2: If any row or column in a Hadamard matrix is multiplied by $-1$ then the resulting matrix is also a Hadamard matrix.

We now state a simple result regarding the determinant of a Hadamard matrix.

Theorem 3: If $H$ is a Hadamard matrix of order $n$ then $\mathrm{det} H = n$.

• Proof: Let $H$ be a Hadamard matrix of order $n$. Then $HH^T = nI_n$. Now $\mathrm{det} (H) = \mathrm{det} (H^T)$ and from linear algebra we have that:

(8)

\begin{align} \quad \mathrm{det} (HH^T) = \mathrm{det} (H) \mathrm{det} (H^T) = \mathrm{det}^2 (H) \end{align}

• Therefore, since $n$ is positive:

(9)

\begin{align} \quad \mathrm{det}(H) &= \sqrt{\mathrm{det} (nI_n)} \\ &= \sqrt{n^2} \\ &= n \quad \blacksquare \end{align}

As a corollary to Theorem 3 we obtain the following criterion for determining whether an $n \times n$ matrix is NOT a Hadamard matrix.

Corollary 4: If $H$ is an $n \times n$ matrix and $\mathrm{det} (H) \neq n$ then $H$ is not a Hadamard matrix.