離散Fourier変換と反転公式

同義語：discrete Fourier transform and inversion formula

概要

前提知識: 1の冪根による振り分けの公式, 巡回群の指標と直交関係, 複素数, de Moivreの定理

この記事で考えること

1の冪根による振り分けの公式では、多項式 $f(x)$ の $1$ の $n$ 乗根での値 $f(1),f(\zeta),\dots,f(\zeta^{n-1})$ から、係数を添字の余りで振り分けた和が取り出せることを見た。特に次数が $n-1$ 以下の多項式なら、余りごとの和は係数そのものである。つまり $n$ 個の値から $n$ 個の係数がすべて復元できる。

4 つの値から 4 つの係数を戻す

$f(x)=1+2x+3x^2+4x^3$ の、$1$ の 4 乗根 $1,i,-1,-i$ での値は
$$ f(1)=10,\quad f(i)=1+2i-3-4i=-2-2i,\quad f(-1)=1-2+3-4=-2,\quad f(-i)=1-2i-3+4i=-2+2i $$
である（$i^2=-1$、$i^3=-i$ を使った）。逆に、この 4 つの値だけを知っているとき、$x^1$ の係数は振り分けの公式（$n=4$、$\zeta=i$、$r=1$）により
$$ \frac14\bigl(f(1)+i^{-1}f(i)+i^{-2}f(-1)+i^{-3}f(-i)\bigr)=\frac14\bigl(10+(-i)(-2-2i)+(-1)(-2)+i(-2+2i)\bigr) $$
で求まる。$(-i)(-2-2i)=2i+2i^2=-2+2i$、$i(-2+2i)=-2i+2i^2=-2-2i$ なので、括弧の中は $10+(-2+2i)+2+(-2-2i)=8$ であり、係数は $\frac84=2$ と正しく戻る。

係数の列 $(1,2,3,4)$ から値の列を作る操作と、値の列から係数の列に戻す操作は、互いに逆の操作になっている。これを長さ $n$ の数列一般の言葉で述べたものが、離散 Fourier 変換とその反転公式である。この記事で答える問いは次のとおりである。

問い	答えるボックス
数列の離散 Fourier 変換とは何か	def-dft-dft
変換した列から、もとの列に戻せるか	thm-dft-inversion
振り分けの公式と反転公式はどういう関係か	prop-dft-filter
変換すると、どんな計算が簡単になるか	prop-dft-convolution、prop-dft-circulant
5 つの未知数の巡回的な連立方程式をどう見通すか	rem-dft-oly63-view

以下、$n$ は正の整数、$\zeta:=\zeta_n=\cos\frac{2\pi}n+i\sin\frac{2\pi}n$ とする。$n=2,3,4$ では $\zeta=-1,\ \omega,\ i$ である（$\omega=\frac{-1+\sqrt3\,i}2$）。

準備：長さ $n$ の数列と冪の和

長さ $n$ の数列 $f(0),f(1),\dots,f(n-1)$（複素数の列）を考える。添字は $n$ で割った余りで考え、$f(n)=f(0)$、$f(-1)=f(n-1)$ のように、すべての整数 $k$ について $f(k)$ を $f(k+n)=f(k)$ となるように延ばしておく。これは、$f$ を群 $\mathbb{Z}/n\mathbb{Z}$ の上の関数と見ることである（巡回群の指標と直交関係）。
$\zeta^m$ についても、$\zeta^n=1$ から $\zeta^{m+n}=\zeta^m$ なので、$\zeta^m$ は $m$ を $n$ で割った余りだけで決まる。また $|\zeta^m|=1$ なので、共役複素数について
$$ \overline{\zeta^m}=\cos\frac{2\pi m}n-i\sin\frac{2\pi m}n=\cos\frac{-2\pi m}n+i\sin\frac{-2\pi m}n=\zeta^{-m} $$
である（$\cos$ は偶関数、$\sin$ は奇関数であることと de Moivreの定理を使った）。
この記事の証明はすべて、1の冪根による振り分けの公式で示した冪の和の補題から出る。記事の中で完結させるため、証明とともにもう一度述べる。

1 の $n$ 乗根の冪の和（復習）

整数 $m$ について
$$ \frac1n\sum_{t=0}^{n-1}\zeta^{tm}=\begin{cases}1&(n\mid m)\\ 0&(n\nmid m)\end{cases} $$
である。

等比数列の和

$q:=\zeta^m$ とおくと、和 $\sum_{t=0}^{n-1}\zeta^{tm}$ は初項 $1$、公比 $q$ の等比数列の $n$ 項の和 $1+q+\cdots+q^{n-1}$ である。
段 1（$n\mid m$ のとき）：$m=nl$ と書けて $q=(\zeta^n)^l=1$ なので、和は $n$ であり、$n$ で割ると $1$ である。
段 2（$n\nmid m$ のとき）：$m$ を $n$ で割った余りを $s$ とすると $0< s< n$ で、$q=\zeta^s=\cos\frac{2\pi s}n+i\sin\frac{2\pi s}n$ である。偏角 $\frac{2\pi s}n$ は $0$ と $2\pi$ の間にあるので $q\ne1$ である。等比数列の和の公式により和は $\dfrac{q^n-1}{q-1}$ で、$q^n=(\zeta^n)^m=1$ なので分子が $0$、和は $0$ である。$\square$

