6
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ 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 . $\endgroup$ – William Muenzinger Mar 22 '16 at 1:59
  • 1
    $\begingroup$ @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}$ $\endgroup$ – reuns Mar 22 '16 at 2:01
0
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.