Fourier-Matrix/Einführung/Textabschnitt

Definition

Es sei  ${}N\in \mathbb {N} _{+}$  und  ${}\zeta =e^{\frac {2\pi {\mathrm {i} }}{N}}$  die ${}N$-te primitive Einheitswurzel. Unter der ${}N$-ten Fourier-Matrix versteht man die ${}N\times N$-Matrix

${}F_{N}={\left(\zeta ^{j\cdot k}\right)}_{0\leq j,k\leq N-1}={\begin{pmatrix}1&1&1&\ldots &1\\1&\zeta &\zeta ^{2}&\ldots &\zeta ^{N-1}\\1&\zeta ^{2}&\zeta ^{4}&\ldots &\zeta ^{2(N-1)}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&\zeta ^{N+1}&\zeta ^{2(N+1)}&\ldots &\zeta ^{(N+1)(N+1)}\end{pmatrix}}\,.$

Entscheidend sind dabei für die Exponenten die Restklassen ${}j\cdot k\mod N$. Es handelt sich um eine symmetrische Matrix. Die ersten Fourier-Matrizen sind

${}F_{1}=(1)\,,$

${}F_{2}={\begin{pmatrix}1&1\\1&-1\end{pmatrix}}\,,$

${}F_{3}={\begin{pmatrix}1&1&1\\1&\zeta _{3}&\zeta _{3}^{2}\\1&\zeta _{3}^{2}&\zeta \end{pmatrix}}={\begin{pmatrix}1&1&1\\1&{\frac {-1+{\sqrt {3}}{\mathrm {i} }}{2}}&{\frac {-1-{\sqrt {3}}{\mathrm {i} }}{2}}\\1&{\frac {-1-{\sqrt {3}}{\mathrm {i} }}{2}}&{\frac {-1+{\sqrt {3}}{\mathrm {i} }}{2}}\end{pmatrix}}\,,$

${}F_{4}={\begin{pmatrix}1&1&1&1\\1&{\mathrm {i} }&-1&-{\mathrm {i} }\\1&-1&1&-1\\1&-{\mathrm {i} }&-1&{\mathrm {i} }\end{pmatrix}}\,.$

Lemma

Für die Fourier-Matrizen ${}F_{N}$ gilt

${}F_{N}{\overline {F_{N}}}={\overline {F_{N}}}F_{N}=NE_{N}\,.$

Insbesondere sind die Fourier-Matrizen invertierbar.

Beweis

Wir wenden die Regel „Zeile mal Spalte“ auf die Zeile ${}r$ und die Spalte ${}s$ an (wir arbeiten konsequent mit der Indexmenge ${}\{0,\ldots ,N-1\}$), dies ergibt den Eintrag

${}{\begin{aligned}&a_{r,s}\sum _{j=0}^{N-1}\zeta ^{rj}\cdot {\overline {\zeta ^{js}}}\\&=\sum _{j=0}^{N-1}\zeta ^{rj}\cdot \zeta ^{-js}\\&=\sum _{j=0}^{N-1}\zeta ^{(r-s)j}.\end{aligned}}$

Dies ist gleich ${}N$ bei  ${}r=s$  und andernfalls gleich ${}0$ nach der endlichen geometrischen Reihe.

$\Box$

Für einen Vektor  ${}y\in {\mathbb {C} }^{N}$  nennt man ${}{\frac {1}{N}}{\overline {F_{N}}}y$ die diskrete Fourier-Transformation von ${}y$, das Ergebnis nennt man den Fourier-Vektor zu ${}y$, und für einen (Spektral)-Vektor  ${}c\in {\mathbb {C} }^{N}$  nennt man ${}F_{N}c$ die inverse diskrete Fourier-Transformation von ${}c$. Nach Fakt sind diese beiden linearen Operationen invers zueinander. Die Darstellung

${}y=F_{N}c\,$

mit

${}c={\frac {1}{N}}{\overline {F_{N}}}y\,$

nennt man die Fourier-Summe oder Fourier-Darstellung für ${}y$. Im gegebenen Kontext sind zu einem Vektor  ${}y\in {\mathbb {C} }^{N}$  die Koeffizienten ${}y_{j}$ für beliebige Indizes  ${}j\in \mathbb {N}$  als ${}y_{j\mod N}$ mit dem kanonischen Vertreter zwischen ${}0$ und ${}N-1$ zu verstehen. Dies gilt insbesondere in der folgenden Definition.

Definition

Sei  ${}N\in \mathbb {N} _{+}$.  Zu Vektoren  ${}y,z\in {\mathbb {C} }^{N}$  versteht man unter der periodischen Faltung den Vektor ${}y*z$ mit den Koeffizienten

${}(y*z)_{k}={\frac {1}{N}}\sum _{j=0}^{N-1}y_{j}z_{k-j}={\frac {1}{N}}\sum _{\ell +m=k\mod N}^{N-1}y_{\ell }z_{m}\,.$

Lemma

Die diskrete Fourier-Transformation führt die periodische Faltung von Vektoren  ${}y,z\in {\mathbb {C} }^{N}$  in das komponentenweise definierte Produkt über.

Es ist also

${}(DFT(y*z))_{r}=(DFT(y))_{r}\cdot (DFT(z))_{r}\,.$

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}}$

$\Box$