Discret Hartley Transform is a unitary transform although its proof is hard to find in the Web. This short note explains that the Discrete Hartley Transform is an involution, which implies that this transform is unitary indeed.
\begin
Discover why 18 million people worldwide trust Overleaf with their work.
\documentclass[12pt]{article}
\usepackage{fullpage}
\usepackage{amsmath,amssymb,amsfonts,amsthm}
\usepackage{ebgaramond}
\usepackage[cmintegrals,cmbraces]{newtxmath}
\usepackage{ebgaramond-maths}
\usepackage{braket}
\DeclareMathOperator{\cas}{cas}
\newcommand{\trans}[1]{\ensuremath{{#1}^\intercal}}
\usepackage{color}
\setlength\parskip{2mm}
\begin{document}
\title{Involutory Property of the Discrete Hartley Transform}
\author{Frank the Giant Bunny}
\maketitle
Given a column vector $x\in\mathbb{R}^n$, its \emph{Discrete Hartley Transform}
(DHT) is defined as another vector $y\in\mathbb{R}^n$ such that
\begin{equation}
y_j = \frac{1}{\sqrt n}\sum_{i=0}^{n-1}x_i
\cas\left(\tfrac{2\pi}{n}ij\right)
\quad\text{for}\quad j\in\set{0,\cdots,n-1}
\label{eq:DHT}
\end{equation}
where the $\cas$ function is defined as $\cas\theta = \cos\theta + \sin\theta$.
Interestingly, the DHT is an \emph{involution}; that is, the DHT is the same as the
inverse DHT.
\begin{equation}
x_i = \frac{1}{\sqrt n}\sum_{j=0}^{n-1}y_j
\cas\left(\tfrac{2\pi}{n}ij\right)
\quad\text{for}\quad i\in\set{0,\cdots,n-1}
\label{eq:IDHT}
\end{equation}
This paper proves the DHT is indeed an involution.
\noindent\textbf{\textsf{Target Equality}}\quad
To simplify \eqref{eq:DHT} and \eqref{eq:IDHT},
define an $n\times n$ symmetric matrix $H$ whose $(i,j)$-entry is
$\frac{1}{\sqrt n}\cas\left(\frac{2\pi}{n}ij\right)$.
Then the DHT and the inverse DHT are
\begin{equation*}
y = Hx
\quad\text{and}\quad
x = Hy
\end{equation*}
where $x=\trans{
\begin{bmatrix}x_0,\cdots,x_{n-1}\end{bmatrix}
}$ and
$y=\trans{
\begin{bmatrix}y_0,\cdots,y_{n-1}\end{bmatrix}
}$.
Then proving the involutory property of the DHT reduces to showing that
$H^2 = I$ where $I$ is an $n\times n$ identity matrix.
This further reduces to showing that the rows in $H$ are orthogonal;
that is,
\begin{equation*}
\braket{h_i, h_{i'}} =
\begin{cases}
1, &\text{if $i=i'$;} \\
0, &\text{otherwise;}
\end{cases}
\end{equation*}
where $h_i=\tfrac{1}{\sqrt n}\trans{
\begin{bmatrix}
\cas\left(\tfrac{2\pi}{n}i0\right),
\cdots,
\cas\left(\tfrac{2\pi}{n}i(n-1)\right)
\end{bmatrix}}$
is the $i^{\mathrm{th}}$ row in $H$.
It may be written in terms of $\cas$ functions as
\begin{equation}
\sum_{j=0}^{n-1}
\cas\left(\tfrac{2\pi}{n}ij\right) \cas\left(\tfrac{2\pi}{n}i'j\right)
=
\begin{cases}
n, &\text{if $i=i'$;} \\
0, &\text{otherwise;}
\end{cases}
\label{eq:target}
\end{equation}
which is the target equality for the involutory property.
\noindent\textbf{\textsf{CAS Identity}}\quad
The proof of \eqref{eq:target} begins with an identity about $\cas$ functions.
\begin{equation}
\cas\alpha\cas\beta = \sin(\alpha+\beta) + \cos(\alpha-\beta)
\label{eq:tool}
\end{equation}
\begin{proof}[Proof of \eqref{eq:tool}]
A $\cas(\cdot)$ can be simplified to $\cos(\cdot)$ as follows:
\begin{equation}
\cas\theta
=
\cos\theta + \sin\theta
=
\sqrt{2}\left(
\frac{1}{\sqrt 2}\cos\theta + \frac{1}{\sqrt 2}\sin\theta
\right)
=
\sqrt{2}\cos\left(\theta - \frac{\pi}{4}\right)
\tag{$\ast$}
\label{eq:cas}
\end{equation}
Then
\begin{alignat*}{2}
\cas\alpha\cas\beta
&=
\sqrt{2}\cos\left(\alpha - \frac{\pi}{4}\right)
\cdot
\sqrt{2}\cos\left(\beta - \frac{\pi}{4}\right)
&
\quad\quad\text{by \eqref{eq:cas}}
\\
&=
\cos\left(\alpha + \beta - {\frac \pi 2}\right)
+
\cos(\alpha - \beta)
&
\quad\quad
2\cos\theta\cos\phi
=
\cos(\theta+\phi) + \cos(\theta-\phi)
\\
&=
\sin(\alpha + \beta) + \cos(\alpha - \beta)
&
\quad\quad
\cos\left(\theta-\frac{\pi}{2}\right) = \sin\theta
\end{alignat*}
which completes the proof.
\end{proof}
\noindent\textbf{\textsf{Target Simplified}}\quad
The target equality \eqref{eq:target} is decomposed into two summations by
\eqref{eq:tool}.
\begin{equation*}
\sum_{j=0}^{n-1}
\cas\left(\tfrac{2\pi}{n}ij\right) \cas\left(\tfrac{2\pi}{n}i'j\right)
=
\sum_{j=0}^{n-1} \sin\left(\tfrac{2\pi}{n}(i+i')j\right)
+
\sum_{j=0}^{n-1} \cos\left(\tfrac{2\pi}{n}(i-i')j\right)
\end{equation*}
The above will be interpreted as the real and imaginary parts in
geometric progressions of complex numbers:
\begin{equation}
\sum_{j=0}^{n-1}
\cas\left(\tfrac{2\pi}{n}ij\right) \cas\left(\tfrac{2\pi}{n}i'j\right)
=
\Im\left\{\sum_{j=0}^{n-1} \omega^{(i+i')j} \right\}
+
\Re\left\{\sum_{j=0}^{n-1} \omega^{(i-i')j} \right\}
\label{eq:geom}
\end{equation}
where $\omega$ is the \emph{primitive $n^{\mathrm{th}}$ root of unity}
$\omega=\exp(\iota 2\pi/n) = \cos(2\pi/n) + \iota\sin(2\pi/n)$.
The identity \eqref{eq:geom} is easily proved by the De Moivre's identity.
\noindent\textbf{\textsf{Summation Lemma}}\quad
The last puzzle to the involutory property proof is the summation
of a geometric series:
\begin{equation*}
\text{For an integer $k$,}\quad
\sum_{j=0}^{n-1}(\omega^k)^j =
\begin{cases}
n, & \text{if $k$ is a multiple of $n$;} \\
0, & \text{otherwise.}
\end{cases}
\end{equation*}
This lemma ensures that the imaginary part of $\sum_{j=0}^{n-1}(\omega^k)^j$ is
zero regardless of the integer value $k$. On the other hand,
the real part is $n$ if $k$ is a multiple of $n$ and zero otherwise.
Plugging in theses values to the RHS of \eqref{eq:geom} yields the desired
identity \eqref{eq:target}, which completes the involutory property proof.
\end{document}