# Prove that the DFT Matrix is Unitary

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.

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.$$

• Thank you very much. Should someone in the future stumble upon this and remain confused, i'd direct them to this link to explain why the fraction and sum are equivalent: en.wikipedia.org/wiki/Geometric_series#Formula . – William Muenzinger Mar 22 '16 at 1:59
• @WilliamMuenzinger : $(1-z)(1+z+z^2+\ldots+z^{n-1}) = (1+z+z^2+\ldots+z^{n-1}) - (z+z^2+\ldots+z^{n}) = 1 - z^{n}$ – reuns Mar 22 '16 at 2:01

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

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

It is now straight forward to calculate

$$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$$

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