巡回行列

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

定義

n次正方行列 C で次の形のものを巡回行列と呼ぶ。

C = [ c 0 c n − 1 … c 2 c 1 c 1 c 0 c n − 1 c 2 ⋮ c 1 c 0 ⋱ ⋮ c n − 2 ⋱ ⋱ c n − 1 c n − 1 c n − 2 … c 1 c 0 ] {\displaystyle C={\begin{bmatrix}c_{0}&c_{n-1}&\dots &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}&\dots &c_{1}&c_{0}\end{bmatrix}}}

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

性質

固有ベクトルと固有値

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

v j = 1 n ( 1 ,   ω j ,   ω j 2 ,   … ,   ω j n − 1 ) T , j = 0 , 1 , … , n − 1 , {\displaystyle v_{j}={\frac {1}{\sqrt {n}}}(1,~\omega _{j},~\omega _{j}^{2},~\ldots ,~\omega _{j}^{n-1})^{T},\quad j=0,1,\ldots ,n-1,}

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

対応する固有値は

λ j = c 0 + c n − 1 ω j + c n − 2 ω j 2 + … + c 1 ω j n − 1 , j = 0 … n − 1. {\displaystyle \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\ldots n-1.}

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

その他の性質

n次の巡回行列の集合は、n次元ベクトル空間を形成する。

任意の2つの巡回行列 A, B について、A + B も AB も巡回行列となり、AB = BA が成り立つ。従って、巡回行列は可換代数を形成する。

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

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

C = W Λ W − 1 {\displaystyle C=W\Lambda W^{-1}} （固有分解による）
det ( C ) = det ( W Λ W − 1 ) {\displaystyle \det(C)=\det \left(W\Lambda W^{-1}\right)}
det ( C ) = det ( W ) det ( Λ ) det ( W − 1 ) {\displaystyle \det(C)=\det \left(W\right)\det \left(\Lambda \right)\det \left(W^{-1}\right)}
det ( C ) = det ( Λ ) = ∏ k = 1 n λ k {\displaystyle \det(C)=\det \left(\Lambda \right)=\textstyle \prod \limits _{k=1}^{n}\lambda _{k}}

ここで

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

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

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

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

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

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

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

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

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

  x = F n − 1 [ ( ( F n ( b ) ) ν ( F n ( c ) ) ν ) ν ∈ Z ] {\displaystyle \ \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]}

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

グラフ理論における応用

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

外部リンク

  • 『巡回行列の固有値・固有ベクトルと行列式』 - 高校数学の美しい物語
  • Toeplitz and Circulant Matrices: A Review, by R. M. Gray