DFT as an Orthogonal Basis Change

Question

In one of the homeworks that I am dealing with for Linear Systems course, I have encountered with such a statement: Consider $\mathbb{C}^N$ the vector space of N dimensional complex vectors. We can define a basis $F=\{f_1,\ldots,f_N\}$ where \begin{align} f_k = \begin{bmatrix} f_{k,1} \\ f_{k,2} \\ .\\ .\\ f_{k,N} \end{bmatrix} \end{align}

and $f_{k,l} = \frac{1}{N}e^{\frac{j2\pi(k-1)(l-1)}{N}}$. It is straightforward to show that those vectors are orthogonal, but I have no idea about how to show that those vectors are linearly independent, and their span is $\mathbb{C}^N$. Could you please give me a clue?

Answer 1

Hint 1: you can rewrite products of the exponential argument:

$$ f_{k,l}=\frac{1}{N}\left(e^{\frac{j2\pi(k-1)}{N}}\right)^{l-1}$$

and recognize a Vandermonde matrix.

Hint 2: consider the dimension of the subspace spanned, and the linear independence.