Circular Convolution and Discrete Fourier Transform

              
\documentclass{article}

\usepackage{fullpage}
\usepackage{amsmath,amssymb}

\usepackage{ebgaramond}

% complex conjugate
\newcommand{\conj}[1]{\ensuremath{\overline{#1}}}

% modulo n operator
\newcommand{\braket}[1]{\ensuremath{\langle{#1}\rangle}}

% Blackboard bold of C
\newcommand{\Cbb}{\ensuremath{\mathbb{C}}}

\begin{document}
\title{Circular Convolution and Discrete Fourier Transform}
\author{Frank the Giant Bunny}
\maketitle
\thispagestyle{empty}

Consider three vectors $a,b,c\in\Cbb^n$ where $c$
is a \emph{circular convolution} of $a$ and $b$:
\begin{equation*}
  c_i = \sum_{k=0}^{n-1}a_kb_{\braket{i-k}_n}
  \quad
  \text{for $i\in\{0,1,\cdots,n-1\}$}
\end{equation*}
where $\braket{\ell}_n$ is a modulo operator.
Define another vectors $\alpha$, $\beta$, and $\gamma$
as the \emph{Discrete Fourier Transform} (DFT)
of $a$, $b$, and $c$
\begin{equation*}
  \alpha_j = \frac{1}{\sqrt n}\sum_{i=0}^{n-1}a_i\conj{\omega}^{ij},
  \quad
  \beta_j = \frac{1}{\sqrt n}\sum_{i=0}^{n-1}b_i\conj{\omega}^{ij},
  \quad\text{and}\quad
  \gamma_j = \frac{1}{\sqrt n}\sum_{i=0}^{n-1}c_i\conj{\omega}^{ij},
\end{equation*}
where $\omega=e^{\iota 2\pi/n}$ is the
\emph{primitive $n^{\mathrm{th}}$ root of unity} and
$\conj\omega$ is its complex conjugate. 
Then the \emph{circular convolution property} states that $\gamma$
is obtained by the entry-wise product of $\alpha$ and $\beta$.
This is easily seen by rearranging terms in summations.

\begin{alignat*}{2}
  \gamma_j
  &=
  \frac{1}{\sqrt n}\sum_{i=0}^{n-1}c_i{\conj\omega}^{ij}
  &\quad\text{by definition of DFT}
  \\
  &=
  \frac{1}{\sqrt n}\sum_{i=0}^{n-1}
  \left(\sum_{k=0}^{n-1}a_k b_{\braket{i-k}_n}\right)
  {\conj\omega}^{ij}
  &\quad\text{by definition of $c_i$}
  \\
  &=
  \frac{1}{\sqrt n}\sum_{k=0}^{n-1}a_k 
  \left(\sum_{i=0}^{n-1}b_{\braket{i-k}_n}\right)
  {\conj\omega}^{ij}
  &\quad\text{by rearranging terms}
  \\
  &=
  \frac{1}{\sqrt n}\sum_{k=0}^{n-1}a_k{\conj\omega}^{kj}
  \left(
    \sum_{i=0}^{n-1}b_{\braket{i-k}_n}{\conj\omega}^{(i-k)j}
  \right)
  &\quad\text{by decomposing ${\conj\omega}^{ij}$}
  \\
  &=
  \alpha_j
  \left(
    \sum_{i=0}^{n-1}b_{\braket{i-k}_n}{\conj\omega}^{(i-k)j}
  \right)
  &\quad\text{by definition of DFT}
  \\
  &=
  \alpha_j
  \left(
    \sum_{i=0}^{n-1}b_{\braket{i-k}_n}{\conj\omega}^{\braket{i-k}_n j}
  \right)
  &\quad\text{${\conj\omega}^n=1$}
  \\
  &=
  \sqrt{n}\alpha_j
  \left(
    \frac{1}{\sqrt n}\sum_{i=0}^{n-1}b_{\braket{i-k}_n}
    {\conj\omega}^{\braket{i-k}_n j}
  \right)
  &\quad\text{by decomposing $1$}
  \\
  &=
  \sqrt{n}\alpha_j\beta_j
  &\quad\text{by definition of DFT}
\end{alignat*}
\end{document}