循環行列

線型代数において、巡回行列は、すべての行が同じ要素で構成され、各行が前の行に対して 1 要素右に回転している正方行列です。これは、テプリッツ行列の特別な種類です。

数値解析において、巡回行列は離散フーリエ変換によって対角化されるため重要であり、そのため巡回行列を含む線形方程式は高速フーリエ変換を使用して迅速に解くことができます。^{[1]これらは}巡回群上の畳み込み演算子の積分核 として解析的に解釈できるため、空間不変の線形演算の形式的な記述で頻繁に使用されます。この特性は、巡回プレフィックスを使用してシンボル（ビット）を拡散するために直交周波数分割多重を使用する最新のソフトウェア定義無線でも重要です。これにより、チャネルを巡回行列で表すことができ、周波数領域でのチャネル均等化が簡素化されます。 ${\displaystyle C_{n}}$

暗号化では、巡回行列はAdvanced Encryption StandardのMixColumnsステップで使用されます。

巡回行列は、形式 またはこの形式の転置(表記の選択による) をとります。各 が正方行列である場合、その行列はブロック巡回行列と呼ばれます。 ${\displaystyle n\times n}$ ${\displaystyle C}$$${\displaystyle C={\begin{bmatrix}c_{0}&c_{n-1}&\cdots &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}&\cdots &c_{1}&c_{0}\\\end{bmatrix}}}$$${\displaystyle c_{i}}$${\displaystyle p\times p}$${\displaystyle np\times np}$${\displaystyle C}$

巡回行列は、の最初の列 (または行) として現れる1 つのベクトル によって完全に指定されます。 の残りの列 (および行) はそれぞれ、行がからまでインデックス付けされている場合、列 (または行) のインデックスに等しいオフセットを持つベクトルの巡回置換です。 (行の巡回置換は、列の巡回置換と同じ効果があります。) の最後の行は、ベクトルを逆に 1 つシフトしたものです。 ${\displaystyle c}$${\displaystyle C}$${\displaystyle C}$${\displaystyle c}$${\displaystyle 0}$${\displaystyle n-1}$${\displaystyle C}$${\displaystyle c}$

さまざまな情報源が、巡回行列をさまざまな方法で定義します。たとえば、上記のように定義したり、行列の最初の列ではなく最初の行に対応するベクトルを使用したり、シフトの方向が異なる場合もあります (これは、反巡回行列と呼ばれることもあります)。 ${\displaystyle c}$

多項式は 行列の関連多項式と呼ばれます。 ${\displaystyle f(x)=c_{0}+c_{1}x+\dots +c_{n-1}x^{n-1}}$${\displaystyle C}$

巡回行列の正規化された固有ベクトルはフーリエモード、つまり、 は1 の原始-乗根であり、は虚数単位です。 $${\displaystyle v_{j}={\frac {1}{\sqrt {n}}}\left(1,\omega ^{j},\omega ^{2j},\ldots ,\omega ^{(n-1)j}\right)^{T},\quad j=0,1,\ldots ,n-1,}$$${\displaystyle \omega =\exp \left({\tfrac {2\pi i}{n}}\right)}$${\displaystyle n}$${\displaystyle i}$

(これは、巡回行列との乗算が畳み込みを実装することを理解することで理解できます。フーリエ空間では、畳み込みは乗算になります。したがって、巡回行列とフーリエ モードの積は、そのフーリエ モードの倍数、つまり固有ベクトルになります。)

対応する固有値は次のように与えられる。 $${\displaystyle \lambda _{j}=c_{0}+c_{1}\omega ^{j}+c_{2}\omega ^{2j}+\dots +c_{n-1}\omega ^{(n-1)j},\quad j=0,1,\dots ,n-1.}$$

上記の固有値の明示的な公式の結果として、巡回行列の行列式は次のように計算できます。 転置しても行列の固有値は変化しないので、同等の定式化は次のようになります 。$${\displaystyle \det C=\prod _{j=0}^{n-1}(c_{0}+c_{n-1}\omega ^{j}+c_{n-2}\omega ^{2j}+\dots +c_{1}\omega ^{(n-1)j}).}$$$${\displaystyle \det C=\prod _{j=0}^{n-1}(c_{0}+c_{1}\omega ^{j}+c_{2}\omega ^{2j}+\dots +c_{n-1}\omega ^{(n-1)j})=\prod _{j=0}^{n-1}f(\omega ^{j}).}$$

巡回行列の階数はに等しく、 は多項式の次数です。^[2]${\displaystyle C}$${\displaystyle nd}$${\displaystyle d}$${\displaystyle \gcd(f(x),x^{n}-1)}$

