循環矩陣

在線性代數中，循環矩陣是一種特殊形式的 Toeplitz矩陣，它的列向量的每個元素都是前一個列向量各元素依次右移一個位置得到的結果。由於可以用離散傅立葉變換快速解循環矩陣，所以在數值分析中有重要的應用。

定義

形式為

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}}

的 $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 就是輪換圖的例子。