\documentclass[t]{paulslides}
\usepackage{pgf,tikz}
\usepackage{enumerate}
\usetikzlibrary{arrows}
\usepackage{amsthm}

\definecolor{UniBlue}{RGB}{83,121,170}
\setbeamercolor{block title}{use=structure,fg=white,bg=blue!75!black}
\setbeamercolor{block body}{use=structure,fg=black,bg=blue!10!white}

\title{MA162: Finite mathematics}
\subtitle{Gauss Jordan}
\author{Paul Koester}
\institute{University of Kentucky}
\date{March 26, 2014}

\begin{document}

\maketitle

\begin{frame}[t]{Last Time}
\begin{itemize}
  \item We solved several systems of two linear equations in two unknowns \vfill
  \item We also solved one system of three linear equations in three unknowns \vfill
  \item With the three by three systems and larger systems, it is very easy to get lost without a systematic
  approach.  
\end{itemize}
\end{frame}


\begin{frame}[t]{Gauss-Jordan Method}
 \begin{itemize}
   \item Given a system of linear equations, the Gauss-Jordan Method will replace our system with another system.
   \item The new system will be 
     \begin{itemize}
       \item equivalent to the original system, i.e., the two systems will have the same solutions
       \item easier to solve than the original system
    \end{itemize}
  \item This is accomplished by performing row operations
 \end{itemize}
\end{frame}

\begin{frame}[t]{Row Operations}
 \begin{itemize}
 \item [] Performing these operations on a system of linear equations will not change the solution set:
   \item Swap the order of any two equations
   \item Replace any equation by a nonzero constant multiple of itself
   \item Replace an equation by the sum of that equations with a constant multiple of any other equation
 \end{itemize}
\end{frame}

\begin{frame}[t]{The Challenge}
 \begin{itemize}
 \item We could apply the row operations in an ad hoc manner to convert our system into another, equivalent system.
 \item But the goal is to choose the "right" row operations so that the resulting system is very easy to solve.
 \end{itemize}
\end{frame}

\begin{frame}[t]{Gauss-Jordan: Warming up with 2 equations, 2 unknowns}
Solve the system of equations:
\[
  \begin{array}{ccccccc}
    x & + &  y & = & 2  \\
    x & + & 2y &= & 4  \\
  \end{array}
\]
Solution:  First replace row 2 with row 2 - row 1:  \(R_2 \mapsto R_2 - R_1\)
\[
  \begin{array}{ccccccc}
    x & + &  y & = & 2  \\
       &    & y   &= & 2  \\
  \end{array}
\]
Now replace row 1 with row 1 - row 2: \(R_1 \mapsto R_1 - R_2\)
\[
  \begin{array}{ccccccc}
    x & + &   & = & 0  \\
       &    & y   &= & 2  \\
  \end{array}
\]
Verify \((x,y) = (0,2)\) is a solution by plugging into the original.
\end{frame}

\begin{frame}[t]{Gauss-Jordan and Augmented Matrices}
The previous system can be written more compactly as 
\[
  \left[\begin{array}{cc|c}
    1 & 1 & 2  \\
    1 & 2 & 4  \\
  \end{array}\right]
\]
We can perform the row operations directly on the augmented matrix:
\[
  \left[\begin{array}{cc|c}
    1 & 1 & 2  \\
    1 & 2 & 4  \\
  \end{array}\right]
  \xrightarrow{R2 \mapsto R2 - R1}
  \left[\begin{array}{cc|c}
    1 & 1 & 2  \\
    0 & 1 & 2  \\
  \end{array}\right]
  \xrightarrow{R1 \mapsto R1 - R2}
  \left[\begin{array}{cc|c}
    1 & 0 & 0  \\
    0 & 1 & 2  \\
  \end{array}\right]
\]
Now put variables back in:  
\[
  \begin{array}{ccccccc}
    x & + &   & = & 0  \\
       &    & y   &= & 2  \\
  \end{array}
\]
\end{frame}

\begin{frame}[t]{Using Gauss-Jordan:  3 equations, 3 unknowns}
Solve the system of equations:
\[
  \begin{array}{ccccccc}
    x & + &  y & + &  z & = & 2  \\
    x & + & 2y & + & 3z & = & 4  \\
    x & + & 4y & + & 9z & = & 6  \\
  \end{array}
\]
\end{frame}

\begin{frame}[t]{Outline of Gauss-Jordan}
Part 1:  Start at the top left of the matrix.
\begin{itemize}
  \item In the current row, find first column with nonzero entry.  Divide entire row by this entry, so that first nonzero entry in row is a 1.
  \item This entry found above is called a \emph{pivot.}
  \item Use the pivot and row operation three for each row below, making the entries below the pivot equal to 0.
  \item Now move down to the next row and repeat the process
\end{itemize}
When done, matrix will have an upper triangular form.
\end{frame}

\begin{frame}[t]{Outline of Gauss-Jordan}
Part 2:  Now that matrix is in upper triangular form, go to the bottom row.
\begin{itemize}
  \item In the current row, the pivot entry, i.e, the first column entry with a nonzero entry.
  \item Use this pivot and row operation three for each row above, making the entries above the pivot equal to 0.
  \item Now move up to the next row and repeat the process
\end{itemize}

For the problems we deal with today, when done, your matrix will look like 
 \[
  \left[\begin{array}{ccc|c}
    1 & 0 & 0 &  a \\
    0 & 1 & 0 &  b \\
    0 & 0 & 1 &  c  \\
  \end{array}\right]
  \]
so the solution is \(x = a\), \(y = b\), and \(z = c\).
\end{frame}

