代数同构视角下的离散 Fourier 变换

多项式环、求值插值与相似对角化

数学
讲稿
Author

sun123zxy

Published

2024年5月13日

1 从 Fourier 变换到 DFT

Fourier 变换及其卷积性质

  • Fourier 变换:将给定函数 \(f\) 映为函数 \(\mathcal F[f]\)\[ \mathcal F[f](\lambda) := \int_{-\infty}^{\infty} f(t) e^{- \mathrm{i}\lambda t} \operatorname{d}\!t \]

  • 定义函数 \(f\)\(g\) 的卷积 \[ (f*g)(\lambda) := \int_{-\infty}^{\infty} f(\lambda-x) g(x) \operatorname{d}\!x \] 则 Fourier 变换将两个函数的卷积化为逐点乘积,即 \[ \mathcal F[f*g] = \mathcal F[f] \mathcal F[g] \]

复数域上的 DFT 及其卷积性质

  • 离散 Fourier 变换(Discrete Fourier Transform, DFT):线性空间 \(\mathbb C^n \to \mathbb C^n\) 上的线性变换 \(F\),将向量 \(\boldsymbol a = (a_0,a_1,\dots,a_{n-1})^\mathrm{T}\in \mathbb C^n\) 映为 \(F \boldsymbol a\),其第 \(i\) 个分量如下所示 \[ (F \boldsymbol a)_i := \sum_{k=0}^{n-1} \omega_n^{ik} a_i \] 这里分量下标从 \(0\) 开始计数,\(\omega_n := e^{2 \pi \mathrm{i}/ n}\)\(\mathbb C\) 上的一个 \(n\) 次本原单位根.

  • 相仿的卷积性:两个向量 \(\boldsymbol a, \boldsymbol b \in \mathbb C^n\)循环卷积定义为 \[ (\boldsymbol a * \boldsymbol b)_k := \sum_{i + j = k \pmod{n}} a_i b_j \] 则 DFT 将两个向量的循环卷积化为逐项乘积 \(\times\),即 \[ F(\boldsymbol a * \boldsymbol b) = (F \boldsymbol a) \times (F \boldsymbol b) \]

矩阵表示

\(\mathbb C^n\) 的自然基下,变换 \(F\) 有矩阵表示 \[ F = \begin{pmatrix} \omega_n^{ij} \end{pmatrix}_{(i,j)\in n \times n} = \begin{pmatrix} 1 & 1 & \dots & 1 \\ 1 & \omega_n & \dots & \omega_n^{n-1} \\ \vdots & \vdots & \ddots & \vdots \\ 1 & \omega_n^{n-1} & \dots & \omega_n^{(n-1)(n-1)} \end{pmatrix} \]

  • 卷积性:系数为全体复平面 \(n\) 次单位根的可逆 Vandermonde 矩阵
  • 正交性:适当单位化后为酉矩阵

问题1

  • DFT 化卷为乘的本质?

    • 我们给出一大类具备卷积性的线性映射的构造,DFT 将作为特例推出.
  • 如何从代数角度理解 DFT?

    • 两个视角:多项式环、矩阵代数
    • 两种表现:求值插值、相似对角化
    • 一致观点:保加法、保数乘、保乘法的代数同构
  • DFT 是否是唯一一类化卷为乘的变换?作为底层结构的 \(\mathbb C\) 是否可以放宽?

    • 工程上复数乘法运算较慢且具有浮点误差,更换底层代数结构具有实际意义.例如,被称为数论变换(number theoretic transforms, NTT)的 DFT 变种就将 \(\mathbb C\) 替换为有限域 \(\mathbb F_p\) 而同时保留了其卷积性质.

    • 我们将其 DFT 扩展至任意整环并证明特定含义下的唯一性.

1 [1]; [2]; [3]; [4]; [5]

2 DFT 与多项式环

2.1 引例:\(\mathbb C[x]\)、求值插值与复数域 DFT

\(\mathbb C[x]\) 与循环卷积

