巡回行列のソースを表示

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

== 定義 ==
{{mvar|n}}次正方行列 {{mvar|C}} で次の形のものを'''巡回行列'''と呼ぶ。
:<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つのベクトル {{mvar|c}} で完全に表すことができる。そのベクトルは {{mvar|C}} の最初の列で表されている。他の列はそれを回転させたものになっている。{{mvar|C}} の最後の行は {{mvar|c}} を逆の順序にしたものであり、他の行はそれを回転させたものになっている。

== 性質 ==

=== 固有ベクトルと固有値 ===
巡回行列の規格化された固有ベクトルは
:<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の冪根|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>

で与えられる(以上の事実は実際に ''Cv<sub>j</sub>'' を計算してみればわかる)。

=== その他の性質 ===
{{mvar|n}}次の巡回行列の[[集合]]は、{{mvar|n}}[[次元]][[ベクトル空間]]を形成する。

任意の2つの巡回行列 {{math2|''A'', ''B''}} について、{{math2|''A'' + ''B''}} も {{mvar|AB}} も巡回行列となり、{{math2|1=''AB'' = ''BA''}} が成り立つ。従って、巡回行列は[[可換環|可換代数]]を形成する。

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

巡回行列の最初の行のFFTを行った場合、その巡回行列の[[行列式]]はスペクトル値の積となる。
:<math>C = W \Lambda W^{-1}</math>（固有分解による）
:<math>\det (C) = \det \left( W \Lambda W^{-1} \right)</math>
:<math>\det (C) = \det \left( W \right) \det \left( \Lambda \right) \det \left( W^{-1} \right)</math>
:<math>\det (C) = \det \left( \Lambda \right) = \textstyle\prod\limits_{k=1}^n \lambda_k</math>

ここで
*{{mvar|C}} は {{mvar|n}}次の巡回行列である
*{{mvar|W}} は、ユニタリーな[[離散フーリエ変換]]行列である
*{{math|Λ}} は、固有値が {{mvar|λ{{sub|k}}}} の[[対角行列]]である
最後の項 <math>\textstyle\prod\limits_{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 の例として[[メビウスの梯子]]がある。

== 外部リンク ==
*{{高校数学の美しい物語|2289|巡回行列の固有値・固有ベクトルと行列式}}
*[https://ee.stanford.edu/~gray/toeplitz.pdf Toeplitz and Circulant Matrices: A Review, by R. M. Gray]

{{DEFAULTSORT:しゆんかいきようれつ}}
[[Category:行列]]
[[Category:数値線形代数]]
[[Category:組合せ論]]
[[Category:数学に関する記事]]