\documentstyle[12pt]{article}

\pagestyle{myheadings}
\def\headlineaux{\sc Math 540 T: Algorithm Design and Analysis
\hrulefill
}
\markboth{\headlineaux}{\headlineaux}

\begin{document}
\begin{titlepage}\begin{centerline}{\Huge \framebox{Burton Rosenberg}}
\end{centerline}\end{titlepage}

\section*{Test 1 Answers\hfill{\parbox{3in}
    {\small\sc\begin{flushright} Februrary 24, 5:00--6:15 \end{flushright}}}}

The four problems were graded as follows:
\begin{enumerate}
\item 5 points.
\item \begin{enumerate}
  \item 2 points. 
  \item 1 point.
  \item 2 points.
  \end{enumerate}
\item \begin{enumerate}
  \item 2 points for $L_i$, 2 points with for $P_i$.
  \item 1 point.
  \end{enumerate}
\item \begin{itemize}
  \item[$\Rightarrow$] 3 points.
  \item[$\Leftarrow$] 2 points.
  \end{itemize}
\end{enumerate}

\newpage
\begin{enumerate}
\item {\sc [Simplex Method]}

Solve the Following LP showing step-by-step the simplex method:
\[\begin{array}{lcccccccc}
   \max & & x_1 & + & 2 x_2 & + & x_3 \\
\\
   \mbox{s.t.} & & x_1 & + & x_2 &+& x_3 &\le&2\\
 & & x_1 &+& x_2 & & &\le& 1 \\
\\
  & & x_1, & x_2, & x_3 &\ge&0\\
\end{array}\]

\begin{center}
\rule{4.5in}{.1mm}
\end{center}

Introduce slack variables:
\begin{eqnarray*}
   x_4 &=& 2 - x_1 + x_2 + x_3 \\
   x_5 &=& 1 - x_1 - x_2 \\
  z &=& x_1 + 2 x_2 + x_3
\end{eqnarray*}
The initial basis is $\{ x_4=2, x_5=1\}$.
We pivot $x_2$ into the basis, and $x_5$ out:
\begin{eqnarray*}
  x_2 &=& 1 - x_1 - x+3 \\
  x_4 &=& 1 - x_3 + x_5 \\
  z &=& 2 - x_1 + x_3 - 2 x_5
\end{eqnarray*}
Now pivot $x_3$ in and $x_4$ out:
\begin{eqnarray*}
  x_2 &=& 1 - x_1 - x_5 \\
  x_3 &=& 1 - x_4 + x_5 \\
  z &=& 3 - x_1 - x_4 - 2 x_5
\end{eqnarray*}
The coefficients of $z$ are all negative. Hence the optimal
solution is $x_1 = x_4 = x_5 = 0, x_2 = x_3 = 1$ and it
has cost $3$.
\newpage

\item {\sc [Duality]}

\begin{itemize}
\item[(a)] Give the Dual of the previous LP problem.
\item[(b)] Find the optimal dual solution, using whatever method
  you wish.
\item[(c)] Demonstrate the Complementary Slackness conditions
  for your optimal dual/primal solution pair.
  That is, what should be true and what is true for each of the
  5 variable-inequality pairings.
\end{itemize}

\begin{center}
\rule{4.5in}{.1mm}
\end{center}

The dual is:
\[ \mbox{minimize } 2 y_1 + y_2 \]
subject to:
\begin{eqnarray*}
   y_1 + y_2 &\ge& 1 \\
  y_1 + y_2 &\ge& 2 \\
  y_1 &\ge& 1 \\
\end{eqnarray*}
and $y_1, y_2 \ge 0$.
Two of the inequalities are redundant.

The solution $y_1=y_2=1$ is feasible and has a cost equal to the
optimal primal solution. Hence this is the optimal dual solution.

\newcommand{\implies}{\;\;\Rightarrow\;\;}
Here are the five complementary slackness conditions:
\begin{enumerate}
\item $y_1 + y_2 >1 \implies x_1 = 0.$
\item $x_2 \neq 0 \implies y_1 + y_2 = 2.$
\item $x_3 \neq 0 \implies y_1 = 1.$
\item $y_1 \neq 0 \implies x_1 + x_2 + x_3 = 2.$
\item $y_2 \neq 0 \implies x_1 + x_2 = 1.$
\end{enumerate}
where the first three come from the primal variables, the last two
come from the dual variables. The equalities are all satisfied.
\newpage

\item {\sc [LU Decomposition]}

\begin{itemize}
\item[(a)]
Use Gaussian Elimination with partial pivoting to decompose,
\[ A = \left [ \begin{array}{ccc} 1&1&1\\
  2&0&2\\ 0&3&3\\ \end{array}\right],\]
