\documentstyle[12pt]{article}

\newcounter{probno}

\newcommand{\prob}{\addtocounter{probno}{1}
   \par\medskip\noindent\theprobno .  }

\newcommand{\by }{\times}
\newcommand{\der}{{d\over dt}}

\begin{document}

\begin{flushright}
  A. Miller\\
  M340 \\
  Exam 2 \\
\end{flushright}
\begin{quote}
 RULES: Do not discuss this exam with anybody except me.  I will
 explain any definition or clarify the statement of
 any of these problems.  My office is 403 Van Vleck, office hours
 MF 2:30-3:30 and W 4:30-5:30, or you can make an appointment.
 You may use minimat to do any calculation.  The exam is due in class on
 Wed April 11.  Exam 2 Part II will be in class on Mon April 16.
\end{quote}

\bigskip

\begin{center}
Linear differential equations.
\end{center}

\prob
 A mass $m_1$ is hung from a spring with spring constant
$k_1$ is attached to a rigid
support.  A mass $m_2$ is hung from a second spring with spring
constant $k_2$ is attached to the mass $m2$.   Let $y_1$ be the
displacement from equilibrium of the mass $m_1$ and similarly
$y_2$ the displacement from equilibrium of the mass $m_2$.
Then using Hooke's law and $F=ma$ we get that:
$$m_1y_1^{\prime\prime}=-k_1y_1+k_2(y_2-y_1)$$
$$m_2y_2^{\prime\prime}=-k_2(y_2-y_1).$$
Let $u_1=y_1$, $u_2=y_1^\prime$, $u_3=y_2$, and $u_4=y_2^\prime$.
Find a matrix $A$ such that $U^\prime=AU$.

\prob Suppose $k_1=21$, $k_2=15$, $m_1=7$, $m_2=3$ in the appropriate units.
Find the general solution.

\prob Suppose $y_1(0)=1$, $y_2(0)=-1$, and both have $0$ initial
velocities.  Find the solution.  Find the displacements and velocities
of the masses at time $t=2$.

\newpage

\begin{center}
The method of least squares.
\end{center}


\prob Prove that if $A$ is an $n\by m$ matrix of functions of $t$ and
$B$ is an $m\by r$ matrix of functions of $t$, then
$$\der (AB)=(\der A)B+ A(\der B).$$

\prob Prove that if $U$ and $V$ are $n\by 1$ vectors of functions
of $t$, then
$$\der\langle U,V\rangle=\langle \der U,V\rangle+\langle U,\der V\rangle.$$

\prob Let $A_{n\by m},B_{m\by 1}$ be matrices of reals.  Prove that
$${\partial\over\partial x_i}||AX-B||^2=2\langle AX-B,Ae_i\rangle.$$

\prob Prove that if $X$ minimizes $||AX-B||^2$, then $A^{T}(AX-B)=0$.

\prob It is good  surveying practice to make more observations than
 are strictly necessary.  For example, to determine the altitude of four
 points $x_1,x_2,x_3,x_4$, eight observations were taken:

\par   $x_1=2.947$
\par   $x_2=1.735$
\par   $x_3=-1.449$
\par   $x_4=1.321$
\par   $x_1-x_2=1.204$
\par   $x_1-x_4=1.631$
\par   $x_2-x_3=3.186$
\par   $x_3-x_4=-2.778$

\noindent Note that all of these observations contain error and there do not
 exists any solutions to all eight equations.
 Find $A_{8\by 4}$ and $B_{8\by 1}$ such that the most likely
 altitudes $X$ minimize $||AX-B||^2$.   Find $X$.

\newpage

\begin{center}
  Linear programming or linear optimization.
\end{center}

Let $A$ be $n\by m$, $B$ be $m\by 1$ and $C=[c_1,c_2,\ldots,c_n]$ be
$1\by n$.

$(*)$ Maximize  $z=c_1x_1+c_2x_2+\cdots+c_nx_n$ subject to the constraints:

\noindent \hspace{.5in} $AX=B$ and $X\geq 0$.

\bigskip

$X\geq 0$ means that $x_1\geq 0, x_2\geq 0,\dots$, and $x_n\geq 0$.
$X$ is called feasible iff $AX=B$ and $X\geq 0$.  A solution to
$(*)$ is a vector $X$ which is feasible and for which the value of
$z$ is as large as the value of $z$ is for any feasible solution.
$X$ is called an
extreme point iff there exists $m_1,m_2,\ldots, m_k$ such that
$X$ is the unique solution of $AX=B,x_{m_1}=0,x_{m_2}=0,\ldots,$ and
$x_{m_k}=0$.