特に $0\le k,l\le n-1$ のとき、$n\mid k-l$ となるのは $k=l$ のときだけである（$k-l$ は $-(n-1)$ 以上 $n-1$ 以下だから）。したがって
$$ \frac1n\sum_{t=0}^{n-1}\zeta^{t(k-l)}=\begin{cases}1&(k=l)\\ 0&(k\ne l)\end{cases} $$
である。これが以下の証明で何度も使う形である。

離散 Fourier 変換

離散Fourier変換

長さ $n$ の数列 $f(0),\dots,f(n-1)$ に対し、
$$ \widehat f(t):=\sum_{k=0}^{n-1}f(k)\,\zeta^{-tk}\qquad(t=0,1,\dots,n-1) $$
で定まる長さ $n$ の数列 $\widehat f$ を、$f$ の離散 Fourier 変換という。$\zeta^{-tk}$ は $t$ を $n$ で割った余りだけで決まるので、$\widehat f(t)$ もすべての整数 $t$ に $\widehat f(t+n)=\widehat f(t)$ となるように延ばしておく。

定義の和は、係数が $f(0),\dots,f(n-1)$ の多項式 $P(x):=\sum_{k=0}^{n-1}f(k)x^k$ に $x=\zeta^{-t}$ を代入した値 $P(\zeta^{-t})$ である。巡回群の指標と直交関係の言葉では、$\zeta^{-tk}=\overline{\chi_t(\overline k)}$ なので、$\widehat f(t)$ は $f$ と指標 $\chi_t$ の「内積」である。

$n=2$ と $n=3$ の変換

$n=2$（$\zeta=-1$）：$\widehat f(0)=f(0)+f(1)$、$\widehat f(1)=f(0)-f(1)$ である。たとえば $f=(3,5)$ なら $\widehat f=(8,-2)$。和と差をとる操作である。
$n=3$（$\zeta=\omega$）、$f=(1,0,0)$：$\widehat f(t)=1\cdot\omega^0=1$ なので $\widehat f=(1,1,1)$。
$n=3$、$f=(1,1,1)$：$\widehat f(0)=3$、$\widehat f(1)=1+\omega^{-1}+\omega^{-2}=1+\omega^2+\omega=0$、$\widehat f(2)=1+\omega^{-2}+\omega^{-4}=1+\omega+\omega^2=0$ なので $\widehat f=(3,0,0)$（$\omega^3=1$ から $\omega^{-1}=\omega^2$、$\omega^{-2}=\omega$、$\omega^{-4}=\omega^{-1}=\omega^2$）。
2 と 3 のように、1 か所だけが $1$ の列は一定の列に、一定の列は 1 か所だけが $0$ でない列に変わる。

(1, 2, 3, 4) を手で変換する

$n=4$、$\zeta=i$、$f=(1,2,3,4)$ とする。$i^{-1}=-i$、$i^{-2}=-1$、$i^{-3}=i$ なので、$\zeta^{-tk}=i^{-tk}$ の表は次のとおりである（行が $t$、列が $k$）。

	$k=0$	$k=1$	$k=2$	$k=3$
$t=0$	$1$	$1$	$1$	$1$
$t=1$	$1$	$-i$	$-1$	$i$
$t=2$	$1$	$-1$	$1$	$-1$
$t=3$	$1$	$i$	$-1$	$-i$

各行と $f=(1,2,3,4)$ を掛けて足すと
$$ \widehat f(0)=1+2+3+4=10,\quad \widehat f(1)=1-2i-3+4i=-2+2i,\quad \widehat f(2)=1-2+3-4=-2,\quad \widehat f(3)=1+2i-3-4i=-2-2i $$
である。ex-dft-intro の多項式の値と比べると、$\widehat f(1)=f(-i)$、$\widehat f(3)=f(i)$ で、$\widehat f(t)$ は $x=\zeta^{-t}$ での値になっている。

数列 (1, 2, 3, 4)（左）と、その離散 Fourier 変換の 4 つの値を複素平面に置いたもの（右）
図 1 の右で、$\widehat f(0)=10$ は数列の総和であり、ほかの 3 つは原点の近くにある。$\widehat f(1)$ と $\widehat f(3)$ は互いに共役である。$f$ が実数の列なら、$\widehat f(n-t)=\sum_kf(k)\zeta^{tk}=\overline{\widehat f(t)}$ となるからである（$\overline{\zeta^{-tk}}=\zeta^{tk}$ を使った）。

主定理：反転公式と Parseval の等式

ex-dft-intro では、4 つの値から係数 $2$ を戻せた。どの長さの数列でも、変換からもとの列に戻せる。

