ZoomNotes for Linear Algebra

Part 9: Complex Numbers and the Fourier Matrix

9.1 Complex Numbers $x + iy = re^{i\theta}$: Unit Circle $r = 1$

A complex number is $z = x + iy$ where $i^2 = -1$.

Polar Form (Euler's formula):

$$e^{i\theta} = \cos\theta + i\sin\theta \\ z = re^{i\theta} = r(\cos\theta + i\sin\theta)$$

where $r = |z| = \sqrt{x^2 + y^2}$ is the modulus and $\theta = \arg(z)$ is the argument.

Complex Conjugate: $\bar{z} = x - iy = re^{-i\theta}$.

Key identity: $|z|^2 = z \bar{z} = x^2 + y^2$.

The unit circle: $z = e^{i\theta}$ has $|z| = 1$. Points on the unit circle are $\cos\theta + i\sin\theta$.

Roots of Unity: The $N$th roots of 1 are $e^{2\pi i k / N}$ for $k = 0, 1, \dots, N-1$.

---

9.2 Complex Matrices: Hermitian $S = S^H$ and Unitary $Q^{-1} = Q^H$

Complex Vectors in $\mathbb{C}^n$:

• Inner product: $\langle z, w \rangle = \bar{z}_1 w_1 + \cdots + \bar{z}_n w_n = z^H w$
• Length: $\|z\|^2 = |z_1|^2 + \cdots + |z_n|^2 = z^H z$

Conjugate Transpose (Hermitian): $A^H = \bar{A}^T$. Also written as $A^*$.

Hermitian Matrices: $S = S^H$ (i.e., $S_{ij} = \bar{S}_{ji}$)

• All eigenvalues are real
• Eigenvectors for distinct eigenvalues are perpendicular (in the complex sense)
• The spectral theorem extends: $S = Q \Lambda Q^H$ with $Q$ unitary

Unitary Matrices: $Q^{-1} = Q^H$ (i.e., $Q^H Q = I$)

• Columns are orthonormal in the complex inner product
• Preserve length: $\|Qz\| = \|z\|$
• All eigenvalues satisfy $|\lambda| = 1$
• Product of unitary matrices is unitary

---

9.3 Fourier Matrix $F$ and the Discrete Fourier Transform

Fourier Matrix $F_N$: Size $N \times N$ with entries:

$$(F_N)_{jk} = w^{jk} \quad \text{where } w = e^{2\pi i / N}$$

for $j, k = 0, 1, \dots, N-1$ (using zero-based indexing).

Thus:

$$F_N = \begin{bmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & w & w^2 & \cdots & w^{N-1} \\ 1 & w^2 & w^4 & \cdots & w^{2(N-1)} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & w^{N-1} & w^{2(N-1)} & \cdots & w^{(N-1)(N-1)} \end{bmatrix}$$

Key Properties:

$$F_N \bar{F}_N = N I, \quad F_N^{-1} = \frac{1}{N} \bar{F}_N, \quad \frac{1}{\sqrt{N}} F_N \text{ is unitary}$$

Discrete Fourier Transform (DFT): Given a signal $f = (f_0, \dots, f_{N-1})$, its DFT coefficients are:

$$c = F_N^{-1} f = \frac{1}{N} \bar{F}_N f$$

Inverse DFT:

$$f = F_N c$$

Each coefficient $c_k$ represents the amplitude of the frequency component $w^{-k}$ in the signal.

---

9.4 Cyclic Convolution and the Convolution Rule

Cyclic Convolution: For two vectors $a$ and $b$ of length $N$, their cyclic convolution $a * b$ is:

$$(a * b)_k = \sum_{j=0}^{N-1} a_j b_{k-j \mod N}$$

Circulant Matrices: A circulant matrix $C$ is an $N \times N$ matrix where each row is a cyclic shift of the first row $c_0, c_1, \dots, c_{N-1}$:

$$C = \begin{bmatrix} c_0 & c_1 & c_2 & \cdots & c_{N-1} \\ c_{N-1} & c_0 & c_1 & \cdots & c_{N-2} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ c_1 & c_2 & c_3 & \cdots & c_0 \end{bmatrix}$$

Convolution Rule (Fundamental):

• Eigenvectors of every circulant matrix are the columns of the Fourier matrix $F_N$
• Eigenvalues are the DFT of the first column

Convolution Theorem: Convolution in the time domain equals pointwise multiplication in the frequency domain:

$$F^{-1} (a * b) = (F^{-1} a) \odot (F^{-1} b) \quad \text{or equivalently} \quad a * b = F[(F^{-1} a) \odot (F^{-1} b)]$$

where $\odot$ denotes componentwise (Hadamard) multiplication. This is why the Fourier transform is so powerful for signal processing: it turns expensive convolution into cheap pointwise multiplication.

---

9.5 FFT: The Fast Fourier Transform

The Fast Fourier Transform (FFT) (Cooley-Tukey algorithm) computes the DFT in $O(N \log N)$ operations instead of $O(N^2)$.

Key Idea: Factor $F_{2N}$ using even and odd permutations:

$$F_{2N} = \begin{bmatrix} I & D \\ I & -D \end{bmatrix} \begin{bmatrix} F_N & 0 \\ 0 & F_N \end{bmatrix} \begin{bmatrix} \text{even-odd permutation} \end{bmatrix}$$

where $D = \text{diag}(1, w, w^2, \dots, w^{N-1})$ for $w = e^{2\pi i / 2N}$.

Recursive Splitting:

• Instead of one $2N$-point DFT, compute two $N$-point DFTs, then combine with $O(N)$ additional work
• Apply the same recursively: an $N$-point DFT uses two $N/2$-point DFTs, etc.

Complexity: For $N = 2^{10} = 1024$:

• Direct DFT: $N^2 \approx 1,000,000$ operations
• FFT: $(N/2) \log_2 N \approx 500 \times 10 = 5000$ operations

Impact: The FFT is one of the most important algorithms of the 20th century. It makes Fourier analysis practical for large-scale signal processing, image compression (JPEG), spectral analysis, and solving partial differential equations.