Hadamard transforms seen as rotations in higher dimensions

Question

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}$$

instead of

$$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$:

Answer 1

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.

1. There is no conflict, because once we label these spaces with a particular basis (which we have as soon as we write down the elements of the transform matrix) they are "self-dual": there is a direct isomorphism between the dual space and the original space given by mapping the first basis vector to the first basis dual-vector, and so forth.

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.

3. 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}$).