• 巡回行列は巡回置換行列 の行列多項式（すなわち、関連する多項式）である。ここで、は付随行列によって与えられる。${\displaystyle P}$$${\displaystyle C=c_{0}I+c_{1}P+c_{2}P^{2}+\dots +c_{n-1}P^{n-1}=f(P),}$$${\displaystyle P}$ $${\displaystyle P={\begin{bmatrix}0&0&\cdots &0&1\\1&0&\cdots &0&0\\0&\ddots &\ddots &\vdots &\vdots \\\vdots &\ddots &\ddots &0&0\\0&\cdots &0&1&0\end{bmatrix}}.}$$
• 巡回行列の集合は、加算とスカラー乗算に関して 次元ベクトル空間を形成します。この空間は、 、 の位数の巡回群上の関数の空間として解釈できます。または、の群環として解釈することもできます。${\displaystyle n\times n}$${\displaystyle n}$ ${\displaystyle n}$${\displaystyle C_{n}}$${\displaystyle C_{n}}$
• 巡回行列は可換代数を形成します。これは、任意の 2 つの巡回行列とに対して、その和が巡回行列であり、積が巡回行列であり、であるためです。${\displaystyle A}$${\displaystyle B}$${\displaystyle A+B}$${\displaystyle AB}$${\displaystyle AB=BA}$
• 非特異巡回行列の場合、その逆行列も巡回行列です。特異巡回行列の場合、そのムーア・ペンローズ擬似逆行列は巡回行列です。${\displaystyle A}$ ${\displaystyle A^{-1}}$ ${\displaystyle A^{+}}$
• 次数の離散フーリエ変換行列は次のように定義される。${\displaystyle n}$

$${\displaystyle F_{n}=(f_{jk}){\text{ ただし }}f_{jk}=e^{-2\pi i/n\cdot jk},\,{\text{ }}0\leq j,k\leq n-1 の場合。}$$ 巡回行列とDFT行列の間には重要な関係があります。実際、 が の最初の列であることを示すことができます。 の固有値はの積で与えられます。この積は高速フーリエ変換によって簡単に計算できます。^[3]$${\displaystyle C=F_{n}^{-1}\operatorname {diag} (F_{n}c)F_{n},}$$${\displaystyle c}$${\displaystyle C}$${\displaystyle C}$${\displaystyle F_{n}c}$

