巡回行列

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

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

定義[編集]

n\times n の行列 \ C が次のような形式であるとき、これを巡回行列と呼ぶ。


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 を逆の順序にしたものであり、他の行はそれを回転させたものになっている。

特性[編集]

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

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

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

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

\ C = W \Lambda W^{-1} (固有分解による)
\ \operatorname{det}(C) = \operatorname{det}\left(W \Lambda W^{-1}\right)
\ \operatorname{det}(C) = \operatorname{det}\left(W\right) \operatorname{det}\left(\Lambda\right) \operatorname{det}\left(W^{-1}\right)
\ \operatorname{det}(C) = \operatorname{det}\left(\Lambda\right) = \prod_{k=1}^{n} \lambda_k

ここで

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

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

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


\ \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 ].

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

グラフ理論における応用[編集]

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

外部リンク[編集]