discrete fourier transform proof (show equals n*I)

Question

Let $w=e^{(-2\pi i/n)}$. Let $W$ be an $n \times n$ matrix defined by

$$ W = \begin{pmatrix} 1 & 1 & 1 & 1 & \cdots & 1 \\ 1 & w & w^2 & w^3 & \cdots & w^{n-1} \\ \vdots & & \ddots & & \cdots & \vdots \\ 1 & w^{n-1} & w^{2(n-1)} & w^{3(n-1)} & \cdots &w^{(n-1)(n-1)} \end{pmatrix} $$

or $W_{ij} = w^{(i-1)(j-1)}$.

Then let complex conjugate $W$ be the matrix of the above form with $w$ replaced by $w^{-1} = e^{(2\pi i/n)}$ everywhere.

Show that the complex conjugate of $W$ * $W$ = nI , where I is the identity matrix.

and there is a hint, which says use the geometric sum formula: $1 + r + r^2 + .... + r^{n-1} = \frac{1-r^n}{1-r}$, $r$ not equal to $1$.

Any help with this would be much appreciated, I am not really sure how to approach this problem. Thank you for your help with this in advance.

Answer 1

Hint: use the Vandermonde formula, plus the cofactors formula for the inverse of a matrix.

Answer 2

Recall the formula for entries of the product matrix, $P=AB$: $$ P_{ij} = \sum_{k=1}^n A_{ik} B_{kj} \tag{1} $$ In our case $A=\overline{W}$ and $B= W$. Plugging in $A_{ik} = \omega^{-1 (i-1)(k-1)}$ and $B_{kj} = \omega^{(k-1)(j-1)}$, we get $$ P_{ij} = \sum_{k=1}^n \omega^{-1 (i-1)(k-1)}\omega^{(k-1)(j-1)} =\sum_{k=1}^n \omega^{(k-1)(j-i)} \tag{2} $$ If $i=j$, then the sum in (2) is simply $\sum_{k=1}^n 1 = n$. So, all diagonal entries of the product are equal to $n$.

If $i\ne j$, then the sum in (2) can be written as $\sum_{k=1}^n r^{k-1}$ where $r=\omega^{j-i}$. This is a geometric sum with $r\ne 1$, because $|j-i|\le n-1$. Note that $r^n = \omega^{n(j-i)} =1$ because $\omega^n =\exp(2\pi i) = 1$. Conclusion: $$ P_{ij} = \frac{1-r^n}{1-r} = \frac{1-1}{1-r}=0 $$ So, all off-diagonal entries of the product are $0$.