Proof of Inverse DFT

1.7k Views Asked by At

In "The Discrete Fourier Transform" of Ivan W. Selesnick, proof of inverse DFT written as

\begin{align} {x_0(j)} &= \frac{1}{n}\sum\limits_{k = 0}^{n - 1} {{y(k)}\omega _n^{ - kj}} \nonumber \\ &= \frac{1}{n}\sum\limits_{k = 0}^{n - 1} {\left( {\sum\limits_{l = 0}^{n - 1} {{x_0(l)}\omega _n^{kl}} } \right)\omega _n^{ - kj}} \nonumber \\ &= \frac{1}{n}\sum\limits_{l = 0}^{n - 1} {{x_0(l)}} \sum\limits_{k = 0}^{n - 1} {\omega _n^{k(j - l)}} \nonumber \\ &= \frac{1}{n}\sum\limits_{l = 0}^{n - 1} {{x_0(l)}} \;n\;\delta(\langle j - l\rangle_n) \\ &= {x_0(j)} \end{align}

with \begin{equation*} \delta(m) = \begin{cases} 1, & \text{if }m=0, \\ 0, & \text{if }m \ne 0, \end{cases} \end{equation*} \begin{equation*} \omega_n=e^\frac{2\pi{}i}{n} \end{equation*} and $\langle r \rangle_n$ is $r$ modulo $n$.

My question in the last two line of the proof. How the detail computation for $$\frac{1}{n}\sum\limits_{l = 0}^{n - 1} {{x_0(l)}} \;n\; \delta(\langle j - l\rangle_N)= {x_0(j)}?$$