反転公式とParsevalの等式

長さ $n$ の数列 $f$ について、次が成り立つ。

（反転公式）$k=0,1,\dots,n-1$ について
$$ f(k)=\frac1n\sum_{t=0}^{n-1}\widehat f(t)\,\zeta^{tk}. $$
（Parseval の等式）
$$ \sum_{k=0}^{n-1}|f(k)|^2=\frac1n\sum_{t=0}^{n-1}|\widehat f(t)|^2. $$

反転公式は、変換の式の $\zeta^{-tk}$ を $\zeta^{tk}$ に替え、最後に $n$ で割れば逆の操作になる、と言っている。Parseval の等式は「長さの 2 乗」を 2 通りに計算した式で、関数の積の積分を内積とみる関数の内積（高校数学）の話でも、同じ形の等式が無限次元のピタゴラスの定理として現れる。

定義を代入して冪の和の補題を使う

方針：右辺に $\widehat f$ の定義を代入し、和の順序を入れ替えて、lem-dft-sum を使う。どちらの式も同じ方針で示す。
1 の証明。
段 1（代入）：$\widehat f(t)=\sum_{l=0}^{n-1}f(l)\zeta^{-tl}$ を右辺に代入すると
$$ \frac1n\sum_{t=0}^{n-1}\widehat f(t)\,\zeta^{tk}=\frac1n\sum_{t=0}^{n-1}\sum_{l=0}^{n-1}f(l)\,\zeta^{-tl}\zeta^{tk}=\frac1n\sum_{t=0}^{n-1}\sum_{l=0}^{n-1}f(l)\,\zeta^{t(k-l)} $$
である。
段 2（和の順序の入れ替え）：有限個の和なので $t$ と $l$ の順序を入れ替えてよく、
$$ =\sum_{l=0}^{n-1}f(l)\cdot\Bigl(\frac1n\sum_{t=0}^{n-1}\zeta^{t(k-l)}\Bigr) $$
となる。
段 3（冪の和の補題）：lem-dft-sum の後に述べた形により、括弧の中は $l=k$ のとき $1$、$l\ne k$ のとき $0$ である。よって和は $l=k$ の項 $f(k)$ だけが残り、右辺は $f(k)$ に等しい。
2 の証明。
段 4（共役の計算）：$|z|^2=z\overline z$ なので $|\widehat f(t)|^2=\widehat f(t)\,\overline{\widehat f(t)}$ である。共役は和と積に分配し、$\overline{\zeta^{-tl}}=\zeta^{tl}$（準備の節）なので
$$ \overline{\widehat f(t)}=\sum_{l=0}^{n-1}\overline{f(l)}\,\zeta^{tl} $$
である。
段 5（展開と入れ替え）：
$$ \sum_{t=0}^{n-1}|\widehat f(t)|^2=\sum_{t=0}^{n-1}\sum_{k=0}^{n-1}\sum_{l=0}^{n-1}f(k)\overline{f(l)}\,\zeta^{-tk}\zeta^{tl}=\sum_{k=0}^{n-1}\sum_{l=0}^{n-1}f(k)\overline{f(l)}\cdot\sum_{t=0}^{n-1}\zeta^{t(l-k)} $$
である。
段 6（冪の和の補題）：最後の $t$ の和は、$k=l$ のとき $n$、$k\ne l$ のとき $0$ である。よって $k=l$ の項だけが残り、全体は $n\sum_kf(k)\overline{f(k)}=n\sum_k|f(k)|^2$ である。両辺を $n$ で割って 2 を得る。$\square$

$n=2$ で確かめる

ex-dft-small の $f=(3,5)$、$\widehat f=(8,-2)$ で確かめる。$\zeta=-1$ である。

反転公式：$f(0)=\frac12\bigl(8+(-2)\bigr)=3$、$f(1)=\frac12\bigl(8\cdot1+(-2)\cdot(-1)\bigr)=\frac{10}2=5$。
Parseval の等式：左辺 $3^2+5^2=34$、右辺 $\frac12\bigl(8^2+(-2)^2\bigr)=\frac{68}2=34$。

(1, 2, 3, 4) に戻す

ex-dft-four の $\widehat f=(10,\,-2+2i,\,-2,\,-2-2i)$ から $f$ を戻す。$\zeta^{tk}=i^{tk}$ である。

$k=0$：$\frac14\bigl(10+(-2+2i)+(-2)+(-2-2i)\bigr)=\frac44=1$。
$k=1$：各項は $10$、$(-2+2i)i=-2i-2$、$(-2)(-1)=2$、$(-2-2i)(-i)=2i-2$ で、和は $8$、$\frac84=2$。
$k=2$：$i^{2t}=(-1)^t$ なので $\frac14\bigl(10-(-2+2i)+(-2)-(-2-2i)\bigr)=\frac{12}4=3$。
$k=3$：各項は $10$、$(-2+2i)(-i)=2i+2$、$(-2)(-1)=2$、$(-2-2i)i=-2i+2$ で、和は $16$、$\frac{16}4=4$。
Parseval の等式は、左辺 $1+4+9+16=30$、右辺 $\frac14(100+8+4+8)=\frac{120}4=30$ である（$|-2\pm2i|^2=4+4=8$）。

