Comment by blt

I like the linear algebra interpretation, where the DFT is a basis change, and the only 'magic' is believing/proving that the Fourier basis is orthogonal. (It's an easy proof.)

I still don't understand how the FFT works though...