查看“︁循环矩阵”︁的源代码

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

==定义==

形式为
:<math>C = \begin{bmatrix}
c_0      & c_{n-1} & \cdots  & c_2     & c_1     \\
c_1      & c_0     & c_{n-1} &         & c_2     \\
\vdots   & c_1     & c_0     & \ddots  & \vdots  \\
c_{n-2}  &         & \ddots  & \ddots  & c_{n-1} \\
c_{n-1}  & c_{n-2} & \cdots  & c_1     & c_0     \\
\end{bmatrix}</math>

的 <math>n\times n</math> 矩阵 ''C'' 就是'''循环矩阵'''。

==特性==
循环矩阵遵循[[代数]]运算法则。对于两个循环矩阵 ''A'' 与 ''B'' 来说，''A'' + ''B'' 也是循环矩阵。''AB'' 也是循环矩阵，并且 <math>AB = BA</math>。

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

:<math>\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.</math>

其中<math>\omega_j=\exp \left(i \tfrac{2\pi j}{n}\right)</math>。

== 对称循环矩阵 ==
[[对称矩阵]] <math>C</math> 附加一个条件 <math>c_{n-i}=c_i</math>。
因此可由 <math>\lfloor n/2\rfloor + 1</math> 个元素定义。
:<math>
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}.
</math>

实对称矩阵的所有特征值都是实数，对于上述定义的实对称循环矩阵，这些特征值在<math>n</math>为偶数时为
:<math>
\lambda_j = c_0 + 2 c_1 \Re \omega_j + 2 c_2 \Re \omega_j^2 +  \ldots + 2c_{n/2-1} \Re \omega_j^{n/2-1}  + c_{n/2} \omega_j^{n/2} </math>
在<math>n</math>为奇数时为
:<math>
\lambda_j = c_0 + 2 c_1 \Re \omega_j + 2 c_2 \Re \omega_j^2 +  \ldots + 2c_{(n-1)/2} \Re \omega_j^{(n-1)/2}
 </math> 
其中<math>\Re </math>表示取实部。
利用<math>\Re \omega_j^k= \cos(2\pi j k/n)</math>，可进一步简化。

==用循环矩阵来解线性方程==

设矩阵方程
:<math>
\mathbf{C} \mathbf{x} = \mathbf{b}
</math>

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

:<math>\mathbf{c} * \mathbf{x} = \mathbf{b}</math>

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

:<math>\mathcal{F}_{n}(\mathbf{c} * \mathbf{x}) = \mathcal{F}_{n}(\mathbf{c}) \mathcal{F}_{n}(\mathbf{x}) = \mathcal{F}_{n}(\mathbf{b})</math>

因此

:<math>\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 ].
</math>

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

==在图论中的应用==

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

==外部链接==
*[http://www-ee.stanford.edu/~gray/toeplitz.pdf Toeplitz and Circulant Matrices: A Review, by R. M. Gray] {{Wayback|url=http://www-ee.stanford.edu/~gray/toeplitz.pdf |date=20131111110156 }}

[[Category:矩陣|X]]
[[Category:数值线性代数|X]]