巡回行列(じゅんかいぎょうれつ)または循環行列(じゅんかんぎょうれつ、英: Circulant matrix)は、テプリッツ行列の特殊なものであり、各行ベクトルが1つ前の行ベクトルの要素を1つずらして配置した形になっているものである。数値解析において、巡回行列は離散フーリエ変換によって対角化されるため、それを含む線型方程式系は高速フーリエ変換で高速に解くことができる。
定義
n次正方行列 C で次の形のものを巡回行列と呼ぶ。
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/188ce2b8430bae5bde83940cff5c1e1e9b3976b0)
巡回行列は1つのベクトル c で完全に表すことができる。そのベクトルは C の最初の列で表されている。他の列はそれを回転させたものになっている。C の最後の行は c を逆の順序にしたものであり、他の行はそれを回転させたものになっている。
性質
固有ベクトルと固有値
巡回行列の規格化された固有ベクトルは
![{\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,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9fa5c48f8af9179ae3b8a21af06694ae1ce64390)
で与えられ、これらは正規直交系を成す。ここで
は1のn 乗根で、
は虚数単位である。
対応する固有値は
![{\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.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3cffdb13517ca9fda8be9a219a48127ee33a7cd)
で与えられる(以上の事実は実際に Cvj を計算してみればわかる)。
その他の性質
n次の巡回行列の集合は、n次元ベクトル空間を形成する。
任意の2つの巡回行列 A, B について、A + B も AB も巡回行列となり、AB = BA が成り立つ。従って、巡回行列は可換代数を形成する。
与えられたサイズの巡回行列の固有ベクトルは、同じサイズの離散フーリエ変換行列の列である。その結果、巡回行列の固有値は高速フーリエ変換 (FFT) で簡単に計算できる。
巡回行列の最初の行のFFTを行った場合、その巡回行列の行列式はスペクトル値の積となる。
(固有分解による) ![{\displaystyle \det(C)=\det \left(W\Lambda W^{-1}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/062242cccaa1d75a756e478a5443a06570b977bd)
![{\displaystyle \det(C)=\det \left(W\right)\det \left(\Lambda \right)\det \left(W^{-1}\right)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4fa8f97dd611ecc8251a44f50b420d617ce58e95)
![{\displaystyle \det(C)=\det \left(\Lambda \right)=\textstyle \prod \limits _{k=1}^{n}\lambda _{k}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c22ac6afa6838683610add35733e90ab865fff53)
ここで
最後の項
は、スペクトル値の積と同じである。
巡回行列を使った線型方程式系の解法
線型方程式系を行列で次のように表す。
![{\displaystyle \ \mathbf {C} \mathbf {x} =\mathbf {b} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/9afd307dbcc63b33e6a0ae6b5c2d3b8387c6d0f9)
ここで、
が大きさ
の巡回行列であれば、循環畳み込みとして次のように方程式を表せる。
![{\displaystyle \ \mathbf {c} *\mathbf {x} =\mathbf {b} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/04352047c00ade059940be6ae2207cfaa4763b31)
ここで、
は
の最初の列であり、ベクトル
、
、
は双方向に循環的に拡張される。畳み込み定理を使うと、離散フーリエ変換を使って循環畳み込みを次のような形式にできる。
![{\displaystyle \ {\mathcal {F}}_{n}(\mathbf {c} *\mathbf {x} )={\mathcal {F}}_{n}(\mathbf {c} ){\mathcal {F}}_{n}(\mathbf {x} )={\mathcal {F}}_{n}(\mathbf {b} )}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a50ee45629aca3bd8b99c5d7ebb62b4aa1cf1886)
従って、次のようになる。
![{\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)
このアルゴリズムは通常のガウスの消去法よりも高速であり、特に高速フーリエ変換を使えば高速になる。
グラフ理論における応用
グラフ理論において、隣接行列が巡回行列になっているグラフをcirculant graph(循環グラフ、巡回グラフ)と呼ぶ。グラフが circulant であるとは、その自己同型群 (automorphism group) に全長サイクル (full-length cycle) が含まれる場合を指す。circulant graph の例としてメビウスの梯子がある。
外部リンク
- 『巡回行列の固有値・固有ベクトルと行列式』 - 高校数学の美しい物語
- Toeplitz and Circulant Matrices: A Review, by R. M. Gray