巡回行列の性質と離散フーリエ変換
線形代数 - 離散フーリエ変換
今日は、備忘録程度に巡回行列の性質を少しだけまとめておきたいと思います。
演算の性質
体 \(K\) 上の \(n\) 次元正方行列 \(C\) が、ある \(n\) 個の係数 \(a_0,\cdots,a_{n-1}\) を用いて、以下のように表現できるとき、\(C\) を巡回行列という。また、\(n\) 次元の巡回行列の全体を \(\mathcal{C}_n(K)\) と表記する。 \[C = \begin{pmatrix} a_0 & a_1 & a_2 & \cdots & a_{n-1} \\ a_{n-1}& a_0 & a_1 & \cdots & a_{n-2} \\ a_{n-2}& a_{n-1}& a_0 & \cdots & a_{n-3} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a_1 & a_2 & a_3 & \cdots & a_0 \end{pmatrix} \]
以降の命題や定理において、断りのない限り $C$ は $n$ 次巡回行列であり、上のような $a_0,\cdots,a_{n-1}$ による表示を持つものとする。
簡単な成分計算により、加法と乗法で閉じていることがわかる。 また、加法と乗法の結合律や分配律などは \(M_n(K)\) の構造を引き継いでいるから成立する。 これにより、\(\mathcal{C}_n(K)\) は環を成すことがわかる。 あるいは、次に証明する定理２の証明に登場する行列 \(P\) を用いれば成分計算を回避することもできる。 これにより、可換性も直ちにわかる。
以下の環同型が成り立つ。 \[\mathcal{C}_n(K) \cong K[x]/(x^n-1)\]
行列 \(P,C \in \mathcal{C}_n(K)\) を \[P = \begin{pmatrix} 0 & 0 & 0 & \cdots & 0 & 1 \\ 1 & 0 & 0 & \cdots & 0 & 0 \\ 0 & 1 & 0 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & 1 & 0 \end{pmatrix} , \quad C = \begin{pmatrix} a_0 & a_1 & a_2 & \cdots & a_{n-1} \\ a_{n-1}& a_0 & a_1 & \cdots & a_{n-2} \\ a_{n-2}& a_{n-1}& a_0 & \cdots & a_{n-3} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a_1 & a_2 & a_3 & \cdots & a_0 \end{pmatrix} \] で定める。このとき、 \[C = a_0P^0 + a_1P^1 + \cdots + a_{n-1}P^{n-1}\] となる。 写像 \(\varphi:\;K[x]\longrightarrow \mathcal{C}_n(K)\) を以下で定める。 \[ \varphi:\;K[x]\longrightarrow \mathcal{C}_n(K),\qquad \varphi\!\left(\sum_{i=0}^m c_i x^i\right)=\sum_{i=0}^m c_i P^i, \] このとき \(\varphi\) は準同型である。 また、\(\varphi\) は全射であり、\(\text{Ker}\varphi = (x^n-1)\) となる。 よって、準同型定理より、\(\mathcal{C}_n(K) \cong K[x]/(x^n-1)\) を得る。\(\square\)
以下の環同型が成り立つ。 \[\mathcal{C}_n(\mathbb{R}) \cong \mathbb{R}[x]/(x^n-1), \quad \mathcal{C}_n(\mathbb{C}) \cong \mathbb{C}^n\]
\(\mathbb{C}\) 上では、\(x^n-1\) は \(n\) 個の一次式の積に因数分解できるので、中国剰余定理を用いれば、 \[\mathcal{C}_n(\mathbb{C}) \cong \mathbb{C}[x]/(x^n-1) \cong \mathbb{C}[x]/(x - 1) \times \mathbb{C}[x]/(x - e^{\frac{2i\pi}{n}}) \times \cdots \times \mathbb{C}[x]/(x - e^{\frac{2i\pi (n-1)}{n}})\cong \mathbb{C}^n\] を得る。 \(\square\)
行列式の計算
巡回行列の行列式は比較的簡単に計算することができます。
巡回行列 $C \in \mathcal{C}_n(\mathbb{C})$ に対して、$\xi = e^{\frac{2i\pi}{n}} , \ f(x) = a_0 + a_1x + \cdots + a_{n-1}x^{n-1}$ とすれば次が成り立つ。 $$\det(C) = f(1)f(\xi)f(\xi^2) \cdots f(\xi^{n-1})$$
行列 $Z \in \mathcal{C}_n(\mathbb{C})$ を $$ Z = \begin{pmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & \xi & \xi^2 & \cdots & \xi^{n-1} \\ 1 & \xi^2 & \xi^4 & \cdots & \xi^{2(n-1)} \\ \vdots & \vdots & \cdots & \ddots & \vdots \\ 1 & \xi^{n-1} & \xi^{2(n-1)} & \cdots & \xi^{(n-1)^2} \end{pmatrix} $$ で定める。このとき、ヴァンデルモンドの公式より $Z$ は正則である。 積 $CZ$ を計算すると $$ CZ = \begin{pmatrix} f(1) & f(\xi) & f(\xi^2) & \cdots & f(\xi^{n-1}) \\ f(1) & f(\xi)\xi & f(\xi^2)\xi^2 & \cdots & f(\xi^{n-1})\xi^{n-1} \\ f(1) & f(\xi)\xi^2 & f(\xi^2)\xi^4 & \cdots & f(\xi^{n-1})\xi^{2(n-1)} \\ \vdots & \vdots & \cdots & \ddots & \vdots \\ f(1) & f(\xi)\xi^{n-1} & f(\xi^2)\xi^{2(n-1)} & \cdots & f(\xi^{n-1})\xi^{(n-1)^2} \end{pmatrix} $$ となる。これより、行列式の多重線型性と併せて $$ \det(C) = \frac{\det(CZ)}{\det(Z)} = \frac{f(1)f(\xi)f(\xi^2) \cdots f(\xi^{n-1})\det(Z)}{\det(Z)} = f(1)f(\xi)f(\xi^2) \cdots f(\xi^{n-1}) $$ を得る。$\square$
この $Z$ で定まるような線型変換を離散フーリエ変換と呼びます。
$\mathbb{C}$ 上の巡回行列
系3より、$\mathcal{C}_n(\mathbb{C}) \cong \mathbb{C}^n$ でした。 具体的に、どのような $n$ 個の複素数と対応しているのかを見てみます。
巡回行列 $C \in \mathcal{C}_n(\mathbb{C})$ に対して、行列 $Z$ を定理4と同様に定めれば、$Z^{-1}CZ$ は対角行列となる。 また、$C$ は正規行列である。
$\lambda_k$ を $\lambda_k = f(\xi^k) \ (k=0,\dots,n-1)$ で定める。 \[ C Z = Z \operatorname{diag}(\lambda_0,\lambda_1,\dots,\lambda_{n-1}). \] であるから、$Z^{-1} C Z = \operatorname{diag}(\lambda_0,\dots,\lambda_{n-1})$ が得られる。
行列 $Z$ を正規化する。 \[ F=\frac{1}{\sqrt{n}}\big(\xi^{jk}\big)_{j,k=0}^{n-1} \] を用いると $F$ はユニタリであり（$F^{-1}=F^*$）、同様に \[ F^* C F = \operatorname{diag}(\lambda_0,\dots,\lambda_{n-1}) \] が成り立つ。 したがって任意の複素巡回行列はユニタリ対角化可能で、特に正規行列である。$\square$
以下で定まる写像 $\Phi$ は環同型である。 \[ \Phi:\; \mathcal{C}_n(\mathbb{C}) \longrightarrow \mathbb{C}^n,\qquad \Phi(C)=(\lambda_0,\lambda_1,\dots,\lambda_{n-1}) \]
定理５より、複素巡回行列は $Z$ によって同時対角化可能である。 $Z$ の正則性により固有ベクトルが基底を成すため写像 $\Phi(C)=(\lambda_0,\dots,\lambda_{n-1})$ は全射かつ単射であり、 行列の和と積はそれぞれ成分ごとの和と積に写る。 すなわち、$C_1,C_2$ に対して \[ \Phi(C_1+C_2)=\Phi(C_1)+\Phi(C_2),\qquad \Phi(C_1C_2)=\Phi(C_1)\odot\Phi(C_2), \] ここで $\odot$ は成分ごとの積である。 従って $\Phi$ は環同型である。
$\Phi$ の逆写像を考えれば、 固有値 $\lambda_k$ から元の係数 $(a_0,\dots,a_{n-1})$ を復元する式が得られます。 この操作は逆離散フーリエ変換と呼ばれます。 \[ a_j = \frac{1}{n}\sum_{k=0}^{n-1} \lambda_k\,\xi^{-jk}\qquad (j=0,\dots,n-1) \]
離散フーリエ変換の性質
ベクトル \(x=(x_0,\dots,x_{n-1})^T\in\mathbb{C}^n\) に対して離散フーリエ変換を行列 $Z$ により定まる線形写像、すなわち、次で定義する。 \[ (\mathcal{F}x)_k := \sum_{j=0}^{n-1} x_j\,\xi^{jk},\qquad (k=0,\dots,n-1) \]
任意の \(x,y\in\mathbb{C}^n\) に対し、添え字をnを法として考える巡回畳み込み \[ (x * y)_m := \sum_{j=0}^{n-1} x_j\,y_{m-j}\qquad(m=0,\dots,n-1) \] を定める。このとき、離散フーリエ変換 \(\mathcal{F}\) について次が成り立つ。 \[ \mathcal{F}(x*y) = (\mathcal{F}x)\odot(\mathcal{F}y) \]
定義から \[ \begin{aligned} (\mathcal{F}(x*y))_k &= \sum_{m=0}^{n-1} (x*y)_m\,\xi^{mk} = \sum_{m=0}^{n-1}\Big(\sum_{j=0}^{n-1} x_j\,y_{m-j}\Big)\xi^{mk} \\ &= \sum_{j=0}^{n-1} x_j \sum_{m=0}^{n-1} y_{m-j}\,\xi^{mk} \end{aligned} \] 添字を \(r=m-j\) と置き換えると、 \[ \sum_{m=0}^{n-1} y_{m-j}\,\xi^{mk} = \sum_{r=0}^{n-1} y_r\,\xi^{(r+j)k} = \xi^{jk}\sum_{r=0}^{n-1} y_r\,\xi^{rk}. \] これを代入すると \[ (\mathcal{F}(x*y))_k = \Big(\sum_{j=0}^{n-1} x_j\,\xi^{jk}\Big)\Big(\sum_{r=0}^{n-1} y_r\,\xi^{rk}\Big) = (\mathcal{F}x)_k(\mathcal{F}y)_k, \] すなわち、\(\mathcal{F}(x*y)=(\mathcal{F}x)\odot(\mathcal{F}y)\) が得られる。 \(\square\)
上のような直接的な計算以外にも、線形代数の知識を使って工夫することもできます。
\(x\) を係数とする巡回行列 \(C(x)\in\mathcal{C}_n(\mathbb{C})\) を \(C(x)_{m,j}=x_{m-j\pmod n}\) と定めれば、線型作用としての畳み込みは行列積にほかならない。 \[ C(x)\,y = x * y \] 一方、定理5 の対角化より \[ Z^{-1} C(x) Z = \operatorname{diag}(\mathcal{F}x), \] したがって \(\mathcal{F}(x*y)=\mathcal{F}(C(x)y)=\operatorname{diag}(\mathcal{F}x)\,\mathcal{F}y\) となり、成分ごとの積への対応が得られる。
任意の \(x,y\in\mathbb{C}^n\) に対して、離散フーリエ変換 \(\mathcal{F}=Z\) とその像 \(X=\mathcal{F}x,\ Y=\mathcal{F}y\) について次の等式が成り立つ。 \[ \sum_{j=0}^{n-1} x_j\overline{y_j} \;=\; \frac{1}{n}\sum_{k=0}^{n-1} X_k\overline{Y_k} \]
非正規化行列 \(Z\) の列ベクトルは互いに直交で、各列のノルムは \(\sqrt{n}\) であるから \[ Z^* Z = n I. \] よって \(X=Zx,\ Y=Zy\) とおくと \[ X^* Y = x^* Z^* Z y = n\, x^* y \] 両辺を \(n\) で割れば \[ x^* y = \frac{1}{n} X^* Y \] が得られる。 \(\square\)
任意の \(x,y\in\mathbb{C}^n\) に対して、離散フーリエ変換 \(\mathcal{F}=Z\) とその像 \(X=\mathcal{F}x,\ Y=\mathcal{F}y\) について次の等式が成り立つ。 \[ \sum_{j=0}^{n-1} |x_j|^2 \;=\; \frac{1}{n}\sum_{k=0}^{n-1} |X_k|^2 \]
定理９において、$x=y$ とすればよい。\(\square\)