设不超过 \(n-1\) 次的多项式 \(f(x) = \sum_{k=0}^{n-1} a_k x^k\)\(g(x) = \sum_{k=0}^{n-1} b_k x^k\).二者的多项式乘积由 Cauchy 乘积给出 \[ f(x) g(x) = \sum_{i=0}^{n-1} a_i x^i \sum_{j=0}^{n-1} b_j x^j = \sum_{k=0}^{2n-2} x^k \sum_{i+j = k} a_i b_j \]\(\boldsymbol a := (a_0,a_1,\dots,a_{n-1})^\mathrm{T}\)\(\boldsymbol b := (b_0,b_1,\dots,b_{n-1})^\mathrm{T}\),回顾循环卷积定义 \[ (\boldsymbol a * \boldsymbol b)_k := \sum_{i + j = k \pmod{n}} a_i b_j \] 可见 Cauchy 乘积与循环卷积尚有区别.稍加改动,若在模 \(x^n - 1\) 的意义下——即商环 \(\mathbb C[x]/(x^n-1)\) 中计算,则二者相合: \[ f(x) g(x) = \sum_{k=0}^{n-1} x^k \sum_{i + j = k \pmod{n}} a_i b_j \pmod{x^n - 1} \]

\(\mathbb C[x]\) 与复数域 DFT

