巡回行列

テンプレート:出典の明記 巡回行列（じゅんかいぎょうれつ）または循環行列（じゅんかんぎょうれつ、テンプレート:Lang-en-short）は、テプリッツ行列の特殊なものであり、各行ベクトルが1つ前の行ベクトルの要素を1つずらして配置した形になっているものである。数値解析において、巡回行列は離散フーリエ変換によって対角化されるため、それを含む線型方程式系は高速フーリエ変換で高速に解くことができる。

定義

テンプレート:Mvar次正方行列 テンプレート:Mvar で次の形のものを巡回行列と呼ぶ。

$C=\left[\begin{array}{ccccc}{c}_0& c_{n-1}& \dots & c_2& c_1\\ c_1& c_0& c_{n-1}& & c_2\\ ⋮& c_1& c_0& \ddots & ⋮\\ c_{n-2}& & \ddots & \ddots & c_{n-1}\\ c_{n-1}& c_{n-2}& \dots & c_1& c_0\end{array}\right]$

巡回行列は1つのベクトル テンプレート:Mvar で完全に表すことができる。そのベクトルは テンプレート:Mvar の最初の列で表されている。他の列はそれを回転させたものになっている。テンプレート:Mvar の最後の行は テンプレート:Mvar を逆の順序にしたものであり、他の行はそれを回転させたものになっている。

性質

固有ベクトルと固有値

巡回行列の規格化された固有ベクトルは

$v_j=\frac{1}{\sqrt{n}}(1,{\omega }_j,{\omega }_j^2,\dots ,{\omega }_j^{n-1}{)}^T,j=0,1,\dots ,n-1,$

で与えられ、これらは正規直交系を成す。ここで${\omega }_j=\exp \left(\frac{2\pi ij}{n}\right)$ は1のn 乗根で、$i$ は虚数単位である。

対応する固有値は

${\lambda }_j=c_0+c_{n-1}{\omega }_j+c_{n-2}{\omega }_j^2+\dots +c_1{\omega }_j^{n-1},j=0\dots n-1.$

で与えられる(以上の事実は実際に Cv_j を計算してみればわかる)。

その他の性質

テンプレート:Mvar次の巡回行列の集合は、テンプレート:Mvar次元ベクトル空間を形成する。

任意の2つの巡回行列 テンプレート:Math2 について、テンプレート:Math2 も テンプレート:Mvar も巡回行列となり、テンプレート:Math2 が成り立つ。従って、巡回行列は可換代数を形成する。

与えられたサイズの巡回行列の固有ベクトルは、同じサイズの離散フーリエ変換行列の列である。その結果、巡回行列の固有値は高速フーリエ変換 (FFT) で簡単に計算できる。

巡回行列の最初の行のFFTを行った場合、その巡回行列の行列式はスペクトル値の積となる。

$C=W\mathrm{\Lambda }{W}^{-1}$（固有分解による）

$\det (C)=\det \left(W\mathrm{\Lambda }{W}^{-1}\right)$

$\det (C)=\det \left(W\right)\det \left(\mathrm{\Lambda }\right)\det \left(W^{-1}\right)$

$\det (C)=\det \left(\mathrm{\Lambda }\right)=\prod _{k=1}^n{\lambda }_k$

ここで

• テンプレート:Mvar は テンプレート:Mvar次の巡回行列である
• テンプレート:Mvar は、ユニタリーな離散フーリエ変換行列である
• テンプレート:Math は、固有値が テンプレート:Mvar の対角行列である

最後の項 $\prod _{k=1}^n{\lambda }_k$ は、スペクトル値の積と同じである。

巡回行列を使った線型方程式系の解法

線型方程式系を行列で次のように表す。

$𝐂𝐱=𝐛$

ここで、$C$ が大きさ $n$ の巡回行列であれば、循環畳み込みとして次のように方程式を表せる。

$𝐜*𝐱=𝐛$

ここで、$c$ は $C$ の最初の列であり、ベクトル $c$、$x$、$b$ は双方向に循環的に拡張される。畳み込み定理を使うと、離散フーリエ変換を使って循環畳み込みを次のような形式にできる。

${ℱ}_n(𝐜*𝐱)={ℱ}_n(𝐜){ℱ}_n(𝐱)={ℱ}_n(𝐛)$

従って、次のようになる。

$𝐱={ℱ}_n^{-1}\left[{\left(\frac{({ℱ}_n(𝐛){)}_{\nu }}{({ℱ}_n(𝐜){)}_{\nu }}\right)}_{\nu \in 𝐙}\right]$

このアルゴリズムは通常のガウスの消去法よりも高速であり、特に高速フーリエ変換を使えば高速になる。

グラフ理論における応用

グラフ理論において、隣接行列が巡回行列になっているグラフをcirculant graph（循環グラフ、巡回グラフ）と呼ぶ。グラフが circulant であるとは、その自己同型群 (automorphism group) に全長サイクル (full-length cycle) が含まれる場合を指す。circulant graph の例としてメビウスの梯子がある。

外部リンク

• テンプレート:高校数学の美しい物語
• Toeplitz and Circulant Matrices: A Review, by R. M. Gray