\documentclass[11pt]{article}
\usepackage{amssymb,bm}

\textwidth=20.3cm
\textheight=26cm
\pagestyle{empty}
\hoffset=-3.9cm
\voffset=-3cm

\begin{document}

\noindent{\it Math 6720}
\hfill{\bf Appl. Complex Var., Asymptc Mthds}\hfill
{\it Alexander Balk}


\bigskip\bigskip

\noindent{\bf HW9}\hfill{\bf\large NAME:
.....................................................................}
\hfill {\bf due 3/30/2016}

\bigskip\bigskip
\begin{enumerate}

\item {\bf Discrete Fourier Transform DFT.} 
Consider the DFT of a vector 
${\bf f}=\left(\begin{array}{c} f_0\\f_1\\.\\.\\.\\f_{N-1}\end{array}\right)\in\mathbb{C}^N$
$$F_k=\sum_{n=0}^{N-1} f_n \; e^{-i\,k\,\frac{2\pi}{N}\,n}\;.$$
\begin{enumerate} 
\bigskip\item Show that the sequence $\{F_k\}$ is $N$-periodic: $F_k=F_{k+N},
\quad (-\infty<k<\infty)$.

[So, we can keep only $N$-component vector 
${\bf F}=\left(\begin{array}{c} F_0\\F_1\\.\\.\\.\\F_{N-1} \end{array}\right)$,
and the DFT is a transformation in $\mathbb{C}^N$.]
\bigskip\item Show that the DFT is an expansion of ${\bf F}\in\mathbb{C}^N$ over vectors
$${\bf v}_n=\left(\begin{array}{c} 1\\e^{-i\,\frac{2\pi}{N}\,n}\\.\\.\\.\\
e^{-i\,(N-1)\,\frac{2\pi}{N}\,n}\end{array}\right)
\quad\quad(n=1,2,\ldots,N-1).$$
Show that these vectors form an orthogonal basis in $\mathbb{C}^N$.
\bigskip\item Find the inverse transform, that restores $f_n$ from the vector ${\bf F}$.
\bigskip\item Show that your formula for the inverse transform defines a periodic sequence $\{f_k\}$: 
              $f_k=f_{k+N}$.
\bigskip\item Show that if ${\bf f}$ is real, then $F_{N-k}=\overline{F_k}$.
\end{enumerate}

\newpage\item\begin{enumerate}

 \item Write out explicitely (w/o the exponent $e^{i k \frac{2\pi}{N} n}$)
DFT for $N=2$, and $N=4$.

 \item Convolution example. Let
\begin{eqnarray*}
 {\bf f}=\left[\begin{array}{c} 1\\2\\3\end{array}\right],\quad
 {\bf g}=\left[\begin{array}{c} 4\\5\\6\end{array}\right]. \quad
\quad\end{eqnarray*}
Find ${\bf h}={\bf f}*{\bf g}$.

\item {\bf Multiplication of polynomials as convolution}.\\
Consider the multiplication of quadratic polynomials, giving a polynomial of
degree 4:
\begin{eqnarray*}
(f_0+f_1 x + f_2 x^2)(g_0 + g_1 x + g_2 x^2)=h_0+h_1x+h_2x^2+h_3x^3+h_4x^4.
\end{eqnarray*}
Show that the cofficient vector $\bf h$ can be obtained as the convolution of
the coefficient vectors $\bf f$ and $\bf g$ padded with zeros so that the length
of all vectors is 5:
\begin{eqnarray*}
{\bf f}=\left[\begin{array}{c}f_0\\f_1\\f_2\\0\\0\end{array}\right],\quad 
{\bf g}=\left[\begin{array}{c} g_0\\g_1\\g_2\\0\\0\end{array}\right],\quad
{\bf h}=\left[\begin{array}{c} h_0\\h_1\\h_2\\h_3\\h_4\end{array}\right].
\end{eqnarray*}
Namely, show that ${\bf h}={\bf f}*{\bf g}$.

 \item Show that {\bf DFT turns convolution into multiplication}. \\
 Let ${\bf f}, \,{\bf g}\;\in \mathbb{C}^N$ and ${\bf h}={\bf f}*{\bf g}$.
If ${\bf f}, \,{\bf g}, \;{\bf h}$ 
have DFTs ${\bf F}\,, {\bf G}\,, {\bf H}\;\in \mathbb{C}^N$ then
$H_k=F_k G_k$.

