Confused as to how to prove the basis of dft is orthonormal

Question

I have been stuck for hours trying to prove that the basis of discrete fourier transform is orthonormal can anyone point me in the direction of how to do so

Answer 1

Let $\omega = e^{-2\pi i/N}$. The Fourier matrix looks like $$ \boldsymbol{F}=\frac{1}{\sqrt{N}} \begin{bmatrix} 1 & 1 & 1 & \ldots & 1 \\ 1 & \omega & \omega^2 & \ldots & \omega^{2(N-1)} \\ 1 & \omega^2 & \\ \vdots & \vdots & & \ddots \\ 1 & \omega^{2(N-1)} & & & \omega^{(N-1)^2} \end{bmatrix}, $$ and you want to show that $\boldsymbol{F}^*\boldsymbol{F}=\boldsymbol{I}$. Note that $$ \boldsymbol{F}^*=\frac{1}{\sqrt{N}} \begin{bmatrix} 1 & 1 & 1 & \ldots & 1 \\ 1 & \omega^{-1} & \omega^{-2} & \ldots & \omega^{-2(N-1)} \\ 1 & \omega^{-2} & \\ \vdots & \vdots & & \ddots \\ 1 & \omega^{-2(N-1)} & & & \omega^{-(N-1)^2} \end{bmatrix}. $$

Simply perform the matrix multiplication, and be sure to use the formula for the geometric sum, $$ 1+r+r^2+\ldots+r^{N-1}= \begin{cases} \frac{r^N-1}{r-1} & \text{if } r\neq 1\\ N & \text{if } r=1 \end{cases}. $$

If you still need more details, just say so in a comment, and I will elaborate when I have time.