巡回行列の固有値分解

はじめに

今読んでいる無線通信工学の本のOFDMの項に差し掛かった。巡回行列がDFT行列で対角化されることが証明無しに用いられたので、導出してみた。

主張

$N\in \mathbb{N},a_0,a_1,\dots ,a_{N-1}\in \mathbb{C},\mathit{a}:=[a_0,\dots ,a_{N-1}{]}^{\mathrm{\top }}$とする。$\mathit{a}$の要素を$m\in \{0,1,\dots ,N-1\}$だけ巡回シフトしたベクトル${\mathit{a}}_m$を次式で定義する。

$${\mathit{a}}_m:=\{\begin{array}{ll}\mathit{a}& (m=0)\\ [a_{N-m},\dots ,a_{N-1},a_0,a_1,\dots ,a_{N-1-m}{]}^{\mathrm{\top }}& (m=1,2,\dots ,N-1)\end{array}$$

$A\in {\mathbb{C}}^{N\times N}$を次式で定義する。

$$A:=[{\mathit{a}}_0,{\mathit{a}}_1,\dots ,{\mathit{a}}_{N-1}]$$

このとき$A$は次のように対角化可能である。

$$A=\sqrt{N}W\mathrm{diag}\left(\mathrm{DFT}\left(\mathit{a}\right)\right)W^{\ast }$$

ここに$W$は$N\times N$ DFT基底行列であり、第$(n,k)$要素は次式で定義される。

$$W_{n,k}:=\frac{1}{\sqrt{N}}\exp i\frac{nk}{N}2\pi$$

$\mathrm{DFT}\left(\mathit{a}\right)$は$\mathit{a}$のDFT(離散 Fourier 変換)であり、次式で定義される。

$$\mathrm{DFT}\left(\mathit{a}\right):=W^{\ast }\mathit{a}$$

すなわち第$k$要素は次式である。

$$\sum _{n=0}^{N-1}\overline{W_{k,n}}{a}_n$$

導出

「離散 Fourier 変換」で述べられているDFTの性質を用いる。${\mathit{e}}_m\in {\mathbb{R}}^N$を第$m$要素が1でそれ以外は0のベクトルとする。${\mathit{a}}_m$は巡回畳み込みを用いて次式で表せる。

$${\mathit{a}}_m=\mathit{a}\underset{\text{cyc}}{\ast }{\mathit{e}}_m$$

巡回畳み込みのDFTの性質より次式が成り立つ。

$$\mathrm{DFT}\left({\mathit{a}}_m\right)=\sqrt{N}\mathrm{DFT}\left(\mathit{a}\right)\odot \mathrm{DFT}\left({\mathit{e}}_m\right)=\sqrt{N}\mathrm{DFT}\left(\mathit{a}\right)\odot W^{\ast }[:,m]$$

これより次式が成り立つ。

$$\begin{array}{rl}{W}^{\ast }A& =[\mathrm{DFT}\left({\mathit{a}}_0\right),\mathrm{DFT}\left({\mathit{a}}_1\right),\dots ,\mathrm{DFT}\left({\mathit{a}}_{N-1}\right)]\\ & =\sqrt{N}[\mathrm{DFT}\left(\mathit{a}\right)\odot W^{\ast }[:,0],\mathrm{DFT}\left(\mathit{a}\right)\odot W^{\ast }[:,1],\dots ,\mathrm{DFT}\left(\mathit{a}\right)\odot W^{\ast }[:,N-1]]\\ & =\sqrt{N}\mathrm{diag}\left(\mathrm{DFT}\left(\mathit{a}\right)\right)W^{\ast }\end{array}$$

両辺に左から$W$を掛け、$W$のユニタリ性$W{W}^{\ast }=I$を用いて次式を得る。

$$A=\sqrt{N}W\mathrm{diag}\left(\mathrm{DFT}\left(\mathit{a}\right)\right)W^{\ast }$$