周期数列の母関数と離散フーリエ変換について
この記事はまだあまり整理されていません．
- 周期$N$の複素数列全体を$\cycles{N}=\{x\mid x_n=x_{n+N}\forevery n\in\numset{Z}\}$とする．
- $\cycles{N}$上のラグ作用素$\lagop$を$\lagop x=\seq{x_{n-1}}_{n\in\numset{Z}}$で定義する．
$\cycles{N}$は加法$x+y=\seq{x_n+y_n}_{n\in\numset{Z}}$，スカラー乗法$\lambda x=\seq{\lambda x_n}_{n\in\numset{Z}}$に関する$N$次元ベクトル空間である．
$\dim\cycles{N}=N$のみ示す．$\delta\in\cycles{N}$を$N\numset{Z}$の指示関数，すなわち
$$
\delta_n = \begin{cases}1 & (n\equiv 0\pmod{N}),\\ 0 & (\text{otherwise})\end{cases}
$$
とする．このとき，集合$\basis{S}=\{\lagop^m\delta\mid 0\leq m< N\}$は$\cycles{N}$の基底である．実際
$$
\lagop^m\delta_n = \delta_{n-m}
= \begin{cases}1 & (n\equiv m\pmod{N}),\\ 0 & (\text{otherwise})\end{cases}
$$
なので，$\basis{S}$の各元は1次独立であり，任意の$x\in\cycles{N}$は$x=\sum_{m=0}^{N-1}x_m\lagop^m\delta$と書ける．
要するに，$\basis{S}$は$\numset{C}^N$の標準基底を周期的に拡張した集合である．
ここで
$$
x = \sum_{m=0}^{N-1}x_m\lagop^m\delta
= \pqty{\sum_{m=0}^{N-1}x_m\lagop^m}\delta
$$
だから，写像$\ztrans\colon\cycles{N}\to\numset{C}[\lagop]$を$x\mapsto\sum_{m=0}^{N-1}x_m\lagop^m$で定義すれば，$(\ztrans x)\delta=x$が成立する．ただし$\numset{C}[\lagop]=\{P(\lagop)\mid P(z)\in\numset{C}[z]\}$である．
環$\numset{C}[z]/\ideal{z^N-1}$は写像$z+\ideal{z^N-1}\mapsto\lagop$によって$\numset{C}[\lagop]$と同型である．
写像$\phi\colon\numset{C}[z]\to\numset{C}[\lagop]$を$P(z)\mapsto P(\lagop)$で定義する．$\ker\phi=\ideal{z^N-1}$が示せれば，準同型定理より$\numset{C}[z]/\ideal{z^N-1}\cong\numset{C}[\lagop]$がしたがう．また，この同型は$z+\ideal{z^N-1}\mapsto\lagop$を満たす．
$P(z)\in\ker\phi$を任意にとり，$P(z)$を$z^N-1$で割った商を$Q(z)$，あまりを$R(z)$とする．このとき$P(z)=Q(z)(z^N-1)+R(z)$，$\lagop^N=1$より$\phi(P(z))=R(\lagop)=0$である．また，$\deg R(z)< N$なので$R(z)=\sum_{m=0}^{N-1}r_mz^m$とおける．すると
$$
\phi(R(z))\delta = \pqty{\sum_{m=0}^{N-1}r_m\lagop^m}\delta
= \sum_{m=0}^{N-1}r_m(\lagop^m\delta)
= 0
$$
であり，$\basis{S}$は$\cycles{N}$の基底だから$r_m=0$である．つまり，$P(z)\in\ker\phi$なら$R(z)=0$，$P(z)\in\ideal{z^N-1}$である．明らかに$\ideal{z^N-1}\subset\ker\phi$も成り立つので，$\ker\phi=\ideal{z^N-1}$である．
$\ztrans$は全単射である．
$\check{\ztrans}\colon\numset{C}[\lagop]\to\cycles{N}$を$P(\lagop)\mapsto P(L)\delta$で定義する．$\check{\ztrans}(\ztrans x)=(\ztrans x)\delta=x$はすでに示したので，$\ztrans(\check{\ztrans}P(\lagop))=P(\lagop)$が示せれば$\check{\ztrans}=\ztrans^{-1}$といえる．
上の同型から$\deg P(z)< N$を仮定してよい．$P(z)=\sum_{m=0}^{N-1}p_mz^m$とし，$m$を$N$で割ったあまりを$m\rem N$と書く，すると
$$
\check{\ztrans}P(\lagop) = \sum_{m=0}^{N-1}p_m\lagop^m\delta
= \seq{p_{m\rem N}}_{m\in\numset{Z}},
\quad\ztrans(\check{\ztrans}P(\lagop)) = \sum_{m=0}^{N-1}p_{m\rem N}\lagop^m
= P(\lagop)
$$
である．
以上により，$\ztrans$は（加法を保つ）全単射である．よって，$\cycles{N}$の乗法を$x\ast y=\ztrans^{-1}((\ztrans x)(\ztrans y))$で定めれば，3つ組$(\cycles{N},+,\ast)$は$\numset{C}[\lagop]$と同型な環になる．
$x\ast y$を$x$と$y$の一般項を用いて表そう．
$$
(\ztrans x)(\ztrans y) = \pqty{\sum_{m=0}^{N-1}x_m\lagop^m}\pqty{\sum_{n=0}^{N-1}y_n\lagop^n}
= \sum_{m=0}^{N-1}\sum_{n=0}^{N-1}x_my_n\lagop^{m+n}
$$
であり，$k=m+n$とおくと
$$
(\ztrans x)(\ztrans y) = \sum_{m=0}^{N-1}\sum_{k=m}^{N-1+m}x_my_{k-m}\lagop^k
$$
となる．$\sum_{k=m}^{N-1+m}$は1周期にわたる和なので，範囲を$\sum_{k=0}^{N-1}$に変えてよい．よって
$$
(\ztrans x)(\ztrans y) = \sum_{m=0}^{N-1}\sum_{k=0}^{N-1}x_my_{k-m}\lagop^k
= \sum_{k=0}^{N-1}\pqty{\sum_{m=0}^{N-1}x_my_{k-m}}\lagop^k
$$
であり，$z=x\ast y$とおくと
$$
z = \sum_{k=0}^{N-1}\pqty{\sum_{m=0}^{N-1}x_my_{k-m}}\lagop^k\delta,
\quad z_k = \sum_{m=0}^{N-1}x_my_{k-m}
$$
となる．
$x,y\in\cycles{N}$とする．次式で定義される$x\ast y\in\cycles{N}$を，$x$と$y$の巡回畳み込みという．また，$x\ast y$は$\ztrans(x\ast y)=(\ztrans x)(\ztrans y)$を満たす．
$$
x\ast y = z,
\quad z_k = \sum_{m=0}^{N-1}x_my_{k-m}
$$
$\bar{z}=z+\ideal{z^N-1}$とする．同型写像$\psi\colon\numset{C}[z]/\ideal{z^N-1}\to\numset{C}[\lagop]$，$P(\bar{z})\mapsto P(\lagop)$を用いて，$\img\ztrans$を$\numset{C}[z]/\ideal{z^N-1}$へと変えた写像$\psi^{-1}\circ\ztrans$を$\tilde{\ztrans}$とおく．つまり
$$
\tilde{\ztrans}\colon\cycles{N} \to \numset{C}[z]/\ideal{z^N-1},
\quad\seq{x_n}_{n\in\numset{Z}} \mapsto \sum_{n=0}^{N-1}x_n\bar{z}^n
$$
である．
写像$f\colon\numset{C}[z]\to\numset{C}^N$を$P(z)\mapsto\seq{P(\zeta^k)}_{k=0}^{N-1}$（$\zeta=\napr^{2\krez\iuni/N}$）で定義する．明らかに，$f$は環準同型である．
$\ker f=\ideal{z^N-1}$である．
$P(z)\in\ideal{z^N-1}$なら，$P(z)=Q(z)(z^N-1)$とおくと$f(P(z))=\seq{Q(\zeta^k)(\zeta^{kN}-1)}_{k=0}^{N-1}=0$である．また$P(z)\in\ker f$なら，因数定理より$P(z)$は$\prod_{k=0}^{N-1}(z-\zeta^k)=z^N-1$で割り切れる．
上の命題から，写像$\bar{f}\colon\numset{C}[z]/\ideal{z^N-1}\to\numset{C}^N$，$P(\bar{z})\mapsto\seq{P(\zeta^k)}_{k=0}^{N-1}$はwell-definedな環同型である．よって，写像$\ftrans$を$\bar{f}\circ\tilde{\ztrans}$で定義すると，$\ftrans$は$(\cycles{N},+,\ast)$から$\numset{C}^N$への環同型である．実際に$\hat{x}=\ftrans x$を計算すると
$$
\ftrans x = f\pqty{\sum_{n=0}^{N-1}x_n\bar{z}^n},
\quad\hat{x}_k = \sum_{n=0}^{N-1}x_n\zeta^{kn}
$$
となる．これは（符号の違いを除いて）$x$の離散フーリエ変換である．
この記事を高評価した人
この記事に送られたバッジ
投稿者
