\documentclass[a4paper]{scrartcl}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage{ngerman}
\usepackage[dvips]{graphicx}
\usepackage{ulem}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{array}
\usepackage{booktabs}
\usepackage{listings}
\usepackage{color} % f{\"u}r den grauen Hintergrund

%\usepackage{endnotes}

\setlength{\parindent}{0 em}

\definecolor{Gray}{gray}{0.9}

\lstset{basicstyle=\ttfamily\scriptsize,
backgroundcolor=\color{Gray}, numbers=left, numberstyle=\tiny,
stepnumber=1, numbersep=5pt}

\DeclareGraphicsExtensions{.eps}

%\DeclareGraphicsRule{.gif}{eps}{}{`convert #1 'eps:-'}

  \setcounter{MaxMatrixCols}{11}

\begin{document}
\begin{center}
\textbf{\huge{Runde 9, Beispiel 59}}

\Large{LVA 118.181, {\"U}bungsrunde 9, 12.01.2007}

\large{Markus Nemetz, \emph{markus.nemetz@tuwien.ac.at}, TU Wien,
08.01.2007}
\end{center}

\section{Angabe}
Man zeige, da{\ss} f{\"u}r die Fouriermatrix $F_N$, gegeben durch
\begin{gather*}
    F_N := \begin{pmatrix} 1 & 1 & 1 & \cdots & 1 \\
    1 & \omega & \omega^2 & \cdots & \omega^{N-1} \\ 1 & \omega^2 &
    \omega^4 & \cdots & \omega^{2(N-1)} \\ \vdots & \vdots & \vdots &
    \ddots & \vdots \\ 1 & \omega^{N-1} & \omega^{2(N-1)} & \cdots &
    \omega^{{(N-1)}^{2}} \\ \end{pmatrix}
\end{gather*}
mit $\omega =e^{2\pi i/N}$ gilt:
\begin{gather*}
    F_N \cdot \overline{F_N} = N \cdot E_N
\end{gather*}
Dabei bezeichnet $\overline{F_N}$ die konjugierte Matrix und $E_N$
die $N \times N$-Einheitsmatrix.

Dabei bezeichnet $\overline{F_N}$ die konjugierte Matrix und $E_N$
die $N$-te Einheitsmatrix.

Anmerkung: Das Element in der $r$-ten Zeile und $s$-ten Spalte der
Matrix $F_N \cdot \overline{F_N}$ berechnet sich durch
\begin{gather*}
    \sum_{k=0}^{N-1}\omega^{k(r-1)}\cdot\omega^{-k(s-1)}
\end{gather*}
Man unterscheide zwischen $r=s$ und $r \neq s$.


\section{Theoretische Grundlagen: Fourier-Matrix}
Durch Bilden von Potenzen der Einheitswurzel
\begin{gather*}
    \omega_n=e^{\frac{2\cdot \pi \cdot i}{n}}
\end{gather*}
erh{\"a}lt man die Fourier-Matrix.

\section{L{\"o}sung des Beispiels}
\subsection{$r=s$}
\begin{gather*}
    \sum_{k=0}^{N-1} \omega^{k\cdot(r-1)} \cdot \omega^{-k\cdot(r-1)}=\sum_{k=0}^{N-1}
    \omega^{k\cdot(r-1)-\cdot(r-1)}= \sum_{k=0}^{N-1} \omega^0=N
\end{gather*}

\subsection{$r \neq s$}
\begin{gather*}
    \sum_{k=0}^{N-1} \omega^{k\cdot(r-1)} \cdot \omega^{-k\cdot(s-1)}=\sum_{k=0}^{N-1}
    \omega^{k\cdot(r-1)-\cdot(s-1)}=\sum_{k=0}^{N-1}
    \omega^{k\cdot r - k - k \cdot s + k}=\sum_{k=0}^{N-1} \omega^{k\cdot (r-s)}
\end{gather*}
Dabei gilt: $\omega^{r-s} := z$, wobei $z$ eine von $1$
verschiedene $N$-te Einheitswurzel ist ($z^N=1$).
\begin{gather*}
    z^{N-1} + z^{N-2} + \dots + z + 1 = \frac{z^N - 1}{z-1}=0
\end{gather*}
Beweis f{\"u}r $z^N=1$ (Moivre-Formeln,$n$-ten Wurzeln in
$\mathbb{C}$):
\begin{gather*}
    z^N=\omega^{N\cdot (r - s)} =e^{\frac{2\cdot \pi \cdot i}{N}\cdot N \cdot
    (r-s)}=e^{2\cdot \pi \cdot i \cdot (r-s)}=\cos(2\cdot \pi
    \cdot (r-s)) + i \cdot \sin(2\cdot \pi \cdot (r-s))=1
\end{gather*}



\end{document}
