# Hadamard transforms seen as rotations in higher dimensions

The Hadamard transform – i.e. the multiplication of a vector $$x \in \mathbb{R}^{N}$$ (with $$N = 2^n$$) by the Hadamard matrix $$H_n$$ – yields another vector $$k = H_n x$$ in $$\mathbb{R}^{N}$$.

When using the normalized Hadamard matrix

$$H'_n = (\det H_n)^{-1/N}\cdot H_n = \frac{H_n}{\sqrt{N}}$$

instead (using $$\det H_n = N^{N/2}$$), the vector $$k = H'_n x$$ has the same norm as $$x$$, and since $$H'_n$$ is orthonormal, the mapping $$x \mapsto k = H'_nx$$ can be seen as a rotation inside $$\mathbb{R}^{N}$$.

This conflicts with the common view that the Fourier transform (which the Hadamard transform is a special/generalized case of) is a mapping of one vector space to a different one (its dual space).

Question 1:

Taking this conflict of views serious: How can it be resolved?

Question 2:

Assuming that $$H'_n$$ corresponds to a rotation: How can it be described?

Question 3:

Since Hadamard transforms are a special/generalized case of discrete Fourier transforms – using Walsh functions instead of trigonometric functions – the question arises: In which respect can discrete Fourier transforms be seen as some kind of rotations?

Edit: It might be necessary to define

$$H_{n+1} = \begin{pmatrix} H_n & H_n \\ -H_n & H_n \end{pmatrix}$$

$$H_{n+1} = \begin{pmatrix} H_n & H_n \\ H_n & -H_n \end{pmatrix}$$

which doesn't make a big difference from the point of view of Hadamard transformation, as I guess, but eases the comparison with rotation matrices:

$$R_\varphi = \begin{pmatrix} \cos\varphi & \sin\varphi \\ -\sin\varphi& \cos\varphi \end{pmatrix}$$

To give some visual sugar to these questions here is a complete table of the Hadamard transforms of $$\{0,1\}^8$$. Note that the "one-bit" arguments $$x = (0,\dots,1,\dots 0)$$ yield the columns of $$H'_3$$.

The inverse is also true: the "one-bit" arguments $$k= (0,\dots,1,\dots 0)$$ yield the rows of $$H'_3$$:

• How do you get from "determinant $1$ orthogonal matrix" to "rotation about some axis"? – Misha Lavrov Apr 25 at 22:58
• The German Wikipedia page on rotation matrices says: "Eine Rotationsmatrix ist eine reelle, orthogonale Matrix mit Determinante +1." Did I misinterpret this? – Hans-Peter Stricker Apr 25 at 23:04
• In higher dimensions, the action of a rotation matrix can be way more complicated than a rotation about a single axis by some angle. – Misha Lavrov Apr 25 at 23:07
• OK, but it's a rotation, nevertheless? (Please note that I edited my question, replacing "rotation about which axis" by "how can it be described".) – Hans-Peter Stricker Apr 25 at 23:23

Well, it depends on what you mean by "rotation". Yes, it's an element of SO(N), though this is almost "by accident". Fourier Transforms are generally complex-valued, and it is usually a good idea to choose conventions so that they are unitary. These aren't so far apart: If you use the standard embedding of a complex $$N \times N$$ matrix into a real $$2N \times 2N$$ matrix (each $$a + ib$$ in the matrix expands to a block of the form $$\begin{pmatrix}a & b \\ -b & a\end{pmatrix}$$), a unitary matrix suddenly looks orthogonal.
2. As a very high dimensional rotation, there isn't necessarily a reason to expect any easy way to visualize or explain the rotation. For the standard form, $$H = H^\dagger = H^{-1}$$, so $$H^2 = I$$, which means that the only eigenvalues are $$\pm 1$$ (and in fact these have equal multiplicity of N/2). As 180 degree rotations and non-rotations, viewing them as rotations really doesn't add much. In the simple case of $$H_1$$, the unit vectors (1, 0) and (1,1)/$$\sqrt{2}$$ are exchanged, so their sum $$x_+ = (1 + \sqrt{2}/2, \sqrt{2})$$ is preserved, and belongs to the positive eigenvalue, and similarly their difference $$x_-$$ is negated, and belongs to the negative eigenvalue. As $$H_n$$ is the $$n$$-fold Kronecker product of $$H_1$$, taking all N combinations of Kronecker products of these eigenvectors will give a set of vectors. The $$N/2$$ with an odd number $$x_{-}$$ will serve as a basis for the negative eigenspace, and the other $$N/2$$ with an even will serve as a basis for the positive eigenspace.
I would've liked to believe that your rearrangement wouldn't make much of a difference, but it does; $$H_1$$ is no longer $$H_1^\dagger=H_1^{-1}$$, and this version has a more complicated structure. Instead $$H_1^4 = -1$$, and the eigenvalues are $$\exp(\pm i \pi/ 4)$$, which really can be viewed as a 45 degree rotation. I don't know a great way of extending this to higher $$n$$ in a useful way, as the eigenvectors are inherently complex, and not in the space you're thinking of acting on. I suppose the right thing is to think of the collection of planes that are rotated, but I don't currently see an easy way to characterize them.
1. There do exist good conventions for discrete Fourier transforms in which they're just a change of basis. However in general these transforms take place with complex coëfficients. You absolutely can view them as a "complex rotation", as they are unitary, and do preserve norm. For e.g. the cyclic group of order $$k$$, you can just take the transform to be: $$F_{ij} = \exp(2 \pi \cdot i \cdot j / k)/\sqrt{k}$$. In general, this has order 4. For $$k=2$$ this reduces to the first order Hadamard $$H_1$$. (It does not for higher $$k$$, as the higher order Hadamard $$H_n$$ are Fourier transforms on $$(\mathbb{Z}/2\mathbb{Z})^n$$, rather than $$\mathbb{Z}/2^{n}\mathbb{Z}$$).