Walsh–Hadamard transform

Remarks

$H_m$ is a symmetric Hadamard matrix 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.