Linear Algebra 101: Gaussian Elimination (3)

First off, let's solve the question from the previous post:

 a     - c = 0
3a + b     = 1
-a + b + c = 4

First off, let's make b the leading variable on the second row by adding it to -3 times the first row:

   -3a     + 3c = 0  
+
    3a + b      = 1
=
         b + 3c = 1

We can now use the second row and first row to make c the only variable on the third row.  First, multiply the (new) second row by -1 and add it to the third row to eliminate the bs:

       -b - 3c = -1 +
   -a + b +  c =  4
=
   -a     - 2c =  3

This gives us the system

 a    -  c = 0
   -b - 3c = 1
-a    - 2c = 3

The last step is now obvious: Add the first row to the third to put the system in echelon form.

   a    -  c = 0
+
  -a    - 2c = 3
=
         -3c = 3

Obviously therefore c is -1; if we substitute back into the second row we see b must be 2, and if we substitute back into the first row we see a must also be -1.

This time we were lucky; the problem had a neat solution.  But how can we tell if a problem actually has no solution?  Consider the following system:

a  +  b = 1
2a + 2b = 1

We can see just by inspecting it that no solution will make any sense.  If the sum of a and b is 1, then the sum of double a and b must be 2.  But in more complex systems it may not be so clear whether a system is solveable.  What happens when we perform Gaussian Elimination on a system with no solution?  We get a contradictory answer.  Using the previous example, if we multiply the first row by 2, we get the result:

2a + 2b = 2
2a + 2b = 1

We can then subtract the first row from the second and receive the nonsense result of:

2a + 2b =  2
      0 = -1

If you follow Gaussian elimination through to the end on any problem that has no solution, you will eventually end up with the system in a contradictory state such as this.  To confirm this, try performing Gaussian Elimination on this system, which we will solve next time:

 x +     z + w = 4
2x + y     - w = 2
3x + y + z     = 7