How can I test an implementation of DFT for correctness? A friend of mine implemented a DFT algorithm for a project we're working on, and we're not quite sure how to test whether or not its correct. We're only in the eleventh grade, so we have very little experience in Fourier Analysis.

I remembered reading somewhere that the Fourier transform of the square wave function was the sinc function, so we thought that if the output of the program was the sinc function then the implementation was correct, but we quickly realized it wouldn't be that simple. Below is a picture of what the program outputs (blue is DFT scaled logarithmically to be in decibels):

!

Below is essentially the same as above only with lines instead of a solid fill:

!

Hmm, well that doesn't look anything like the sinc function. After looking at the code, I realized it was actually a plot of $\sqrt{r^2 + i^2}$ where $r$ and $i$ are the real and imaginary parts of the DFT respectively. So now I'm out of ideas as to how to test the validity of this program.

Does the output look correct? What other tests can we perform to verify the implementation?
A very quick and easy test that catches all relevant structural mistakes follows from a fundamental property of the Fourier transform (and also its inverse): It is a square root of the sequence order reversal operator. That means applying your implementation twice on a data vector will reverse the sequence order and applying it four times will give your original data back.

Note that this requires the so called unitary scaling convention, where the Fourier transform and its inverse share the same scaling factor. Otherwise you will get back a scaled version of the original signal.