離散Fourier変換

要点：逆写像は $\chi\mapsto(\chi(\cdot,0),\chi(0,\cdot))$ である。

$G$ が自明群ならすべて明らかなので、そうでないとする。有限アーベル群の基本定理 の定理「不変因子分解の存在」により、ある整数 $k_1,\dots,k_r\ge2$ について同型 $\phi\colon G\to\mathbb{Z}/k_1\mathbb{Z}\times\cdots\times\mathbb{Z}/k_r\mathbb{Z}$ がある。指標は同型 $\phi$ との合成で 1 対 1 に移り合うので、$G$ がこの直積そのものである場合に示せばよい。
1：ex-dft-cyclic により $\widehat{\mathbb{Z}/k\mathbb{Z}}\cong\mathbb{Z}/k\mathbb{Z}$ であり、prop-dft-product を $r-1$ 回使うと $\widehat G\cong\prod_j\widehat{\mathbb{Z}/k_j\mathbb{Z}}\cong G$ となる。とくに $\lvert\widehat G\rvert=\lvert G\rvert$ である。
2：$g=(a_1,\dots,a_r)\ne0$ なら、ある $j$ で $a_j\not\equiv0\pmod{k_j}$ である。第 $j$ 成分だけを見る指標 $\chi(x_1,\dots,x_r):=\zeta_{k_j}^{x_j}$ をとると、$\chi(g)=\zeta_{k_j}^{a_j}\ne1$ である。
3：$\mathrm{ev}(g)(\chi):=\chi(g)$ と書く。$\mathrm{ev}(g)$ は $\widehat G$ の指標であり（$(\chi\psi)(g)=\chi(g)\psi(g)$）、$\mathrm{ev}(g+h)=\mathrm{ev}(g)\mathrm{ev}(h)$ なので $\mathrm{ev}$ は準同型である。2 により核は $\{0\}$ なので単射であり、1 を $G$ と $\widehat G$ に使うと $\lvert\widehat{\widehat G}\rvert=\lvert\widehat G\rvert=\lvert G\rvert$ なので全射である。$\square$

1：$\eta:=\chi\overline\psi=\chi\psi^{-1}$ とおくと、左辺は $S:=\sum_g\eta(g)$ である。$\chi=\psi$ なら $\eta=\chi_0$ で $S=\lvert G\rvert$ である。$\chi\ne\psi$ なら $\eta(a)\ne1$ となる $a$ がある。$g\mapsto g+a$ は $G$ の全単射なので $S=\sum_g\eta(g+a)=\eta(a)S$ であり、$S=0$ である。
2：$\chi(g)\overline{\chi(h)}=\chi(g-h)=\mathrm{ev}(g-h)(\chi)$ である（prf-dft-dual の 3 の記号）。$\widehat G$ に 1 を使うと、$\mathrm{ev}(g-h)$ が $\widehat G$ の自明な指標かどうかで和は $\lvert\widehat G\rvert=\lvert G\rvert$ か $0$ になる。thm-dft-dual の 2 により、$\mathrm{ev}(g-h)$ が自明であることと $g=h$ は同値である。$\square$

1：定義を代入して和の順序を入れ替えると
$$ \frac1{\lvert G\rvert}\sum_\chi\widehat f(\chi)\chi(g)=\sum_{x\in G}f(x)\cdot\frac1{\lvert G\rvert}\sum_\chi\chi(g)\overline{\chi(x)} $$
であり、thm-dft-orthogonality の 2 により内側は $x=g$ のとき $1$、ほかで $0$ なので、右辺は $f(g)$ に等しい。
2：同じく
$$ \sum_\chi\widehat f(\chi)\overline{\widehat h(\chi)}=\sum_{x,y\in G}f(x)\overline{h(y)}\sum_\chi\chi(y)\overline{\chi(x)} $$
であり、thm-dft-orthogonality の 2 により内側は $x=y$ のとき $\lvert G\rvert$、ほかで $0$ なので、右辺は $\lvert G\rvert\sum_xf(x)\overline{h(x)}$ である。$h=f$ とすれば後半を得る。
3：線形性は定義から明らかである。1 により $\widehat f=0$ なら $f=0$ なので単射であり、thm-dft-dual の 1 により $\dim\mathbb{C}^G=\lvert G\rvert=\lvert\widehat G\rvert=\dim\mathbb{C}^{\widehat G}$ なので全射でもある。$\square$

