\begin{equation*}
\newcommand\ve[1]{\boldsymbol{#1}}
\end{equation*}
巡回行列は何度も何度も重要性を認識している。群論では巡回群が密接に絡む。
以下の記事
の焼き直しに過ぎないが、自分の言葉で再度書き直してみる。
\(n \times n\) 行列
\begin{equation*}
\ve{C} = \left[ \begin{array}{ccccc}
c_{0} & c_{1} & c_{2} & ... & c_{n-1} \\
c_{n-1} & c_{0} & c_{1} & ... & c_{n-2} \\
\vdots & & \ddots & \ddots & \vdots \\
c_{1} & c_{2} & c_{3} & ... & c_{0} \\
\end{array} \right]
\end{equation*}
を巡回行列（Circulant Matrix）という。これに対してDFT（離散フーリエ変換）を行うことを考える。離散フーリエ変換は、フーリエ変換行列
\begin{align*}
\ve{F} &= \left[ \begin{array}{cccc}
\omega_{n}^{0 \times 0} & \omega_{n}^{0 \times 1} & ... & \omega_{n}^{0 \times (n-1)} \\
\omega_{n}^{1 \times 0} & \omega_{n}^{1 \times 1} & & \omega_{n}^{1 \times (n-1)} \\
\vdots & & \ddots & \vdots \\
\omega_{n}^{(n-1) \times 0} & ... & & \omega_{n}^{(n-1) \times (n-1)} \\
\end{array} \right] \\
\omega_{n} &:= \frac{1}{\sqrt{n}} \exp\left(\frac{j2\pi}{n}\right)
\end{align*}
を作用させる（乗ずる）ことで実現される。いま、
\begin{equation*}
\ve{F} := \left[\ \ve{f}_{0} \ \ve{f}_{1} \ ... \ \ve{f}_{n-1} \ \right]
\end{equation*}
と \(\ve{F}\) を列ベクトルに分解して表す（ \((\ve{F})_{ij} = (\ve{f}_{j})_{i} = \omega_{n}^{ij}\) となる。議論の簡単のため、ここでは、行列要素のインデックスは0から始めている）。このとき、おもむろに \(\ve{y} = \ve{C} \ve{f}_{k}\) を計算してみると、
\begin{align*}
(\ve{y})_{l} &= \sum_{j=0}^{n-1} c_{j-l}(\ve{f}_{k})_{j} := \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_{j}\) と \(\omega_{n}\) は共に周期 \(n\) (すなわち \(c_{j} = c_{j + mn},\ \omega_{n}^{m} = \omega_{n}^{mn}\ (m \in \mathbb{Z})\) ) だから、 \(\sum_{j=0}^{n-1} c_{j-l} \omega_{n}^{(j-l)k}\) は1周期分の和になっており \(l\) に依存しない。そこで、 \(k\) だけに依存する数として
\begin{equation*}
\lambda_{k} := \sum_{j=0}^{n-1} c_{j-l} \omega_{n}^{(j-l)k}
\end{equation*}
とおく。すると、
\begin{align*}
(\ve{y})_{l} &= \omega_{n}^{lk} \lambda_{k} = (\ve{f}_{k})_{l} \lambda_{k} \\
&= \lambda_{k} (\ve{f}_{k})_{l}
\end{align*}
だから、結果をベクトルにまとめると
\begin{equation*}
\ve{y} = \lambda_{k} \ve{f}_{k} = \ve{C} \ve{f}_{k}
\end{equation*}
この結果を見ると、 \(\lambda_{k}\) は \(\ve{C}\) は固有値、 \(\ve{f}_{k}\) はそれに対応する固有ベクトルになっていることがわかる。さらに、この結果を \(k=0,...,n-1\) で並べていくと、
\begin{align*}
\left[\ \lambda_{0} \ve{f}_{0} \ \lambda_{1} \ve{f}_{1} \ ... \ \lambda_{n-1}\ve{f}_{n-1} \ \right] &= \left[\ \ve{C}\ve{f}_{0} \ \ve{C}\ve{f}_{1} \ ... \ \ve{C}\ve{f}_{n-1} \ \right] \\
&= \ve{C} \left[ \ \ve{f}_{0} \ \ve{f}_{1} \ ... \ \ve{f}_{n-1}\ \right] = \ve{CF}
\end{align*}
よって、
\begin{align*}
\ve{F}^{\mathsf{T}} \ve{C} \ve{F} &= \left[ \ \ve{f}_{0} \ \ve{f}_{1} \ ... \ \ve{f}_{n-1}\ \right]^{\mathsf{T}} \left[ \ \lambda_{0} \ve{f}_{0} \ \lambda_{1} \ve{f}_{1} \ ... \ \lambda_{n-1} \ve{f}_{n-1} \ \right] \\
&= \left[ \begin{array}{c} \ve{f}_{0}^{\mathsf{T}} \\ \vdots \\ \ve{f}_{n-1}^{\mathsf{T}} \end{array} \right] \left[ \ \lambda_{0} \ve{f}_{0} \ \lambda_{1} \ve{f}_{1} \ ... \ \lambda_{n-1}\ve{f}_{n-1} \ \right] \\
&= \left[ \begin{array}{cccc}
\lambda_{0}\ve{f}_{0}^{\mathsf{T}}\ve{f}_{0} & \lambda_{1}\ve{f}_{0}^{\mathsf{T}}\ve{f}_{1} & ... & \lambda_{n-1}\ve{f}_{n-1}^{\mathsf{T}}\ve{f}_{n-1} \\
\vdots & & \ddots & \vdots \\
\lambda_{0}\ve{f}_{n-1}^{\mathsf{T}}\ve{f}_{0} & \lambda_{1}\ve{f}_{n-1}^{\mathsf{T}}\ve{f}_{1} & ... & \lambda_{n-1}\ve{f}_{n-1}^{\mathsf{T}}\ve{f}_{n-1} \\
\end{array} \right]
\end{align*}
となる。行列の各要素は、
\begin{align*}
\ve{f}_{i}^{\mathsf{T}} \ve{f}_{j} &= \sum_{k=0}^{n-1} (\ve{f}_{i})_{k} (\ve{f}_{j})_{k} = \sum_{k=0}^{n-1} \frac{1}{\sqrt{n}} \omega_{n}^{ki} \frac{1}{\sqrt{n}} \omega_{n}^{kj} \\
&= \frac{1}{n} \sum_{k=0}^{n-1} \omega_{n}^{k(i+j)}
\end{align*}
ここで一旦止めて、式を見てみる。今、 \(i+j=n\) つまり \(i=n-j\) （もっというと \(i \equiv j\ (\mathrm{mod}\ n)\) ）ならば、
\begin{align*}
\frac{1}{n} \sum_{k=0}^{n-1} \omega_{n}^{k(i+j)} &= \frac{1}{n} \sum_{k=0}^{n-1} \omega_{n}^{kn} \\
&= \frac{1}{n} \sum_{k=0}^{n-1} \exp\left( j 2 \pi k \right) = \frac{1}{n} \sum_{k=0}^{n-1} 1 \\
&= 1
\end{align*}
それ以外の場合は、
\begin{align*}
\frac{1}{n} \sum_{k=0}^{n-1} \omega_{n}^{k(i+j)} &= \frac{1}{n} \omega_{n}^{(i+j)} \sum_{k=0}^{n-1} \omega_{n}^{k} \\
&= \frac{1}{n} \sum_{k=0}^{n-1} \exp\left( \frac{j 2 \pi}{n} k \right) \\
&= \exp(0) + \exp\left( j\frac{2\pi}{n} \right) + \exp\left( j\frac{\pi}{n} \right) + ... + \exp\left[ j\frac{(n-1)\pi}{n} \right] \\
&= 0
\end{align*}
となる（実際に \(n=2,3\) あたりで試してみると良い。複素平面上の単位円を \(n\) 分割して和を取るので \(0\) になる。厳密な証明は \(n\) に関する帰納法を使えばよいが、やらない。。。）。まとめると、
\begin{align*}
\ve{f}_{i}^{\mathsf{T}} \ve{f}_{j} &= \delta_{ij} \quad (\delta_{ij}: \text{クロネッカーのデルタ}) \\
\delta_{ij} &= \left\{ \begin{array}{ll}
1 & i = j \\
0 & i \neq j
\end{array} \right.
\end{align*}
だから（これより、 \(\ve{F}\) が直交行列 \(\ve{F}^{-1} = \ve{F}^{\mathsf{T}}\) であることが分かる）、
\begin{equation*}
\ve{F}^{\mathsf{T}} \ve{C} \ve{F} = \left[ \begin{array}{cccc}
\lambda_{0} & 0 & ... & 0 \\
0 & \lambda_{1} & & 0 \\
\vdots & & \ddots & \vdots \\
0 & ... & & \lambda_{n-1} \\
\end{array} \right] = \mathrm{diag}(\lambda_{0}, \lambda_{1}, ..., \lambda_{n-1})
\end{equation*}
この式は巡回行列 \(\ve{C}\) はフーリエ変換行列 \(\ve{F}\) で対角化できることを示している。
さらに、巡回行列 \(\ve{C}\) の1行目をDFTすると、 \(\ve{C}\) の固有値が全て求まることが示せる。\(\ve{C}\) の1行目を縦ベクトル化して \(\ve{c} = [ c_{0} \ c_{1} \ ... \ c_{n-1} ]^{\mathsf{T}}\) と書き、そのDFTを \(\mathcal{F}(\ve{c})\) と書くと、
\begin{align*}
\mathcal{F}(\ve{c}) &:= \ve{F}\ve{c} \\
&= \left[ \ \ve{f}_{0} \ \ve{f}_{1} \ ... \ \ve{f}_{n-1}\ \right] \ve{c} \\
&= \left[ \begin{array}{c}
(\ve{f}_{0})_{0} c_{0} + (\ve{f}_{1})_{0} c_{1} + ... + (\ve{f}_{n-1})_{0} c_{n-1} \\
(\ve{f}_{0})_{1} c_{0} + (\ve{f}_{1})_{1} c_{1} + ... + (\ve{f}_{n-1})_{1} c_{n-1} \\
\vdots \\
(\ve{f}_{0})_{n-1} c_{0} + (\ve{f}_{1})_{n-1} c_{1} + ... + (\ve{f}_{n-1})_{n-1} c_{n-1} \\
\end{array} \right] \\
&= \left[ \begin{array}{c}
\omega_{n}^{0 \times 0} c_{0} + \omega_{n}^{0 \times 1} c_{1} + ... + \omega_{n}^{0 \times (n-1)} c_{n-1} \\
\omega_{n}^{1 \times 0} c_{0} + \omega_{n}^{1 \times 1} c_{1} + ... + \omega_{n}^{1 \times (n-1)} c_{n-1} \\
\vdots \\
\omega_{n}^{(n-1) \times 0} c_{0} + \omega_{n}^{(n-1) \times 1} c_{1} + ... + \omega_{n}^{(n-1) \times (n-1)} c_{n-1} \\
\end{array} \right]
= \left[ \begin{array}{c}
\sum_{j=0}^{n-1} c_{j} \omega_{n}^{0 \times j} \\
\sum_{j=0}^{n-1} c_{j} \omega_{n}^{1 \times j} \\
\vdots \\
\sum_{j=0}^{n-1} c_{j} \omega_{n}^{(n-1) \times j}
\end{array} \right] \\
&= \left[ \begin{array}{c}
\lambda_{0} \\ \lambda_{1} \\ \vdots \\ \lambda_{n-1}
\end{array} \right]
\end{align*}
フーリエ係数がそのまま固有値になっており、したがって、 \(\ve{c}\) のDFTは \(\ve{C}\) の固有値を並べたベクトルに変換される事がわかった。求まった固有値の逆数をとって逆フーリエ変換すれば、巡回行列の逆 \(\ve{C}^{-1}\) が求まってしまう。離散フーリエ変換はFFT（高速フーリエ変換）によって \(\mathcal{O}(n\log n)\) で計算できるから高速に逆行列計算ができることになる。たまげたなあ。
なにかの時系列データに対してDFT(FFT)を実行すると、それは巡回行列の固有値を求めていることに等しくなる。