振り分けの公式は反転公式である

振り分けの公式は、次数が $n$ 以上の多項式にも使えた。係数を余りごとにまとめた列を考えると、それも反転公式の特別な場合になる。

振り分けの公式と反転公式

$f(x)=\sum_{k=0}^Ma_kx^k$ を複素数係数の多項式とし、$r=0,1,\dots,n-1$ について
$$ A(r):=\sum_{\substack{0\le k\le M\\ k\equiv r\ (\mathrm{mod}\ n)}}a_k $$
とおく（係数を添字の余りでまとめた長さ $n$ の列）。このとき、次が成り立つ。

$f(\zeta^t)=\widehat A(-t)$（$t$ は整数）。
反転公式を $A$ に使うと、振り分けの公式 $A(r)=\dfrac1n\displaystyle\sum_{t=0}^{n-1}\zeta^{-tr}f(\zeta^t)$ が得られる。

項を余りごとにまとめる

段 1（1 の証明）：$f(\zeta^t)=\sum_{k=0}^Ma_k\zeta^{tk}$ の項を、$k$ を $n$ で割った余り $r$ ごとにまとめる。$k\equiv r\pmod n$ なら $\zeta^{tk}=\zeta^{tr}$（$\zeta^m$ は $m$ の余りだけで決まる）なので、
$$ f(\zeta^t)=\sum_{r=0}^{n-1}\Bigl(\sum_{k\equiv r}a_k\Bigr)\zeta^{tr}=\sum_{r=0}^{n-1}A(r)\,\zeta^{tr}=\sum_{r=0}^{n-1}A(r)\,\zeta^{-(-t)r}=\widehat A(-t) $$
である（最後は def-dft-dft で $t$ を $-t$ にしたもの）。
段 2（2 の証明）：thm-dft-inversion の 1 を $A$ に使うと $A(r)=\frac1n\sum_{s=0}^{n-1}\widehat A(s)\zeta^{sr}$ である。$\widehat A(s)$ と $\zeta^{sr}$ は $s$ の余りだけで決まるので、$s$ は $0,1,\dots,n-1$ の代わりに $0,-1,\dots,-(n-1)$ を動かしてもよい（$-t$ を $n$ で割った余りは、$t=0,\dots,n-1$ のとき $0,n-1,n-2,\dots,1$ で、全部の余りを 1 回ずつとる）。$s=-t$ とおいて段 1 を使うと
$$ A(r)=\frac1n\sum_{t=0}^{n-1}\widehat A(-t)\,\zeta^{-tr}=\frac1n\sum_{t=0}^{n-1}\zeta^{-tr}f(\zeta^t) $$
である。$\square$

$(1+x)^4$ の係数を 4 つおきにまとめる

$f(x)=(1+x)^4=1+4x+6x^2+4x^3+x^4$、$n=4$ とする。$x^4$ の係数は余り $0$ に入るので、$A=(1+1,\,4,\,6,\,4)=(2,4,6,4)$ である。

変換：$\widehat A(0)=16$、$\widehat A(1)=2-4i-6+4i=-4$、$\widehat A(2)=2-4+6-4=0$、$\widehat A(3)=2+4i-6-4i=-4$。
値：$f(1)=16$、$f(i)=(1+i)^4=\bigl((1+i)^2\bigr)^2=(2i)^2=-4$、$f(-1)=0$、$f(-i)=(1-i)^4=(-2i)^2=-4$。
たとえば $f(i)=f(\zeta^1)=\widehat A(-1)=\widehat A(3)=-4$ で、prop-dft-filter の 1 と一致する。反転公式で $A(0)=\frac14\bigl(16+(-4)+0+(-4)\bigr)=2$ と戻り、これは $\binom40+\binom44=2$ である（二項係数を余りで分けた和）。

変換で簡単になる計算：畳み込みと巡回行列

離散 Fourier 変換が役に立つのは、変換すると「ずらして掛けて足す」計算が、成分ごとの掛け算に変わるからである。まず高校の多項式の計算で、その計算を見ておく。

多項式の積を $x^4=1$ として計算する

$P(x)=1+2x+3x^2+4x^3$ と $Q(x)=1+x$ を掛けると
$$ P(x)Q(x)=1+3x+5x^2+7x^3+4x^4 $$
である。ここで $x^4=1$ とみなして（$x^4-1$ で割った余りをとって）$x^4$ を $1$ に置き換えると、$5+3x+5x^2+7x^3$ になる。係数の列で書くと、$(1,2,3,4)$ と $(1,1,0,0)$ から $(5,3,5,7)$ ができた。$x^k$ の係数は「$P$ の $x^m$ の係数」と「$Q$ の $x^{k-m}$ の係数」の積を、$m$ について、添字を $4$ で割った余りで考えて足したものである。

