M.E. Irizarry-Gelpí

Physics impostor. Mathematics interloper. Husband. Father.

Discrete Hartley Transforms 2


Here is a quick recap of four distinct transforms that can be adapted to quantum Hilbert spaces. First, the most important one: the discrete Fourier transforms:

\begin{align*} (F_{N})_{mn} &= \frac{1}{\sqrt{N}} \left[ \exp{\left(- \frac{2 \pi i}{N} \right)} \right]^{mn}, & (G_{N})_{mn} &= \frac{1}{\sqrt{N}} \left[ \exp{\left( \frac{2 \pi i}{N} \right)} \right]^{mn} \end{align*}

Next, the two discrete Hartley transforms:

\begin{align*} (P_{N})_{mn} &= \sqrt{\frac{2}{N}} \operatorname{cps}{\left( \frac{2 \pi m n}{N} \right)}, & (Q_{N})_{mn} &= \sqrt{\frac{2}{N}} \operatorname{cqs}{\left( \frac{2 \pi m n}{N} \right)} \end{align*}

with the Hartley functions given by

\begin{align*} \operatorname{cps}{(x)} &= \frac{\cos{(x)} + \sin{(x)}}{\sqrt{2}} & \operatorname{cqs}{(x)} &= \frac{\cos{(x)} - \sin{(x)}}{\sqrt{2}} \end{align*}

And finally, the discrete Hadamard transform, which is defined recursively:

\begin{align*} H_{2} &= \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}, & H_{4} &= H_{2} \otimes H_{2}, & H_{8} &= H_{4} \otimes H_{2}, & H_{16} &= H_{8} \otimes H_{2}, & H_{32} &= \ldots \end{align*}

Let us look at these transforms for different values of \(N\).

One-Dimensional Hilbert Space

For \(N = 1\), all of these transforms agree:

\begin{equation*} F_{1} = G_{1} = P_{1} = Q_{1} = H_{1} = 1 \end{equation*}

One-dimensional Hilbert spaces are not interesting, so not much to see here.

Two-Dimensional Hilbert Space

The first non-trivial dimension is the \(N = 2\) case. However, all transforms agree:

\begin{equation*} F_{2} = G_{2} = P_{2} = Q_{2} = H_{2} = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} \end{equation*}

So Fourier and Hartley are all equivalent to Hadamard. Note that

\begin{equation*} (F_{2})^{2} = I_{2} \end{equation*}

That is, each transform is its own inverse.

Three-Dimensional Hilbert Space

For \(N = 3\) you cannot have the Hadamard transform. The Fourier transforms are

\begin{align*} F_{3} &= \frac{1}{\sqrt{3}} \begin{pmatrix} 1 & 1 & 1 \\ 1 & c & c^{2} \\ 1 & c^{2} & c \end{pmatrix}, & G_{3} &= \frac{1}{\sqrt{3}} \begin{pmatrix} 1 & 1 & 1 \\ 1 & c^{2} & c \\ 1 & c & c^{2} \end{pmatrix}, & c &= -\frac{1}{2} - \frac{\sqrt{3}}{2}i, & c^{2} &= \frac{1}{c} \end{align*}

Note that the squared Fourier transforms give a permutation matrix

\begin{equation*} (F_{3})^{2} = (G_{3})^{2} = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix} \end{equation*}

The fourth power of the Fourier transforms gives the identity:

\begin{equation*} (F_{3})^{4} = (G_{3})^{4} = I_{3} \end{equation*}

You also have \(F_{3} G_{3} = G_{3} F_{3} = I_{3}\).

The Hartley transforms are

\begin{align*} P_{3} &= \frac{1}{\sqrt{3}} \begin{pmatrix} 1 & 1 & 1 \\ 1 & \operatorname{cps}{\left(\dfrac{2 \pi}{3}\right)} & \operatorname{cps}{\left(\dfrac{4 \pi}{3}\right)} \\ 1 & \operatorname{cps}{\left(\dfrac{4 \pi}{3}\right)} & \operatorname{cps}{\left(\dfrac{2 \pi}{3}\right)} \end{pmatrix}, & Q_{3} &= \frac{1}{\sqrt{3}} \begin{pmatrix} 1 & 1 & 1 \\ 1 & \operatorname{cps}{\left(\dfrac{4 \pi}{3}\right)} & \operatorname{cps}{\left(\dfrac{2 \pi}{3}\right)} \\ 1 & \operatorname{cps}{\left(\dfrac{2 \pi}{3}\right)} & \operatorname{cps}{\left(\dfrac{4 \pi}{3}\right)} \end{pmatrix} \end{align*}

Note that the squared Hartley transforms give the identity:

\begin{equation*} (P_{3})^{2} = (Q_{3})^{2} = I_{3} \end{equation*}

That is, each Hartley transform is its own inverse.

If \(r_{3}\) is the permutation matrix given by

\begin{equation*} r_{3} = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix} = P_{3} Q_{3} = Q_{3} P_{3} \end{equation*}

