Hadamard matrices

A Hadamard matrix is an orthogonal matrix with entries drawing from ({+1, -1}). A Walsh-Hadamard matrix is a square matrix of size (d = 2^n), with

$${\mathbf{H}}_2=\frac{1}{\sqrt{2}}\left[\begin{array}{cc}1& 1\\ 1& -1\end{array}\right]\text{and}{\mathbf{H}}_{2^n}={\mathbf{H}}_2\otimes {\mathbf{H}}_{2^{n-1}}.$$

These identities give rise to the Walsh-Hadamard transform, which computes the matrix-vector product $\mathbf{Hx}$ in $\mathcal{O}(d{\log }_2(d))$ operations. This is because the Kronecker product recursive nature.

For matrix sizes that are not $2^n$, the existence of a Hadamard matrix is not guaranteed. A useful list of known Hadamard matrices is made available by Sloane

Where we require a Hadamard matrix of size $d\ne 2^n$, we factorize $d=2^{n}m$, where $m$ is the size of a known Hadamard matrix. Then we use a Kronecker construction ${\mathbf{H}}_d={\mathbf{H}}_{2^n}\otimes {\mathbf{H}}_m$. This allows computation of ${\mathbf{H}}_d\mathbf{x}$ in $\mathcal{O}(d(m+n))$ operations. There exist also randomized Hadamard matrices. Let $\mathbf{s}$ be a vector containing random draws from $\{+1,-1\}$, and $\tilde{\mathbf{H}}=\mathbf{H}\text{diag}(\mathbf{s})$. It is straightforward to see that $\tilde{\mathbf{H}}$ is also an orthogonal matrix.

What is the Kronecker Product?

The Kronecker product of two matrices $\mathbf{A}$ of size $m\times n$ and $\mathbf{B}$ of size $p\times q$ is a block matrix of size $mp\times nq$ defined as:

\begin{bmatrix} a_{11}\mathbf{B} & a_{12}\mathbf{B} & \cdots & a_{1n}\mathbf{B} \\ a_{21}\mathbf{B} & a_{22}\mathbf{B} & \cdots & a_{2n}\mathbf{B} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1}\mathbf{B} & a_{m2}\mathbf{B} & \cdots & a_{mn}\mathbf{B} \end{bmatrix}$$ ## Example for Hadamard Matrices For example, with $\mathbf{H}_2 = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}$, we can compute $\mathbf{H}_4 = \mathbf{H}_2 \otimes \mathbf{H}_2$ as: $$\mathbf{H}_4 = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} \otimes \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} = \frac{1}{2} \begin{bmatrix} 1 \cdot \mathbf{H}_2 & 1 \cdot \mathbf{H}_2 \\ 1 \cdot \mathbf{H}_2 & -1 \cdot \mathbf{H}_2 \end{bmatrix}$$ Which gives: $$\mathbf{H}_4 = \frac{1}{2} \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \end{bmatrix}$$ This recursive construction using the Kronecker product allows: 1. The Walsh-Hadamard transform to be implemented efficiently 2. The resulting matrix to maintain orthogonality 3. The matrix size to grow as powers of 2 ($2^n$)