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