Prove that the DFT Matrix is Unitary

Question

We have that the DFT Matrix is: $$ W = \frac{1}{\sqrt{N}} \begin{bmatrix} 1&1&1&1&\cdots &1 \\ 1&\omega&\omega^2&\omega^3&\cdots&\omega^{N-1} \\ 1&\omega^2&\omega^4&\omega^6&\cdots&\omega^{2(N-1)}\\ 1&\omega^3&\omega^6&\omega^9&\cdots&\omega^{3(N-1)}\\ \vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\ 1&\omega^{N-1}&\omega^{2(N-1)}&\omega^{3(N-1)}&\cdots&\omega^{(N-1)(N-1)}\\ \end{bmatrix} $$ where $\omega = e^{\frac{2\pi i}{N}} $. We seek to prove that this matrix is unitary, i.e. $ WW^*=W^*W=I. $

Then for an element $ W_{ij} $ of $ WW^* $, $ W_{ij} = \sum\limits_{k=0}^{N-1} \omega^{jk}\omega^{-ik} $. We have that the conjugate of $e^{xi}$ is $ e^{-xi} $, so that the diagonal will be a summation of $N$ 1s, multiplied by $(\frac{1}{\sqrt{N}})^2$. Thus, the diagonal will be 1s. However, I am having difficulty conceiving a general proof for the rest of the matrix being 0s. Any help would be appreciated.

Answer 1

Note that $W_{ij} = \sum_{k=0}^{N-1} \omega^{(j-i)k}$. Let $j-i\neq0$, then $\omega^{(j-i)}\neq 1$ itself is another $N$-th root of unity and let's call it $\omega_0$. Hence, what you get is $$W_{ij} = \sum_{k=0}^{N-1} \omega_0^{k} = \frac{1-\omega_0^N}{1-\omega_0} = 0.$$

Answer 2

Another approach that seems reasonable that doesn't require geometric series.

Define $A := diag(w^0, w^1, ..., w^{N-1})$ and $(S_k)_{ij} := \delta_{jk}$, i.,e. $S$ is a matrix where row $k$ is full of $1$s.

Notice that $S_n^* S_m = \delta_{nm} I$. Only when $n = m$ is the product not zero, and it is the identity matrix.

Also notice $A^* A = diag(w^0, w^1, ..., w^{N-1}) diag(w^0, w^{-1}, ..., w^{-(N-1)}) = I$

We introduce this to rewrite $W$ taking the constant factor to the left side

\begin{equation} \sqrt{N} \cdot W = \sum_{k = 0}^{N - 1} S_k A^k \end{equation}

It is now straight forward to calculate

\begin{equation} N \cdot W^* W = (\sum_{k = 0}^{N - 1} {A^*}^k S_k^*)(\sum_{l = 0}^{N - 1} S_l A^l) = \sum_{k = 0}^{N - 1}\sum_{l = 0}^{N - 1} {A^*}^k S_k^* S_l A^l =^{(1)} \sum_{k = 0}^{N - 1}\sum_{l = 0}^{N - 1} \delta_{kl} {A^*}^k I A^l = \sum_{k = 0}^{N - 1} {A^*}^k A^k = N * I \end{equation}

and we can conclude $W^* W = I \ _\square$