into the product,
\[ L_3P_3L_2P_2L_1P_1A=U,\]
where $L_i$ are column $i$ eta-matrices, $P_i$ are permutation
matrices, and $U$ is upper triangular with 1's down the diagonal.

\item[(b)] Use back substitution and your decomposition to
find $x_1,x_2,x_3$ real numbers which satisfy,
\[ \begin{array}{ccccccc}
   x_1 &+& x_2 &+& x_3 &=& 1 \\
  x_1 & & &+& x_3 &=& 1/2 \\
   & & x_2 &+& x_3 &=& 1/3 \\
\end{array}\]
\end{itemize}

\begin{center}
\rule{4.5in}{.1mm}
\end{center}

\newcommand{\mymat}[9]{\left[\begin{array}{ccc} #1 & #2 & #3 \\
#4 & #5 & #6 \\ #7 & #8 & #9 \\ \end{array}\right]}
\newcommand{\myvect}[3]{\left[ \begin{array}{c} #1\\#2\\#3\end{array}\right]}

\[
\begin{array}{cc} 
 P_1 = \mymat 0 1 0 1 0 0 0 0 1 & 
 L_1 = \mymat {1/2} 0 0 {-1/2} 1 0 0 0 1 \\
 P_2 =\mymat 1 0 0 0 0 1 0 1 0 &
 L_2 = \mymat 1 0  0 0 {1/3} 0 0 {-1/3} 1 \\
 P_3 = \mymat 1 0 0 0 1 0 0 0 1 &
 L_3 = \mymat 1 0 0 0 1 0 0 0 {-1} \\
 U = \mymat 1 0 1 0 1 1 0 0 1 & \\
\end{array}\]

Part (b) seeks $x$ such that $Ax = [1, 1, 1]$ (a column vector of 1's).
First calculate:
\begin{eqnarray*} L_3P_3L_2P_2L_1P_1 \myvect 1 1 1
  &=& L_3P_3L_2P_2 \myvect {1/2}{1/2} 1 \\
 &=& L_3P_3L_2 \myvect {1/2} 1 {1/2} \\
  &=& L_3P_3 \myvect {1/2}{1/3}{1/6} \\
   &=& \myvect {1/2}{1/3}{-1/6}
\end{eqnarray*}
Then back substitute:
\[ Ux = \mymat 1 0 1 0 1 1 0 0 1 x = \left[
  \begin{array}{c} 1/2\\1/3\\-1/6\end{array}\right] \]
giving,
\[ x = \myvect {2/3}{1/2}{-1/6}.\]
\newpage

\item {\sc [Theory]}

Prove that the product $AB$ of two square matrices is nonsingular 
if and only if both $A$ and $B$ are nonsingular.

\begin{center}
\rule{4.5in}{.1mm}
\end{center}

Suppose $A$ and $B$ are nonsingular. By Theorem 6.2, a
matrix is nonsingular if and only if there exists an
inverse. In our case,
there exist $A^{-1}$ and $B^{-1}$ such that,
\[ A A^{-1} = A^{-1}A=B^{-1}B = B^{-1}B = I.\]
Then,
\[ AB(B^{-1}A^{-1}) = A(B B^{-1})A^{-1} = AIA^{-1} = AA^{-1}=I,\]
and,
\[ (B^{-1}A^{-1})AB = B^{-1}(A^{-1}A)B = B^{-1}IB = B^{-1}B=I.\]
So $AB$ has an inverse, namely $B^{-1}A^{-1}$, and is therefore
nonsingular.

Now suppose that $AB$ is nonsingular.
By Theorem 6.1, a square matrix has two possibilities only: it is
nonsingular and each equation $Ax=b$ has a unique solution for
$x$, or it is singular and the equation $Ax=b$ has either no
or an infinity of solutions, depending on the $b$.
It is enough to show that $Ax=0$ and $Bx=0$ have unique solutions.
Because $Ax=0$ has a solution, $x=0$, if it is singular it must
have an infinity of solutions $Ax=0$. If it has only one solution,
than it must be nonsingular. The same goes for $B$.

Suppose $Bx_1=Bx_2=0$. Then $ABx_1=ABx_2=0$ so $x_1=x_2=0$.
Thus $B$ is nonsingular. If $Ax_1=Ax_2=0$, then since $B$
is non-singular, there are unique solutions to $By_i=x_i$,
with $i=1,2.$ Hence $ABy_i=0$ and thus $y_1=y_2$, and
$x_1=By_1=By_2=x_2$. So $A$ is nonsingular.




\newpage

\end{enumerate}
\end{document}

