離散 Fourier 変換について確認してみたい。簡単のため長さ 3 の複素数列 $\{x_0, x_1, x_2\}$ を考える。
$$
\begin{align*}
y_m = \sum_{k=0}^2 x_k e^{-2 \pi i \frac{mk}{3}},\ 0 \leq m \leq 2
\tag{1}
\end{align*}
$$
と置く。次に $\{y_0, y_1, y_2\}$ を用いて
$$
\begin{align*}
z_n = \sum_{m=0}^2 y_m e^{2 \pi i \frac{nm}{3}},\ 0 \leq n \leq 2
\tag{2}
\end{align*}
$$
と置く。(1) 式を (2) 式に代入すると、$0 \leq n \leq 2$ に対して
$$
\begin{align*}
z_n &= \sum_{k=0}^2 y_m e^{2 \pi i \frac{nm}{3}} \\
&= \sum_{m=0}^2 \sum_{k=0}^2 x_k e^{-2 \pi i \frac{mk}{3}} e^{2 \pi i \frac{nm}{3}} \\
&= \sum_{k=0}^2 x_k \sum_{m=0}^2 e^{2 \pi i \frac{m(n-k)}{3}}
\tag{3}
\end{align*}
$$
となる。
$k=n$ の時
$$
\begin{align*}
\sum_{m=0}^2 e^{2 \pi i \frac{m(n-k)}{3}} = \sum_{m=0}^2 1 = 3
\tag{4}
\end{align*}
$$
である。
$k \neq n$ の時
まず $\left( e^{2 \pi i \frac{m(n-k)}{3}} \right)^3 = e^{2 \pi i m(n-k)} = 1$ なので、$e^{2 \pi i \frac{m(n-k)}{3}}$ は 1 の 3 乗根である。$m = 0, 1, 2$ に対してこれらが互いに異なることを見よう:
$0 \leq m, m^\prime \leq 2$ として、$2 \pi \frac{m(n-k)}{3} \equiv 2 \pi \frac{m^\prime(n-k)}{3} \mod 2 \pi$ とすると、$\frac{(m-m^\prime)(n - k)}{3} \in \Z$ となる。$m \neq m^\prime$ と仮定すると、$m - m^\prime$ と $3$ は互いに素であるので、$n-k$ が 3 の倍数である必要がある。ところが、$k \neq n$ かつ $0 \leq n, k \leq 2$ であるので矛盾する。よって、$m = m^\prime$ である。${}_\square$
よって、$e^{2 \pi i \frac{m(n-k)}{3}},\ 0 \leq m \leq 2$ は 1 の 3 乗根 $1, \omega, \omega^2$ のいずれかに割りあたる。ところで、$(1-\omega)(1 + \omega + \omega^2) = 1 -\omega^3 = 0$ であるので、$1 + \omega + \omega^2 = 0 $である。故に、
$$
\begin{align*}
\sum_{m=0}^2 e^{2 \pi i \frac{m(n-k)}{3}} = 0
\tag{5}
\end{align*}
$$
となる。(4) 式と (5) 式を (3) 式に代入すると
$$
\begin{align*}
z_n = 3 x_n
\end{align*}
$$
を得る。
以上の考察から、(1) 式と (2) 式を正規化して
$$
\begin{align*}
y_m &= \frac{1}{\sqrt{3}} \sum_{k=0}^2 x_k e^{-2 \pi i \frac{mk}{3}},\ 0 \leq m \leq 2 \\
z_n &= \frac{1}{\sqrt{3}} \sum_{m=0}^2 y_m e^{2 \pi i \frac{nm}{3}},\ 0 \leq n \leq 2
\end{align*}
$$
と置き直すと $z_n = x_n$ が成立する。これが列の長さが 3 の時の離散 Fourier 変換とその逆変換である。$\{x_0, x_1, x_2\} \longleftrightarrow \{y_0, y_1, y_2\}$ で列が行ったり来たりすることが分かった。
