\begin
Discover why over 20 million people worldwide trust Overleaf with their work.
\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}