The Kronecker Product of Two Hadamard Matrices

Recall from The Kronecker Product of Two Matrices page that if $A$ is an $m \times n$ matrix and $B$ is an $s \times t$ matrix then the Kronecker product $A \otimes B$ of these two matrices is the $ms \times nt$ given by:

(1)

\begin{align} \quad A \otimes B = A \otimes B = \begin{bmatrix} a_{1,1} B & a_{1,2} B & \cdots & a_{1,n} B \\ a_{2,1} B & a_{2,2} B & \cdots & a_{2,n} B\\ \vdots & \vdots & \ddots & \vdots \\ a_{m,1} B & a_{m,2} B & \cdots & a_{m,n} B \end{bmatrix} \end{align}

We will now state a remarkable theorem which tells us that if $H_1$ and $H_2$ are both Hadamard matrices then so is their Kronecker product.

Theorem 1: If $H_1$ is an $m \times m$ Hadamard matrix and $H_2$ is an $n \times n$ Hadamard matrix then $H_1 \otimes H_2$ is an $mn \times mn$ Hadamard matrix.

For example, consider the following Hadamard matrices:

(2)

\begin{align} \quad H_1 = \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} \quad , \quad H_2 = \begin{bmatrix} 1 & 1 & 1 & 1 \\1 & -1 & -1 & 1 \\ -1 & -1 & 1 & 1 \\ -1 & 1 & -1 & 1 \end{bmatrix} \end{align}

The Kronecker product $H_1 \otimes H_2$ is:

(3)

\begin{align} \quad H_1 \otimes H_2 = \begin{bmatrix} 1 \begin{bmatrix} 1 & 1 & 1 & 1 \\1 & -1 & -1 & 1 \\ -1 & -1 & 1 & 1 \\ -1 & 1 & -1 & 1 \end{bmatrix} & 1 \begin{bmatrix} 1 & 1 & 1 & 1 \\1 & -1 & -1 & 1 \\ -1 & -1 & 1 & 1 \\ -1 & 1 & -1 & 1 \end{bmatrix}\\ 1 \begin{bmatrix} 1 & 1 & 1 & 1 \\1 & -1 & -1 & 1 \\ -1 & -1 & 1 & 1 \\ -1 & 1 & -1 & 1 \end{bmatrix}& -1 \begin{bmatrix} 1 & 1 & 1 & 1 \\1 & -1 & -1 & 1 \\ -1 & -1 & 1 & 1 \\ -1 & 1 & -1 & 1 \end{bmatrix} \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & -1 & -1 & 1 & 1 & -1 & -1 & 1 \\ -1 & -1 & 1 & 1 & -1 & -1 & 1 & 1 \\ -1 & 1 & -1 & 1 & -1 & 1 & -1 & 1 \\ 1 & 1 & 1 & 1 & -1 & -1 & -1 & -1 \\ 1 & -1 & -1 & 1 & -1 & 1 & 1 & -1 \\ -1 & -1 & 1 & 1 & 1 & 1 & -1 & -1 \\ -1 & 1 & -1 & 1 & 1 & -1 & 1 & -1 \end{bmatrix} \end{align}

We know that if $H$ is a Hadamard matrix of order $n$ then $n = 1$, $n = 2$, or $n \equiv 0 \pmod 4$ but in general, it is not known if these are sufficient conditions for the existence of a Hadamard matrix of order $n$, that is, there may exist a positive integer $n > 2$ with $n \equiv 0 \pmod 4$ for which no Hadamard matrix exists. The theorem above gives us a criterion for the existence of Hadamard matrices of certain orders. In particular, if $n\equiv 0 \pmod 4$ and $n = st$ where $s, t = 1, 2 $] or [[$ s \equiv 0 \pmod 4$ and $t \equiv 0 \pmod 4$; and it is known that Hadamard matrices of order $s$ and $t$ exist, then it is guaranteed that a Hadamard matrix of order $n$ exists.