Gaussian elimination

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

\begin{eqnarray*}
x_1 + 2x_2 &=& -1 \\
2x_1 + x_2 + x_3 &=& -1 \\
3x_1 + x_2 + x_3 &=& 4\\
\end{eqnarray*}

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.

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.

The method has two parts. First ``triangulation'' and then ``back substitution''.

Triangulation

Equations Matrix-vector representation

Starting equation

\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*}

Equivalent matrix-vector equation

\begin{displaymath}
\left(
\begin{array}{rrr}
1 & 2 & 0 \\
2 & 1 & -1 \\
3 & ...
...left(
\begin{array}{r}
-1 \\
-1 \\
4 \\
\end{array}\right)
\end{displaymath}


First step: examine the coefficients of $x_1$. Swap equations (1) and (3) so the largest coefficient is in the first equation (first row). This is called the ``pivot'' element.

\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*}

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 don't interchange $x_1$ and $x_3$.

\begin{displaymath}
\left(
\begin{array}{rrr}
3 & 1 & 1 \\
2 & 1 & -1 \\
1 & ...
...left(
\begin{array}{r}
4 \\
-1 \\
-1 \\
\end{array}\right)
\end{displaymath}


Next step: Divide the first equation by the coefficient $3$ to make the pivot element equal to $1$.

\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*}


\begin{displaymath}
\left(
\begin{array}{rrr}
1 & 1/3 & 1/3 \\
2 & 1 & -1 \\
...
...ft(
\begin{array}{r}
4/3 \\
-1 \\
-1 \\
\end{array}\right)
\end{displaymath}


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 $x_1$ in the second equation.

\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*}


\begin{displaymath}
\left(
\begin{array}{rrr}
1 & 1/3 & 1/3 \\
0 & 1/3 & -5/3 ...
...
\begin{array}{r}
4/3 \\
-11/3 \\
-1 \\
\end{array}\right)
\end{displaymath}


Next step: Eliminate the coefficient of $x_1$ in the third equation by subtracting the first equation from the third, putting the result into the third equation.

\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*}


\begin{displaymath}
\left(
\begin{array}{rrr}
1 & 1/3 & 1/3 \\
0 & 1/3 & -5/3 ...
...begin{array}{r}
4/3 \\
-11/3 \\
-7/3 \\
\end{array}\right)
\end{displaymath}

Next step: Now work on the second column (coefficients $x_2$). We want the largest coefficient in the second equation (diagonal element in the matrix.) So swap the second and third equation.

\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*}


\begin{displaymath}
\left(
\begin{array}{rrr}
1 & 1/3 & 1/3 \\
0 & 5/3 & -1/3 ...
...begin{array}{r}
4/3 \\
-7/3 \\
-11/3 \\
\end{array}\right)
\end{displaymath}


Now divide by 5/3, the pivot element in the second column.

\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*}


\begin{displaymath}
\left(
\begin{array}{rrr}
1 & 1/3 & 1/3 \\
0 & 1 & -1/5 \\...
...begin{array}{r}
4/3 \\
-7/5 \\
-11/3 \\
\end{array}\right)
\end{displaymath}


Now eliminate the coefficient of $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.

\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*}


\begin{displaymath}
\left(
\begin{array}{rrr}
1 & 1/3 & 1/3 \\
0 & 1 & -1/5 \\...
...egin{array}{r}
4/3 \\
-7/5 \\
-48/15 \\
\end{array}\right)
\end{displaymath}


To complete the ``triangulation'' step we divide the third equation by the coefficient of $x_3$, namely $-24/15$.

\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*}

Notice that the matrix is now in upper triangular form - all elements below the diagonal are zero.

\begin{displaymath}
\left(
\begin{array}{rrr}
1 & 1/3 & 1/3 \\
0 & 1 & -1/5 \\...
...(
\begin{array}{r}
4/3 \\
-7/5 \\
2 \\
\end{array}\right)
\end{displaymath}

Back substitution

Next, we do ``back substitution.'' We start by noticing that the last equation gives us the solution for $x_3$. Then we work our way up the third column, eliminating the coefficients of $x_3$ - this is just Gaussian elimination backwards! But it amounts to the same thing as plugging in the solution for $x_3$ into the other two equations and moving the resulting constant to the rhs of the equation. So multiply the third equation by $-3/5$ and subtract from equation two, leaving the result in equation two.

\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*}

Notice that the matrix is now in upper triangular form - all elements below the diagonal are zero.

\begin{displaymath}
\left(
\begin{array}{rrr}
1 & 1/3 & 1/3 \\
0 & 1 & 0 \\
0...
...ft(
\begin{array}{r}
4/3 \\
-1 \\
2 \\
\end{array}\right)
\end{displaymath}


Continuing on the third column, eliminate the coefficient of $x_3$ in equation 1.

\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*}


\begin{displaymath}
\left(
\begin{array}{rrr}
1 & 2/3 & 0 \\
0 & 1 & 0 \\
0 &...
...ft(
\begin{array}{r}
2/3 \\
-1 \\
2 \\
\end{array}\right)
\end{displaymath}


Next, work on the second column. We have only the coefficient of $x_2$ in the first equation to eliminate. We then get the answer.

\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*}

Notice that we now have a unit matrix, so the solution can be read off.

\begin{displaymath}
\left(
\begin{array}{rrr}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0...
...left(
\begin{array}{r}
1 \\
-1 \\
2 \\
\end{array}\right)
\end{displaymath}


The last step, of course, is to check the solution by plugging it in to the orginal system of equations.

\begin{eqnarray*}
1 + 2\cdot(-1) &=& -1 \\
2\cdot 1 + (-1) - 2 &=& -1 \\
3\cdot 1 + (-1) + 2 &=& 4\\
\end{eqnarray*}


\begin{displaymath}
\left(
\begin{array}{rrr}
1 & 2 & 0 \\
2 & 1 & -1 \\
3 & ...
...left(
\begin{array}{r}
-1 \\
-1 \\
4 \\
\end{array}\right)
\end{displaymath}