A linear map \(F_N\colon \mathbb{C}^N\to \mathbb{C}^N\) with
\[ F_N=(e_l(-k))_{l,k\in \{0,\ldots ,N-1\}}, \]and \(e_l(k)=\e^{2\pi i kl/N}\) is called Fourier matrix.
The discrete Fourier transform of a vector \(x\in \mathbb{C}^N\) is given by \(\hat{x}=F_Nx\) or more precisely for \(k\in \{1,\ldots ,N\}\)
\[ \hat{x}(k)=\sum_{l=0}^{N-1} \e^{-2\pi i\frac{lk}{N}}x(l)=\sum_{l\in \mathbb{Z}_N}e_l(-k)x(l). \]
Remarks
- \(\frac{1}{\sqrt{N}}F_N\) is a unitary matrix .
- The inverse of \(F_N\) is given by \[ F_N^{-1}=\frac{1}{N}F_N^*. \] This implies \(x=\frac{1}{N}F_N^*\hat{x}\). We write \(\check{x}=F_N^{-1}x\).