循环矩阵

维基百科,自由的百科全书
跳转至: 导航搜索

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

定义[编辑]

形式为


C=
\begin{bmatrix}
c_1     & c_2 & c_3 & \dots  & c_n     \\
c_n     & c_1 & c_2 &        & c_{n-1} \\
c_{n-1} & c_n & c_1 &        & c_{n-2} \\
\vdots  &     &     & \ddots & \vdots  \\
c_2     & c_3 & c_4 & \dots  & c_1
\end{bmatrix}

n\times n 矩阵 C 就是循环矩阵

特性[编辑]

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

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

用循环矩阵来解线性方程[编辑]

设矩阵方程


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

其中 Cn 维方形循环矩阵,这样就可以将方程表示成循环卷积

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

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

\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 就是轮换图的例子。

外部链接[编辑]