循环矩阵与 DFT：属性与计算

循环矩阵：特征值、DFT 与代数结构

循环矩阵是方阵的一种，每行（除第一行外）都是前一行向右循环移位的结果。对于阶数 n 的循环矩阵 C(a₀,…,aₙ₋₁)，其形式如下：

C(a_0,\ldots,a_{n-1})=\begin{pmatrix} a_0 & a_1 & a_2 & \ldots & a_{n-2} & a_{n-1} \\  a_{n-1} & a_0 & a_1 & \ldots & a_{n-3} & a_{n-2} \\ a_{n-2} & a_{n-1} & a_0 & \ldots & a_{n-4} & a_{n-3} \\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \\ a_2 & a_3 & a_4 & \ldots & a_0 & a_1 \\ a_1 & a_2 & a_3 & \ldots & a_{n-1} & a_0 \end{pmatrix}

所有计算均在 ℂ 上进行。主要记号：χ_A(t) — 特征多项式，μ_A(t) — 最小多项式，Sp(A) — 谱，A* = \overline{A}^⊤ — 厄米共轭。

考虑阶数为 4 的循环置换矩阵 M：

M=\begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{pmatrix}

其幂：M², M³, M⁴ = I。最小多项式 μ_M(t) = t⁴ - 1，因为 {I, M, M², M³} 线性无关。谱 Sp(M) = {±1, ±i}。

任意循环矩阵均为 M 的多项式：C(a,b,c,d) = f(M)，其中 f(t) = a + bt + ct² + dt³。

代数性质与对角化

循环矩阵构成 M_n(ℂ) 的一个交换子代数：

• 循环矩阵的乘积仍是循环矩阵：f(M)g(M) = h(M)，h(t) = f(t)g(t)。
• 谱：Sp(C) = {f(λ) | λ ∈ Sp(M)}。
• 行列式：det C(a,b,c,d) = (a+b+c+d)(a-b+c-d)(a+bi-c-di)(a-bi-c+di)。
• 所有循环矩阵可在同一组基下对角化；循环矩阵代数同构于 ℂ⁴。

M 的特征向量，对于 λ ∈ Sp(M)，满足：

\begin{pmatrix} p\\q\\r\\s \end{pmatrix} \overset{M}{\longmapsto} \begin{pmatrix} q\\r\\s\\p \end{pmatrix}=\lambda\begin{pmatrix} p\\q\\r\\s \end{pmatrix}

对于 λ=1：p=q=r=s。对于 λ=i：q=ip, r=iq=-p, s=ir=-ip。

M 是酉矩阵（M* = M⁻¹），因此可在正交基下对角化。归一化矩阵 U（即 1/2 F，其中 F 为 DFT 矩阵）给出：

U^{-1}MU = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & i & 0 & 0 \\ 0 & 0 & -1 & 0 \\ 0 & 0 & 0 & -i \end{pmatrix}, \quad U=\dfrac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1 \\  1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i\end{pmatrix}

与离散傅里叶变换的联系

矩阵 F 将循环矩阵的第一行 (a,b,c,d) 变换为特征值向量：

F\begin{pmatrix} a \\ b\\c\\d\end{pmatrix}=\begin{pmatrix} a+b+c+d\\a+bi-c-di\\a-b+c-d\\a-bi-c+di\end{pmatrix}

推广到阶数 n：Sp(M) = {1, ω, …, ω^{n-1}}，ω = e^{2πi/n}。DFT 矩阵 F 计算多项式 f(t) = Σ a_k t^k 在 ω^k 处的取值。

快速傅里叶变换（FFT）将复杂度从 O(n²) 降至 O(n log n)。对于 n=4：

• E₀ = a+c, E₁ = a-c, O₀ = b+d, O₁ = b-d。
• f(1) = E₀ + O₀, f(i) = E₁ + iO₁, f(-1) = E₀ - O₀, f(-i) = E₁ - iO₁。

FFT 应用：

• 循环矩阵与向量的乘法：F⁻¹(FA · FB)。
• 循环矩阵乘法：结果第一行为 F⁻¹(FA · FB)^⊤。

酉 DFT 矩阵 U = F/√n 的谱位于单位圆上。U² 是一个反射矩阵，其特征值 {1（出现 ⌈(n+1)/2⌉ 次），-1（出现 ⌊(n-1)/2⌋ 次）}。

高斯和与 U 的谱

U 的迹涉及二次高斯和：

tr U = (1 + ω + ω⁴ + … + ω^{(n-1)²}) / √n。

高斯公式：

| n mod 4 | tr U |

|---------|------|

| 0 | 1+i |

| 1 | 1 |

| 2 | 0 |

| 3 | i |

U 的谱通过 tr U 确定 1、-1、i、-i 的重数。

关键要点：

• 循环矩阵是置换矩阵 M 的多项式，可在 DFT 基下对角化。
• 循环矩阵代数同构于 ℂ[t]/(tⁿ-1)，因此是交换的。
• DFT 高效计算循环矩阵谱；FFT 加速运算。
• 酉 DFT 矩阵 U 的谱与高斯和相关。
• 应用：快速卷积、多项式在 tⁿ-1 模下的乘法。

— Editorial Team