Proof of orthonormality of basis of DFT

3.9k Views Asked by At

The DFT's main foundation is the discrete orthogonal property of it's basis vector:

$$\sum\limits_{n=0}^{N-1} e^{i(\frac{2\pi}{N})nk} e^{-i(\frac{2\pi}{N})nl} = \{\begin{matrix} N, k \neq l \\0, k =l\end{matrix}$$

The condition of the different frequencies is easy enough to understand as then the product of the two exponential is equal to $e^0$.

The condition with the same frequencies of course makes sense graphically as the product effectively is another sinousioud in both the real and imaginary domain. This means that it's average/integral over one period is 0.

I however could not come up with/find a algebraic argument for this. Is there a way to demonstrate that algebraicly?

1

There are 1 best solutions below

0
On BEST ANSWER

If you write $\omega = e^{2\pi i/N}$, the sum is $$\sum_{n=0}^{N-1} \omega^{(k-l)n}. $$ If $k=l$, every term is $1$. If $k \neq l$, it's a geometric series with common ratio $\omega^{k-l}$, so the sum is given by the geometric series formula as $$ \frac{1-\omega^{N(k-l)}}{1-\omega^{k-l}}. $$ But $\omega^N=1$, so the numerator vanishes but the denominator doesn't, and hence the sum vanishes.