第 37A 章 Toeplitz·Hankel·循环矩阵

前置：矩阵运算 (Ch02) · 矩阵分解 (Ch10) · 离散傅里叶变换 (Ch30)

本章脉络：结构化矩阵的动机（参数压缩与计算加速） \(\to\) 循环矩阵 (Circulant) 定义 \(\to\) 循环矩阵的 DFT 对角化（核心定理） \(\to\) Toeplitz 矩阵定义与平移不变性 \(\to\) Hankel 矩阵定义与对称性 \(\to\) Toeplitz 与 Hankel 的转换（反序阵 \(J\)） \(\to\) 快速算法初步：Levinson-Durbin 递推 \(\to\) 应用：数字滤波、自相关函数、离散卷积的代数表示

延伸：结构化矩阵是现代通信与信号处理的代数底座；循环矩阵的对角化本质上揭示了卷积定理的代数根源；而 Toeplitz 矩阵则是所有线性时不变系统 (LTI) 的标准表达

在一般的矩阵理论中，存储 \(n \times n\) 的元素需要 \(n^2\) 个空间。然而，许多工程问题中出现的矩阵是由极少数参数（如 \(O(n)\) 个）生成的。Toeplitz（沿对角线常数）、Hankel（沿反对角线常数）和循环矩阵就是这类结构化矩阵的典型代表。本章将展示这些特定的几何结构如何转化为计算速度的飞跃。

---

37A.1 循环矩阵与 DFT

定义 37A.1 (循环矩阵)

矩阵 \(C\) 称为循环矩阵，如果其每一行是前一行的循环右移。它完全由第一行向量 \(\mathbf{c} = (c_0, c_1, \ldots, c_{n-1})\) 决定。

定理 37A.1 (对角化定理)

每一个 \(n\) 阶循环矩阵 \(C\) 都可以被 \(n\) 阶 DFT 矩阵 \(F_n\) 对角化： $\(C = F_n^* \Lambda F_n\)$ 其中对角阵 \(\Lambda\) 的元素恰好是第一行向量 \(\mathbf{c}\) 的离散傅里叶变换（DFT）。 推论：循环矩阵的乘法和求逆可以在 \(O(n \log n)\) 时间内完成。

---

37A.2 Toeplitz 与 Hankel 矩阵

定义 37A.2 (Toeplitz 矩阵)

矩阵 \(T\) 称为 Toeplitz 矩阵，如果其元素满足 \(t_{ij} = t_{i-j}\)，即沿平行于主对角线的直线元素相等。

定义 37A.3 (Hankel 矩阵)

矩阵 \(H\) 称为 Hankel 矩阵，如果其元素满足 \(h_{ij} = h_{i+j}\)，即沿垂直于主对角线的直线元素相等。 关系：\(T\) 是 Toeplitz 阵 \(\iff JT\) 是 Hankel 阵（其中 \(J\) 是反序矩阵）。

---

37A.3 快速算法初步

技术：Levinson-Durbin 递推

对于对称正定的 Toeplitz 方程组 \(T\mathbf{x} = \mathbf{b}\)，可以利用其结构的嵌套性，通过 \(O(n^2)\) 的复杂度求得精确解。这在预测编码和语音信号处理中至关重要。

---

练习题

1. [计算] 写出第一行为 \((1, 2, 3)\) 的 \(3 \times 3\) 循环矩阵。

参考答案

构造步骤： 1. 第一行：\((1, 2, 3)\)。 2. 第二行（右移一位）：\((3, 1, 2)\)。 3. 第三行（再右移一位）：\((2, 3, 1)\)。 结果：\(\begin{pmatrix} 1 & 2 & 3 \\ 3 & 1 & 2 \\ 2 & 3 & 1 \end{pmatrix}\)。

2. [Toeplitz] 一个 \(n \times n\) Toeplitz 矩阵最多由多少个独立参数确定？

参考答案

计数： 1. 主对角线：1 个参数。 2. 上方平行对角线：\(n-1\) 个参数。 3. 下方平行对角线：\(n-1\) 个参数。 总计：\(1 + (n-1) + (n-1) = 2n - 1\) 个。 这说明存储该类矩阵的空间复杂度仅为 \(O(n)\)。

