The Discrete Fourier Transform

Let \(X \in \mathbb{C}^{N}\).

The length-\(N\) Discrete Fourier Transform \(\text{DFT}_{N}\{X\} \in \mathbb{C}^{N}\) is defined as:

\[\text{DFT}_{N}\{X\}[k] = \sum_{n = 0}^{N - 1} X[n] W_{N}^{n k}, \qquad k \in \{ 0, \ldots, N - 1 \},\]

with \(W_{N} = \exp\left( -j \frac{2 \pi}{N} \right)\).

The length-\(N\) inverse Discrete Fourier Transform \(\text{iDFT}_{N}\{X\} \in \mathbb{C}^{N}\) is defined as:

\[\text{iDFT}_{N}\{X\}[n] = \frac{1}{N} \sum_{k = 0}^{N - 1} X[k] W_{N}^{-n k}, \qquad n \in \{ 0, \ldots, N - 1 \}.\]

Moreover, \(\text{(i)DFT}_{N}\) is reversible:

\[(\text{iDFT}_{N} \circ \text{DFT}_{N})\{X\} = (\text{DFT}_{N} \circ \text{iDFT}_{N})\{X\} = X.\]

Particularly efficient \(\mathcal{O}(N \log N)\) algorithms exist to compute \(\text{(i)DFT}_{N}\), especially if \(N\) is highly composite.