0
$\begingroup$

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

enter image description here

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

enter image description here

$\endgroup$
  • $\begingroup$ How do you get from "determinant $1$ orthogonal matrix" to "rotation about some axis"? $\endgroup$ – Misha Lavrov Apr 25 at 22:58
  • $\begingroup$ The German Wikipedia page on rotation matrices says: "Eine Rotationsmatrix ist eine reelle, orthogonale Matrix mit Determinante +1." Did I misinterpret this? $\endgroup$ – Hans-Peter Stricker Apr 25 at 23:04
  • 2
    $\begingroup$ In higher dimensions, the action of a rotation matrix can be way more complicated than a rotation about a single axis by some angle. $\endgroup$ – Misha Lavrov Apr 25 at 23:07
  • $\begingroup$ 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".) $\endgroup$ – Hans-Peter Stricker Apr 25 at 23:23
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.