then \(P_{3}\) and \(Q_{3}\) are related via

\begin{equation*} P_{3} = Q_{3} r_{3} \end{equation*}

Four-Dimensional Hilbert Space

For \(N = 4\), the Hadamard transform is given by

\begin{equation*} H_{4} = H_{2} \otimes H_{2} = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \end{pmatrix} \end{equation*}

The Fourier transforms are given by

\begin{align*} F_{4} &= \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & -i & -1 & i \\ 1 & -1 & 1 & -1 \\ 1 & i & -1 & -i \end{pmatrix}, & G_{4} &= \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \end{pmatrix} \end{align*}

The squared Fourier transforms give a permutation matrix:

\begin{equation*} (F_{4})^{2} = (G_{4})^{2} = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \end{pmatrix} \end{equation*}

The fourth power of the Fourier transforms give the identity

\begin{equation*} (F_{4})^{4} = (G_{4})^{4} = I_{4} \end{equation*}

You also have \(F_{4} G_{4} = G_{4} F_{4} = I_{4}\).

The Hartley transforms are given by

\begin{align*} P_{4} &= \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & 1 & -1 \\ 1 & -1 & -1 & 1 \end{pmatrix}, & Q_{4} &= \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & -1 & -1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \end{pmatrix} \end{align*}

Note that the squared Hartley transforms give the identity:

\begin{equation*} (P_{4})^{2} = (Q_{4})^{2} = I_{4} \end{equation*}

That is, each Hartley transform is its own inverse.

Clearly, the Fourier transforms are in their own class, since they contain complex entries whereas the other transforms are real. The Hartley transforms are however related to the Hadamard transform. If \(p_{4}\), \(q_{4}\), and \(r_{4}\) are permutation matrices given by

\begin{align*} p_{4} &= \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} = P_{4}H_{4} = H_{4}P_{4} \\ q_{4} &= \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \end{pmatrix} = H_{4}Q_{4}, & (q_{4})^{T} &= \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{pmatrix} = Q_{4}H_{4} \\ r_{4} &= \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \end{pmatrix} = P_{4}Q_{4} = Q_{4}P_{4} \end{align*}

then \(P_{4}\), \(Q_{4}\), and \(H_{4}\) are related via

\begin{align*} P_{4} &= H_{4} p_{4}, & Q_{4} &= H_{4} q_{4}, & P_{4} &= Q_{4} r_{4} \end{align*}

Five-Dimensional Hilbert Space

Since five is not a power of two, you cannot have a Hadamard transform. The Fourier transforms satisfy the property

\begin{equation*} (F_{5})^{2} = (G_{5})^{2} = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \end{pmatrix} \end{equation*}

and also

\begin{equation*} (F_{5})^{4} = (G_{5})^{4} = I_{5} \end{equation*}

The Hartley transforms satisfy

\begin{equation*} (P_{5})^{2} = (Q_{5})^{2} = I_{5} \end{equation*}

and also

\begin{equation*} P_{5} Q_{5} = Q_{5} P_{5} = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \end{pmatrix} \end{equation*}

The explicit details are gnarly.

Six-Dimensional Hilbert Space

Here is the \(N = 6\) case. Since six is not a power of two, you cannot have a Hadamard transform. The Fourier transforms satisfy the property

\begin{equation*} (F_{6})^{2} = (G_{6})^{2} = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \end{pmatrix} \end{equation*}

and also

\begin{equation*} (F_{6})^{4} = (G_{6})^{4} = I_{6} \end{equation*}

However, since six is not prime, and the only finite group of order six is a product group, the six-dimensional Fourier transforms is equivalent to the Kronecker product of the two-dimensional and three-dimensional Fourier transforms:

\begin{align*} F_{2} \otimes F_{3} &= L_{23} F_{6} R_{23}, & L_{23} &= \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 \end{pmatrix}, & R_{23} &= \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix} \end{align*}

Note that \(L_{23}\) and \(R_{23}\) are permutation matrices. Another set of matrices works equally well:

\begin{align*} L_{23} &= \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix}, & R_{23} &= \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \end{pmatrix} \end{align*}

The tensor products \(F_{2} \otimes F_{3}\) and \(F_{3} \otimes F_{2}\) as usual, are related by permutation matrices:

\begin{equation*} F_{3} \otimes F_{2} = A \left( F_{2} \otimes F_{3} \right) B \end{equation*}

with \(A\) and \(B\) given by

\begin{align*} A &= \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix}, & B &= \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{pmatrix} \end{align*}

or also

\begin{align*} A &= \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \end{pmatrix}, & B &= \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 \end{pmatrix} \end{align*}

I personally believe it is good to know these things. The same permutation matrices also work with \(G_{6}\), \(G_{2}\), and \(G_{3}\).

The Hartley transforms satisfy

\begin{equation*} (P_{6})^{2} = (Q_{6})^{2} = I_{6} \end{equation*}

and also

\begin{equation*} P_{6} Q_{6} = Q_{6} P_{6} = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \end{pmatrix} \end{equation*}