\documentclass[12pt]{article}
%\usepackage{ccfonts,euler}
\usepackage{fullpage,amsmath,amsfonts,graphicx,url}

\def\Var{\operatorname{Var}}

\begin{document}

\title{General Mathematics and ACM II}
\author{Final Exam}
\date{May 21, 2011}
\maketitle

% \vspace*{\fill}
% {\baselineskip=40pt
% \begin{tabbing}
% Student ID Number: \= \kill
% Last Name: \> \rule[-2pt]{10cm}{0.3pt} \\
% First Name:  \> \rule[-2pt]{10cm}{0.3pt} \\
% Signature: \> \rule[-2pt]{10cm}{0.3pt} \\
% %Code: \> \fbox{\rule{0pt}{1.5em}\rule{1.5ex}{0pt}}
% %\fbox{\rule{0pt}{1.5em}\rule{1.5ex}{0pt}}
% %\fbox{\rule{0pt}{1.5em}\rule{1.5ex}{0pt}}
% %\fbox{\rule{0pt}{1.5em}\rule{1.5ex}{0pt}}
% \end{tabbing}}


% \vspace*{\fill}


% \newpage

\begin{enumerate}

\item Show that in a finite graph without cycles, there is a vertex of
valency at most one.
\hbox{\quad}\hfill (10)

%\newpage

\item Let $\ell$ be a fixed line in the plane.  Recall that a \emph{glide
reflection} with axis $\ell$ is a transformation $U = R_\ell \Pi$
where $R_\ell$ is the line reflection about $\ell$ and $\Pi$ is some
nonidentity translation which leaves $\ell$ invariant.

\begin{enumerate}
\item Show that $R_\ell \Pi = \Pi R_\ell$.
\item Show that $U^{-1} = R_\ell \Pi^{-1}$.
\item Show that $U^{-1}$ is a glide reflection with axis $\ell$.
\item Consider the set of all glide reflections with axis $\ell$.  Is
it a group?  If not, describe the group it generates.
\end{enumerate}
\hfill(5+5+5+5)

% \newpage
% \null
% \newpage

\item Fix $N \in \mathbb N$.  The $i$th \emph{circular shift matrix}
is the $N \times N$ matrix
\[
  S_i =
  \begin{pmatrix}
  && \cdots & 0 & 1 & 0 & \cdots & 0 \\
   &&&& \ddots & \ddots & \ddots & \vdots\\
  \vdots &&&&& 0 & 1 & 0\\
  0 & & &&&& 0 & 1 \\
  1 & 0 &&&&&& \vdots \\
  0 & 1 & 0 \\
  \vdots & \ddots & \ddots & \ddots \\
  0 & \cdots & 0 & 1 & 0 & \cdots
  \end{pmatrix}
\]
where the leftmost $1$ appears in the $i$th row.

Further, let $M$ denote the diagonal matrix
\[
  M = \begin{pmatrix}
  m_1 & 0 &  \\
  0 & m_2 & \ddots \\
  & \ddots & \ddots & \ddots \\
  &  & \ddots & \ddots & 0 \\
  & & & 0 & m_N
  \end{pmatrix}
\]
where $\lvert m_1 \rvert = \dots = \lvert m_N \rvert = 1$.

\begin{enumerate}
% \item Show that the set $\{ S_i \colon i = 1, \dots, N \}$ is a
% group.  What is  $S_i^{-1}$?

\item Under which condition on the values $m_1, \dots, m_N$ does
$S_iM=MS_i$ hold for every $i=1,\dots,N$?


\item Show that $\{ (S_2M)^i \colon i \in \mathbb Z \}$ is a group.
What is its order (the number of elements)?

\item There is a correspondence of this construction with the Kac
ring model.  Explain!

\item There is a correspondence of this construction with glide
reflections.  Explain! 
\end{enumerate}
\hfill (5+5+5+5)

% \newpage
% \null
% \newpage

\item Solve the linear programming problem
\[
  \text{minimize } z=x+3\,y
\]
subject to
\begin{gather*}
  x + 2 \, y \geq 2 \,, \\
  2 \, x + y \geq 2 \,, \\
  x \geq 0 \,, \\
  y \geq 0 \,,
\end{gather*}
using either the graphical method or the simplex method.
\hfill(10)
%\newpage
\item The linear programming problem
\begin{equation}
\begin{gathered}
  \text{maximize } \boldsymbol c^T \boldsymbol x \\
  \text{subject to } A \boldsymbol x \leq \boldsymbol b, 
  \boldsymbol x \geq \boldsymbol 0
\end{gathered}
\tag{P}
\end{equation}
has a corresponding symmetric dual problem 
  \begin{equation}
\begin{gathered}
  \text{minimize } \boldsymbol b^T \boldsymbol y \\
  \text{subject to } A^T \boldsymbol y \geq \boldsymbol c, 
  \boldsymbol y \geq \boldsymbol 0 \,.
\end{gathered}
\tag{D}
\end{equation}
Suppose that $\boldsymbol x$ is feasible for (P) and $\boldsymbol y$
is feasible for (D).
\begin{enumerate}
\item Show that $\boldsymbol c^T \boldsymbol x \leq \boldsymbol b^T
\boldsymbol y$.
\item Conclude that if $\boldsymbol c^T \boldsymbol x = \boldsymbol b^T
\boldsymbol y$, then $\boldsymbol x$  and $\boldsymbol y$ are optimal
for their respective linear programming problems.
\end{enumerate}
\hfill(5+5)

%\newpage

\item
Recall that for $v \in \mathbb C^N$, the discrete Fourier transform of
$v$ is defined
\[
  \hat v_k = \frac1N \sum_{j=0}^{N-1} \mathrm e^{-\mathrm i jkh} \, v_j 
\]
with $h = 2\pi/N$ and for $k=0,\dots,N-1$.
\begin{enumerate}
\item Set $w_j = \mathrm e^{\mathrm i jmh} \, v_j$ for $j=1,\dots,N$.
Express the discrete Fourier transform of $w$ in terms of the discrete
Fourier transform of $v$.

\item Let $v \in \mathbb R^N$ be a vector of \emph{real} numbers.
Show that its discrete Fourier transform satisfies
\[
  \overline{\hat v_k} = \hat v_{N-k} \,,
\]
where the overbar denotes the complex conjugate.
\end{enumerate}
\hfill(5+5)

% \newpage
% \null
% \newpage

\end{enumerate}

\end{document}
