线性代数 ZoomNotes

第 9 部分：复数与傅里叶矩阵

9.1 复数 $x + iy = re^{i\theta}$：单位圆 $r = 1$

复数 (complex number) 是 $z = x + iy$，其中 $i^2 = -1$。

极坐标形式（欧拉公式）：

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

其中 $r = |z| = \sqrt{x^2 + y^2}$ 称为模 (modulus)，$\theta = \arg(z)$ 称为辐角 (argument)。

复共轭 (complex conjugate)： $\bar{z} = x - iy = re^{-i\theta}$。

关键恒等式： $|z|^2 = z \bar{z} = x^2 + y^2$。

单位圆： $z = e^{i\theta}$ 满足 $|z| = 1$。单位圆上的点为 $\cos\theta + i\sin\theta$。

单位根 (roots of unity)： 1 的 $N$ 次方根为 $e^{2\pi i k / N}$，$k = 0, 1, \dots, N-1$。

---

9.2 复数矩阵：Hermite 矩阵 $S = S^H$ 与酉矩阵 $Q^{-1} = Q^H$

$\mathbb{C}^n$ 中的复向量：

• 内积 (inner product)：$\langle z, w \rangle = \bar{z}_1 w_1 + \cdots + \bar{z}_n w_n = z^H w$
• 长度：$\|z\|^2 = |z_1|^2 + \cdots + |z_n|^2 = z^H z$

共轭转置（Hermite 转置）： $A^H = \bar{A}^T$。也记作 $A^*$。

Hermite 矩阵 (Hermitian matrices)： $S = S^H$（即 $S_{ij} = \bar{S}_{ji}$）

• 所有特征值均为实数
• 不同特征值对应的特征向量（在复数意义下）相互垂直
• 谱定理的推广：$S = Q \Lambda Q^H$，其中 $Q$ 为酉矩阵

酉矩阵 (unitary matrices)： $Q^{-1} = Q^H$（即 $Q^H Q = I$）

• 各列在复内积意义下标准正交
• 保持长度不变：$\|Qz\| = \|z\|$
• 所有特征值满足 $|\lambda| = 1$
• 酉矩阵的乘积仍为酉矩阵

---

9.3 傅里叶矩阵 $F$ 与离散傅里叶变换

傅里叶矩阵 $F_N$： 大小为 $N \times N$，其元素为：

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

其中 $j, k = 0, 1, \dots, N-1$（使用从零开始的索引）。

因此：

$$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}$$

关键性质：

$$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{ 是酉矩阵}$$

离散傅里叶变换 (DFT)： 给定信号 $f = (f_0, \dots, f_{N-1})$，其 DFT 系数为：

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

逆 DFT：

$$f = F_N c$$

每个系数 $c_k$ 表示信号中频率分量 $w^{-k}$ 的振幅 (amplitude)。

---

9.4 循环卷积与卷积定理

循环卷积 (cyclic convolution)： 对两个长度为 $N$ 的向量 $a$ 和 $b$，其循环卷积 $a * b$ 定义为：

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

循环矩阵 (circulant matrices)： 循环矩阵 $C$ 是一个 $N \times N$ 矩阵，其中每一行是第一行 $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}$$

卷积定理（基本原理）：

• 每个循环矩阵的特征向量是傅里叶矩阵 $F_N$ 的列
• 特征值是第一列的 DFT

卷积定理： 时域中的卷积等价于频域中的逐点相乘 (pointwise multiplication)：

$$F^{-1} (a * b) = (F^{-1} a) \odot (F^{-1} b) \quad \text{或等价地} \quad a * b = F[(F^{-1} a) \odot (F^{-1} b)]$$

其中 $\odot$ 表示分量方式（Hadamard）乘法。这正是傅里叶变换在信号处理中如此强大的原因：它将昂贵的卷积运算转化为廉价的逐点乘法。

---

9.5 FFT：快速傅里叶变换

快速傅里叶变换 (FFT)（Cooley-Tukey 算法）用 $O(N \log N)$ 次运算而非 $O(N^2)$ 来计算 DFT。

核心思想： 利用偶排列和奇排列对 $F_{2N}$ 进行分解：

$$F_{2N} = \begin{bmatrix} I & D \\ I & -D \end{bmatrix} \begin{bmatrix} F_N & 0 \\ 0 & F_N \end{bmatrix} \begin{bmatrix} \text{奇偶置换} \end{bmatrix}$$

其中 $D = \text{diag}(1, w, w^2, \dots, w^{N-1})$，$w = e^{2\pi i / 2N}$。

递归分解：

• 将一次 $2N$ 点 DFT 替换为两次 $N$ 点 DFT，再以 $O(N)$ 的额外工作量进行组合
• 递归地应用同样的方法：一次 $N$ 点 DFT 使用两次 $N/2$ 点 DFT，依此类推

复杂度： 对于 $N = 2^{10} = 1024$：

• 直接 DFT：约 $N^2 \approx 1,000,000$ 次运算
• FFT：约 $(N/2) \log_2 N \approx 500 \times 10 = 5000$ 次运算

影响： FFT 是 20 世纪最重要的算法之一。它使傅里叶分析在大规模信号处理、图像压缩（JPEG）、频谱分析以及偏微分方程求解等领域得以实际应用。