循环矩阵与离散 Fourier 变换

给定 $n$ 个数 $c_0,c_1,\dots,c_{n-1}$ ，循环矩阵形如

Copy LaTeX

即每一行都是上一行循环右移一位得到的。

引入基本循环移位矩阵

Copy LaTeX

显然有

Copy LaTeX

并且 $S$ 可逆， $S^{-1} = S^\top$ 就是循环左移

Copy LaTeX

一般循环矩阵可以用 $S$ 的多项式表示

Copy LaTeX

由此易得循环矩阵具有如下性质：

下面关注循环矩阵的特征系统。对于 $S$ 的特征值，计算可得

Copy LaTeX

因此所有特征值就是 $x^n - 1 = 0$ 的全部复数根，并且显然特征值两两互异，代数重数为 $1$ 。

记 $n$ 次单位根 $w = e^{2\pi i/n}$ ，则 $x^n - 1 = 0$ 的全部根为

Copy LaTeX

也就是 $S$ 的所有特征值。

Remark

$S^\top$ 就是多项式 $x^n - 1$ 对应的友方阵，由此也可以看出，循环矩阵和单位根存在密切的联系。

定义向量

Copy LaTeX

其中 $k=0,1,\dots,n-1$ 。计算可得 $\| v_k \|_2 = 1$ 以及

Copy LaTeX

因此 $v_k$ 就是 $S$ 在特征值 $w^k$ 所对应的单位特征向量。由此得到 $S$ 的酉相似对角化分解

Copy LaTeX

其中 $F$ 是特征向量组成的过渡矩阵

Copy LaTeX

验证可知这是一个酉方阵，其实就是著名的离散 Fourier 矩阵（根据习惯不同，也可能差一个常系数倍）。

由于一般的循环矩阵都可以用 $S$ 的多项式表示 $f(S)$ ，易得

Copy LaTeX

因此任意循环矩阵 $f(S)$ 都可以用公共的离散 Fourier 矩阵进行酉相似对角化，只是全体特征值变为

Copy LaTeX

其中 $f(1) = \sum_{i=0}^{n-1} c_i$ 就是循环矩阵的一行求和。

Remark

离散 Fourier 矩阵可以把所有循环矩阵同时酉相似对角化。

酉相似对角化可以让循环矩阵的 $m$ 次幂计算非常简单：（由循环矩阵乘法封闭性，循环矩阵的 $m$ 次幂还是一个循环矩阵）

Copy LaTeX

Example

考虑三阶循环矩阵（ $a,b,c \in \mathbb{R}$ ）

Copy LaTeX

计算特征系统和 $n$ 次幂。

Solution

记多项式

Copy LaTeX

记单位根

Copy LaTeX

离散 Fourier 矩阵为

Copy LaTeX

三个特征值具体为

Copy LaTeX

因此

Copy LaTeX

具体展开计算

Copy LaTeX

其中

Copy LaTeX