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 ${A}$) is defined as:

$\displaystyle \left( \begin{array}{cccccc} 1 & 1 & 1 & \cdots & 1 & 1\\ 1 & e^{\frac{-2\pi i}{N}} & e^{\frac{-2\pi i (2)}{N}} & \cdots & e^{\frac{-2\pi i (N-2)}{N}} & e^{\frac{-2\pi i (N-1)}{N}} \\ 1 & e^{\frac{-2\pi i(2)}{N}} & e^{\frac{-2\pi i (4)}{N}} & \cdots & e^{\frac{-2\pi i (N-2)(2)}{N}} & e^{\frac{-2\pi i (N-1)(2)}{N}} \\ \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\ 1 & e^{\frac{-2\pi i(N-1)}{N}} & e^{\frac{-2\pi i (N-1)(2)}{N}} & \cdots & e^{\frac{-2\pi i (N-2)(N-1)}{N}} & e^{\frac{-2\pi i (N-1)(N-1)}{N}} \end{array} \right)$

The utility of the DFT matrix is of course to compute the discrete fourier transform. If ${f}$ is a ${N}$ dimensional vector of function values then clearly its DFT is just ${\hat{f} = Af}$. Now, if we replace all the elements in the DFT matrix by their inverses, we get a new matrix ${\hat{A}}$ which looks like this:

$\displaystyle \left( \begin{array}{cccccc} 1 & 1 & 1 & \cdots & 1 & 1\\ 1 & e^{\frac{2\pi i}{N}} & e^{\frac{2\pi i (2)}{N}} & \cdots & e^{\frac{2\pi i (N-2)}{N}} & e^{\frac{2\pi i (N-1)}{N}} \\ 1 & e^{\frac{2\pi i(2)}{N}} & e^{\frac{2\pi i (4)}{N}} & \cdots & e^{\frac{2\pi i (N-2)(2)}{N}} & e^{\frac{2\pi i (N-1)(2)}{N}} \\ \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\ 1 & e^{\frac{2\pi i(N-1)}{N}} & e^{\frac{2\pi i (N-1)(2)}{N}} & \cdots & e^{\frac{2\pi i (N-2)(N-1)}{N}} & e^{\frac{2\pi i (N-1)(N-1)}{N}} \end{array} \right)$

It can be clearly seen that ${\frac{1}{N}\hat{A}}$ is just the matrix associated with the inverse transformation, i.e. ${f=\frac{1}{N}\hat{A}\hat{f}}$. Hence,

$\displaystyle \begin{array}{rcl} f = \frac{1}{N}\hat{A}Af \end{array}$

Now, if the rank of ${A}$ is less than ${N}$ then there exist a vector ${f^\prime \neq 0}$ such that ${Af^\prime = 0}$ (note here that ${A}$ 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 ${f^\prime=0}$ from ${f^\prime = \frac{1}{N}\hat{A}Af^\prime}$ which is a mega contradiction.