3. [谱性质] 证明：循环矩阵的所有特征向量构成的矩阵恰好是 DFT 矩阵。

参考答案

证明思路： 1. 设 \(W\) 是循环算子（移位矩阵）。循环矩阵 \(C\) 是 \(W\) 的多项式：\(C = \sum c_k W^k\)。 2. 由于 \(W\) 是一个周期算子，\(W^n = I\)，其特征向量是复谐波向量。 3. 所有的 \(W^k\) 具有共同的特征向量集。 结论：因此任何循环矩阵 \(C\) 的特征向量集都是固定的，即单位根的幂构成的基。

4. [性质] 两个循环矩阵的乘积还是循环矩阵吗？它们交换吗？

参考答案

结论： 是的，且它们彼此交换。 理由： 1. 由于它们都被同一个 DFT 矩阵 \(F_n\) 对角化。 2. \(C_1 C_2 = (F^* \Lambda_1 F)(F^* \Lambda_2 F) = F^* (\Lambda_1 \Lambda_2) F\)。 3. 对角阵相乘满足交换律且结果仍为对角阵。 4. 对角阵在 \(F\) 的相似变换下返回循环矩阵空间。

5. [Hankel] 证明：若 \(A\) 是 Hankel 阵，则 \(A\) 必是对称阵。

参考答案

证明： 1. 根据定义 \(a_{ij} = h_{i+j}\)。 2. 转置元 \(a_{ji} = h_{j+i}\)。 3. 由于标量加法满足交换律，\(i+j = j+i\)，故 \(a_{ij} = a_{ji}\)。 结论：Hankel 矩阵关于主对角线对称。

6. [逆矩阵] Toeplitz 矩阵的逆还是 Toeplitz 吗？

参考答案

结论： 一般不是。 理由：Toeplitz 矩阵的逆虽然不再保持严格的对角线相等性，但它保留了一种称为“位移秩”（Displacement Rank）的属性。其逆矩阵通常是两个位移秩极低的矩阵之积（见 Ch37B）。

7. [卷积] 循环矩阵与向量相乘在信号处理中对应什么运算？

参考答案

结论： 对应于信号的循环卷积（Circular Convolution）。 意义：这正是为什么在频域执行点乘可以加速时域卷积的矩阵论解释。

8. [伴随阵] 判定伴随矩阵（Companion Matrix）是否是 Toeplitz 或循环结构？

参考答案

判定：不是。 理由：伴随矩阵在次对角线上是 1，在最后一列（或最后一行）是多项式系数，其余为 0。这种结构不满足 \(t_{ij} = t_{i-j}\) 的平移不变性。

9. [病态性] 为什么大规模 Hilbert 矩阵（一种特殊的 Hankel 阵）很难求逆？

参考答案

数值分析： Hilbert 矩阵的元素为 \(1/(i+j-1)\)。它的奇异值随阶数呈指数级衰减。这导致其条件数极大，即使在很小的维度下，求逆运算也会被舍入误差彻底淹没。

10. [应用] 在语音信号处理中，线性预测分析 (LPC) 通常需要求解哪种矩阵方程？

参考答案

结论： 需要求解 Yule-Walker 方程，其中的系数矩阵是由信号的自相关函数构成的对称正定 Toeplitz 矩阵。Levinson-Durbin 算法正是为此而开发的。

本章小结

结构化矩阵是线性代数与快速算法的交汇点：

1. 参数的压缩：Toeplitz 和循环结构证明了通过利用平移不变性，我们可以用线性级别的空间描述平方级别的变换，极大地降低了数据存储压力。
2. 频域的桥梁：循环矩阵的对角化定理确立了离散傅里叶变换在算子对角化中的核心地位，将复杂的时域耦合转化为简单的频域缩放。
3. 递推的艺术：Levinson 等快速算法揭示了结构化矩阵内部的子问题重叠性质，是动态规划思想在矩阵计算领域的精彩体现。