巡回行列
巡回行列（じゅんかいぎょうれつ）または循環行列（じゅんかんぎょうれつ、英: Circulant matrix）は、テプリッツ行列の特殊なものであり、各行ベクトルが1つ前の行ベクトルの要素を1つずらして配置した形になっているものである。数値解析において、巡回行列は離散フーリエ変換によって対角化されるため、それを含む線型方程式系は高速フーリエ変換で高速に解くことができる。
定義
[math]n\times n[/math] の行列 [math]\ C[/math] が次のような形式であるとき、これを巡回行列と呼ぶ。
- [math] 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} [/math]
巡回行列は1つのベクトル [math]\ c[/math] で完全に表すことができる。そのベクトルは [math]\ C[/math] の最初の列で表されている。他の列はそれを回転させたものになっている。[math]\ C[/math] の最後の行は [math]\ c[/math] を逆の順序にしたものであり、他の行はそれを回転させたものになっている。
性質
固有ベクトルと固有値
巡回行列の規格化された固有ベクトルは
- [math]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,[/math]
で与えられる。ここで[math]\omega_j=\exp \left(\tfrac{2\pi i j}{n}\right)[/math] は1のn 乗根で、[math]i[/math] は虚数単位である。
対応する固有値は
- [math]\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.[/math]
で与えられる。
その他の性質
[math]n\times n[/math] の巡回行列の集合は、n-次元ベクトル空間を形成する。
任意の2つの巡回行列 [math]\ A[/math] と [math]\ B[/math] について、[math]\ A + B[/math] も [math]\ AB[/math] も巡回行列となり、[math]\ AB = BA[/math] が成り立つ。従って、巡回行列は可換代数を形成する。
与えられたサイズの巡回行列の固有ベクトルは、同じサイズの離散フーリエ変換行列の列である。その結果、巡回行列の固有値は高速フーリエ変換 (FFT) で簡単に計算できる。
巡回行列の最初の行のFFTを行った場合、その巡回行列の行列式はスペクトル値の積となる。
- [math]\ C = W \Lambda W^{-1}[/math] （固有分解による）
- [math]\ \operatorname{det}(C) = \operatorname{det}\left(W \Lambda W^{-1}\right)[/math]
- [math]\ \operatorname{det}(C) = \operatorname{det}\left(W\right) \operatorname{det}\left(\Lambda\right) \operatorname{det}\left(W^{-1}\right)[/math]
- [math]\ \operatorname{det}(C) = \operatorname{det}\left(\Lambda\right) = \prod_{k=1}^{n} \lambda_k[/math]
ここで
- [math]\ C[/math] は [math]n\times n[/math] の巡回行列である
- [math]\ W[/math] は、ユニタリーな離散フーリエ変換行列である
- [math]\ \Lambda[/math] は、固有値が [math]\ \lambda_k[/math] の対角行列である
最後の項 [math]\ \Pi_{k=1}^{n} \lambda_k[/math] は、スペクトル値の積と同じである。
巡回行列を使った線型方程式系の解法
線型方程式系を行列で次のように表す。
- [math] \ \mathbf{C} \mathbf{x} = \mathbf{b} [/math]
ここで、[math]\ C[/math] が大きさ [math]\ n[/math] の巡回行列であれば、循環畳み込みとして次のように方程式を表せる。
- [math]\ \mathbf{c} * \mathbf{x} = \mathbf{b}[/math]
ここで、[math]\ c[/math] は [math]\ C[/math] の最初の列であり、ベクトル [math]\ c[/math]、[math]\ x[/math]、[math]\ b[/math] は双方向に循環的に拡張される。畳み込み定理を使うと、離散フーリエ変換を使って循環畳み込みを次のような形式にできる。
- [math]\ \mathcal{F}_{n}(\mathbf{c} * \mathbf{x}) = \mathcal{F}_{n}(\mathbf{c}) \mathcal{F}_{n}(\mathbf{x}) = \mathcal{F}_{n}(\mathbf{b})[/math]
従って、次のようになる。
- [math]\ \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 ]. [/math]
このアルゴリズムは通常のガウスの消去法よりも高速であり、特に高速フーリエ変換を使えば高速になる。
グラフ理論における応用
グラフ理論において、隣接行列が巡回行列になっているグラフをcirculant graph（循環グラフ、巡回グラフ）と呼ぶ。グラフが circulant であるとは、その自己同型群（automorphism group）に全長サイクル（full-length cycle）が含まれる場合を指す。circulant graph の例としてメビウスの梯子がある。