学术帖不删也没事吧，删了还浪费编号
by 警策看取 @ 2020-04-05 22:19:32
@[违规用户名FkZyA0!2](/user/51569) 有一种比较直观的方式，是把 DFT 写成矩阵乘法的形式，IDFT 就是转移矩阵的逆，然后就能搞出来了
by NaCly_Fish @ 2020-04-05 22:23:43
OIer 不需要证明，只需要背结论((((((((((((
by WYXkk @ 2020-04-05 22:24:58
@[NaCly_Fish](/user/115864) 谢谢
by wgyhm @ 2020-04-05 22:27:17
### DFT与IDFT
$$DFT:b_k=\sum\limits_{i=0}^{n-1}ai·\omega_n^{ki} (0 \leq k < n)$$
$$IDFT:a_k=\frac{1}{n} \sum\limits_{i=0}^{n-1}b_i·\omega_n^{-ki} (0 \leq k < n)$$
证明如下：
将$DFT$带入$IDFT$得到：
$$\begin{aligned}\sum\limits_{i=0}^{n-1}b_i·\omega_n^{-ki} & =\sum\limits_{i=0}^{n-1}\omega_n^{ij}a_j \\ & = \sum\limits_{j=0}^{n-1}a_j\sum\limits_{i=0}^{n-1}\omega_n^{-ki}·\omega_n^{ij} \\& =\sum\limits_{j=0}^{n-1}a_j\sum\limits_{i=0}^{n-1}\omega_n^{i(j-k)} \end{aligned}$$
对于$\sum\limits_{i=0}^{n-1}\omega_n^{i(j-k)}$:
若$j=k$，则
$$\sum\limits_{i=0}^{n-1}\omega_n^{i(j-k)}=\sum\limits_{i=0}^{n-1}1=n$$
若$j\not=k$，则因为$0\le j,k<n$，有$|j-k|<n$，所以$\omega_n^{j-k}\not=1$，可以利用等比数列求和得到：
$$\begin{aligned}\sum\limits_{i=0}^{n-1}\omega_n^{i(j-k)} & =\sum\limits_{i=0}^{n-1}(\omega_n^{j-k})^i\\& =\frac{1-(\omega_n^{j-k})^n}{1-\omega_n^{j-k}}\\& =\frac{1-(\omega_n^n)^{j-k}}{1-\omega_n^{j-k}}\\& =\frac{1-1}{1-\omega_n^{j-k}}\\& = 0\end{aligned}$$
因此有
$$\begin{aligned}\frac{1}{n}\sum\limits_{i=0}^{n-1}b_i·\omega_n^{-ki} & =\frac{1}{n}\sum\limits_{i=0}^{n-1}\omega_n^{ij}a_j\\ & =\frac{1}{n}\sum\limits_{j=0}^{n-1}a_j\sum\limits_{i=0}^{n-1}\omega_n^{i(j-k)}\\ & =\frac{1}{n}·na_k\\ & =a_k \end{aligned}$$
by 盧鋅 @ 2020-04-15 13:35:14