巡回行列の固有値・固有ベクトルと行列式

巡回行列

(xyzzxyyzx)\begin{pmatrix}x&y&z\\z&x&y\\y&z&x\end{pmatrix} のように,「左上~右下方向」に同じ値が並んだ行列を巡回行列(循環行列,Circulant matrix)という。

※より正確に述べると,ijij 成分の値が「(ij)(i-j)nn で割った余り」のみで決まる n×nn\times n 行列のことです。

巡回行列の行列式

巡回行列の行列式は,因数分解できておもしろいです。

定理1

巡回行列 CC の行列式は,CC の1行目を (c0,c1,,cn1)(c_0,c_1,\dots,c_{n-1}) とすると,

detC=k=0n1(l=0n1ζklcl)\det C=\displaystyle\prod_{k=0}^{n-1}\left(\sum_{l=0}^{n-1}\zeta_k^lc_l\right)

ただし,この記事で ζk\zeta_ke2πkine^{\frac{2\pi ki}{n}},つまり 11nn 乗根を表します。→1のn乗根の性質と複素数平面

難しそうな式ですが,n=3n=3 の場合で書いてみるとわかりやすいです。

  • 定理の左辺は,det(c0c1c2c2c0c1c1c2c0)\det\begin{pmatrix}c_0&c_1&c_2\\c_2&c_0&c_1\\c_1&c_2&c_0\end{pmatrix} です。行列式の定義にもとづいて計算すると,c03+c13+c233c0c1c2c_0^3+c_1^3+c_2^3-3c_0c_1c_2 となります。
  • 定理の右辺は,1133 乗根を ω\omega とおくと,
    (c0+c1+c2)(c0+ωc1+ω2c2)(c0+ω2c1+ωc2)(c_0+c_1+c_2)(c_0+\omega c_1+\omega^2c_2)(c_0+\omega^2c_1+\omega c_2)
    となります。

つまり,この式は,高校数学で登場する因数分解公式
a3+b3+c33abc=(a+b+c)(a2+b2+c2abbcca)a^3+b^3+c^3-3abc\\=(a+b+c)(a^2+b^2+c^2-ab-bc-ca)
の右辺第2項をさらに複素数の範囲で分解したものです!→因数分解公式一覧

定理1の証明
  1. 行列式が固有値の積であること:detC=k=0n1λk\det C=\displaystyle\prod_{k=0}^{n-1}\lambda_k
  2. 固有値が λk=l=0n1ζklcl(k=0,1,,n1)\lambda_k=\displaystyle\sum_{l=0}^{n-1}\zeta_k^lc_l\:(k=0,1,\dots,n-1) であること(→後述の定理2)

からわかる。

巡回行列の固有値・固有ベクトル

定理2

巡回行列 CC について,CC の1行目を (c0,c1,,cn1)(c_0,c_1,\dots,c_{n-1}) とする。

  • 固有ベクトルは,xkundefined=(1,ζk,ζk2,,ζkn1)\overrightarrow{x_k}=(1,\zeta_k,\zeta_k^2,\dots,\zeta_k^{n-1})
  • xkundefined\overrightarrow{x_k} に対応する固有値は λk=l=0n1ζklcl\lambda_k=\displaystyle\sum_{l=0}^{n-1}\zeta_k^lc_l

(ただし,k=0,1,,n1k=0,1,\dots,n-1

証明の概要

Cxkundefined=λkxkundefinedC\overrightarrow{x_k}=\lambda_k\overrightarrow{x_k} が簡単な計算で確認できる。例えば n=3n=3 のときには以下の式を確認することになる。

  • k=0k=0
    (c0c1c2c2c0c1c1c2c0)(111)=(c0+c1+c2)(111)\begin{pmatrix}c_0&c_1&c_2\\c_2&c_0&c_1\\c_1&c_2&c_0\end{pmatrix}\begin{pmatrix}1\\1\\1\end{pmatrix}=(c_0+c_1+c_2)\begin{pmatrix}1\\1\\1\end{pmatrix}

  • k=1k=1
    (c0c1c2c2c0c1c1c2c0)(1ωω2)=(c0+ωc1+ω2c2)(1ωω2)\begin{pmatrix}c_0&c_1&c_2\\c_2&c_0&c_1\\c_1&c_2&c_0\end{pmatrix}\begin{pmatrix}1\\\omega\\\omega^2\end{pmatrix}=(c_0+\omega c_1+\omega^2c_2)\begin{pmatrix}1\\\omega\\\omega^2\end{pmatrix}

  • k=2k=2
    (c0c1c2c2c0c1c1c2c0)(1ω2ω)=(c0+ω2c1+ωc2)(1ω2ω)\begin{pmatrix}c_0&c_1&c_2\\c_2&c_0&c_1\\c_1&c_2&c_0\end{pmatrix}\begin{pmatrix}1\\\omega^2\\\omega\end{pmatrix}=(c_0+\omega^2 c_1+\omega c_2)\begin{pmatrix}1\\\omega^2\\\omega\end{pmatrix}

さらに,k1k2k_1\neq k_2 なら xk1undefined\overrightarrow{x_{k_1}}xk2undefined\overrightarrow{x_{k_2}} が直交することも確認できる。

巡回行列と離散フーリエ変換

定理2の応用です。この節は少し難しいです。

  • 巡回行列の固有ベクトルを求めましたが,これらを並べた行列は,離散フーリエ変換を表す行列 FF と一致します。
    例えば,n=3n=3 の場合,3次元ベクトル aundefined\overrightarrow{a} の離散フーリエ変換は Faundefined=(1111ωω21ω2ω4)aundefinedF\overrightarrow{a}=\begin{pmatrix}1&1&1\\1&\omega&\omega^2\\1&\omega^2&\omega^4 \end{pmatrix}\overrightarrow{a} と表せます。

  • つまり,巡回行列は「離散フーリエ変換を表す行列で対角化できる」と言えます:F1CF=DF^{-1}CF=D(ただし DD が固有値を並べた対角行列)

  • さらに,この式から F(cundefinedxundefined)=F(cundefined)F(xundefined)F(\overrightarrow{c}*\overrightarrow{x})=F(\overrightarrow{c})\circ F(\overrightarrow{x}) という重要な式を導出できます。ただし,cundefinedxundefined\overrightarrow{c}*\overrightarrow{x}nn 次元ベクトルの巡回畳み込み(畳み込みの巡回バージョン)で,\circ はベクトルの要素ごとの積を表します。

証明の概要

1行目が cc^{\top} である巡回行列を CC とおくと,巡回畳み込みの定義より cundefinedxundefined=Cxundefined\overrightarrow{c}*\overrightarrow{x}=C^{\top}\overrightarrow{x}

よって,

F(cundefinedxundefined)=FCxundefined=FCF1Fxundefined=(F1CF)Fxundefined=DFxundefined=F(cundefined)F(xundefined)F(\overrightarrow{c}*\overrightarrow{x})\\ =FC^{\top}\overrightarrow{x}\\ =FC^{\top}F^{-1}F\overrightarrow{x}\\ =(F^{-1}CF)^{\top}F\overrightarrow{x}\\ =DF\overrightarrow{x}\\ =F(\overrightarrow{c})\circ F(\overrightarrow{x})

高校数学で習う因数分解公式が出てくるのがおもしろいです。