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.

Advertisements