巡回行列（じゅんかいぎょうれつ）または循環行列（じゅんかんぎょうれつ、）は、テプリッツ行列の特殊なものであり、各行ベクトルが1つ前の行ベクトルの要素を1つずらして配置した形になっているものである。数値解析において、巡回行列は離散フーリエ変換によって対角化されるため、それを含む線型方程式系は高速フーリエ変換で高速に解くことができる。formula_1 の行列 formula_2 が次のような形式であるとき、これを巡回行列と呼ぶ。巡回行列は1つのベクトル formula_4 で完全に表すことができる。そのベクトルは formula_2 の最初の列で表されている。他の列はそれを回転させたものになっている。formula_2 の最後の行は formula_4 を逆の順序にしたものであり、他の行はそれを回転させたものになっている。巡回行列の規格化された固有ベクトルはで与えられる。ここでformula_9 は1のn 乗根で、formula_10 は虚数単位である。対応する固有値はで与えられる。formula_1 の巡回行列の集合は、"n"-次元ベクトル空間を形成する。任意の2つの巡回行列 formula_13 と formula_14 について、formula_15 も formula_16 も巡回行列となり、formula_17 が成り立つ。従って、巡回行列は可換代数を形成する。与えられたサイズの巡回行列の固有ベクトルは、同じサイズの離散フーリエ変換行列の列である。その結果、巡回行列の固有値は高速フーリエ変換 (FFT) で簡単に計算できる。巡回行列の最初の行のFFTを行った場合、その巡回行列の行列式はスペクトル値の積となる。ここで最後の項 formula_27 は、スペクトル値の積と同じである。線型方程式系を行列で次のように表す。ここで、formula_2 が大きさ formula_30 の巡回行列であれば、循環畳み込みとして次のように方程式を表せる。ここで、formula_4 は formula_2 の最初の列であり、ベクトル formula_4、formula_35、formula_36 は双方向に循環的に拡張される。畳み込み定理を使うと、離散フーリエ変換を使って循環畳み込みを次のような形式にできる。従って、次のようになる。このアルゴリズムは通常のガウスの消去法よりも高速であり、特に高速フーリエ変換を使えば高速になる。グラフ理論において、隣接行列が巡回行列になっているグラフをcirculant graph（循環グラフ、巡回グラフ）と呼ぶ。グラフが circulant であるとは、その自己同型群（automorphism group）に全長サイクル（full-length cycle）が含まれる場合を指す。circulant graph の例としてメビウスの梯子がある。

出典:wikipedia