Why IDFT really is the Inverse DFT?

Question

There was a useful website engineeringproductivitytools.com that contained information regarding transformations. StackOverflow even points to this site in the dft tag. But for some reason the website is down. Fortunately, we can use Web Archive to see the website (kind of). But as you can see, it does not show the formulas in the "IDFT really is the Inverse DFT" page.

Can someone please explain why and how to show that "IDFT really is the Inverse DFT"? What do you think they tried to show there?

Answer 1

Let $\omega = e^{\frac{2\pi i}{n}}$ be the first $n$th root of unity. I'm guessing they showed that the functions $e_k(j) := \frac{1}{\sqrt{n}}\omega^{jk}$, $k = 0, 1, \dots, n - 1$ are an orthonormal set of vectors in $l^2(\mathbb{Z}_n)$, the space of functions from $\mathbb{Z}_n = \{0, 1, \dots, n - 1\}$ to $\mathbb{C}$ with inner product $(f, g) = \sum_{j \in \mathbb{Z}_n}f(j)\overline{g(j)}$. By elementary linear algebra, this means it forms an orthonormal basis of $l^2(\mathbb{Z}_n)$, and for every $f \in l^2(\mathbb{Z}_n)$, $$f = \sum_{k \in \mathbb{Z}_n}(f, e_k)e_k.$$ The orthonormality can be proved either by direct computations of $(e_j, e_k)$, or by noting that the translation map $T : l^2(\mathbb{Z}_n) \to l^2(\mathbb{Z}_n)$ defined by $Tf(j) = f(j + 1)$ is unitary and that $e_k$s are eigenvectors of $T$.

The DFT $\mathcal{F} : l^2(\mathbb{Z}_n) \to l^2(\mathbb{Z}_n)$ is defined by $$\mathcal{F}f(k) = (f, e_k).$$ The DFT takes a vector $f \in l^2(\mathbb{Z}_n)$ and gives you the components $\hat{f} := \mathcal{F}f$ of $f$ in the basis $\{e_0, \dots, e_{n - 1}\}$. The IDFT $\mathcal{F}^{-1}$ takes a vector $x$ and gives you the vector $f$ whose coordinates are $x$ in this basis. Explicitly, $$\mathcal{F}^{-1}x = \sum_{k \in \mathbb{Z}_n}x_ke_k.$$ So, somewhat trivially, the IDFT and DFT are inverses of each other. This coordinate transformation perspective also explains why the DFT preserves the inner product, or in other words, $\mathcal{F}^{-1} = \mathcal{F}^*$.

Answer 2

It says 'IDFT is really the inverse DFT'. They wanted to show that you can fully recover a transformed signal using the IDFT, thus showing that the IDFT is really the inverse DFT. Consider the Hilbert space $\mathcal{H}$ of square summable functions $u:\{0,2,...,n-1\}\to \mathbb{C}$ with the inner product $\langle u, v\rangle=\sum_{k<n}u_kv_k^*$ and norm $\|u\|_2=\sqrt{\langle u, u\rangle}$. Then it can be shown that $\varepsilon_{k,\xi}=\{e^{2\pi i k\xi/n}/\sqrt{n},0\leq k,\xi<n\}$ forms a complete orthonormal basis of $\mathcal{H}$, in the sense that for all $u \in \mathcal{H}$ $$u_k=\frac{1}{\sqrt{n}}\sum_{\xi <n}\phi_\xi e^{2\pi ik\xi/n},\,\ \phi_\xi=\langle u_.,\varepsilon_{.,\xi}\rangle=\frac{1}{\sqrt{n}}\sum_{\xi <n}u_k e^{-2\pi ik\xi/n}$$ On the site, they show that this makes sense in practice because if we substitute $\phi_\xi$ in the series for $u_k$ we get $$\begin{aligned} u_k&=\frac{1}{\sqrt{n}}\sum_{\xi <n}\phi_\xi e^{2\pi ik\xi/n}=\\ &=\frac{1}{n}\sum_{\xi <n}\sum_{j <n}u_je^{2\pi i\xi(k-j)/n}=\\ &=\frac{1}{n}\sum_{j <n}u_j\sum_{\xi <n}e^{2\pi i\xi(k-j)/n}=\\ &=\sum_{j <n}u_j\delta_{k,j}=u_k \end{aligned}$$ using the Kronecker delta.