巡回畳み込み

長さ $n$ の数列 $f,g$ に対し、
$$ (f*g)(k):=\sum_{m=0}^{n-1}f(m)\,g(k-m)\qquad(k=0,1,\dots,n-1) $$
で定まる長さ $n$ の数列 $f*g$ を、$f$ と $g$ の巡回畳み込みという。$g(k-m)$ の添字 $k-m$ は $n$ で割った余りで考える（$k-m<0$ なら $n$ を足す）。

ex-dft-poly-mult の $(5,3,5,7)$ は、$f=(1,2,3,4)$ と $g=(1,1,0,0)$ の巡回畳み込みである（ex-dft-conv-check で成分を確かめる）。

畳み込みは変換で積になる

長さ $n$ の数列 $f,g$ について、すべての $t$ で
$$ \widehat{f*g}(t)=\widehat f(t)\,\widehat g(t) $$
である。

和の変数を取り替える

方針：$\zeta^{-tk}=\zeta^{-tm}\zeta^{-t(k-m)}$ と分けて、$k-m$ を新しい変数にする。
段 1（定義を代入）：
$$ \widehat{f*g}(t)=\sum_{k=0}^{n-1}\sum_{m=0}^{n-1}f(m)\,g(k-m)\,\zeta^{-tk}=\sum_{m=0}^{n-1}f(m)\,\zeta^{-tm}\sum_{k=0}^{n-1}g(k-m)\,\zeta^{-t(k-m)} $$
である（和の順序を入れ替え、$\zeta^{-tk}=\zeta^{-tm}\zeta^{-t(k-m)}$ と分けた）。
段 2（変数の取り替え）：$m$ を固定する。$k$ が $0,1,\dots,n-1$ を動くとき、$j:=k-m$ を $n$ で割った余りは $0,1,\dots,n-1$ をちょうど 1 回ずつとる（$k$ が $n$ 個の異なる余りをとり、$m$ を引くと異なる余りは異なる余りに移るから）。$g(j)$ と $\zeta^{-tj}$ は $j$ の余りだけで決まるので、
$$ \sum_{k=0}^{n-1}g(k-m)\,\zeta^{-t(k-m)}=\sum_{j=0}^{n-1}g(j)\,\zeta^{-tj}=\widehat g(t) $$
である。
段 3：段 1 に戻すと $\widehat{f*g}(t)=\sum_mf(m)\zeta^{-tm}\cdot\widehat g(t)=\widehat f(t)\,\widehat g(t)$ である。$\square$

畳み込みの変換を確かめる

$f=(1,2,3,4)$、$g=(1,1,0,0)$、$f*g=(5,3,5,7)$ とする（$n=4$）。

畳み込みの成分：$k=0$ では、$g(0-m)$ が $0$ でないのは $m=0$（$g(0)=1$）と $m=3$（$g(-3)=g(1)=1$）なので、$(f*g)(0)=f(0)+f(3)=1+4=5$。同様に $(f*g)(k)=f(k)+f(k-1)$ で、$(f*g)(1)=2+1=3$、$(f*g)(2)=3+2=5$、$(f*g)(3)=4+3=7$。
$\widehat f=(10,\,-2+2i,\,-2,\,-2-2i)$（ex-dft-four）。
$\widehat g(t)=1+i^{-t}$ なので $\widehat g=(2,\,1-i,\,0,\,1+i)$。
積：$10\cdot2=20$、$(-2+2i)(1-i)=-2+2i+2i-2i^2=4i$、$(-2)\cdot0=0$、$(-2-2i)(1+i)=-2-2i-2i-2i^2=-4i$。
$f*g$ を直接変換すると、$5+3+5+7=20$、$5-3i-5+7i=4i$、$5-3+5-7=0$、$5+3i-5-7i=-4i$ で、4 と一致する。

多項式の言葉では、prop-dft-convolution は「$PQ$ の $x=\zeta^{-t}$ での値は、$P$ の値と $Q$ の値の積」という当たり前の式である。$x^n=1$ とみなしても $1$ の $n$ 乗根での値は変わらないので、巡回畳み込みでも成り立つ。整数の掛け算の筆算も、繰り上げを後回しにすると各位の数字の畳み込みになる（掛け算の筆算と畳み込み）。上の prop-dft-convolution は、大きな整数の掛け算を速く行う方法の土台でもある（「さらに先へ」の高速 Fourier 変換）。

巡回行列の固有ベクトル

各行が 1 つ上の行を右へ 1 つずらしたものになっている正方行列を巡回行列という。正確には、長さ $n$ の数列 $c$ に対し、$(j,k)$ 成分（$j,k=0,\dots,n-1$）が $c(k-j)$（添字は $n$ で割った余り）の $n$ 次正方行列 $C$ である。たとえば $n=3$ では
$$ C=\begin{pmatrix}c(0)&c(1)&c(2)\\ c(2)&c(0)&c(1)\\ c(1)&c(2)&c(0)\end{pmatrix} $$
である。$0$ でないベクトル $v$ と数 $\lambda$ が $Cv=\lambda v$ を満たすとき、$v$ を $C$ の固有ベクトル、$\lambda$ を固有値という。