$y=g-x$ と置き換え、$\overline{\chi(x+y)}=\overline{\chi(x)}\,\overline{\chi(y)}$ を使うと
$$ \widehat{f*h}(\chi)=\sum_{g,x}f(x)h(g-x)\overline{\chi(g)}=\sum_{x,y}f(x)\overline{\chi(x)}\,h(y)\overline{\chi(y)}=\widehat f(\chi)\,\widehat h(\chi) $$
である。$\square$

1 から 2：$k:=T\delta_0$ とおく。$\tau_a\delta_0=\delta_a$ と $f=\sum_af(a)\delta_a$ から $Tf=\sum_af(a)T\tau_a\delta_0=\sum_af(a)\tau_ak$ であり、その $g$ での値は $\sum_af(a)k(g-a)=(f*k)(g)$ である。
2 から 3：$f*k=k*f$ なので
$$ (\chi*k)(g)=\sum_{y}k(y)\chi(g-y)=\chi(g)\sum_yk(y)\overline{\chi(y)}=\widehat k(\chi)\,\chi(g) $$
である。$\chi\ne0$ なので $\chi$ は固有値 $\widehat k(\chi)$ の固有ベクトルである。
3 から 1：$(\tau_a\chi)(g)=\chi(g-a)=\overline{\chi(a)}\chi(g)$ なので、各指標は $\tau_a$ の固有ベクトルでもある。thm-dft-inversion の 3 により指標全体は $\mathbb{C}^G$ の基底なので、$T$ と $\tau_a$ はどちらもこの基底で対角行列に表され、互いに可換である。
最後の主張：2 から 3 の計算で固有値が $\widehat k(\chi)$ と分かり、行列式は基底をなす固有ベクトルの固有値の積である。$\square$

$(Cf)(j)=\sum_kc(k-j)f(k)=\sum_mc(m)f(j+m)$ である。$\check c(m):=c(-m)$ とおくと、これは $(f*\check c)(j)=\sum_xf(x)c(x-j)$ に等しい。$T:=C$ に thm-dft-invariant の 2 を $k=\check c$ で使えば、$v_t=\chi_t$ の固有値は $\widehat{\check c}(\chi_t)=\sum_mc(-m)\zeta_N^{-tm}=\sum_mc(m)\zeta_N^{tm}=\lambda_t$ であり、行列式も同じ定理から従う。$v_t$ の組は $c$ によらない。$\square$

$\| f\|_2^2:=\sum_g\lvert f(g)\rvert^2$、$M:=\max_\chi\lvert\widehat f(\chi)\rvert$ とおく。$\lvert\chi(g)\rvert=1$ と Cauchy–Schwarzの不等式 により、各 $\chi$ で
$$ \lvert\widehat f(\chi)\rvert\le\sum_{g\in\operatorname{supp}f}\lvert f(g)\rvert\le\sqrt{\lvert\operatorname{supp}f\rvert}\,\| f\|_2 $$
なので $M^2\le\lvert\operatorname{supp}f\rvert\,\| f\|_2^2$ である。一方 thm-dft-inversion の 2 により
$$ \lvert G\rvert\,\| f\|_2^2=\sum_{\chi\in\operatorname{supp}\widehat f}\lvert\widehat f(\chi)\rvert^2\le\lvert\operatorname{supp}\widehat f\rvert\,M^2\le\lvert\operatorname{supp}\widehat f\rvert\,\lvert\operatorname{supp}f\rvert\,\| f\|_2^2 $$
である。$f\ne0$ より $\| f\|_2>0$ なので、両辺を割って主張を得る。$\square$