<BODY > <HR><center> <table border=1> <td> <A NAME="tex2html16" HREF="linalg.html"><img height=36 width=36 alt="PREVIOUS" src="../../../icons/latex2html/previous.gif"></A></td> <td> <A NAME="tex2html22" HREF="linalg.html"><img height=36 width=36 alt="UP" src="../../../icons/latex2html/up.gif"></A></td> <td> <A NAME="tex2html24" HREF="node2.html"><img height=36 width=36 alt="NEXT" src="../../../icons/latex2html/next.gif"></A></td> <td><a href="contents-node1.html"><img height=36 width=36 alt="CONTENTS" src="../../../icons/latex2html/toc.gif"></a></td> </table> </center> <HR> <!--End of Navigation Panel--> <H1><A NAME="SECTION00010000000000000000"> Gaussian elimination</A> </H1> <P> Gaussian elimination is a systematic strategy for solving a set of linear equations. It can also be used to construct the inverse of a matrix and to factor a matrix into the product of lower and upper triangular matrices. We start by solving the linear system <P></P> <DIV ALIGN="CENTER"> <!-- MATH \begin{eqnarray*} x_1 + 2x_2 &=& -1 \\ 2x_1 + x_2 + x_3 &=& -1 \\ 3x_1 + x_2 + x_3 &=& 4\\ \end{eqnarray*} --> <IMG WIDTH="159" HEIGHT="96" BORDER="0" SRC="img1.png" ALT="\begin{eqnarray*} x_1 + 2x_2 &amp;=&amp; -1 \\ 2x_1 + x_2 + x_3 &amp;=&amp; -1 \\ 3x_1 + x_2 + x_3 &amp;=&amp; 4\\ \end{eqnarray*}"></DIV> <BR CLEAR="ALL"><P></P> Basically, the objective of Gaussian elimination is to do transformations on the equations that do not change the solution, but systematically zero out (eliminate) the off-diagonal coefficients, leaving a set of equations from which we can read off the answers. <P> We express the problem in terms of a set of equations, and side-by-side, we express it in terms of an equivalent matrix product. We do this to show how the manipulations in the matrix tracks the manipulations of the equations, where it is easier to see that we are not changing the solution. <P> The method has two parts. First triangulation'' and then back substitution''. <P> <H2><A NAME="SECTION00011000000000000000"> Triangulation</A> </H2> <DIV ALIGN="CENTER"> <TABLE CELLPADDING=3 BORDER="1"> <TR><TD ALIGN="LEFT"><B>Equations</B></TD> <TD ALIGN="LEFT"><B>Matrix-vector representation</B></TD> </TR> <TR><TD ALIGN="LEFT"> <BR> <TABLE WIDTH="357"> <TR><TD> Starting equation <P></P> <DIV ALIGN="CENTER"> <!-- MATH \begin{eqnarray*} x_1 + 2x_2 + 0x_3 &=& -1 \\ 2x_1 + x_2 - x_3 &=& -1 \\ 3x_1 + x_2 + x_3 &=& 4\\ \end{eqnarray*} --> <IMG WIDTH="167" HEIGHT="96" BORDER="0" SRC="img2.png" ALT="\begin{eqnarray*} x_1 + 2x_2 + 0x_3 &amp;=&amp; -1 \\ 2x_1 + x_2 - x_3 &amp;=&amp; -1 \\ 3x_1 + x_2 + x_3 &amp;=&amp; 4\\ \end{eqnarray*}"></DIV> <BR CLEAR="ALL"><P></P></TD></TR> </TABLE></TD> <TD ALIGN="LEFT"><TABLE WIDTH="276"> <TR><TD> Equivalent matrix-vector equation <BR><P></P> <DIV ALIGN="CENTER"> <!-- MATH \begin{displaymath} \left( \begin{array}{rrr} 1 & 2 & 0 \\ 2 & 1 & -1 \\ 3 & 1 & 1 \end{array} \right) \left( \begin{array}{r} x_1 \\ x_2 \\ x_3 \\ \end{array} \right) = \left( \begin{array}{r} -1 \\ -1 \\ 4 \\ \end{array} \right) \end{displaymath} --> <IMG WIDTH="251" HEIGHT="64" BORDER="0" SRC="img3.png" ALT="\begin{displaymath} \left( \begin{array}{rrr} 1 &amp; 2 &amp; 0 \\ 2 &amp; 1 &amp; -1 \\ 3 &amp; ... ...left( \begin{array}{r} -1 \\ -1 \\ 4 \\ \end{array}\right) \end{displaymath}"> </DIV> <BR CLEAR="ALL"> <P></P></TD></TR> </TABLE></TD> </TR> <TR><TD ALIGN="LEFT"> <BR> <TABLE WIDTH="357"> <TR><TD> First step: examine the coefficients of <IMG WIDTH="21" HEIGHT="30" ALIGN="MIDDLE" BORDER="0" SRC="img4.png" ALT="$x_1$">. Swap equations (1) and (3) so the largest coefficient is in the first equation (first row). This is called the pivot'' element. <P></P> <DIV ALIGN="CENTER"> <!-- MATH \begin{eqnarray*} 3x_1 + x_2 + x_3 &=& 4 \\ 2x_1 + x_2 - x_3 &=& -1 \\ x_1 + 2x_2 + 0x_3 &=& -1 \\ \end{eqnarray*} --> <IMG WIDTH="167" HEIGHT="96" BORDER="0" SRC="img5.png" ALT="\begin{eqnarray*} 3x_1 + x_2 + x_3 &amp;=&amp; 4 \\ 2x_1 + x_2 - x_3 &amp;=&amp; -1 \\ x_1 + 2x_2 + 0x_3 &amp;=&amp; -1 \\ \end{eqnarray*}"></DIV> <BR CLEAR="ALL"><P></P></TD></TR> </TABLE></TD> <TD ALIGN="LEFT"><TABLE WIDTH="276"> <TR><TD> Swap the first the third rows of the matrix and the first and third elements of the vector on the right side. Note that in the matrix equation we <EM>don't</EM> interchange <IMG WIDTH="21" HEIGHT="30" ALIGN="MIDDLE" BORDER="0" SRC="img4.png" ALT="$x_1$"> and <IMG WIDTH="21" HEIGHT="30" ALIGN="MIDDLE" BORDER="0" SRC="img6.png" ALT="$x_3$">. <BR><P></P> <DIV ALIGN="CENTER"> <!-- MATH \begin{displaymath} \left( \begin{array}{rrr} 3 & 1 & 1 \\ 2 & 1 & -1 \\ 1 & 2 & 0 \\ \end{array} \right) \left( \begin{array}{r} x_1 \\ x_2 \\ x_3 \\ \end{array} \right) = \left( \begin{array}{r} 4 \\ -1 \\ -1 \\ \end{array} \right) \end{displaymath} --> <IMG WIDTH="251" HEIGHT="64" BORDER="0" SRC="img7.png" ALT="\begin{displaymath} \left( \begin{array}{rrr} 3 &amp; 1 &amp; 1 \\ 2 &amp; 1 &amp; -1 \\ 1 &amp; ... ...left( \begin{array}{r} 4 \\ -1 \\ -1 \\ \end{array}\right) \end{displaymath}"> </DIV> <BR CLEAR="ALL"> <P></P></TD></TR> </TABLE></TD> </TR> <TR><TD ALIGN="LEFT"> <BR> <TABLE WIDTH="357"> <TR><TD> Next step: Divide the first equation by the coefficient <IMG WIDTH="12" HEIGHT="13" ALIGN="BOTTOM" BORDER="0" SRC="img8.png" ALT="$3$"> to make the pivot element equal to <IMG WIDTH="12" HEIGHT="13" ALIGN="BOTTOM" BORDER="0" SRC="img9.png" ALT="$1$">. <P></P> <DIV ALIGN="CENTER"> <!-- MATH \begin{eqnarray*} x_1 + x_2/3 + x_3/3 &=& 4/3 \\ 2x_1 + x_2 - x_3 &=& -1 \\ x_1 + 2x_2 +0x_3 &=& -1 \\ \end{eqnarray*} --> <IMG WIDTH="187" HEIGHT="96" BORDER="0" SRC="img10.png" ALT="\begin{eqnarray*} x_1 + x_2/3 + x_3/3 &amp;=&amp; 4/3 \\ 2x_1 + x_2 - x_3 &amp;=&amp; -1 \\ x_1 + 2x_2 +0x_3 &amp;=&amp; -1 \\ \end{eqnarray*}"></DIV> <BR CLEAR="ALL"><P></P></TD></TR> </TABLE></TD> <TD ALIGN="LEFT"><TABLE WIDTH="276"> <TR><TD> <BR><P></P> <DIV ALIGN="CENTER"> <!-- MATH \begin{displaymath} \left( \begin{array}{rrr} 1 & 1/3 & 1/3 \\ 2 & 1 & -1 \\ 1 & 2 & 0 \\ \end{array} \right) \left( \begin{array}{r} x_1 \\ x_2 \\ x_3 \\ \end{array} \right) = \left( \begin{array}{r} 4/3 \\ -1 \\ -1 \\ \end{array} \right) \end{displaymath} --> <IMG WIDTH="274" HEIGHT="64" BORDER="0" SRC="img11.png" ALT="\begin{displaymath} \left( \begin{array}{rrr} 1 &amp; 1/3 &amp; 1/3 \\ 2 &amp; 1 &amp; -1 \\ ... ...ft( \begin{array}{r} 4/3 \\ -1 \\ -1 \\ \end{array}\right) \end{displaymath}"> </DIV> <BR CLEAR="ALL"> <P></P></TD></TR> </TABLE></TD> </TR> <TR><TD ALIGN="LEFT"> <BR> <TABLE WIDTH="357"> <TR><TD> Next step: Multiply the first equation by 2 and subtract it from the second equation, putting the result in the second equation. This eliminates'' the coefficient of <IMG WIDTH="21" HEIGHT="30" ALIGN="MIDDLE" BORDER="0" SRC="img4.png" ALT="$x_1$"> in the second equation. <P></P> <DIV ALIGN="CENTER"> <!-- MATH \begin{eqnarray*} x_1 + x_2/3 + x_3/3 &=& 4/3 \\ 0x_1 + x_2/3 - 5x_3/3 &=& -11/3 \\ x_1 + 2x_2 +0x_3 &=& -1 \\ \end{eqnarray*} --> <IMG WIDTH="223" HEIGHT="96" BORDER="0" SRC="img12.png" ALT="\begin{eqnarray*} x_1 + x_2/3 + x_3/3 &amp;=&amp; 4/3 \\ 0x_1 + x_2/3 - 5x_3/3 &amp;=&amp; -11/3 \\ x_1 + 2x_2 +0x_3 &amp;=&amp; -1 \\ \end{eqnarray*}"></DIV> <BR CLEAR="ALL"><P></P></TD></TR> </TABLE></TD> <TD ALIGN="LEFT"><TABLE WIDTH="276"> <TR><TD> <BR><P></P> <DIV ALIGN="CENTER"> <!-- MATH \begin{displaymath} \left( \begin{array}{rrr} 1 & 1/3 & 1/3 \\ 0 & 1/3 & -5/3 \\ 1 & 2 & 0 \\ \end{array} \right) \left( \begin{array}{r} x_1 \\ x_2 \\ x_3 \\ \end{array} \right) = \left( \begin{array}{r} 4/3 \\ -11/3 \\ -1 \\ \end{array} \right) \end{displaymath} --> <IMG WIDTH="306" HEIGHT="64" BORDER="0" SRC="img13.png" ALT="\begin{displaymath} \left( \begin{array}{rrr} 1 &amp; 1/3 &amp; 1/3 \\ 0 &amp; 1/3 &amp; -5/3 ... ... \begin{array}{r} 4/3 \\ -11/3 \\ -1 \\ \end{array}\right) \end{displaymath}"> </DIV> <BR CLEAR="ALL"> <P></P></TD></TR> </TABLE></TD> </TR> <TR><TD ALIGN="LEFT"> <BR> <TABLE WIDTH="357"> <TR><TD> Next step: Eliminate the coefficient of <IMG WIDTH="21" HEIGHT="30" ALIGN="MIDDLE" BORDER="0" SRC="img4.png" ALT="$x_1$"> in the third equation by subtracting the first equation from the third, putting the result into the third equation. <P></P> <DIV ALIGN="CENTER"> <!-- MATH \begin{eqnarray*} x_1 + x_2/3 + x_3/3 &=& 4/3 \\ 0x_1 + x_2/3 - 5x_3/3 &=& -11/3 \\ 0x_1 + 5x_2/3 -x_3/3 &=& -7/3 \\ \end{eqnarray*} --> <IMG WIDTH="223" HEIGHT="96" BORDER="0" SRC="img14.png" ALT="\begin{eqnarray*} x_1 + x_2/3 + x_3/3 &amp;=&amp; 4/3 \\ 0x_1 + x_2/3 - 5x_3/3 &amp;=&amp; -11/3 \\ 0x_1 + 5x_2/3 -x_3/3 &amp;=&amp; -7/3 \\ \end{eqnarray*}"></DIV> <BR CLEAR="ALL"><P></P></TD></TR> </TABLE></TD> <TD ALIGN="LEFT"><TABLE WIDTH="276"> <TR><TD> <BR><P></P> <DIV ALIGN="CENTER"> <!-- MATH \begin{displaymath} \left( \begin{array}{rrr} 1 & 1/3 & 1/3 \\ 0 & 1/3 & -5/3 \\ 0 & 5/3 & -1/3 \\ \end{array} \right) \left( \begin{array}{r} x_1 \\ x_2 \\ x_3 \\ \end{array} \right) = \left( \begin{array}{r} 4/3 \\ -11/3 \\ -7/3 \\ \end{array} \right) \end{displaymath} --> <IMG WIDTH="306" HEIGHT="64" BORDER="0" SRC="img15.png" ALT="\begin{displaymath} \left( \begin{array}{rrr} 1 &amp; 1/3 &amp; 1/3 \\ 0 &amp; 1/3 &amp; -5/3 ... ...begin{array}{r} 4/3 \\ -11/3 \\ -7/3 \\ \end{array}\right) \end{displaymath}"> </DIV> <BR CLEAR="ALL"> <P></P></TD></TR> </TABLE></TD> </TR> </TABLE> </DIV> <DIV ALIGN="CENTER"> <TABLE CELLPADDING=3 BORDER="1"> <TR><TD ALIGN="LEFT"><TABLE WIDTH="357"> <TR><TD> Next step: Now work on the second column (coefficients <IMG WIDTH="21" HEIGHT="30" ALIGN="MIDDLE" BORDER="0" SRC="img16.png" ALT="$x_2$">). We want the largest coefficient in the second equation (diagonal element in the matrix.) So swap the second and third equation. <P></P> <DIV ALIGN="CENTER"> <!-- MATH \begin{eqnarray*} x_1 + x_2/3 + x_3/3 &=& 4/3 \\ 0x_1 + 5x_2/3 -x_3/3 &=& -7/3 \\ 0x_1 + x_2/3 - 5x_3/3 &=& -11/3 \\ \end{eqnarray*} --> <IMG WIDTH="223" HEIGHT="96" BORDER="0" SRC="img17.png" ALT="\begin{eqnarray*} x_1 + x_2/3 + x_3/3 &amp;=&amp; 4/3 \\ 0x_1 + 5x_2/3 -x_3/3 &amp;=&amp; -7/3 \\ 0x_1 + x_2/3 - 5x_3/3 &amp;=&amp; -11/3 \\ \end{eqnarray*}"></DIV> <BR CLEAR="ALL"><P></P></TD></TR> </TABLE></TD> <TD ALIGN="LEFT"><TABLE WIDTH="276"> <TR><TD> <BR><P></P> <DIV ALIGN="CENTER"> <!-- MATH \begin{displaymath} \left( \begin{array}{rrr} 1 & 1/3 & 1/3 \\ 0 & 5/3 & -1/3 \\ 0 & 1/3 & -5/3 \\ \end{array} \right) \left( \begin{array}{r} x_1 \\ x_2 \\ x_3 \\ \end{array} \right) = \left( \begin{array}{r} 4/3 \\ -7/3 \\ -11/3 \\ \end{array} \right) \end{displaymath} --> <IMG WIDTH="306" HEIGHT="64" BORDER="0" SRC="img18.png" ALT="\begin{displaymath} \left( \begin{array}{rrr} 1 &amp; 1/3 &amp; 1/3 \\ 0 &amp; 5/3 &amp; -1/3 ... ...begin{array}{r} 4/3 \\ -7/3 \\ -11/3 \\ \end{array}\right) \end{displaymath}"> </DIV> <BR CLEAR="ALL"> <P></P></TD></TR> </TABLE></TD> </TR> <TR><TD ALIGN="LEFT"> <BR> <TABLE WIDTH="357"> <TR><TD> Now divide by 5/3, the pivot element in the second column. <P></P> <DIV ALIGN="CENTER"> <!-- MATH \begin{eqnarray*} x_1 + x_2/3 + x_3/3 &=& 4/3 \\ 0x_1 + x_2 - x_3/5 &=& -7/5 \\ 0x_1 + x_2/3 - 5x_3/3 &=& -11/3 \\ \end{eqnarray*} --> <IMG WIDTH="223" HEIGHT="96" BORDER="0" SRC="img19.png" ALT="\begin{eqnarray*} x_1 + x_2/3 + x_3/3 &amp;=&amp; 4/3 \\ 0x_1 + x_2 - x_3/5 &amp;=&amp; -7/5 \\ 0x_1 + x_2/3 - 5x_3/3 &amp;=&amp; -11/3 \\ \end{eqnarray*}"></DIV> <BR CLEAR="ALL"><P></P></TD></TR> </TABLE></TD> <TD ALIGN="LEFT"><TABLE WIDTH="276"> <TR><TD> <BR><P></P> <DIV ALIGN="CENTER"> <!-- MATH \begin{displaymath} \left( \begin{array}{rrr} 1 & 1/3 & 1/3 \\ 0 & 1 & -1/5 \\ 0 & 1/3 & -5/3 \\ \end{array} \right) \left( \begin{array}{r} x_1 \\ x_2 \\ x_3 \\ \end{array} \right) = \left( \begin{array}{r} 4/3 \\ -7/5 \\ -11/3 \\ \end{array} \right) \end{displaymath} --> <IMG WIDTH="306" HEIGHT="64" BORDER="0" SRC="img20.png" ALT="\begin{displaymath} \left( \begin{array}{rrr} 1 &amp; 1/3 &amp; 1/3 \\ 0 &amp; 1 &amp; -1/5 \\... ...begin{array}{r} 4/3 \\ -7/5 \\ -11/3 \\ \end{array}\right) \end{displaymath}"> </DIV> <BR CLEAR="ALL"> <P></P></TD></TR> </TABLE></TD> </TR> <TR><TD ALIGN="LEFT"> <BR> <TABLE WIDTH="357"> <TR><TD> Now eliminate the coefficient of <IMG WIDTH="21" HEIGHT="30" ALIGN="MIDDLE" BORDER="0" SRC="img16.png" ALT="$x_2$"> in the third equation by multiplying the second equation by 1/3, subtracting the result from the third equation, and putting the result in the third equation. <P></P> <DIV ALIGN="CENTER"> <!-- MATH \begin{eqnarray*} x_1 + x_2/3 + x_3/3 &=& 4/3 \\ 0x_1 + x_2 - x_3/5 &=& -7/5 \\ 0x_1 + 0x_2 -24x_3/15 &=& -48/15 \\ \end{eqnarray*} --> <IMG WIDTH="239" HEIGHT="96" BORDER="0" SRC="img21.png" ALT="\begin{eqnarray*} x_1 + x_2/3 + x_3/3 &amp;=&amp; 4/3 \\ 0x_1 + x_2 - x_3/5 &amp;=&amp; -7/5 \\ 0x_1 + 0x_2 -24x_3/15 &amp;=&amp; -48/15 \\ \end{eqnarray*}"></DIV> <BR CLEAR="ALL"><P></P></TD></TR> </TABLE></TD> <TD ALIGN="LEFT"><TABLE WIDTH="276"> <TR><TD> <BR><P></P> <DIV ALIGN="CENTER"> <!-- MATH \begin{displaymath} \left( \begin{array}{rrr} 1 & 1/3 & 1/3 \\ 0 & 1 & -1/5 \\ 0 & 0 & -24/15 \\ \end{array} \right) \left( \begin{array}{r} x_1 \\ x_2 \\ x_3 \\ \end{array} \right) = \left( \begin{array}{r} 4/3 \\ -7/5 \\ -48/15 \\ \end{array} \right) \end{displaymath} --> <IMG WIDTH="330" HEIGHT="64" BORDER="0" SRC="img22.png" ALT="\begin{displaymath} \left( \begin{array}{rrr} 1 &amp; 1/3 &amp; 1/3 \\ 0 &amp; 1 &amp; -1/5 \\... ...egin{array}{r} 4/3 \\ -7/5 \\ -48/15 \\ \end{array}\right) \end{displaymath}"> </DIV> <BR CLEAR="ALL"> <P></P></TD></TR> </TABLE></TD> </TR> <TR><TD ALIGN="LEFT"> <BR> <TABLE WIDTH="357"> <TR><TD> To complete the triangulation'' step we divide the third equation by the coefficient of <IMG WIDTH="21" HEIGHT="30" ALIGN="MIDDLE" BORDER="0" SRC="img6.png" ALT="$x_3$">, namely <IMG WIDTH="57" HEIGHT="32" ALIGN="MIDDLE" BORDER="0" SRC="img23.png" ALT="$-24/15$">. <P></P> <DIV ALIGN="CENTER"> <!-- MATH \begin{eqnarray*} x_1 + x_2/3 + x_3/3 &=& 4/3 \\ 0x_1 + x_2 - x_3/5 &=& -7/5 \\ 0x_1 + 0x_2 + x_3 &=& 2 \\ \end{eqnarray*} --> <IMG WIDTH="199" HEIGHT="96" BORDER="0" SRC="img24.png" ALT="\begin{eqnarray*} x_1 + x_2/3 + x_3/3 &amp;=&amp; 4/3 \\ 0x_1 + x_2 - x_3/5 &amp;=&amp; -7/5 \\ 0x_1 + 0x_2 + x_3 &amp;=&amp; 2 \\ \end{eqnarray*}"></DIV> <BR CLEAR="ALL"><P></P></TD></TR> </TABLE></TD> <TD ALIGN="LEFT"><TABLE WIDTH="276"> <TR><TD> Notice that the matrix is now in upper triangular form - all elements below the diagonal are zero. <BR><P></P> <DIV ALIGN="CENTER"> <!-- MATH \begin{displaymath} \left( \begin{array}{rrr} 1 & 1/3 & 1/3 \\ 0 & 1 & -1/5 \\ 0 & 0 & 1 \\ \end{array} \right) \left( \begin{array}{r} x_1 \\ x_2 \\ x_3 \\ \end{array} \right) = \left( \begin{array}{r} 4/3 \\ -7/5 \\ 2 \\ \end{array} \right) \end{displaymath} --> <IMG WIDTH="298" HEIGHT="64" BORDER="0" SRC="img25.png" ALT="\begin{displaymath} \left( \begin{array}{rrr} 1 &amp; 1/3 &amp; 1/3 \\ 0 &amp; 1 &amp; -1/5 \\... ...( \begin{array}{r} 4/3 \\ -7/5 \\ 2 \\ \end{array}\right) \end{displaymath}"> </DIV> <BR CLEAR="ALL"> <P></P></TD></TR> </TABLE></TD> </TR> </TABLE> </DIV> <H2><A NAME="SECTION00012000000000000000"> Back substitution</A> </H2> <DIV ALIGN="CENTER"> <TABLE CELLPADDING=3 BORDER="1"> <TR><TD ALIGN="LEFT"><TABLE WIDTH="357"> <TR><TD> Next, we do back substitution.'' We start by noticing that the last equation gives us the solution for <IMG WIDTH="21" HEIGHT="30" ALIGN="MIDDLE" BORDER="0" SRC="img6.png" ALT="$x_3$">. Then we work our way up the third column, eliminating the coefficients of <IMG WIDTH="21" HEIGHT="30" ALIGN="MIDDLE" BORDER="0" SRC="img6.png" ALT="$x_3$"> - this is just Gaussian elimination backwards! But it amounts to the same thing as plugging in the solution for <IMG WIDTH="21" HEIGHT="30" ALIGN="MIDDLE" BORDER="0" SRC="img6.png" ALT="$x_3$"> into the other two equations and moving the resulting constant to the rhs of the equation. So multiply the third equation by <IMG WIDTH="41" HEIGHT="32" ALIGN="MIDDLE" BORDER="0" SRC="img26.png" ALT="$-3/5$"> and subtract from equation two, leaving the result in equation two. <P></P> <DIV ALIGN="CENTER"> <!-- MATH \begin{eqnarray*} x_1 + x_2/3 + x_3/3 &=& 4/3 \\ 0x_1 + x_2 + 0 x_3 &=& -1 \\ 0x_1 + 0x_2 + x_3 &=& 2 \\ \end{eqnarray*} --> <IMG WIDTH="187" HEIGHT="96" BORDER="0" SRC="img27.png" ALT="\begin{eqnarray*} x_1 + x_2/3 + x_3/3 &amp;=&amp; 4/3 \\ 0x_1 + x_2 + 0 x_3 &amp;=&amp; -1 \\ 0x_1 + 0x_2 + x_3 &amp;=&amp; 2 \\ \end{eqnarray*}"></DIV> <BR CLEAR="ALL"><P></P></TD></TR> </TABLE></TD> <TD ALIGN="LEFT"><TABLE WIDTH="276"> <TR><TD> Notice that the matrix is now in upper triangular form - all elements below the diagonal are zero. <BR><P></P> <DIV ALIGN="CENTER"> <!-- MATH \begin{displaymath} \left( \begin{array}{rrr} 1 & 1/3 & 1/3 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \right) \left( \begin{array}{r} x_1 \\ x_2 \\ x_3 \\ \end{array} \right) = \left( \begin{array}{r} 4/3 \\ -1 \\ 2 \\ \end{array} \right) \end{displaymath} --> <IMG WIDTH="274" HEIGHT="64" BORDER="0" SRC="img28.png" ALT="\begin{displaymath} \left( \begin{array}{rrr} 1 &amp; 1/3 &amp; 1/3 \\ 0 &amp; 1 &amp; 0 \\ 0... ...ft( \begin{array}{r} 4/3 \\ -1 \\ 2 \\ \end{array}\right) \end{displaymath}"> </DIV> <BR CLEAR="ALL"> <P></P></TD></TR> </TABLE></TD> </TR> <TR><TD ALIGN="LEFT"> <BR> <TABLE WIDTH="357"> <TR><TD> Continuing on the third column, eliminate the coefficient of <IMG WIDTH="21" HEIGHT="30" ALIGN="MIDDLE" BORDER="0" SRC="img6.png" ALT="$x_3$"> in equation 1. <P></P> <DIV ALIGN="CENTER"> <!-- MATH \begin{eqnarray*} x_1 + 2x_2/3 + 0x_3 &=& 2/3 \\ 0x_1 + x_2 + 0x_3 &=& -1 \\ 0x_1 + 0x_2 + x_3 &=& 2 \\ \end{eqnarray*} --> <IMG WIDTH="187" HEIGHT="96" BORDER="0" SRC="img29.png" ALT="\begin{eqnarray*} x_1 + 2x_2/3 + 0x_3 &amp;=&amp; 2/3 \\ 0x_1 + x_2 + 0x_3 &amp;=&amp; -1 \\ 0x_1 + 0x_2 + x_3 &amp;=&amp; 2 \\ \end{eqnarray*}"></DIV> <BR CLEAR="ALL"><P></P></TD></TR> </TABLE></TD> <TD ALIGN="LEFT"><TABLE WIDTH="276"> <TR><TD> <BR><P></P> <DIV ALIGN="CENTER"> <!-- MATH \begin{displaymath} \left( \begin{array}{rrr} 1 & 2/3 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \right) \left( \begin{array}{r} x_1 \\ x_2 \\ x_3 \\ \end{array} \right) = \left( \begin{array}{r} 2/3 \\ -1 \\ 2 \\ \end{array} \right) \end{displaymath} --> <IMG WIDTH="258" HEIGHT="64" BORDER="0" SRC="img30.png" ALT="\begin{displaymath} \left( \begin{array}{rrr} 1 &amp; 2/3 &amp; 0 \\ 0 &amp; 1 &amp; 0 \\ 0 &amp;... ...ft( \begin{array}{r} 2/3 \\ -1 \\ 2 \\ \end{array}\right) \end{displaymath}"> </DIV> <BR CLEAR="ALL"> <P></P></TD></TR> </TABLE></TD> </TR> <TR><TD ALIGN="LEFT"> <BR> <TABLE WIDTH="357"> <TR><TD> Next, work on the second column. We have only the coefficient of <IMG WIDTH="21" HEIGHT="30" ALIGN="MIDDLE" BORDER="0" SRC="img16.png" ALT="$x_2$"> in the first equation to eliminate. We then get the answer. <P></P> <DIV ALIGN="CENTER"> <!-- MATH \begin{eqnarray*} x_1 + 0x_2 + 0x_3 &=& 1 \\ 0x_1 + x_2 + 0 x_3 &=& -1 \\ 0x_1 + 0x_2 + x_3 &=& 2 \\ \end{eqnarray*} --> <IMG WIDTH="167" HEIGHT="96" BORDER="0" SRC="img31.png" ALT="\begin{eqnarray*} x_1 + 0x_2 + 0x_3 &amp;=&amp; 1 \\ 0x_1 + x_2 + 0 x_3 &amp;=&amp; -1 \\ 0x_1 + 0x_2 + x_3 &amp;=&amp; 2 \\ \end{eqnarray*}"></DIV> <BR CLEAR="ALL"><P></P></TD></TR> </TABLE></TD> <TD ALIGN="LEFT"><TABLE WIDTH="276"> <TR><TD> Notice that we now have a unit matrix, so the solution can be read off. <BR><P></P> <DIV ALIGN="CENTER"> <!-- MATH \begin{displaymath} \left( \begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{array} \right) \left( \begin{array}{r} x_1 \\ x_2 \\ x_3 \\ \end{array} \right) = \left( \begin{array}{r} 1 \\ -1 \\ 2 \\ \end{array} \right) \end{displaymath} --> <IMG WIDTH="238" HEIGHT="64" BORDER="0" SRC="img32.png" ALT="\begin{displaymath} \left( \begin{array}{rrr} 1 &amp; 0 &amp; 0 \\ 0 &amp; 1 &amp; 0 \\ 0 &amp; 0... ...left( \begin{array}{r} 1 \\ -1 \\ 2 \\ \end{array}\right) \end{displaymath}"> </DIV> <BR CLEAR="ALL"> <P></P></TD></TR> </TABLE></TD> </TR> <TR><TD ALIGN="LEFT"> <BR> <TABLE WIDTH="357"> <TR><TD> The last step, of course, is to check the solution by plugging it in to the orginal system of equations. <P></P> <DIV ALIGN="CENTER"> <!-- MATH \begin{eqnarray*} 1 + 2\cdot(-1) &=& -1 \\ 2\cdot 1 + (-1) - 2 &=& -1 \\ 3\cdot 1 + (-1) + 2 &=& 4\\ \end{eqnarray*} --> <IMG WIDTH="170" HEIGHT="96" BORDER="0" SRC="img33.png" ALT="\begin{eqnarray*} 1 + 2\cdot(-1) &amp;=&amp; -1 \\ 2\cdot 1 + (-1) - 2 &amp;=&amp; -1 \\ 3\cdot 1 + (-1) + 2 &amp;=&amp; 4\\ \end{eqnarray*}"></DIV> <BR CLEAR="ALL"><P></P></TD></TR> </TABLE></TD> <TD ALIGN="LEFT"><TABLE WIDTH="276"> <TR><TD> <BR><P></P> <DIV ALIGN="CENTER"> <!-- MATH \begin{displaymath} \left( \begin{array}{rrr} 1 & 2 & 0 \\ 2 & 1 & -1 \\ 3 & 1 & 1 \\ \end{array} \right) \left( \begin{array}{r} 1 \\ -1 \\ 2 \\ \end{array} \right) = \left( \begin{array}{r} -1 \\ -1 \\ 4 \\ \end{array} \right) \end{displaymath} --> <IMG WIDTH="255" HEIGHT="64" BORDER="0" SRC="img34.png" ALT="\begin{displaymath} \left( \begin{array}{rrr} 1 &amp; 2 &amp; 0 \\ 2 &amp; 1 &amp; -1 \\ 3 &amp; ... ...left( \begin{array}{r} -1 \\ -1 \\ 4 \\ \end{array}\right) \end{displaymath}"> </DIV> <BR CLEAR="ALL"> <P></P></TD></TR> </TABLE></TD> </TR> </TABLE> </DIV> <P> <HR><center> <table border=1> <td> <A NAME="tex2html16" HREF="linalg.html"><img height=36 width=36 alt="PREVIOUS" src="../../../icons/latex2html/previous.gif"></A></td> <td> <A NAME="tex2html22" HREF="linalg.html"><img height=36 width=36 alt="UP" src="../../../icons/latex2html/up.gif"></A></td> <td> <A NAME="tex2html24" HREF="node2.html"><img height=36 width=36 alt="NEXT" src="../../../icons/latex2html/next.gif"></A></td> <td><a href="contents-node1.html"><img height=36 width=36 alt="CONTENTS" src="../../../icons/latex2html/toc.gif"></a></td> </table> </center> <HR> <!--End of Navigation Panel--> <HR><P><ADDRESS> <I></I> </ADDRESS> </BODY>