巡回行列の固有ベクトル

$t=0,1,\dots,n-1$ について、ベクトル $v_t:=\bigl(1,\ \zeta^t,\ \zeta^{2t},\ \dots,\ \zeta^{(n-1)t}\bigr)^{\top}$ は巡回行列 $C$ の固有ベクトルで、固有値は
$$ \lambda_t:=\sum_{m=0}^{n-1}c(m)\,\zeta^{tm} $$
である。$v_t$ は $c$ によらない。

第 $j$ 成分を計算する

段 1：$Cv_t$ の第 $j$ 成分は $\sum_{k=0}^{n-1}c(k-j)\,\zeta^{tk}$ である。
段 2：$j$ を固定し、$m:=k-j$ とおく。prf-prop-dft-convolution の段 2 と同じく、$k$ が $0,\dots,n-1$ を動くとき $m$ の余りは $0,\dots,n-1$ を 1 回ずつとる。$\zeta^{tk}=\zeta^{t(j+m)}=\zeta^{tj}\zeta^{tm}$ なので
$$ \sum_{k=0}^{n-1}c(k-j)\,\zeta^{tk}=\zeta^{tj}\sum_{m=0}^{n-1}c(m)\,\zeta^{tm}=\lambda_t\,\zeta^{tj} $$
である。$\zeta^{tj}$ は $v_t$ の第 $j$ 成分なので、$Cv_t=\lambda_tv_t$ である。$v_t$ の第 $0$ 成分は $1$ なので $v_t\ne0$ である。$\square$

2 次と 3 次の巡回行列

$n=2$、$c=(2,1)$：$C=\begin{pmatrix}2&1\\ 1&2\end{pmatrix}$。$\zeta=-1$ で、$v_0=(1,1)^{\top}$、$v_1=(1,-1)^{\top}$。$\lambda_0=2+1=3$、$\lambda_1=2-1=1$ である。実際 $Cv_0=(3,3)^{\top}=3v_0$、$Cv_1=(1,-1)^{\top}=v_1$。
$n=3$、$c=(2,1,0)$：$C=\begin{pmatrix}2&1&0\\ 0&2&1\\ 1&0&2\end{pmatrix}$。$\lambda_t=2+\omega^t$ なので、$\lambda_0=3$、$\lambda_1=2+\omega=\frac32+\frac{\sqrt3}2i$、$\lambda_2=2+\omega^2=\frac32-\frac{\sqrt3}2i$ である。$v_1=(1,\omega,\omega^2)^{\top}$ で確かめると、$Cv_1$ の成分は $2+\omega$、$2\omega+\omega^2=\omega(2+\omega)$、$1+2\omega^2=\omega^2(\omega+2)$（$\omega^3=1$）で、$(2+\omega)v_1$ に等しい。

巡回行列 $C$ を掛けることは、ベクトルを数列と見て $c$ を裏返した列と巡回畳み込みをとることである。変換すると畳み込みは積になるので、$Cx=b$ の形の連立 1 次方程式は、$\widehat x$ の成分ごとの $n$ 個の 1 次方程式に分かれる。次の節の問題がその例である。

数学オリンピックの問題から

1963 年第 4 問：巡回的な連立方程式

5 つの未知数が輪になって並び、どの式も「両隣の和が自分の $y$ 倍」という形をしている連立方程式である。左辺は巡回行列を掛けたものなので、離散 Fourier 変換で式がばらばらに分かれる。

国際数学オリンピック（1963 年）第 4 問

$y$ をパラメータとして、連立方程式
$$ x_5+x_2=yx_1,\quad x_1+x_3=yx_2,\quad x_2+x_4=yx_3,\quad x_3+x_5=yx_4,\quad x_4+x_1=yx_5 $$
の解 $x_1,x_2,x_3,x_4,x_5$ をすべて求めよ。
出典：国際数学オリンピック（1963 年）第 4 問（Oly63）。和訳は本記事による。

高校数学で解く

方針：$x_1=s$、$x_2=t$ とおき、はじめの 3 式で $x_3,x_4,x_5$ を $s,t$ で表して、残りの 2 式に代入する。
段 1（$x_3,x_4,x_5$ を表す）：第 1 式から $x_5=ys-t$、第 2 式から $x_3=yt-s$、第 3 式から
$$ x_4=yx_3-x_2=y(yt-s)-t=(y^2-1)t-ys $$
である。
段 2（第 4 式）：$x_3+x_5=yx_4$ に代入すると、左辺は $(yt-s)+(ys-t)=(y-1)(s+t)$、右辺は $(y^3-y)t-y^2s$ である。右辺から左辺を引いて整理すると
$$ (y^3-2y+1)t-(y^2+y-1)s=0 $$
となる。$y^3-2y+1=(y-1)(y^2+y-1)$ なので（右辺を展開すると $y^3+y^2-y-y^2-y+1$ となり一致する）、この式は $(y^2+y-1)\bigl((y-1)t-s\bigr)=0$ である。
段 3（第 5 式）：$x_4+x_1=yx_5$ に代入すると、$(y^2-1)t-ys+s=y^2s-yt$ である。移項して整理すると $(y^2+y-1)t-(y^2+y-1)s=0$、すなわち $(y^2+y-1)(t-s)=0$ である。
段 4（$y^2+y-1\ne0$ の場合）：段 2・段 3 から $s=(y-1)t$ かつ $s=t$ なので、$(y-1)t=t$、すなわち $(y-2)t=0$ である。