DFT 亦有在 \(\mathbb C[x]\) 上的表示.给定 \(\boldsymbol a := (a_0,a_1,\dots,a_{n-1})^\mathrm{T}\in \mathbb C^n\),其对应多项式 \(f(x) = \sum_{k=0}^{n-1} a_k x^k\) 次数不超过 \(n-1\) 次,则 \[ (F \boldsymbol a)_i = \sum_{k=0}^{n-1} \omega_n^{ik} \boldsymbol a_i = \sum_{k=0}^{n-1} \boldsymbol a_i (\omega_n^i)^k = f(\omega_n^i) \] 恰为 \(f(x)\) 分别在 \(n\)\(\mathbb C\)\(n\) 次单位根处多点求值的结果.

  • 可逆性:\(n\) 点唯一确定一个不超过 \(n-1\) 次的多项式(Lagrange 插值
  • 线性性:\((af+bg) (\omega_n^i) = a f(\omega_n^i) + b g(\omega_n^i)\)
  • 卷积性:将取模乘法化为点值逐项相乘,再次与 \(\mathbb C^n\) 上的表现相合 \[ \begin{aligned} F(\boldsymbol a * \boldsymbol b) &= (F \boldsymbol a) \times (F \boldsymbol b) \\ (fg)(\omega_n^i) &= f(\omega_n^i) g(\omega_n^i) \end{aligned} \]

小结

  • \(\mathbb C^n\)\(\mathbb C[x]\) 视角下的 DFT:

    • \(\mathbb C^n\):作为以单位根为参数的 Vandermonde 矩阵,DFT 是 \(\mathbb C^n\) 上的可逆线性变换,将向量间的循环卷积 \(*\) 化为逐项乘积 \(\times\)

    • \(\mathbb C[x]\):作为单位根处的多点求值插值,DFT 在全体不超过 \(n-1\) 次的多项式和 \(\mathbb C^n\) 间建立起线性同构关系,将多项式乘积化为函数值逐点乘积.

  • 化卷为乘,就是把多项式环上的取模乘法变为 \(\mathbb C^n\) 上的逐项乘积,DFT 保持了两个代数结构间的乘法.

    • \(\mathbb C[x]\) 作为环结构乘法自然,在多项式环上刻画 DFT 较在 \(\mathbb C^n\) 上强行定义循环卷积具有优越性.

2.2 整环上的推广

代数、代数同构与直积

  • 整环:无零因子交换幺环

  • \(R\) 是一整环,若 \((A,+,\times)\) 为一环且配备了与乘法 \(\times\) 相容的 \(R\)-数乘 \(\cdot\),则称 \(A\) 是一 \(R\)-代数,不至混淆时简称代数.

    • 整环 \(R\) 自身也可视为一个代数.
  • 我们将 \(R^n\) 理解为作为代数的 \(R\) 的直积,即 \(R^n = R \times R \times \dots \times R\).直积的加法、数乘和乘法均在逐项意义下定义.

  • 保持代数间加法、数乘和乘法的双射被称为代数同构.

几个观察与整环的优势

  • 关于引例的若干观察:

    • DFT 是 \(\mathbb C[x] / (x^n-1) \to R^n\) 的一个代数同构,具体做法是在单位根处多点求值插值

    • 求值插值在任意 \(n\) 个不同位置进行即可,单位根不是本质要求

    • 商环 \(\mathbb C[x] / (x^n-1)\) 带来了与循环卷积对应的多项式取模乘法,还蕴含着“不超过 \(n-1\) 次”为求值插值带来的单与满

    • 第一同构定理:设 \(f: R \to S\) 是环同态,则 \(f\) 诱导出环同构 \(R / \operatorname{Ker}f \cong \operatorname{Im}f\)

  • 选取整环作为底层代数结构的理由:

    • 交换:确保求值操作是同态
    • 保留环上整除的结构和多项式根与因子的关系(带余除法、余式定理)
    • 在唯一性证明中发挥作用

商环到直积的代数同构

下面固定 \(R\) 是一整环.令 \(C\)\(R\) 的一有限子集,由若干不同一次多项式乘积 \(\prod_{c \in C} (x-c)\) 生成的 \(R[x]\) 上的理想记为 \(\left( \prod_{c \in C} (x-c) \right)\)

用记号 \(R^C\) 代表全体 \(C\) 上的 \(R\) 值函数构成的集合.\(R^C\) 与其上定义的函数逐点加法、数乘和乘法构成一个代数,自然也与 \(R^n\) 代数同构.

命题 1 多项式商环 \(R[x] / \left( \prod_{c \in C} (x-c) \right)\) 与代数直积 \(R^C\) 代数同构.

图 1: 命题 1 构造示意图

构造

考察 \(R[x]\)\(R^C\) 上的代数同态 \(\varphi: f \mapsto (C \ni x \mapsto f(x))\),其含义为在每一 \(c \in C\) 处对多项式 \(f\) 进行求值.

  • \(\varphi\) 的核:

    \[ \operatorname{Ker}\varphi = \{f \in R[x]: f(C)=\{0\}\} = \left( \prod_{c \in C} (x-c) \right) \]

  • \(\varphi\) 的像:对每个 \(c \in C\) 对应的理想 \((x-c)\) 应用中国剩余定理就有 \(\operatorname{Im}\varphi = R^C\)

故由第一同构定理,\(\varphi\) 诱导的 \[ \bar \varphi: R[x] / \left( \prod_{c \in C} (x-c) \right) \to R^C \] 是一同构映射.

DFT:代数同构的特例

作为上一定理的特例,DFT 在单位根处求值插值.若 \(\omega_n\) 为内嵌于 \(R\) 的某一 \(n\) 阶循环(乘法)群的生成元,则称其为 \(R\) 上的 \(n\) 次本原单位根

推论 1\(R\) 上存在 \(n\) 次本原单位根 \(\omega_n\),则多项式 \[ x^n - 1 = \prod_{k=0}^{n-1} (x - \omega_n^k) \]\(R[x] / \left( x^n - 1 \right)\)\(R^n\) 代数同构.我们便称二者间的代数同构为 \(R\) 上的 \(n\) 点 DFT

2.3 唯一性的讨论

全体代数同构的结构

图 2

已经建立 \(R[x]/(m(x)) \to R^n\) 的同构关系,这里 \(m(x)\) 是若干不同一次因式的乘积.但这种同构或不止一种.为研究其是否在某种意义下具有唯一性,需研究全体同构 \(\operatorname{Iso}(R[x]/(m(x)),R^n)\) 的结构.该问题化归为研究 \(R^n\) 上全体自同构 \(\operatorname{Aut}(R^n)\) 的结构.

命题 2\(\mathcal A\) 是一与 \(R^n\) 同构的任一代数.固定代数同构 \(\varphi: \mathcal A \to R^n\),则任一 \(\mathcal A \to R^n\) 的代数同构 \(f\) 都具有形式 \(f = p \varphi\),这里 \(p \in \operatorname{Aut}(R^n)\)

\(R^n\) 上的自同构

\(\boldsymbol e_1,\dots,\boldsymbol e_n\)\(R^n\) 上的自然基,设 \(\sigma \in S_n\) 是有限集 \(\{0,1,\dots,n-1 \}\) 上的一个置换.定义 \(R^n\) 上由置换 \(\sigma\) 诱导的模自同构 \[ P_\sigma: \boldsymbol e_k \mapsto \boldsymbol e_{\sigma(k)} \] 容易验证 \(P_\sigma\) 保持逐项乘法,因此它也是 \(R^n\) 上的代数自同构.

下面的引理刻画了 \(R^n\) 上代数自同构的形式.

引理 1 全体 \(P_\sigma\) 构成 \(R^n\) 上全体代数自同构,即 \[ \operatorname{Aut}(R^n) = \{ P_\sigma : \sigma \in S_n \} \]

只需证对任意 \(R^n\) 上任意代数自同构 \(P\),其都可被某一置换 \(\sigma \in S_n\) 诱导得到.不妨考察 \(P\)\(R^n\) 自然基下的矩阵表示 \((p_{i,j})_{(i,j) \in n \times n}\).则 \[ P(\boldsymbol e_i) \times P(\boldsymbol e_i) = P(\boldsymbol e_i \times \boldsymbol e_i) = P(\boldsymbol e_i) \] 可分行写为对 \(k = 0,1,\dots,n-1\),都有 \(p_{k,i}^2 = p_{k,i}\),因为 \(R\) 是整环,故 \(p_{k,i}\)\(0\)\(1\),即矩阵各元素只能取 \(0\)\(1\).又对 \(i \neq j\)\[ P(\boldsymbol e_i) \times P(\boldsymbol e_j) = P(\boldsymbol e_i \times \boldsymbol e_j) = P(\boldsymbol 0) = \boldsymbol 0 \] 分行写开,得对 \(k = 0,1,\dots,n-1\),都有 \(p_{k,i} p_{k,j} = 0\).于是(由 \(R\) 是整环)矩阵任一行至多只能由一个 \(1\).假如存在第 \(k\) 行全为 \(0\),则 \(\boldsymbol e_k \notin \operatorname{Im}P\),与 \(P\) 作为自同构的满性矛盾,故 \(P\) 的矩阵表示每行有且只有一个 \(1\),其余为 \(0\)\(P\) 的某两行亦不能完全相同,否则(由鸽巢原理)矩阵某列一定全为 \(0\),与 \(P\) 作为自同构的单性矛盾.因此 \(P\) 的矩阵表示是一个置换矩阵,即 \(P\) 由一置换诱导.

DFT 的唯一性

推论 2\(f\) 是任一 \(R\) 上的 \(n\) 点 DFT,则任何 \(R\) 上的 \(n\) 点 DFT \(g\) 都具有形式 \(g = P_\sigma f\),这里 \(f\) 是一事先固定的 \(n\) 点 DFT.

作为推论,\(n\) 点 DFT 共有 \(n!\) 种.这一结果的显著性在于,只要不计求值得到的 \(n\) 个点值在 \(R^n\) 上的排列顺序,DFT 是唯一满足卷积性质的可逆线性映射.

3 DFT 与矩阵代数

第二个视角:矩阵代数

我们建立了

图 3

这一交换图可以继续扩展.将视角从多项式环转向矩阵代数,我们将看到,DFT 不仅是多项式环上的求值插值,更体现为矩阵代数上的相似对角化.

简单起见,下面只考察代数闭域的情况,并用域的常用记号 \(K\) 替代 \(R\)

相似对角化

\(C\) 是域 \(K\) 上的 \(n\) 阶可对角化矩阵,特征值两两不同.设其特征多项式(或最小多项式)为 \(m(x)\)\(\Lambda\) 为其对角化得到的矩阵.\(K[C]\)\(K[\Lambda]\) 分别是矩阵 \(C\)\(\Lambda\)\(K^{n \times n}\) 上生成的代数.

图 4

对角化 \(C\) 的矩阵也同时对角化了 \(K[C]\) 中的任意矩阵.若设这一对角化矩阵为 \(F\),则 \(A \mapsto F^{-1} A F\) 便规定了一个 \(K[C] \to K[\Lambda]\) 的代数同构.\(K^n\)\(K[\Lambda]\) 的代数同构是平凡的.下面来建立 \(K[x] / m(x)\)\(K[C]\) 间的联系.

命题 3\(C\) 是域 \(K\) 上的 \(n\) 阶矩阵,\(m(x)\) 是其最小多项式,则 \(K[x] / m(x)\)\(K[C]\) 代数同构.

仍然考察 \(K[x] \to K[C]\) 自然的“代入” \(\psi : f \mapsto f(C)\)\(C\) 的全体零化多项式恰为 \(m(x)\) 生成的 \(K[x]\) 上的理想,因此 \(\operatorname{Ker}\psi = (m(x))\)\(\psi\) 的满射性平凡.用第一同构定理就得到结论.

图 5: 命题 3 证明示意图

友矩阵

为显式刻画上述对角化过程,我们选取一类特殊的矩阵2作为 \(C\) 进行研究: \[ C = \begin{pmatrix} 0 & 1 & 0 &\ldots & 0\\ 0 & 0 & 1 &\ldots & 0 \\ 0 & 0 & 0 &\ldots & 0 \\ \vdots & \vdots & \vdots & \ddots &1\\ -c_0 & -c_1 & -c_2 & \ldots & -c_{n-1} \end{pmatrix} \] \(C\) 被称为首一多项式 \(m(x) = c^n + a_{n-1} c^{n-1} + \dots + c_0\)友矩阵(companion matrix).

2 这类矩阵在高阶常系数线性 ODE 和常系数齐次线性递推中也有重要应用.

  • 直接计算,\(C\) 的特征多项式恰为 \(m(x)\)

  • 直接验证,\((1,\lambda,\dots,\lambda^{n-1})^\mathrm{T}\) 是其特征值 \(\lambda\) 的一个特征向量.

友矩阵的最小多项式

命题 4 \(C\) 的最小多项式也恰为 \(m(x)\).等价地,友矩阵的特征多项式与最小多项式相同.

等价地,我们研究 \(C^\mathrm{T}\) 的最小多项式.注意到如下事实: \[ C^\mathrm{T}\boldsymbol e_i = \begin{cases} \boldsymbol e_{i+1} & i=0,1,\dots,n-2 \\ -\sum_{k=0}^{n-1} c_k \boldsymbol e_k & i=n-1 \end{cases} \] 考察不超过 \(n-1\) 次的多项式 \(f(x)\).假若 \(f(C^\mathrm{T}) = 0\),则 \[ \boldsymbol 0 = f(C^\mathrm{T}) \boldsymbol e_0 = \sum_{k=0}^{n-1} c_k (C^\mathrm{T})^k \boldsymbol e_0 = \sum_{k=0}^{n-1} c_k \boldsymbol e_k \] 因此 \(c_k = 0\) 对所有 \(k\) 成立,即 \(f = 0\).这说明 \(C^\mathrm{T}\) 的零化多项式次数至少为 \(n\).再用零化多项式和最小多项式的整除关系就得到结论.

上述命题的逆命题在相似意义下成立.

命题 5 若矩阵的特征多项式与最小多项式相同,则它与其特征多项式对应的友矩阵相似.

可在 Jordan 标准型下理解.此时每个特征值对应的 Jordan 块有且只有一个.

当友矩阵 \(C\) 可对角化时,其可分解为不同一次因式的乘积.又其最小多项式与特征多项式相同,故其必有 \(n\) 个两两不同的特征值 \(\lambda_0,\lambda_1,\dots,\lambda_{n-1}\).结合上述命题可以看到,我们特殊地取 \(C\) 为友矩阵做研究是不失一般性的.

友矩阵对角化的显式表达

前面已经得到友矩阵特征向量的形式,因此 Vandermonde 矩阵 \[ F = \begin{pmatrix} 1 & 1 & \dots & 1 \\ \lambda_0 & \lambda_1 & \dots & \lambda_{n-1} \\ \vdots & \vdots & \ddots & \vdots \\ \lambda_0^{n-1} & \lambda_1^{n-1} & \dots & \lambda_{n-1}^{n-1} \end{pmatrix} \] 正是将 \(C\) 对角化的矩阵. \[ F^{-1} C F = \Lambda = \operatorname{diag}(\lambda_0,\lambda_1,\dots,\lambda_{n-1}) \] 注意到 \(K[C]\) 也被对角化 \(C\) 的矩阵同时对角化,故 \(A \mapsto F^{-1} A F\) 确为 \(K[C] \to K[\Lambda]\) 的代数同构,与先前的关于对角化的讨论结果一致.

循环矩阵的对角化

特别地,若取 \[ C = \begin{pmatrix} 0 & 1 & 0 &\ldots & 0\\ 0 & 0 & 1 &\ldots & 0 \\ 0 & 0 & 0 &\ldots & 0 \\ \vdots & \vdots & \vdots & \ddots &1\\ 1 & 0 & 0 & \ldots & 0 \end{pmatrix} \] 它是基本循环矩阵,对应最小多项式 \(m(x) = x^n - 1\)\(C\) 生成的代数 \(K[C]\)\(K^{n \times n}\) 上的全体循环矩阵.此时 DFT 体现为利用 DFT 矩阵 \[ F = \begin{pmatrix} 1 & 1 & \dots & 1 \\ 1 & \omega_n & \dots & \omega_n^{n-1} \\ \vdots & \vdots & \ddots & \vdots \\ 1 & \omega_n^{n-1} & \dots & \omega_n^{(n-1)(n-1)} \end{pmatrix} \] 对循环矩阵进行对角化的过程.

结语

以刻画 DFT 的卷积性质为目标,以代数同构为构造手段,我们为理解 DFT 的代数含义提供了两个视角:

  • DFT 是多项式商环上的多点求值插值
  • DFT 是矩阵代数上的相似对角化

可见 DFT 背后的代数理论非常丰富,不失为联系起本科阶段代数课程的有趣实例,亦体现出代数工具与视角在工程实践中的强大效用.

图 6

References

[1]
R. C. Agarwal 和 C. S. Burrus, 《Number theoretic transforms to implement fast digital convolution》, Proceedings of the IEEE, 卷 63, 期 4, 页 550–560, 4月 1975, doi: 10.1109/PROC.1975.9791.
[2]
P. J. Nicholson, 《Algebraic theory of finite fourier transforms》, Journal of Computer and System Sciences, 卷 5, 期 5, 页 524–547, 10月 1971, doi: 10.1016/S0022-0000(71)80014-4.
[3]
M. Fürer, 《Faster Integer Multiplication, SIAM Journal on Computing, 卷 39, 期 3, 页 979–1005, 1月 2009, doi: 10.1137/070711761.
[4]
E. Amiot, Music Through Fourier Space. 收入 Computational Music Science. Cham: Springer International Publishing, 2016. doi: 10.1007/978-3-319-45581-5.
[5]
I. Baraquin 和 N. Ratier, 《Uniqueness of the discrete Fourier transform》, Signal Processing, 卷 209, 页 109041, 8月 2023, doi: 10.1016/j.sigpro.2023.109041.