\documentclass[10pt]{article}
\setlength{\textwidth}{6.3in}
\setlength{\textheight}{9in}
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\topmargin}{-.6in}
\linespread{1}

% \renewcommand{\labelenumi}{\alph{enumi}}
%\newtheorem{thm}{Theorem}[section]
\newtheorem{thm}{Theorem}
% says that to start a new theorem, type \begin{thm} and to end it type
% \end{thm}.  To start proof, type \begin{proof} and finish with
% \end{proof}.  The appearance of [section] says to label theorems
% according to section

\newtheorem{cor}[thm]{Corollary}
\newtheorem{defn}[thm]{Definition}
\newtheorem{remark}[thm]{Remark}
\newtheorem{lemma}[thm]{Lemma}

\newcommand{\be}{\begin{equation}}
\newcommand{\ee}{\end{equation}}
\newcommand{\beq}{\begin{eqnarray}}
\newcommand{\eeq}{\end{eqnarray}}
\newcommand{\beqq}{\begin{eqnarray*}}
\newcommand{\eeqq}{\end{eqnarray*}}
\newcommand{\qed}{\hspace*{\fill}Q.E.D.}  %Use at end of proof
\def\been{\begin{enumerate}}
\def\enen{\end{enumerate}}
\def\beit{\begin{itemize}}
\def\enit{\end{itemize}}
\def\dsst{\displaystyle}
\def\dx{\Delta x}
\def\dy{\Delta y}
\def\dz{\Delta z}
\def\dw{\Delta w}
\def\dfdx{\frac{\partial f}{\partial x}}
\def\dfdy{\frac{\partial f}{\partial y}}
\def\dfdz{\frac{\partial f}{\partial z}}
\def\dzdx{\frac{\partial z}{\partial x}}
\def\dzdy{\frac{\partial z}{\partial y}}
\hyphenation{}
\newcommand{\blank}[1]{\underline{\hspace{#1}}}
\newcommand{\vect}[1]{\mathbf{#1}}
\newcommand{\bnabla}{\boldsymbol\nabla}
\usepackage{fancyhdr}
\pagestyle{fancy}
\headheight = 14.5pt
\lhead{{\bf Mark Iwen, Spring 2023}}
\rhead{{\bf Homework 1}, MTH496-001, Fourier Analysis}
%\cfoot{\it MORE QUESTIONS ON OTHER SIDE}
% \cfoot{\thepage}

\usepackage{epsfig,url}
\usepackage{amsmath,bbm}
\usepackage{amssymb}

% Special Constants and vectors
\def\i{{\mathbbm i}}
\def\e{{\mathbbm e}}
\newcommand{\1}{\mathbbm{1}}

% Computational Complexity
\def\O{{\mathcal O}}


\begin{document}

Any of the following exercises are fair game for appearing in a slightly altered state on an exam.  I suggest that you write up your solutions {\bf neatly} in your own handwriting, or .tex them up, so that you can easily use them for studying later.  All solutions should be your own!  Feel free to discuss solutions with others, but don't write anything down that you don't understand (and write it all yourself!).  {\bf Only a subset of the problems will be graded, so do them all to the best of your ability, and be aware:  even if there is only one problem that you don't do well, it might be one that's graded!  So, try to do them all well!}\\

\begin{center}
PROBLEMS ASSIGNED ABOUT DISCRETE FOURIER TRANSFORMS AND CONVOLUTIONS
\end{center}

\been

\item Show that $\e^{x + \i 2\pi \theta} = \e^x$ holds for all $\theta \in \mathbbm{Z}$ and $x \in \mathbbm{C}$.  As a consequence, conclude, for example, that $\e^{\i \pi \theta} = \e^{-\i \pi \theta} = (-1)^\theta$ for all $\theta \in \mathbbm{Z}$.

\item Show that $\langle {\bf x}, {\bf y} \rangle := \sum_{j=0}^{N-1} x_j \overline{y_j}$ is an inner product for $\mathbbm{C}^N$.

\item Prove that the DFT matrix, $F \in \mathbbm{C}^{N \times N}$, is unitary.

\item Show that $\| \hat{\bf v} \|_2 = \| {\bf v} \|_2$ holds for all ${\bf v} \in \mathbbm{C}^{N}$.  Here $\| {\bf v} \|_2 := \sqrt{\sum_j | v_j |^2} $ is ${\bf v}$'s Euclidean norm.

\item Let ${\bf v}, {\bf u} \in \mathbbm{C}^{N}$.  Show that $\textbf{u} \star \textbf{v} = \textbf{v} \star \textbf{u}$ holds (i.e., order doesn't matter).

\item Let $a, b, c \in [N]$ be such that $a$ is invertible modulo $N$.\footnote{A value $a \in [N]$ is invertible modulo $N$ if there exists an $h \in [N]$ such that $\left( a ~h \right) ~\equiv~ 1 \textrm{ mod } N$.  Any $a \in [N]$ that is relatively prime to $N$ will be invertible modulo $N$ by the Fermat-Euler Theorem.}  Furthermore, suppose that ${\bf u}, {\bf v} \in \mathbbm{C}^N$ satisfy $$v_j = \e^{\frac{2 \pi \i c j}{N}} u_{a j  + b\mod N}$$ for all $j \in [N]$.  Calculate $\hat{\bf v}$ in terms of $\hat{\bf u}$.  How does $a$ affect $\hat{\bf v}$ when $c = b = 0$?  How does $b$ affect $\hat{\bf v}$ when $a = 1$ and $c = 0$?  How does $c$ affect $\hat{\bf v}$ when $a = 1$ and $b = 0$?

\item Let $\omega \in \mathbbm{Z}$.  Show that $$\frac{1}{2 \pi} \int_{- \pi}^{\pi} \e^{\i \omega x} ~dx ~=~ \begin{cases} 1 ~{\rm if}~ \omega = 0\\ 0 ~{\rm if}~ \omega \neq 0 \end{cases}.$$

\item Let $p: [-\pi, \pi] \rightarrow \mathbbm{C}$ be a degree $N$ trigonometric polynomial given by $p(x) = \sum_{\omega = -N}^N \hat{p}_\omega \e^{\i \omega x}$.  Show that $$\| p \|_2 := \sqrt{\int_{- \pi}^{\pi} | p(x) |^2 ~dx} = \sqrt{\sum_{\omega = -N}^N |\hat{p}_\omega|^2} =: \| (\hat{p}_{-N}, \dots, \hat{p}_0, \dots, \hat{p}_{N}) \|_2 = \left\| ~\mathcal{F}[p]~ \right\|_2.$$

\item Let $g:  [0,1] \rightarrow \mathbbm{R}$ be a twice continuously differentiable and periodic function.  We will prove a little later that any such $g$ will have a {\it Fourier series expansion} of the form
\begin{equation}
g(x) = \sum_{\omega \in \mathbbm{Z}} c_\omega \e^{2 \pi \i \omega x}~~ \forall x \in [0,1],
\end{equation}
where the {\it Fourier series coefficients} $c_{\omega} \in \mathbbm{C}$ satisfy $(i)$ $c_{\omega} = \overline{c_{-\omega}}$ for all $\omega \in \mathbbm{Z}$, and $(ii)$ $\sum_{\omega \in \mathbbm{Z}} \left| c_\omega \right| < \infty$.  Let $\textbf{u} \in \mathbbm{R}^N$ be a vector whose entries are given by $u_j = g(j / N)$ for all $j \in [N]$.  Show that the vector $F \textbf{u}$ has entries $$\left(F \textbf{u} \right)_j = \sqrt{N} \sum_{\omega \equiv j \textrm{ mod } N } c_\omega.$$

\enen

\end{document}