\begin{frame}[t]{Applied Problem}
Mr. and Mrs. Garcia have a total of \(\$100,000\) to be invested in stocks, bonds, and a money market account.  
The stocks have a rate of return (RoR) of \(12\%\)/year, the bonds pay \(8\%\)/year and the money market pays \(6\%\)/year.  
The Garcias have stipulated that the amount invested in stocks should be equal to the sum of the amount invested in money 
markets and 3 times the amount invested in the bonds.  
How should the Garcias allocate their resources if they require an annual income of \(\$10,000\) from their investments?  
\end{frame}

\begin{frame}[t]{Garcia's System of Equations}
Let \(S\) denote the amount in stocks, \(B\) the amount in bonds, and \(M\) the amount in money markets.\\
\vfill
\textbf{Three equations:}\\
The Garcia's capital:   \(  S + B + M = \$100,000\) \\
Required return:   \(  0.12S + 0.08B + 0.06M = \$10,000\) \\
Desired Diversification:   \(  S =  3 B + M = 0\) \\  \vfill
Rewrite the last one as \(S - 3B - M = 0\), and build the matrix:
\vfill
 \[
  \left[\begin{array}{ccc|c}
          1 &       1  &        1 &  100000 \\
    0.12 &  0.08  &  0.06 &    10000 \\
          1 &      -3  &      -1 &              0 \\
  \end{array}\right]
  \]
\vfill  
Now apply Gauss-Jordan
  
\end{frame}

\begin{frame}[t]{Applied Problem}
What if the Garcias want to consider other possibilities, like
\begin{itemize}
  \item if they invest \(\$120,000\) and want return of \(\$10,000\)
  \item if they invest \(\$100,000\) and want return of \(\$12,000\)
  \item if they invest \(\$100,000\) and want return of \(\$9,000\)
\end{itemize}
You could repeat the previous calculation for each of these right hand sides.  
BUT, if we know all of the cases they want to consider in advance, we can do it all in a single calculation by using a larger augmented matrix:
 \[
  \left[\begin{array}{ccc|cccc}
          1 &       1  &        1 &  100000 & 120000 & 100000 & 100000 \\
    0.12 &  0.08  &  0.06 &    10000  &   10000 &    12000 &     9000 \\
          1 &      -3  &      -1 &              0  &            0  &             0  &          0 \\
  \end{array}\right]
  \]
Since the coefficients of the variables did not change, we will use the exact same row operations as before.
\end{frame}

\begin{frame}[t]{Applied Problem}
\begin{scriptsize}
 \[
  \left[\begin{array}{ccc|cccc}
1	&	1	&	1	&	100000	&	120000	&	100000	&	100000	\\
0.12	&	0.08	&	0.06	&	10000	&	10000	&	12000	&	9000	\\
1	&	-3	&	-1	&	0	&	0	&	0	&	0	\\
  \end{array}\right]
  \]
 \[
  \xrightarrow[R_2 \mapsto R_2 - 0.12R_1]{R3\mapsto R_3 - R1}
  \left[\begin{array}{ccc|cccc}
1	&	1	&	1	&	100000	&	120000	&	100000	&	100000	\\
0	&	-0.04	&	-0.06	&	-2000	&	-4400	&	0	&	-3000	\\
0	&	-4	&	-2	&	-100000	&	-120000	&	-100000	&	-100000	\\
  \end{array}\right]
  \]
 \[
  \xrightarrow{R2\mapsto -(R_2)/4}
  \left[\begin{array}{ccc|cccc}
1	&	1	&	1	&	100000	&	120000	&	100000	&	100000	\\
0	&	1	&	1.5	&	50000	&	110000	&	0	&	75000	\\
0	&	-4	&	-2	&	-100000	&	-120000	&	-100000	&	-100000	\\
  \end{array}\right]
  \]
 \[
  \xrightarrow{R3\mapsto R_3 + 4 R2}
  \left[\begin{array}{ccc|cccc}
1	&	1	&	1	&	100000	&	120000	&	100000	&	100000	\\
0	&	1	&	1.5	&	50000	&	110000	&	0	&	75000	\\
0	&	0	&	4	&	100000	&	320000	&	-100000	&	200000	\\
  \end{array}\right]
  \]
 \[
  \xrightarrow{R3\mapsto (R_3)/4}
  \left[\begin{array}{ccc|cccc}
1	&	1	&	1	&	100000	&	120000	&	100000	&	100000	\\
0	&	1	&	1.5	&	50000	&	110000	&	0	&	75000	\\
0	&	0	&	1	&	25000	&	80000	&	-25000	&	50000	\\
  \end{array}\right]
  \] 
\end{scriptsize}
\end{frame}
\begin{frame}
\begin{scriptsize}
  \[
  \xrightarrow[R_1\mapsto R_1 - R_3]{R_2 \mapsto R_2 - 1.5 R_3}
  \left[\begin{array}{ccc|cccc}
1	&	1	&	0	&	75000	&	40000	&	125000	&	50000	\\
0	&	1	&	0	&	12500	&	-10000	&	37500	&	0	\\
0	&	0	&	1	&	25000	&	80000	&	-25000	&	50000	\\
  \end{array}\right]
  \]
  \[
  \xrightarrow{R_1\mapsto R_1 - R_2}
  \left[\begin{array}{ccc|cccc}
1	&	0	&	0	&	62500	&	50000	&	87500	&	50000	\\
0	&	1	&	0	&	12500	&	-10000	&	37500	&	0	\\
0	&	0	&	1	&	25000	&	80000	&	-25000	&	50000	\\
  \end{array}\right]
  \]

Now we can read off the answers for each of the Garcia's scenarios.  
Notice the second and third cases are going to cause trouble, as they require the Garcias to invest negative amounts.


\end{scriptsize}
\end{frame}



\end{document}
