この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方 ） 出典検索? "巡回行列" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL （2017年5月
巡回行列 （じゅんかいぎょうれつ）または循環行列 （じゅんかんぎょうれつ、英 : 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 の例としてメビウスの梯子がある。
外部リンク 
![{\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]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b682183caadd5e5974485e99ea87d1b8bbd53ba0)
全ての辞書から巡回行列
を検索
