Fourier-Matrix/Periodische Faltung/Produkt/Fakt/Beweis

Beweis

Es sei ${}\zeta$ die erste primitive ${}N$ -te Einheitswurzel. Es ist

{}{\begin{aligned}(DFT(y*z))_{r}&={\left({\frac {1}{N}}{\overline {F_{N}}}(y*z)\right)}_{r}\\&={\frac {1}{N}}{\left({\overline {F_{N}}}{\left({\left({\frac {1}{N}}\sum _{j=0}^{N-1}y_{j}z_{k-j}\right)}_{k=0,\ldots ,N-1}\right)}\right)}_{r}\\&={\frac {1}{N^{2}}}{\left(\sum _{k=0}^{N-1}\zeta ^{-rk}{\left(\sum _{\ell +m=k}y_{\ell }z_{m}\right)}\right)}\\&={\frac {1}{N^{2}}}{\left(\sum _{0\leq \ell ,m\leq N-1}\zeta ^{-r(\ell +m)}y_{\ell }z_{m}\right)}\\&={\frac {1}{N^{2}}}{\left(\sum _{\ell =0}^{N-1}\zeta ^{-r\ell }y_{\ell }\right)}\cdot {\left(\sum _{m=0}^{N-1}\zeta ^{-rm}z_{m}\right)}\\&={\frac {1}{N^{2}}}{\left({\overline {F_{N}}}(y)\right)}_{r}\cdot {\left({\overline {F_{N}}}(z)\right)}_{r}\\&=(DFT(y))_{r}\cdot (DFT(z))_{r}.\end{aligned}}