I have had to compute the rank of the DFT matrix and even though I did guess that it is full rank, I still had to prove it just to make sure. Note that, as we are dealing with a complex matrix, to make sure that the DFT matrix is full rank, we should show that none of the rows (or columns) is a complex linear combination of the other rows (or columns). Here is a simple proof (if it is correct!):
The DFT matrix (say ) is defined as:
The utility of the DFT matrix is of course to compute the discrete fourier transform. If is a dimensional vector of function values then clearly its DFT is just . Now, if we replace all the elements in the DFT matrix by their inverses, we get a new matrix which looks like this:
It can be clearly seen that is just the matrix associated with the inverse transformation, i.e. . Hence,
Now, if the rank of is less than then there exist a vector such that (note here that is symmetric so a linear combination of its columns is the same as a linear combination of its rows. Anyways this argument is not needed to write the above). This of course means that from which is a mega contradiction.