---
tag: 3BTA41B7M1
kind: definition
name: Walsh–Hadamard transform
msc: [42C10, 65T50, 94A12]
defines: K784BA2WHV
uses: [J0N4J606X0, 0N7ENQRCXN]
sources:
  - url: https://en.wikipedia.org/wiki/Hadamard_transform
---

## Definition

Let $m \ge 0$ and $N = 2^m$.
Let $H_0 = (1)$, and for $m \ge 1$ let $H_m = H_1 \otimes H_{m-1}$, where $\otimes$ is the [[Kronecker product|0N7ENQRCXN]] and
$$H_1 = \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}.$$
The *Walsh–Hadamard transform* of a vector $x \in \C^N$ is the vector $H_m x \in \C^N$.
Index rows and columns by $0, \dots, N-1$.
Then $(H_m)_{jk} = (-1)^{j \cdot k}$, where $j \cdot k$ counts the positions where the binary expansions of $j$ and $k$ both have the digit $1$.

## Remarks

$H_m$ is a symmetric [[Hadamard matrix|J0N4J606X0]] of order $N$, so $H_m^2 = N I$ and the inverse transform is $x = N^{-1} H_m (H_m x)$.
Many authors use the normalized matrix $N^{-1/2} H_m$, which is orthogonal and its own inverse.
Writing $x$ as two halves $x = (x', x'')$, one has $H_m x = (H_{m-1}(x' + x''), H_{m-1}(x' - x''))$; iterating this gives the fast transform with $m N$ additions and subtractions.

Example: for $m = 2$,
$$H_2 = \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \end{pmatrix},$$
and $x = (1, 0, 0, 0)$ goes to $(1, 1, 1, 1)$, while $x = (1, 1, 1, 1)$ goes to $(4, 0, 0, 0)$.
Check of one entry: $(H_2)_{3,3} = (-1)^{2} = 1$, since $3 = 11_2$ shares two digits $1$ with itself.

Non-example: the discrete Fourier transform matrix $(e^{-2\pi i jk/4})_{j,k}$ of order $4$ has entries $\pm i$, so it is not $H_2$, although its rows are also orthogonal.