Proving that $\frac{1}{n}DFT(DFT(x_N))$ is $\{x_0, x_{N - 1}, \dots, x_1 \}$

123 Views Asked by At

I'm trying to prove that $\frac{1}{n}DFT(DFT(x_N))$ is $\{x_0, x_{N - 1}, \dots, x_1\}$. So, I write ($X_k$ is nth coefficient of $DFT(x_N)$, $r_t$ is tth coefficient of $DFT(DFT(x_N))$):

$$ X_k = \sum \limits_{n = 0}^{N - 1} x_n e^{-\frac{2 \pi i k n}{N}} \\ r_t = \sum \limits_{p = 0}^{N - 1} X_p e^{-\frac{2 \pi i t p}{N}} \\ r_t = \sum \limits_{p = 0}^{N - 1} \sum \limits_{n = 0}^{N - 1} x_n e^{-\frac{2 \pi i (tp + pn)}{N}} \\ r_t = \sum \limits_{n = 0}^{N - 1} x_n \left(\sum \limits_{p = 0}^{N - 1} e^{-\frac{2 \pi i p (t + n)}{N}}\right) \\ r_t = \sum \limits_{n = 0}^{N - 1} x_n \left(\sum \limits_{p = 0}^{N - 1} \left(e^{-\frac{2 \pi i (t + n)}{N}}\right)^p\right) \\ r_t = \sum \limits_{n = 0}^{N - 1} x_n \frac{1 - \left(e^{-\frac{2 \pi i (t + n)}{N}}\right)^N}{1 - e^{-\frac{2 \pi i (t + n)}{N}}} = 0 $$

Last equality follows from the fact that $\omega = e^{-\frac{2 \pi i (t + n)}{N}}$ is one of the Nth roots of 1, so $\omega^N$ is 1.

I can't seem to find any mistakes here, but the result is obviously wrong.

1

There are 1 best solutions below

2
On BEST ANSWER

You almost got it. In the final line, this sum of a geometric series is correct except in the case where the denominator is zero; here you are simply summing $\sum_{p=0}^{N-1}(1)=N$. Another point is that the inverse discrete Fourier transform requires the inverse root of unity, but I realise now that this might not be a mistake; it is unclear what sequence $x_N$ is meant to represent, but it looks like you are infact trying to show the output is reversed. In this case, you will be left with the only term that doesn't sum to $0$ being $r_t=Nx_{-t}$ (where the index is modulo $N$), and I'll leave the details for you to work on.

Basically, the moral , as ever, is never divide by $0$