Q:

Simple proof of Inverse Discrete Fourier Transformation (IDFT)?

Discrete Fourier Transformation (DFT) is defined by:
$X_k = \sum_{n=0}^{N-1} x_n \exp(\frac{-2 \pi i k n}{N}) ; 0\leq k \leq N-1$
And Inverse Discrete Fourier Transformation (IDFT) is defined by:
$x_n = \frac{1}{N} \sum_{k=0}^{N-1} X_k \exp(\frac{2 \pi i k n}{N})$
How can I proof IDFT using DFT?

A:

Observe
\begin{align}
\frac{1}{N}\sum^{N-1}_{k=0} X_k \exp\left(\frac{2\pi i kn}{N} \right) =&\ \frac{1}{N}\sum^{N-1}_{k=0} \left(\sum^{N-1}_{m=0}x_m\exp\left(-\frac{2\pi i km}{N} \right)\right) \exp\left(\frac{2\pi i kn}{N} \right) \\
=&\ \frac{1}{N}\sum^{N-1}_{m=0}\sum^{N-1}_{k=0} x_m \exp\left(\frac{2\pi i k(n-m)}{N} \right)\\
=&\ \sum^{N-1}_{m=0}x_m\left(\frac{1}{N}\sum^{N-1}_{k=0}  \exp\left(\frac{2\pi i k(n-m)}{N}\right)\right)\\
=& \sum^{N-1}_{m=0} x_m \delta_{n, m} = x_n.
\end{align}
Note that I have used the fact that
\begin{align}
\frac{1}{N}\sum^{N-1}_{k=0}  \exp\left(\frac{2\pi i k(n-m)}{N}\right)= \frac{1}{N}\frac{1-\exp(2\pi i(n-m))}{1-\exp(\frac{2\pi i(n-m)}{N})} =0
\end{align}
if $n\ne m$. However, if $n=m$ then
\begin{align}
\frac{1}{N}\sum^{N-1}_{k=0}  \exp\left(\frac{2\pi i k(n-m)}{N}\right)=\frac{1}{N}\sum^{N-1}_{k=0}  1 = \frac{N}{N} =1.
\end{align}
Another way is to consider the DFT matrix. Let $e(x) = \exp(\frac{2\pi i x}{N})$ then
\begin{align}
F = \frac{1}{\sqrt{N}}
\begin{bmatrix}
e(1\cdot 1) & e(1\cdot 2) & \cdots & e(1\cdot (N-1))\\
 e(2\cdot 1) & e(2\cdot 2) & \cdots & e(2\cdot (N-1))\\
\vdots & \vdots & \ddots & \vdots\\
\vdots & \vdots & \ddots & \vdots\\
e((N-1)\cdot 1) & \cdots & \cdots & e((N-1)\cdot (N-1))
\end{bmatrix}.
\end{align}
Let us check that the columns of $F$ are orthonormal. Observe
\begin{align}
(\text{column m})^H(\text{column n}) = \frac{1}{N}\sum_{\ell=0}^{N-1}e(-\ell \cdot m)e(\ell \cdot n) = \frac{1}{N}\sum_{\ell=0}^{N-1}e(\ell \cdot (n-m)) = \delta_{n, m}
\end{align}
which means the columns are orthogonal. It's also clear that each column has norm 1. So $F$ is a unitary matrix, which means
\begin{align}
F^{-1} = F^H = 
\frac{1}{\sqrt{N}}
\begin{bmatrix}
e(-1\cdot 1) & e(-2\cdot 1) & \cdots & e(-(N-1)\cdot 1)\\
 e(-1\cdot 2) & e(-2\cdot 2) & \cdots & e(-(N-1)\cdot 2)\\
\vdots & \vdots & \ddots & \vdots\\
\vdots & \vdots & \ddots & \vdots\\
e(-1\cdot(N-1)) & \cdots & \cdots & e(-(N-1)\cdot (N-1))
\end{bmatrix}.
\end{align}

