takahiro_itazuriの公倍数的ブログ

本やWebを通して学習したことをまとめるブログです。最大公約数(つまり、共通部分)的なという表現と対比して、「なるべく包括的にカバーしつつ、更に+αの要素も加えられたらいいな」という意味で公倍数的ブログと名付けました。

巡回行列とフーリエ変換による対角化

はじめに

巡回行列という行列が、離散フーリエ変換行列を用いて対角化可能であると知って、かなり衝撃を受けたので記事にしておきます。

巡回行列(Circulant Matrix)とは

巡回行列は、各行ベクトルが1つ前の行ベクトルを1つずらした配置した形になっている行列である。数式で表現すると、以下のような形で定義される。

$ n \times n $の行列$ C $が次のような形式である時、これを巡回行列と呼ぶ。
\begin{align}
C =
\begin{bmatrix}
c_0 & c_1 & c_2 & \cdots & c_{n-1} \\
c_{n-1} & c_0 & c_1 & \cdots & c_{n-2} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
c_1 & c_2 & c_3 & \cdots & c_0
\end{bmatrix}
\end{align}

このような巡回行列$ C $に対して、ベクトル$ x \in {\mathbb{R}}^{n} $と積を取ると、以下のようになる。

\begin{align}
y &= Cx \\
&=
\begin{bmatrix}
c_0 & c_1 & c_2 & \cdots & c_{n-1} \\
c_{n-1} & c_0 & c_1 & \cdots & c_{n-2} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
c_1 & c_2 & c_3 & \cdots & c_0
\end{bmatrix}
\begin{bmatrix}
x_0 \\ x_1 \\ \vdots \\ x_{n-1}
\end{bmatrix}
\end{align}

したがって、$ y $の$ k $番目の成分は以下のように記述できる。

\begin{align}
y_k &= \sum_{j=0}^{n-1} c_{j-k} x_j \\
c_{j \pm n} &= c_j
\end{align}

既に何かが起こりそうな雰囲気を醸していますね。

離散フーリエ変換行列

離散フーリエ変換は皆さんご存知だと思います。これを行列で表現すると以下のように書くことができます。

\begin{align}
F &=
\begin{bmatrix}
\omega_n^{00} & \omega_n^{01} & \cdots & \omega_n^{0k} & \cdots & \omega_n^{0(n-1)} \\
\omega_n^{10} & \omega_n^{11} & \cdots & \omega_n^{1k} & \cdots & \omega_n^{1(n-1)} \\
\vdots & \vdots & \ddots & \vdots & \ddots & \vdots \\
\omega_n^{j0} & \omega_n^{j1} & \cdots & \omega_n^{jk} & \cdots & \omega_n^{j(n-1)} \\
\vdots & \vdots & \ddots & \vdots & \ddots & \vdots \\
\omega_n^{(n-1)0} & \omega_n^{(n-1)1} & \cdots & \omega_n^{(n-1)k} & \cdots & \omega_n^{(n-1)(n-1)} \\
\end{bmatrix} \\
\omega_n &= \frac{1}{\sqrt{n}} e^{\frac{2 \pi i}{n}}
\end{align}

巡回行列とフーリエ変換

実はこの離散フーリエ変換行列の列ベクトルが、巡回行列の固有ベクトルになっているという性質があります。

この性質を確認してみましょう。
ここで離散フーリエ変換行列の$ k $番目の列ベクトルを$ x^{(k)} $とします。
この列ベクトル$ x^{(k)} $に先程の巡回行列を左からかけて、$ x^{(k)} $の整数倍のベクトルになっていれば、$ x^{(k)} $は固有ベクトルと言えますね。

\begin{align}
y &= C x^{(k)} \\
y_l &= \sum_{j=0}^{n-1} c_{j-l} x_j^{(k)} \\
&= \sum_{j=0}^{n-1} c_{j-l} \omega_n^{jk} \\
&= \omega_n^{lk} \sum_{j=0}^{n-1} c_{j-l} \omega_n^{(j-l)k}
\end{align}

ここで、第二項の和は$c$と$\omega$は共に周期$n$であるので、$l$に依存しません。したがって、これを$\lambda_k$とします。

\begin{align}
\lambda_k = \sum_{j=0}^{n-1} c_j \omega_n^{jk}
\end{align}

さらに、第一項である$ \omega_n^{lk} $は$ x^{(k)} $の$l$番目の成分です。
以上から、以下のように書くことができます。

\begin{align}
y_l &= \lambda_k x_l^{(k)} \\
y &= C x^{(k)} = \lambda_k x^{(k)} \\
\end{align}

以上から、離散フーリエ変換行列の列ベクトルはすべて、任意の巡回行列$C$の固有ベクトルです。

巡回行列の対角化

先程の性質を用いて、巡回行列を対角化します。
先程の性質から、以下の式が得られます。

\begin{align}
CF =
\begin{bmatrix}
\lambda_0 x^{(0)} & \lambda_1 x^{(1)} & \cdots & \lambda_{n-1} x^{(n-1)}
\end{bmatrix}
\end{align}

これに対して左から離散フーリエ変換行列の転置$F^T$をかけると、フーリエ行列のすべての列ベクトルは直交しているため、

\begin{align}
F^T C F &=
\begin{bmatrix}
{x^{(0)}}^T \\ {x^{(1)}}^T \\ \vdots \\ {x^{(0)}}^T
\end{bmatrix}
\begin{bmatrix}
\lambda_0 x^{(0)} & \lambda_1 x^{(1)} & \cdots & \lambda_{n-1} x^{(n-1)}
\end{bmatrix} \\
&= diag(\lambda_0, \lambda_1, \lambda_2, \cdots, \lambda_{n-1})
\end{align}

以上のように対角化ができました。

巡回行列による線形方程式の解法

線形方程式が次のように与えられたとする。

\begin{align}
Cx = b
\end{align}

ここで$C$が巡回行列であれば、巡回畳み込みとして次の方程式で表せる。

\begin{align}
c \ast x = b
\end{align}

ここで離散フーリエ変換を利用して、以下のような形式にできる。(capella さんにご指摘いただき修正しました)

\begin{align}
\mathcal{F} (c \ast x) = \mathcal{F} (c) \mathcal{F} (x) = \mathcal{F}(b)
\end{align}

したがって、以下のように計算できる。

\begin{align}
x = {\mathcal{F}}^{-1} \left[ \frac{\mathcal{F}(b)}{\mathcal{F}(c)} \right]
\end{align}

数学って神秘的ですね~。