\magnification=\magstep1
\centerline{Mathematics 174 -- Applied Mathematics 2}
\centerline{Selected Solutions -- Discussion 6}
\centerline{April 25, 2000}
\bigskip
\noindent
C) 2. Let $h_j$ be the convolution sequence $h = f * g$.  Then taking
its DFT, and interchanging the summations, and splitting the 
exponential into a product of two factors, we have
$$\eqalign{
H_k &= {1\over 2\pi} \sum_{j=0}^{N-1} h_j e^{2\pi i(jk)/N}\cr
    &= {1\over 2\pi} \sum_{j=0}^{N-1}
          \left( \sum_{\ell=0}^{N-1} f_\ell g_{j-\ell} \right)e^{2\pi i(jk)/N}\cr
    &= {1\over 2\pi} \sum_{\ell=0}^{N-1} f_\ell
          \left( \sum_{j=0}^{N-1}  g_{j-\ell}e^{2\pi i(j-\ell)k/N} \right)e^{2\pi i(\ell k)/N}\cr}$$
For each value of $\ell$, in the inner sum over $j$, $m = j - \ell$ also
ranges over all classes mod $N$.  Hence we can factor this
as a product of two sums and rewrite the inner one above as follows:
$$\eqalign{
&={1\over 2\pi} \left(\sum_{\ell=0}^{N-1} f_\ell e^{2\pi i(\ell k)/N}\right)
\left(\sum_{m=0}^{N-1}  g_{m}e^{2\pi i(mk)/N} \right)\cr
&=F_k \cdot 2\pi G_k\cr}$$
Hence the convolution formula holds.
\bigskip
\noindent
D) 1.  Everyone correctly saw that if the powers $z_\ell^k$
$k = 0, \ldots, N-1$ give {\it all of the $N$th roots of unity
in ${\bf C}$}, then 
$${1\over N}\sum_{k=0}^{N-1} z_\ell^k = \cases{1 & if $\ell \equiv 0 \bmod N$\cr
                                               0 & otherwise\cr}\leqno(1)$$
However, if $N$ is composite, and $\gcd(\ell,N) \ne 1$, then
the powers $z_\ell^k$ will not yield all the $N$th roots of unity.

For example, with $N = 6$, $z_2 = e^{4\pi i/6} = e^{2\pi i/3}$
satisfies $z_2^3 - 1 = 0$ (hence also $z_2^6 - 1 = 0$).  But the
powers of $z_2$ will give only cube roots of unity, not all the 6th roots
of unity.  We will get each cube root of unity twice if we
consider the powers $z_2^k$, $k = 0, \ldots 5$.

In general, if $\gcd(\ell,N) = m > 1$, then 
the powers $z_\ell^k$ are all the $(N/m)$th roots of unity, and as 
$k$ goes from $0$ to $N-1$, each $(N/m)$th root of unity is obtained 
exactly $m$ times.
The $(N/m)$th roots of unity are the roots of the equation $z^{N/m} - 1 = 0$,
so their sum is also zero for the same reason as in the first 
case.  This shows (1) holds in this case also.
\bigskip
\noindent
D) 2.  The Discrete Inverse Transform:  Let $F_k$ be the DFT of a
sequence $f_j$.  Then we work with 
the $j$th term in the inverse transform sequence, interchanging order
of summation and combining the exponentials.  (Note that if 
$\ell, j\in \{0,1,\ldots,N-1\}$, then the only time
when $\ell - j \equiv 0\bmod N$ as in the statement of part 1 is 
when $\ell = j$.)
$$\eqalign{
{2\pi\over N} \sum_{k=0}^{N-1} F_k e^{-2\pi i (kj)/N}
&= {2\pi\over N}\sum_{k=0}^{N-1} 
\left({1\over 2\pi} \sum_{\ell=0}^{N-1} f_\ell e^{2\pi i(\ell k)/n}\right)e^{-2\pi i (kj)/N}\cr
&= {1\over N}\sum_{\ell=0}^{N-1} f_\ell \cdot \sum_{k=0}^{N-1} \left(e^{2\pi i(\ell - j)/N}\right)^k\cr
&= {1\over N}\sum_{\ell=0}^{N-1} f_\ell\cdot\cases{N & if $\ell = j$\cr
                                                   0 & if $\ell \ne j$\cr}\cr
&= {1\over N}(f_0\cdot 0 + \cdots + f_{j-1}\cdot 0 + f_j\cdot N + 
f_{j+1}\cdot 0 + \cdots + f_{N-1}\cdot 0)\cr
&=f_j\cr}$$
Hence the ``DIFT undoes the DFT''.

\bye
