Ask Me Help Desk - Gaussian Elimination

Bonnie W: hello, and don't worry - lots of folks here to help.

First, here's a link to a description of the Gaussoian elimination procedure:

Gaussian elimination - Wikipedia, the free encyclopedia

Gaussian elimination is a method for solving multiple simultaneous linear equations. Assume you have N equations in N unknowns. The steps are basically these:

1. Set up a matrix of the coefficients of the N equations and a vector of the N values for each equation - this sets up an NxN matrix, where each row represents the coefficients of one of the equations and each column contains the coefficients of a particular variable, and a 1XN vector of the values of each equation.
2. Perform linear manipulations with the objective to turn the first coefficient of all rows of the matrix except for the first to 0. The process here is key - it's based on the fact that you can add or subtract multiples of one equation to another without changing the variables. By deciding what multiples to use, you can make it so that the first coefficient is anything you want - here you want it to be 0.
3. Perform additional manipulations to turn the 2nd coefficient of all except the 1st and 2nd rows to 0.
4. Repeat until the last row has only one coefficient - which will be in the last column. You can now determine the value of that variable.
5. Now start working back - since you know the value of the last variable you can eliminate it from each of the rows above it. Repeat, until you end up with a matrix that consists of values on the diagonal and 0's everywhere else.

Here's an example that I hope will help clarify this. Suppose you are given the following 3 linear equations to solve:

3A + 4B - 2C = 5
2A - 2B + C = 1
1A +2B - 3C = -4

The matrix equation that you set up is:

$ \begin{pmatrix} 3 & 4 & -2\\ 2 & -2 & 1\\ 1 & 2 & -3\\ \end{pmatrix} \begin{pmatrix} A\\ B\\ C\\ \end{pmatrix} \ =\ \begin{pmatrix} 5 \\ 1\\ -4\\ \end{pmatrix} $

Now look at the 3rd equation and figure out how you would combine it with one of the equations above it to eliminate the first coefficient. Here you see that if you multiply the 3rd equation by 2, and then subtract it from the 2nd equation, the first coefficient becomes 0. So let's do this, and the matrix equation becomes:

$ \begin{pmatrix} 3 & 4 & -2\\ 2 & -2 & 1\\ 0 & -6 & 7\\ \end{pmatrix} \begin{pmatrix} A\\ B\\ C\\ \end{pmatrix} \ =\ \begin{pmatrix} 5 \\ 1\\ 9\\ \end{pmatrix} $

Do you see how I did that?

Now continue to eliminate the first coefficient from the 2nd equation. I can multiply the 2nd equation by 1.5, and subtract that from the first:

$ \begin{pmatrix} 3 & 4 & -2\\ 0 & 7 & -3.5\\ 0 & -6 & 7\\ \end{pmatrix} \begin{pmatrix} A\\ B\\ C\\ \end{pmatrix} \ =\ \begin{pmatrix} 5 \\ 3.5\\ 9\\ \end{pmatrix} $

Now I've eliminated all the 1st coefficients except for the first row, so I go back to the third equation and try to eliminate the 2nd coefficient (the -6). I can multiply the third equation by 7/6 and add it to the 2nd equation, and get:

$ \begin{pmatrix} 3 & 4 & -2\\ 0 & 7 & -3.5\\ 0 & 0 & 49/6 -3.5\\ \end{pmatrix} \begin{pmatrix} A\\ B\\ C\\ \end{pmatrix} \ =\ \begin{pmatrix} 5 \\ 3.5\\ 9*7/6+3.5\\ \end{pmatrix} $

At this point I recommend multiplying the last row by 6, in order to get rid of these messy fractions:

$ \begin{pmatrix} 3 & 4 & -2\\ 0 & 7 & -3.5\\ 0 & 0 & 28\\ \end{pmatrix} \begin{pmatrix} A\\ B\\ C\\ \end{pmatrix} \ =\ \begin{pmatrix} 5 \\ 3.5\\ 84\\ \end{pmatrix} $

Now you can divide the last equation by 28, to get the value of the 3rd variable:

$ \begin{pmatrix} 3 & 4 & -2\\ 0 & 7 & -3.5\\ 0 & 0 & 1\\ \end{pmatrix} \begin{pmatrix} A\\ B\\ C\\ \end{pmatrix} \ =\ \begin{pmatrix} 5 \\ 3.5\\ 3\\ \end{pmatrix} $

So we know that C is equal to 3.

Next we start working back up the equations, eliminating the 3rd coefficient in the first two equations. I can replace the 1st equation by adding it to 2 times the third, and I can replace the 2nd equation by adding 3.5 times the third to it:

$ \begin{pmatrix} 3 & 4 & 0\\ 0 & 7 & 0\\ 0 & 0 & 1\\ \end{pmatrix} \begin{pmatrix} A\\ B\\ C\\ \end{pmatrix} \ =\ \begin{pmatrix} 11 \\ 14\\ 3\\ \end{pmatrix} $

Divide the 2nd equation by 7:

$ \begin{pmatrix} 3 & 4 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1\\ \end{pmatrix} \begin{pmatrix} A\\ B\\ C\\ \end{pmatrix} \ =\ \begin{pmatrix} 11 \\ 2\\ 3\\ \end{pmatrix} $

Now to eliminate the 2nd coefficient in the first row: replace the first row by subtracting 4 times the 2nd row from it:

$ \begin{pmatrix} 3 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1\\ \end{pmatrix} \begin{pmatrix} A\\ B\\ C\\ \end{pmatrix} \ =\ \begin{pmatrix} 3 \\ 2\\ 3\\ \end{pmatrix} $

And finally, divide through the first row by 3:

$ \begin{pmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1\\ \end{pmatrix} \begin{pmatrix} A\\ B\\ C\\ \end{pmatrix} \ =\ \begin{pmatrix} 1 \\ 2\\ 3\\ \end{pmatrix} $

We're done - from this equation you see that the values of A, B and C are 1, 2, and 3, respectively.

I hope this little example helped - post back if it's still confusing. I suggest practicing by making up your own simple set of equations like I did here and working it through.