# Discrete Fourier Transform

### Big Idea
The *Discrete Fourier Transform (DFT)* is a mathematical tool that decomposes a discrete signal (a vector $\mathbf{x} \in \mathbb{C}^N$) into a sum of complex exponential functions (sines and cosines). Mathematically, the DFT calculates the coordinates of the signal vector $\mathbf{x}$ in the orthogonal *Fourier basis* $\{\mathbf{f}_0, \dots, \mathbf{f}_{N-1}\}$. The DFT is a projection operation onto this basis.

## Roots of Unity
The Fourier basis is constructed using the complex *$N$th roots of unity*.

:::info
**Definition** An *$N$th root of unity* is a complex number $\omega$ such that $\omega^N = 1$.
:::

:::danger
**Proposition** Let $\omega_N = e^{2 \pi i / N}$. This complex number is called the *primitive $N$th root of unity*.
* The set of all $N$th roots of unity is $\{1, \omega_N, \omega_N^2, \dots, \omega_N^{N-1}\}$.
* (Conjugate/Inverse) $\overline{\omega}_N = \omega_N^{-1} = \omega_N^{N-1}$.
* (Euler's Formula) $\omega_N^k = \cos\left( \frac{2 \pi k}{N} \right) + i \sin \left( \frac{2 \pi k}{N} \right)$.
* (Summation Property) For any integer $k$ such that $0 < k < N$: $$\sum_{n=0}^{N-1} \omega_N^{nk} = 0$$
:::

:::warning
**Examples** Find all $N$-th roots of unity.
* $N = 2 \Rightarrow \omega_2 = -1 \Rightarrow \{1, -1\}$
* $N = 3 \Rightarrow \omega_3 = -\frac12 + \frac{\sqrt{3}}{2}i \Rightarrow \{1, -\frac12 + \frac{\sqrt{3}}{2}i, -\frac12 - \frac{\sqrt{3}}{2}i\}$
* $N = 4 \Rightarrow \omega_4 = i \Rightarrow \{1, i, -1, -i\}$
:::

## Fourier Basis
The Fourier basis vectors are columns formed by the powers of the roots of unity.

:::info
**Definition** The *Fourier basis* of $\mathbb{C}^N$ is the set of vectors $\{\mathbf{f}_0, \dots, \mathbf{f}_{N-1}\}$, where the $k$th vector is defined by:$$\mathbf{f}_k = \begin{bmatrix} 1 \\ \omega_N^k \\ \omega_N^{2k} \\ \vdots \\ \omega_N^{(N-1)k} \end{bmatrix}, \quad \text{where } \omega_N = e^{2 \pi i / N}$$
:::

:::warning
**Example (Constructing the Fourier Basis)**
The Fourier basis $\mathbf{f}_k$ is constructed using the powers of the primitive root of unity, $\omega_N = e^{2 \pi i / N}$, where the $j$th entry of $\mathbf{f}_k$ is $\omega_N^{jk}$.

* **Case $N=2$:** $\omega_2 = -1$.$$\mathbf{f}_0 = \begin{bmatrix} 1 \\ 1 \end{bmatrix}, \quad \mathbf{f}_1 = \begin{bmatrix} 1 \\ (-1)^1 \end{bmatrix} = \begin{bmatrix} 1 \\ -1 \end{bmatrix}$$
* **Case $N=3$:** $\omega_3 = e^{2 \pi i/3} = \frac{-1 + \sqrt{3}i}{2}$. The roots are $\{1, \omega_3, \omega_3^2\}$, where $\omega_3^2 = \overline{\omega}_3 = \frac{-1 - \sqrt{3}i}{2}$.$$\mathbf{f}_0 = \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}, \quad \mathbf{f}_1 = \begin{bmatrix} 1 \\ \omega_3 \\ \omega_3^2 \end{bmatrix}, \quad \mathbf{f}_2 = \begin{bmatrix} 1 \\ \omega_3^2 \\ \omega_3^4 \end{bmatrix} = \begin{bmatrix} 1 \\ \omega_3^2 \\ \omega_3 \end{bmatrix}$$ Written with explicit complex values:$$\mathbf{f}_1 = \begin{bmatrix} 1 \\ (-1 + \sqrt{3}i)/2 \\ (-1 - \sqrt{3}i)/2 \end{bmatrix}, \quad \mathbf{f}_2 = \begin{bmatrix} 1 \\ (-1 - \sqrt{3}i)/2 \\ (-1 + \sqrt{3}i)/2 \end{bmatrix}$$
* **Case $N=4$:** $\omega_4 = i$. The roots are $\{1, i, i^2, i^3\} = \{1, i, -1, -i\}$.$$\mathbf{f}_0 = \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix}, \quad \mathbf{f}_1 = \begin{bmatrix} 1 \\ i \\ -1 \\ -i \end{bmatrix}, \quad \mathbf{f}_2 = \begin{bmatrix} 1 \\ i^2 \\ (-1)^2 \\ (-i)^2 \end{bmatrix} = \begin{bmatrix} 1 \\ -1 \\ 1 \\ -1 \end{bmatrix}, \quad \mathbf{f}_3 = \begin{bmatrix} 1 \\ i^3 \\ -1^3 \\ -i^3 \end{bmatrix} = \begin{bmatrix} 1 \\ -i \\ -1 \\ i \end{bmatrix}$$
:::