$y=2$ のとき：$s=t$ は任意で、段 1 から $x_3=2t-t=t$、$x_4=3t-2t=t$、$x_5=2t-t=t$。解は $x_1=\cdots=x_5=t$（$t$ は任意）。
$y\ne2$ のとき：$t=0$、$s=0$ で、解は $x_1=\cdots=x_5=0$ だけ。
段 5（$y^2+y-1=0$、すなわち $y=\frac{-1\pm\sqrt5}2$ の場合）：段 2・段 3 の式は $s,t$ によらず成り立つので、$s,t$ は任意である。$y^2-1=-y$ を使うと $x_4=-yt-ys=-y(s+t)$ なので、解は
$$ (x_1,x_2,x_3,x_4,x_5)=\bigl(s,\ t,\ yt-s,\ -y(s+t),\ ys-t\bigr)\qquad(s,t\text{ は任意}) $$
である。第 1〜3 式は段 1 の作り方から、第 4・5 式は段 2・段 3 から成り立つ。$\square$

y の特別な値 2, 2cos72°, 2cos144° は、1 の 5 乗根と共役の和として単位円から読める

大学数学で見ると

添字を $5$ で割った余りで考え、$x(k):=x_k$、$x(0):=x_5$ とおく。$n=5$、$\zeta=\zeta_5$ とする。
段 1（1 つの形にまとめる）：5 つの式はどれも、$k=0,1,2,3,4$ について
$$ x(k-1)+x(k+1)=y\,x(k) $$
の形である（$k=1$ が第 1 式で、$x(0)=x_5$）。これは三項間漸化式 $x(k+1)=y\,x(k)-x(k-1)$ と同じ形で、特性方程式 $\lambda^2-y\lambda+1=0$ の解が $\zeta^t,\zeta^{-t}$ になる $y$ のとき、周期 $5$ の解が現れる（三項間漸化式の一般論は三項間漸化式と行列の固有値で扱う）。
段 2（ずらしの変換）：数列 $k\mapsto x(k+1)$ の変換は、$j=k+1$ とおくと
$$ \sum_{k=0}^4x(k+1)\,\zeta^{-tk}=\sum_{j}x(j)\,\zeta^{-t(j-1)}=\zeta^t\,\widehat x(t) $$
である（$j$ の余りは $0,\dots,4$ を 1 回ずつとる）。同じく $k\mapsto x(k-1)$ の変換は $\zeta^{-t}\widehat x(t)$ である。
段 3（式が分かれる）：両辺を変換すると、$t=0,1,2,3,4$ について
$$ \bigl(\zeta^t+\zeta^{-t}-y\bigr)\,\widehat x(t)=0 $$
となる。5 つの未知数が絡んだ式が、未知数 1 つずつの 5 つの式に分かれた。$\zeta^t+\zeta^{-t}=2\cos\frac{2\pi t}5$ である（$\zeta^{-t}=\overline{\zeta^t}$）。
段 4（特別な値）：$t=0$ では $2$。$t=1,4$ では $2\cos72^\circ$、$t=2,3$ では $2\cos144^\circ$ である。$u:=\zeta+\zeta^{-1}$ とおくと、$1+\zeta+\zeta^2+\zeta^3+\zeta^4=0$（lem-dft-sum で $m=1$）を $\zeta^2$ で割って $(\zeta^2+\zeta^{-2})+(\zeta+\zeta^{-1})+1=0$、$\zeta^2+\zeta^{-2}=u^2-2$ から $u^2+u-1=0$ である。$\zeta^2+\zeta^{-2}$ も同じ式を満たす。実際、上の式 $(\zeta^2+\zeta^{-2})+u+1=0$ から $\zeta^2+\zeta^{-2}=-1-u$ なので
$$ (\zeta^2+\zeta^{-2})^2+(\zeta^2+\zeta^{-2})-1=(1+u)^2-(1+u)-1=u^2+u-1=0 $$
である。$\cos72^\circ>0>\cos144^\circ$ なので、$2\cos72^\circ=\frac{\sqrt5-1}2$、$2\cos144^\circ=-\frac{1+\sqrt5}2$ であり、これらは $y^2+y-1=0$ の 2 解である。
段 5（反転公式で戻す）：$y$ が $2,\ 2\cos72^\circ,\ 2\cos144^\circ$ のどれでもなければ、すべての $t$ で $\widehat x(t)=0$ で、thm-dft-inversion により $x=0$ である。$y=2$ なら $\widehat x(0)$ だけが自由で、$x(k)=\frac15\widehat x(0)$ は定数列である。$y=2\cos72^\circ$ なら $\widehat x(1),\widehat x(4)$ が自由で、$x(k)=\frac15\bigl(\widehat x(1)\zeta^k+\widehat x(4)\zeta^{-k}\bigr)$ の 2 次元の解になる。実数の解は $x_k=a\cos\frac{2\pi k}5+b\sin\frac{2\pi k}5$ の形である。$y=2\cos144^\circ$ も $\frac{4\pi k}5$ で同様である。
高校の解法で因子 $y^2+y-1$ が 2 回（第 4 式と第 5 式に）現れ、解が $s,t$ の 2 つの自由度をもったのは、この値の固有値が $t$ と $-t$ の 2 つから来ているからである。左辺は $c(1)=c(4)=1$、ほかは $0$ の巡回行列を掛けたもので、prop-dft-circulant の固有値 $\lambda_t=\zeta^t+\zeta^{4t}=2\cos\frac{2\pi t}5$ が、図 2 の 3 つの値である。

