Discrete Fourier Transform

Let be the space of all bi-infinite complex -periodic sequences (such that ).
Set the primitive root of unity of degree .
The discrete Fourier transform (DFT) of is such that:

where
(note that this does define the whole sequence uniquely).

Theorem

is an isomorphism of to itself with inverse:

Fast Fourier Transform