循环矩阵

在线性代数中，循环矩阵是一种特殊形式的 Toeplitz矩阵，它的列向量的每个元素都是前一个列向量各元素依次右移一个位置得到的结果。由于可以用离散傅立叶变换快速解循环矩阵，所以在数值分析中有重要的应用。

定义

形式为

C={\begin{bmatrix}c_{0}&c_{n-1}&c_{n-2}&\dots &c_{1}\\c_{1}&c_{0}&c_{n-1}&c_{2}\\c_{2}&c_{1}&c_{0}&c_{n-1}\\\vdots &&&\ddots &\vdots \\c_{n-1}&c_{n-2}&c_{n-3}&\dots &c_{0}\end{bmatrix}}

的 $n\times n$ 矩阵 C 就是循环矩阵。

循环矩阵遵循代数运算法则。对于两个循环矩阵 A 与 B 来说，A + B 也是循环矩阵。AB 也是循环矩阵，并且 $AB=BA$ 。

循环矩阵的特征向量矩阵是同样维数的离散傅立叶变换矩阵，因此循环矩阵的特征值可以很容易地通过快速傅立叶变换计算出来。具体对应关系为

\lambda _{j}=c_{0}+c_{n-1}\omega _{j}+c_{n-2}\omega _{j}^{2}+\ldots +c_{1}\omega _{j}^{n-1},\qquad j=0,1,\ldots ,n-1.

其中 $\omega _{j}=\exp \left(i{\tfrac {2\pi j}{n}}\right)$ 。

对称矩阵 $C$ 附加一个条件 $c_{n-i}=c_{i}$ 。因此可由 $\lfloor n/2\rfloor +1$ 个元素定义。

C={\begin{bmatrix}c_{0}&c_{1}&\dots &c_{2}&c_{1}\\c_{1}&c_{0}&c_{1}&&c_{2}\\\vdots &c_{1}&c_{0}&\ddots &\vdots \\c_{2}&&\ddots &\ddots &c_{1}\\c_{1}&c_{2}&\dots &c_{1}&c_{0}\\\end{bmatrix}}.

实对称矩阵的所有特征值都是实数，对于上述定义的实对称循环矩阵，这些特征值在 $n$ 为偶数时为

\lambda _{j}=c_{0}+2c_{1}\Re \omega _{j}+2c_{2}\Re \omega _{j}^{2}+\ldots +2c_{n/2-1}\Re \omega _{j}^{n/2-1}+c_{n/2}\omega _{j}^{n/2}

在 $n$ 为奇数时为

\lambda _{j}=c_{0}+2c_{1}\Re \omega _{j}+2c_{2}\Re \omega _{j}^{2}+\ldots +2c_{(n-1)/2}\Re \omega _{j}^{(n-1)/2}

其中 $\Re$ 表示取实部。利用 $\Re \omega _{j}^{k}=\cos(2\pi jk/n)$ ，可进一步简化。

设矩阵方程

\mathbf {C} \mathbf {x} =\mathbf {b}

其中 C 是 n 维方形循环矩阵，这样就可以将方程表示成循环卷积

\mathbf {c} *\mathbf {x} =\mathbf {b}

其中 c 是循环矩阵 C 的第一列，c、x与b分别向每个方向循环。用离散傅立叶变换将循环卷积转换成两个变量之间的乘积

{\mathcal {F}}_{n}(\mathbf {c} *\mathbf {x} )={\mathcal {F}}_{n}(\mathbf {c} ){\mathcal {F}}_{n}(\mathbf {x} )={\mathcal {F}}_{n}(\mathbf {b} )

因此

\mathbf {x} ={\mathcal {F}}_{n}^{-1}\left[\left({\frac {({\mathcal {F}}_{n}(\mathbf {b} ))_{\nu }}{({\mathcal {F}}_{n}(\mathbf {c} ))_{\nu }}}\right)_{\nu \in \mathbf {Z} }\right].

这个算法比标准的高斯消元法的速度要快很多，尤其是当使用快速傅立叶变换的时候更是如此。

在图论中，邻接矩阵为循环矩阵的图与有向图叫作轮换图。同样，如果图的自同构群包含全部的循环，那么图就是轮换图。Möbius ladder 就是轮换图的例子。