図 2 は、$1$ の 5 乗根 $\zeta_5^t$ と、その共役 $\zeta_5^{-t}$ の和 $2\cos\frac{2\pi t}5$ の位置（四角はその半分、つまり 2 点の中点）を示す。$\zeta_5^1$ と $\zeta_5^4$、$\zeta_5^2$ と $\zeta_5^3$ が同じ値を与えるので、特別な値は 3 つしかない。

例と反例

外した仮定	崩れる結論	ボックス
$\zeta$ が $1$ の原始 $n$ 乗根	反転公式（もとの列に戻せる）	ex-dft-nonprimitive
畳み込みの添字を $n$ で割った余りで考える	畳み込みが変換で積になる	ex-dft-truncated

反例：原始的でない 1 の冪根では戻せない

$n=4$ で、$\zeta=i$ の代わりに $-1$（$1$ の 4 乗根だが原始 4 乗根ではない）を使って $F(t):=\sum_{k=0}^3f(k)(-1)^{-tk}$ と定める。$f=(1,0,-1,0)$ では、$(-1)^{-tk}$ は $k=0,2$ でどちらも $1$ なので $F(t)=1-1=0$ がすべての $t$ で成り立つ。$f=(0,0,0,0)$ でも $F=(0,0,0,0)$ なので、$F$ から $f$ を区別できず、反転公式に当たる式は存在しない。lem-dft-sum の段 2 で使った「$n\nmid m$ なら $\zeta^m\ne1$」が、$\zeta=-1$、$m=2$ で成り立たないからである。

反例：添字を回さない畳み込み

$f=(1,2,3,4)$、$g=(1,1,0,0)$ で、$k-m<0$ の項を $0$ として（余りで回さずに）$h(k):=\sum_{0\le m\le k}f(m)g(k-m)$ を作ると $h=(1,3,5,7)$ である（ex-dft-poly-mult で $x^4$ の項を捨てたもの）。$\widehat h(0)=16$ だが、$\widehat f(0)\widehat g(0)=10\cdot2=20$ で一致しない。捨てた $4x^4$ の分だけずれる。仮定「添字を $n$ で割った余りで考える」を外すと、prop-dft-convolution は成り立たない。

さらに先へ

高速 Fourier 変換：定義どおりに $\widehat f$ を計算すると $n^2$ 回程度の掛け算が要る。$n=2^m$ のとき、$\zeta_n^2=\zeta_{n/2}$ を使って偶数番目と奇数番目に分けることをくり返すと、$n\log_2n$ 回程度に減る。prop-dft-convolution と組み合わせて、大きな整数や多項式の高速な掛け算、信号処理に使われる（高速Fourier変換）。
Fourier 級数：$\mathbb{Z}/n\mathbb{Z}$ を円周上の等間隔の $n$ 点と見て $n$ を大きくすると、$\zeta_n^{tk}$ は $\cos t\theta+i\sin t\theta$ に、平均 $\frac1n\sum_k$ は積分 $\frac1{2\pi}\int_0^{2\pi}d\theta$ に、冪の和の補題は三角関数の直交性に移る（三角関数の直交性（高校数学）、Fourier級数）。
変換 $f\mapsto\widehat f$ を $\frac1{\sqrt n}$ 倍したものは、Parseval の等式により長さを変えない 1 次変換である（SS03 Chapter 7）。prop-dft-circulant の固有ベクトル $v_0,\dots,v_{n-1}$ を並べた行列を使うと、すべての巡回行列が同時に対角化される（本記事では証明しない）。
大学向けの説明：一般の有限アーベル群の上の Fourier 変換を含む大学向けの説明は離散Fourier変換にある。