复内积 = 共轭转置
Hermitian 内积 \(\mathbf{y}^* \mathbf{x}\) 是复向量空间的标准内积，注意共轭和顺序。
18.06 · 第 28 课
信号是向量，频率是特征值。进入复数域后，Fourier 矩阵作为酉矩阵（unitary matrix）统一了级数展开与快速算法——这是线性代数在信号处理中的辉煌应用。
在复向量空间 \(\mathbb{C}^n\) 中，内积需要修改。对 \(\mathbf{x}, \mathbf{y} \in \mathbb{C}^n\)，定义 Hermitian 内积（Hermitian inner product）：
\[\langle \mathbf{x}, \mathbf{y} \rangle = \mathbf{y}^* \mathbf{x} = \sum_{i=1}^{n} \overline{y_i}\, x_i\]其中 \(\mathbf{y}^* = \overline{\mathbf{y}}^T\) 是共轭转置（conjugate transpose）。注意顺序：内积对第一个变量是线性的，对第二个变量是共轭线性的：
\[\langle \mathbf{x}, c \mathbf{y} \rangle = \overline{c}\, \langle \mathbf{x}, \mathbf{y} \rangle\]向量的长度（norm）为 \(\|\mathbf{x}\| = \sqrt{\mathbf{x}^* \mathbf{x}}\)。两个向量正交当且仅当 \(\mathbf{y}^* \mathbf{x} = 0\)。
注意：复内积不满足交换律。\(\langle \mathbf{x}, \mathbf{y} \rangle = \overline{\langle \mathbf{y}, \mathbf{x} \rangle}\)。顺序至关重要！
在复矩阵的类比中，正交矩阵被酉矩阵（unitary matrix）取代。矩阵 \(Q\) 是酉矩阵当且仅当：
\[Q^* Q = I \quad \text{即} \quad Q^{-1} = Q^*\]酉矩阵的列构成 \(\mathbb{C}^n\) 的一组标准正交基（orthonormal basis）。它保持内积和长度不变：\(\|Q \mathbf{x}\| = \|\mathbf{x}\|\)。
实酉矩阵就是正交矩阵——酉矩阵是正交矩阵在复数域的推广。
\(n \times n\) Fourier 矩阵（Fourier matrix）\(F_n\) 定义为：
\[(F_n)_{jk} = \omega^{jk}, \quad \omega = e^{-2\pi i / n}, \quad j,k = 0,1,\dots,n-1\]例如 \(n=4\) 时，\(\omega = e^{-2\pi i/4} = -i\)：
\[F_4 = \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & -i & (-i)^2 & (-i)^3 \\ 1 & (-i)^2 & (-i)^4 & (-i)^6 \\ 1 & (-i)^3 & (-i)^6 & (-i)^9 \end{pmatrix} = \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & -i & -1 & i \\ 1 & -1 & 1 & -1 \\ 1 & i & -1 & -i \end{pmatrix}\]Fourier 矩阵是酉矩阵（在适当归一化之后）。具体地：
\[F_n^* F_n = n I \quad \Longrightarrow \quad \frac{1}{\sqrt{n}} F_n \text{ 是酉矩阵}\]核心联系：离散 Fourier 变换（DFT）就是乘以 Fourier 矩阵。信号 \(\mathbf{x}\) 的 Fourier 系数 \(\hat{\mathbf{x}} = F_n \mathbf{x}\) ——这正是信号在复指数正交基下的坐标。
直接计算 \(\hat{\mathbf{x}} = F_n \mathbf{x}\) 需要 \(O(n^2)\) 次运算。当 \(n\) 是 2 的幂时，快速 Fourier 变换（FFT）利用 \(F_n\) 的对称性将复杂度降到 \(O(n \log n)\)。
FFT 的关键是分治：把 \(F_n\) 分解为两个 \(n/2\) 规模的 Fourier 矩阵，加上一个对角"旋转因子"矩阵。递归下去，总运算量为 \(O(n \log_2 n)\)。
FFT 是二十世纪最重要的算法之一。没有它，数字通信、医学成像、音频压缩都不可能实现。
连续版本的 Fourier 级数是同一思想的无穷维推广。周期为 \(2\pi\) 的函数 \(f(x)\) 可以展开为：
\[f(x) = \sum_{k=-\infty}^{\infty} c_k e^{i k x}\]复指数函数 \(\{e^{ikx}\}_{k \in \mathbb{Z}}\) 在 \(L^2([-\pi,\pi])\) 中构成一组正交基：
\[\langle e^{imx}, e^{inx} \rangle = \int_{-\pi}^{\pi} e^{-imx} e^{inx}\, dx = 2\pi\, \delta_{mn}\]系数由内积给出：\(c_k = \frac{1}{2\pi} \langle f, e^{ikx} \rangle\)。这正是有限维正交展开的无穷维版本。
问题 1：复矩阵 \(Q\) 是酉矩阵的条件是什么？
问题 2：FFT 算法的核心改进是什么？
问题 3：关于 Fourier 矩阵 \(F_n\)，下列哪项正确？
问题 4：离散 Fourier 变换（DFT）的几何含义是什么？
Hermitian 内积 \(\mathbf{y}^* \mathbf{x}\) 是复向量空间的标准内积，注意共轭和顺序。
归一化的 Fourier 矩阵 \(\frac{1}{\sqrt{n}}F_n\) 是酉矩阵，其列构成 \(\mathbb{C}^n\) 的标准正交基。
利用对称性，FFT 把 DFT 从 \(O(n^2)\) 降到 \(O(n \log n)\)，是算法设计的经典范例。
连续 Fourier 级数是函数空间中的正交基展开，与有限维线性代数完全平行。
lecture_slides/lecture_26.pdflecture_slides/lecture_32.pdf