\bigskip

\prob Give an example of $(*)$ where there are no feasible solutions.
 Give an example of $(*)$ where there are feasible solutions but
no solutions.
 Give an example of $(*)$ where there are there infinitely many
solutions.
  Give an example of $(*)$ with an extreme point which is not feasible.

\prob Let $X_1$ and $X_2$ be solutions of
$AX=B,x_{m_1}=0,x_{m_2}=0,\ldots,$ and
$x_{m_k}=0$.
Define $L[t]=X_1+t(X_2-X_1)$
where $t$ is a scalar.  Show that $L[t]$ is a solution of
$AX=B,x_{m_1}=0,x_{m_2}=0,\ldots,$ and
$x_{m_k}=0$
for every $t$.

\prob  Suppose in addition to above that all coordinates of $X_1$ other
than ${m_1},{m_2},\ldots,
{m_k}$ are strictly positive. Show that there exists $\epsilon>0$ such that
$L[t]\geq 0$ for every $t$ with $-\epsilon <t<\epsilon$.

\prob Define $Z(t)=CL[t]$.  Prove that for some scalars
$p$ and $q$ that $Z(t)=pt+q$.
Prove that $Z$ is maximized at $t=0$ iff $p=0$.

\prob Given the problem $(*)$ suppose $X_0$ is any solution which has
the maximum number of zero coordinates as any other solution.
Prove that $X_0$ is an extreme point.

\newpage
\begin{center}
  Graph theory.
\end{center}

   Suppose that $A$ is an $n\by n$ matrix  such that
for any $i,j$ we have that $a_{i,j}=0$ or $a_{i,j}=1$.
The matrix $A$ determines a graph $G_A$ on n vertices
${v_1,v_2,\ldots,v_n}$ by  the rule that  $v_i$ and $v_j$ are
connected by an edge iff $a_{i,j}=1$.  A path in a graph $G$ is a sequence of
vertices $u_1,u_2,\ldots, u_k$ such that for each $i=1,\ldots,k-1$
there is an edge in $G$ which connects $u_i$ and $u_{i+1}$.
A graph $G$ is connected iff
any two vertices of $G$ can be connected by a path.

\prob Give an example of a $4\by 4$ matrix $A$ as above
  whose graph is connected.
  Give an example of a $4\by 4$ matrix $A$ as above
  whose graph is not connected.

\prob Prove that if $A^m=[c_{ij}]$, then $c_{ij}$ is the number
  of paths of length $m$ connecting $v_i$ to $v_j$.

\prob Prove that the graph associated to such an $n\by n$ matrix $A$
  is connected iff every entry of $I+A+A^2+\cdots+A^{n-1}$ is positive.

\begin{center}
    Markov processes.
\end{center}
 In the Land of OZ there are three states for the
weather: nice, rain, and snow.   The weather follows the following rules:
\begin{enumerate}
\begin{enumerate}
  \item There are never two nice days in a row.
  \item When it rains or snows, half the time it the same the next day.
  \item If the weather changes, the chances are equal for a change to each
        of the two other types of weather.
\end{enumerate}
\end{enumerate}

\prob  Draw a graph with vertices $N,R$, and $S$ and label the edges
       with the appropriate probabilities.

\prob  Find the $3\by 3$ transition matrix $A$ corresponding to this graph.

\prob  Prove that the probability that it will rain exactly one week after
       it was nice is the $(1,2)$ entry of the matrix $A^7$.
       Find this probability.

\prob  Find the probability that the weather
       will be nice, rain, or snow on a random day in the Land of OZ.

\newpage

\begin{center}
  Determinants, etc.
\end{center}

   The trace of an $n\by n$ matrix $A$ is defined by
$$trace(A)=a_{11}+a_{22}+\cdots+a_{nn}.$$
 The characteristic polynomial of a matrix $A$ is defined
by $p(x)=det(xI-A)$.

\prob Prove that if $A$ and $B$ are similar, then $trace(A)=trace(B)$.

\prob Prove that if $A$ and $B$ are similar, then
 $det(A)=det(B)$.

\prob Prove or disprove: if two matrices
$A$ and $B$ have the same characteristic polynomial, then they are
similar.

\prob  Prove or disprove: if two matrices
$A$ and $B$ are similar, then they have the same characteristic polynomial.


\end{document}