\item {\bf Parseval's identities}.
\begin{enumerate}
\item Show that DFT preserves the inner product (up to normalization).
\item Show that DFT preserves the norm (up to normalization).
\end{enumerate}
\end{enumerate}


\newpage\item  {\bf Rouche's theorem}
\begin{enumerate}
\item Prove:
If the functions $f(z)$ and $\phi(z)$ are analytic inside and on simple
closed curve $C$ and if the strict inequality $|\phi(z)|<|f(z)|$ holds
for all $z\in C$, then the function $f(z)+\phi(z)$ has exactly as many
zeros (counting their multiplicities) inside $C$ as the function $f(z)$.

{\footnotesize{\it Suggestion:} 
First, show that the functions $f(z)$ and $f(z)+\phi(z)$  do not vanish on
$C$.\\
Then show that $\Delta_C\arg\{f(z)\}=\Delta_C\arg\{f(z)+\phi(z)\}$}
\item Determine the number of roots (counting their multiplicities) of
  the equation $\;z^4+3z^3+6=0\;$ inside the circle $|z|=2$.
\item Determine the number of roots (counting their multiplicities) of
  the equation $\;2z^5-6z^2+z+1=0\;$ inside the annulus $1\le|z|\le2$.
\end{enumerate}

\newpage\item\begin{enumerate}
\item Let a continuously differentiable real function $y=f(x)$ 
take some interval $(a,b)$ to an interval $(\alpha, \beta)$. \\
Suppose $f'(x)\neq 0$ for all $x\in(a,b)$. \\
Is it true that the map $y=f(x)$ is one-to-one?
\item Let an analytic function $w=f(z)$ take some domain $D$ to a domain
$\Delta$. 
Suppose, $f'(z)\neq 0$ for all $z\in D$. \\
Is it true that the map $w=f(z)$ is one-to-one?\\
What if $D$ is simply connected?
\item A continuously differentiable real function $y=f(x)$ takes one-to-one an
interval $(a,b)$ 
to an interval $(\alpha, \beta)$. Does this imply $f'(x)\neq 0$ for all $x\in
(a,b)$?
\item An analytic function $w=f(z)$ takes a domain $D$ to a domain $\Delta$
one-to-one. \\
Does this imply $f'(z)\neq 0$ for all $z\in D$?
\end{enumerate}

\newpage\item \begin{enumerate}
\item Show that all bilinear transformations form a {\it group}, i.e.
\begin{enumerate}
 \item the inverse of a bilinear map is also a bilinear map,
 \item composition of two bilinear maps is bilinear.
\end{enumerate}
\item Does the set of all conformal transformations form a group?
\end{enumerate}

\newpage\item \begin{enumerate}
\item Show that a bilinear map takes circles into circles.

{\footnotesize{\it Suggestion:} Follow these steps: 
\begin{enumerate}
\item Any bilinear map is a composition of linear maps and inversion.
\item A linear map takes circles into circles.
\item The inversion $w=1/z$ takes circles into circles.
[This is trivial for a circle centered at the origin. But it is true for any
circle. \\
To show this, write the equation of a circle in terms of $z$ and $\bar z$.]
\end{enumerate}}
\item Show that any circle in the $z$-plane can be mapped onto any circle in the
$w$-plane 
by a suitable bilinear map.

{\footnotesize{\it Suggestion:} Note that any circle is determined by three
points 
(on its circumference) and consider the equation
$$\frac{(w_1-w)(w_3-w_2)}{(w_1-w_2)(w_3-w)}=\frac{(z_1-z)(z_3-z_2)}{
(z_1-z_2)(z_3-z)}.$$
See that it defines a bilinear transformation $w(z)$ which 
takes points $z_1,z_2,z_3$ to points $w_1,w_2,w_3$.}
\end{enumerate}

\end{enumerate}

\end{document}
{\footnotesize{\it Suggestion:} Assume on the contrary that $F'(z_0)=0$ for some
$z_0\in D$
and represent $F(z)$ by its Taylor series centered at $z_0$: 
$$F(z)=a_0+a_2(z-z_0)^2+a_3(z-z_0)^3+\ldots.$$ Assume $a_2\neq 0$.
To get contradiction, we show that some images $w$ have two originals: 
Apply {\it Rouche's Th.} with the main part $f(z)=a_0+a_2(z-z_0)^2-w$ to 
show that in some neighborhood of $z_0$, 
the equation $F(z)=w$ has two roots.}
The two roots would be distinct since all zeros of analytic function $F'(z)$ are
isolated 
(from the beginning, you need to choose so small neighborhood of $z_0$ that
$F'(z)$ has no 
other zeros in that neighborhood, besides the point $z_0$.}

 \item Calculate the DFT (with arbitrary $N$) 
       of exponential sequence $f_n=e^{i\omega n}\;, n=1,2,\ldots,N-1$.\\
The continious Fourier transform of this function is zero, besides one point.\\
Is this true for the discrete Fourier transform? 
Distinguish two cases:
\begin{enumerate}
\item The frequency $\omega$ is an integer multiple of $\frac{2\pi}{N}$
(in-bin sinusoid).
\item The frequency $\omega$ is {\it not} an integer multiple of
$\frac{2\pi}{N}$ (out-of-bin sinusoid).
\end{enumerate}
