While reading about the discrete Fourier transform, I learned about a related topic called the discrete Hartley transform.
Recall the discrete Fourier transform:
\begin{equation*}
y_{n} = \frac{1}{\sqrt{N}} \sum_{m = 0}^{N-1} x_{m} \exp{\left( -\frac{2 \pi m n i}{N} \right)}
\end{equation*}
This transforms takes a set of \(N\) complex numbers \(x_{n}\) and returns another set of \(N\) complex numbers \(y_{n}\). If the \(x_{n}\) are real, it is likely that the \(y_{n}\) will be complex.
The discrete Hartley transform can take \(N\) real numbers \(x_{n}\) and return \(N\) real numbers \(y_{n}\):
\begin{equation*}
y_{n} = \frac{1}{\sqrt{N}} \sum_{m = 0}^{N-1} x_{m} \operatorname{cas}{\left( \frac{2 \pi m n}{N} \right)}
\end{equation*}
Here, \(\operatorname{cas}\) is the cosine-and-sine function:
\begin{equation*}
\operatorname{cas}{(x)} \equiv \cos{(x)} + \sin{(x)}
\end{equation*}
Recall the identities
\begin{align*}
\cos{(x \pm y)} &= \cos{(x)} \cos{(y)} \mp \sin{(x)} \sin{(y)} \\
\sin{(x \pm y)} &= \sin{(x)} \cos{(y)} \pm \cos{(x)} \sin{(y)}
\end{align*}
Thus,
\begin{equation*}
\cos{\left(x \pm \frac{\pi}{4} \right)} = \sin{\left(\frac{\pi}{4} \mp x \right)} = \frac{1}{\sqrt{2}}\left(\cos{(x)} \mp \sin{(x)} \right)
\end{equation*}
Indeed, I would like to introduce the following notation instead:
\begin{align*}
\operatorname{cps}{(x)} &\equiv \cos{(x)} + \sin{(x)}, & \operatorname{cqs}{(x)} &\equiv \cos{(x)} - \sin{(x)}
\end{align*}
and the following transforms, given a set of \(N\) complex numbers \(x_{n}\):
\begin{align*}
p_{n} &= \frac{1}{\sqrt{N}} \sum_{m = 0}^{N - 1} x_{m} \operatorname{cps}{\left( \frac{2 \pi m n}{N} \right)}, & q_{n} &= \frac{1}{\sqrt{N}} \sum_{m = 0}^{N - 1} x_{m} \operatorname{cqs}{\left( \frac{2 \pi m n}{N} \right)}
\end{align*}
Let us check the first few cases.
First, the \(N = 1\) case. You have
\begin{equation*}
\operatorname{cps}{(0)} = \operatorname{cqs}{(0)} = 1
\end{equation*}
Thus, both transforms are trivial:
\begin{equation*}
p_{1} = q_{1} = x_{1}
\end{equation*}
This is just like the \(N = 1\) discrete Fourier transform.
Next, the \(N = 2\) case. You need
\begin{equation*}
\operatorname{cps}{(\pi)} = \operatorname{cqs}{(\pi)} = -1
\end{equation*}
Thus, both transforms are equivalent (up to a rename):
\begin{align*}
p_{0} &= q_{0} = \frac{1}{\sqrt{2}} \left( x_{0} + x_{1} \right), & p_{1} &= q_{1} = \frac{1}{\sqrt{2}} \left( x_{0} - x_{1} \right)
\end{align*}
This transformation is also equivalent to the \(N = 2\) discrete Fourier transform and the Hadamard transform.
Next, the \(N = 3\) case. You need
\begin{align*}
\operatorname{cps}{\left( \frac{2 \pi}{3} \right)} &= \operatorname{cqs}{\left( \frac{4 \pi}{3} \right)} = \operatorname{cps}{\left( \frac{8 \pi}{3} \right)} = -\frac{1}{2} + \frac{\sqrt{3}}{2}, \\
\operatorname{cqs}{\left( \frac{2 \pi}{3} \right)} &= \operatorname{cps}{\left( \frac{4 \pi}{3} \right)} = \operatorname{cqs}{\left( \frac{8 \pi}{3} \right)} = -\frac{1}{2} - \frac{\sqrt{3}}{2}
\end{align*}
Again, both transforms are equivalent (up to a rename):
\begin{align*}
p_{0} &= q_{0} = \frac{1}{\sqrt{3}} \left( x_{0} + x_{1} + x_{2} \right) \\
p_{1} &= q_{2} = \frac{1}{\sqrt{3}} \left( x_{0} + x_{1}\operatorname{cps}{\left( \frac{2 \pi}{3} \right)} + x_{2} \operatorname{cps}{\left( \frac{4 \pi}{3} \right)} \right) \\
p_{2} &= q_{1} = \frac{1}{\sqrt{3}} \left( x_{0} + x_{1} \operatorname{cps}{\left( \frac{4 \pi}{3} \right)} + x_{2} \operatorname{cps}{\left( \frac{8 \pi}{3} \right)} \right)
\end{align*}
Next, the \(N = 4\) case. You get
\begin{equation*}
\begin{pmatrix}
p_{0} \\
p_{1} \\
p_{2} \\
p_{3}
\end{pmatrix} = \begin{pmatrix}
q_{0} \\
q_{3} \\
q_{2} \\
q_{1}
\end{pmatrix} = \frac{1}{\sqrt{4}} \begin{pmatrix}
1 & 1 & 1 & 1 \\
1 & 1 & -1 & -1 \\
1 & -1 & 1 & -1 \\
1 & -1 & -1 & 1
\end{pmatrix} \begin{pmatrix}
x_{0} \\
x_{1} \\
x_{2} \\
x_{3}
\end{pmatrix}
\end{equation*}
Again, both transformations are equivalent (up to a rename). However, the \(N = 4\) discrete Hartley transform is very different from the \(N = 4\) discrete Fourier transform. Indeed, the \(N = 4\) discrete Hartley transform is equivalent to the tensor product of two \(N = 2\) discrete Hartley transforms.