• を巡回行列の（モニック）特性多項式とする。スケールされた導関数は、次の部分行列の特性多項式である（証明については^[4]を参照）。${\displaystyle p(x)}$${\displaystyle n\times n}$${\displaystyle C}$ ${\textstyle {\frac {1}{n}}p'(x)}$${\displaystyle (n-1)\times (n-1)}$${\displaystyle C}$$${\displaystyle C_{n-1}={\begin{bmatrix}c_{0}&c_{n-1}&\cdots &c_{3}&c_{2}\\c_{1}&c_{0}&c_{n-1}&&c_{3}\\\vdots &c_{1}&c_{0}&\ddots &\vdots \\c_{n-3}&&\ddots &\ddots &c_{n-1}\\c_{n-2}&c_{n-3}&\cdots &c_{1}&c_{0}\\\end{bmatrix}}}$$

巡回行列は幾何学的に解釈することができ、離散フーリエ変換との関連を説明します。

のベクトルを、周期 の整数上の関数（つまり、周期的な双無限列: ）として考えます。または、幾何学的には、正-角形 （の頂点）上の、位数の巡回群（または と表記）上の関数として同等に考えます。これは、実数直線または円上の周期関数の離散的な類似物です。 ${\displaystyle \mathbb {R} ^{n}}$${\displaystyle n}$${\displaystyle \dots ,a_{0},a_{1},\dots ,a_{n-1},a_{0},a_{1},\dots }$${\displaystyle n}$${\displaystyle C_{n}}$${\displaystyle \mathbb {Z} /n\mathbb {Z} }$${\displaystyle n}$

そして、作用素理論の観点からは、巡回行列は離散積分変換の核、つまり関数の畳み込み演算子であり、これは離散巡回畳み込みである。関数の畳み込みの式は、 ${\displaystyle (c_{0},c_{1},\dots ,c_{n-1})}$${\displaystyle (b_{i}):=(c_{i})*(a_{i})}$

${\displaystyle b_{k}=\sum _{i=0}^{n-1}a_{i}c_{k-i}}$

(シーケンスは周期的であることを思い出してください) これは、ベクトルと巡回行列の積です。 ${\displaystyle (a_{i})}$${\displaystyle (c_{i})}$

離散フーリエ変換は畳み込みを乗算に変換します。これは行列設定では対角化に対応します。

複素要素を持つすべての巡回行列の -代数は、群-代数と同型である。${\displaystyle C^{*}}$${\displaystyle C^{*}}$${\displaystyle \mathbb {Z} /n\mathbb {Z} .}$

対称循環行列の場合、という追加条件があります。したがって、これは要素によって決定されます。 ${\displaystyle C}$${\displaystyle c_{n-i}=c_{i}}$${\displaystyle \lfloor n/2\rfloor +1}$$${\displaystyle C={\begin{bmatrix}c_{0}&c_{1}&\cdots &c_{2}&c_{1}\\c_{1}&c_{0}&c_{1}&&c_{2}\\\vdots &c_{1}&c_{0}&\ddots &\vdots \\c_{2}&&\ddots &\ddots &c_{1}\\c_{1}&c_{2}&\cdots &c_{1}&c_{0}\\\end{bmatrix}}.}$$

任意の実対称行列の固有値は実数です。対応する固有値は、 が偶数 の場合、 が 奇数 の場合、となります 。ここで、は の実部を表します。これは、と が偶数または奇数に依存するという事実を使用することでさらに簡略化できます。 ${\displaystyle {\vec {\lambda }}={\sqrt {n}}\cdot F_{n}^{\dagger }c}$$${\displaystyle {\begin{array}{lcl}\lambda _{k}&=&c_{0}+c_{n/2}e^{-\pi i\cdot k}+2\sum _{j=1}^{{\frac {n}{2}}-1}c_{j}\cos {(-{\frac {2\pi }{n}}\cdot kj)}\\&=&c_{0}+c_{n/2}\omega _{k}^{n/2}+2c_{1}\Re \omega _{k}+2c_{2}\Re \omega _{k}^{2}+\dots +2c_{n/2-1}\Re \omega _{k}^{n/2-1}\end{array}}}$$${\displaystyle n}$ $${\displaystyle {\begin{array}{lcl}\lambda _{k}&=&c_{0}+2\sum _{j=1}^{\frac {n-1}{2}}c_{j}\cos {(-{\frac {2\pi }{n}}\cdot kj)}\\&=&c_{0}+2c_{1}\Re \omega _{k}+2c_{2}\Re \omega _{k}^{2}+\dots +2c_{(n-1)/2}\Re \omega _{k}^{(n-1)/2}\end{array}}}$$${\displaystyle n}$ ${\displaystyle \Re z}$${\displaystyle z}$${\displaystyle \Re \omega _{k}^{j}=\Re e^{-{\frac {2\pi i}{n}}\cdot kj}=\cos(-{\frac {2\pi }{n}}\cdot kj)}$${\displaystyle \omega _{k}^{n/2}=e^{-{\frac {2\pi i}{n}}\cdot k{\frac {n}{2}}}=e^{-\pi i\cdot k}}$${\displaystyle k}$

対称巡回行列は、双対称行列のクラスに属します。

通信理論でよく使われる巡回行列の複素バージョンは、通常エルミートです。この場合、 とその行列式およびすべての固有値は実数です。 ${\displaystyle c_{n-i}=c_{i}^{*},\;i\leq n/2}$

nが偶数の場合、最初の 2 行は必ず、 上の 2 番目の半行の 最初の要素が実数となる形式になります。$${\displaystyle {\begin{bmatrix}r_{0}&z_{1}&z_{2}&r_{3}&z_{2}^{*}&z_{1}^{*}\\z_{1}^{*}&r_{0}&z_{1}&z_{2}&r_{3}&z_{2}^{*}\\\dots \\\end{bmatrix}}.}$$${\displaystyle r_{3}}$

nが奇数の 場合、$${\displaystyle {\begin{bmatrix}r_{0}&z_{1}&z_{2}&z_{2}^{*}&z_{1}^{*}\\z_{1}^{*}&r_{0}&z_{1}&z_{2}&z_{2}^{*}\\\dots \\\end{bmatrix}}.}$$

ティー^[5]はエルミート条件の固有値に対する制約について議論した。

行列方程式が与えられた場合

${\displaystyle C\mathbf {x} =\mathbf {b} ,}$

ここで はサイズ の巡回行列であり、方程式は巡回畳み込みと書くことができます。 ここで はの最初の列であり、ベクトル、および は各方向に巡回的に拡張されます。巡回畳み込み定理 を使用すると、離散フーリエ変換を使用して巡回畳み込みを成分ごとの乗算に変換できる ため、 ${\displaystyle C}$${\displaystyle n}$ $${\displaystyle \mathbf {c} \star \mathbf {x} =\mathbf {b} ,}$$${\displaystyle \mathbf {c} }$${\displaystyle C}$${\displaystyle \mathbf {c} }$${\displaystyle \mathbf {x} }$${\displaystyle \mathbf {b} }$$${\displaystyle {\mathcal {F}}_{n}(\mathbf {c} \star \mathbf {x} )={\mathcal {F}}_{n}(\mathbf {c} ){\mathcal {F}}_{n}(\mathbf {x} )={\mathcal {F}}_{n}(\mathbf {b} )}$$$${\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 \mathbb {Z} }\,\right]^{\rm {T}}.}$$

このアルゴリズムは、特に高速フーリエ変換を使用する 場合、標準のガウス消去法よりもはるかに高速です。

グラフ理論では、隣接行列が巡回するグラフまたは有向グラフを巡回グラフ/有向グラフと呼びます。同様に、自己同型群に全長の閉路が含まれる場合、グラフは巡回グラフです。メビウスの梯子は巡回グラフの例であり、素数位数の体のペイリーグラフも同様です。

• Gray, RM (2006). Toeplitz および Circulant Matrices: A Review (PDF) . 第 2 巻. 現在. pp. 155–239​​. doi :10.1561/0100000006. ISBN 978-1-933019-68-0– スタンフォード大学経由。 {{cite book}}:|journal=無視されました (ヘルプ)
• 巡回行列の特性を示す IPython Notebook