巡回行列

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

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

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

 性質 

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

で与えられ、これらは正規直交系を成す。ここで は1のn 乗根で、 は虚数単位である。

対応する固有値は

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

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

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

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

巡回行列の最初の行のFFTを行った場合、その巡回行列の行列式はスペクトル値の積となる。
（固有分解による）

ここで
 は 次の巡回行列である
 は、ユニタリーな離散フーリエ変換行列である
 は、固有値が  の対角行列である
最後の項  は、スペクトル値の積と同じである。

 巡回行列を使った線型方程式系の解法 
線型方程式系を行列で次のように表す。

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

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

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

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

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

 外部リンク 

Toeplitz and Circulant Matrices: A Review, by R. M. Gray

Category:行列
Category:数値線形代数
Category:組合せ論
Category:数学に関する記事