:::danger
**Lemma**
$$\overline{\mathbf{f}}_k = \mathbf{f}_{N-k}$$
:::

### Orthogonality
:::danger
**Proposition** The Fourier basis satisfies the following key property for its standard inner product: $$\langle \mathbf{f}_k , \mathbf{f}_{\ell} \rangle = \left\{ \begin{array}{cl} N & \text{if } k = \ell \\ 0 & \text{otherwise} \end{array} \right.$$

This confirms that the Fourier basis is an orthogonal basis of $\mathbb{C}^N$.
:::

## Discrete Fourier Transform (DFT)
The DFT maps a signal vector $\mathbf{x}$ to a vector of its Fourier coefficients.

:::info
**Definition** The *discrete Fourier transform* of a signal $\mathbf{x} \in \mathbb{C}^N$ is defined as: $$\mathrm{DFT}(\mathbf{x}) = F_N \mathbf{x}$$where $F_N$ is the *Fourier matrix*. The rows of $F_N$ are the conjugate transposes ($\overline{\mathbf{f}}^T_k$) of the Fourier basis vectors: $$F_N = \begin{bmatrix}
\overline{\mathbf{f}}^T_0 \\ \overline{\mathbf{f}}^T_1 \\ \vdots \\ \overline{\mathbf{f}}^T_{N-1}
\end{bmatrix}
= \begin{bmatrix}
1 & 1 & 1 & \cdots & 1 \\
1 & \overline{\omega}_N & \overline{\omega}_N^2 & \cdots & \overline{\omega}_N^{N-1} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
1 & \overline{\omega}_N^{N-1} & \overline{\omega}_N^{2(N-1)} & \cdots & \overline{\omega}_N^{(N-1)^2}
\end{bmatrix}$$

The $k$th component of the DFT, $\mathrm{DFT}(\mathbf{x})[k]$, is the inner product $\langle \mathbf{x} , \mathbf{f}_k \rangle$. This means $\mathrm{DFT}(\mathbf{x})$ is the vector of coefficients of $\mathbf{x}$ with respect to the Fourier basis, scaled by $N$: $$\mathrm{DFT}(\mathbf{x}) = \begin{bmatrix} \langle \mathbf{x} , \mathbf{f}_0 \rangle \\ \langle \mathbf{x} , \mathbf{f}_1 \rangle \\ \vdots \\ \langle \mathbf{x} , \mathbf{f}_{N-1} \rangle \end{bmatrix}$$
:::

**Signal Notation:** In the context of the DFT, the term *signal* refers to a vector $\mathbf{x} \in \mathbb{C}^N$. We often use the notation $\mathbf{x}[n]$ to refer to the $n$th entry ($x_n$) of the signal vector, using $0$-indexing.

:::warning
**Example (Constructing the Fourier Matrix)**
The Fourier matrix $F_N$ is formed using the powers of $\overline{\omega}_N = \omega_N^{-1}$. The entry at row $k$ and column $n$ (using 0-indexing) is $F_N[k, n] = \overline{\omega}_N^{kn}$.

* **Case $N = 1$:** $\omega_1 = 1$.$$F_1 = [1]$$
* **Case $N = 2$:** $\overline{\omega}_2 = -1$.$$F_2 = \begin{bmatrix}
\overline{\omega}_2^{0\cdot 0} & \overline{\omega}_2^{0\cdot 1} \\
\overline{\omega}_2^{1\cdot 0} & \overline{\omega}_2^{1\cdot 1}
\end{bmatrix}
= \begin{bmatrix}
1 & 1 \\
1 & -1
\end{bmatrix}$$
* **Case $N = 4$:** $\overline{\omega}_4 = -i$. The powers of $-i$ fill the matrix.$$F_4 = \begin{bmatrix}
1 & 1 & 1 & 1 \\
1 & (-i)^1 & (-i)^2 & (-i)^3 \\
1 & (-i)^2 & (-i)^4 & (-i)^6 \\
1 & (-i)^3 & (-i)^6 & (-i)^9
\end{bmatrix}
= \begin{bmatrix}
1 & 1 & 1 & 1 \\
1 & -i & -1 & i \\
1 & -1 & 1 & -1 \\
1 & i & -1 & -i
\end{bmatrix}$$
:::

:::danger
**Proposition** For each $k=0,\dots,N-1$, we have $$\mathrm{DFT}(\mathbf{f}_k) = N \mathbf{e}_k$$ where $\mathbf{e}_k$ is the $k$th standard basis vector.
:::

### Properties of Real Signals
:::danger
**Proposition** If $\mathbf{x}$ is a real signal (i.e., $\mathbf{x}[k] \in \mathbb{R}$ for all $k$), its DFT $\mathbf{y} = \mathrm{DFT}(\mathbf{x})$ exhibits conjugate symmetry:$$\overline{\mathbf{y}[k]} = \mathbf{y}[N-k]$$
:::

This means that the negative frequency components $\mathbf{y}[N-k]$ are completely determined by the positive frequency components ($\mathbf{y}[k]$), a crucial property for signal compression.

### Inverse Discrete Fourier Transform
Since the Fourier basis is orthogonal, the matrix $\frac{1}{\sqrt{N}} F_N$ is *unitary*, which guarantees that the transformation is invertible.

:::info
**Definition** The inverse discrete Fourier transform (IDFT) of a coefficient vector $\mathbf{y} \in \mathbb{C}^N$ is: $$\mathrm{IDFT}(\mathbf{y}) = \frac{1}{N} F_N^\ast \mathbf{y}$$
:::

:::danger
**Proposition**
* $\mathrm{IDFT}(\mathrm{DFT}(\mathbf{x})) = \mathbf{x}$.
* The original signal $\mathbf{x}$ can be reconstructed by:$$\mathbf{x} = \sum_{k=0}^{N-1} \frac{\langle \mathbf{x} , \mathbf{f}_k \rangle}{N} \mathbf{f}_k$$
:::

:::success
**Exercise**
1. Determine whether the statement is *True* or *False*.
* If $N$ is an even integer then the vector $\mathbf{f}_{N/2}$ in the Fourier basis of $\mathbb{C}^N$ has real entries.
* Let $\mathbf{x} \in \mathbb{R}^N$ and let $\mathbf{y} = \mathrm{DFT}(\mathbf{x})$. Then $\overline{\mathbf{x}[k]} = \mathbf{x}[N-k]$ for all $0<k<N$.
2. Suppose a signal $\mathbf{x} \in \mathbb{R}^9$ of length 9 has real values and let $\mathbf{y} = \mathrm{DFT}(\mathbf{x})$. Determine all the values of $\mathbf{y}$ given the values at even indices:$$\mathbf{y}[0] = 1 \hspace{5mm} \mathbf{y}[2] = 2+i \hspace{5mm} \mathbf{y}[4] = 1+2i \hspace{5mm} \mathbf{y}[6] = 1-3i \hspace{5mm} \mathbf{y}[8] = 1-i$$
3. Let $N$ be an even integer and let $\mathbf{x} \in \mathbb{R}^N$ such that $\mathbf{x}[n] = 1$ if $n$ is even and $\mathbf{x}[n] = 0$ if $n$ is odd. Find $\mathrm{DFT}(\mathbf{x})$.
4. Let $N$ be an even integer and let $\mathbf{x} \in \mathbb{R}^N$ such that $\mathbf{x}[n] = 1$ if $n$ is even and $\mathbf{x}[n] = -1$ if $n$ is odd. Find $\mathrm{DFT}(\mathbf{x})$.
5. Let $N$ be an integer and let $\mathbf{x} \in \mathbb{R}^N$ such that $\mathbf{x}[0] = 0$ and $\mathbf{x}[n] = 1$ for $0<n<N$. Find $\mathrm{DFT}(\mathbf{x})$.
:::