Linear Algebra 101: Gaussian Elimination (2)

Last time we introduced the concept of linear systems and set up a problem.  How do we solve a system such as the following?

 2x + 2y =  2
 2x - 2y = -2

The answer is Gaussian elimination.  This is a relatively straightforward algorithm in which you are permitted three operations on the system:

1. multiplying one row with a scalar variable (i.e., single, real number),
2. adding two rows together, or
3. exchanging the position of two rows. 

The overall goal is to reduce the system to Echelon form.  This is the form where each variable (in this case, x, and y) "leads" a row.  In other words, the first row will contain at least the variable x and a coefficient; the second row will contain no instances of x and y with a coefficient.  As long as we strictly stick to these steps, we will be able to reduce the system to echelon form (assuming the system supports such a configuration - more on this in the future).

Luckily we have a very simple first example.

 2x + 2y =  2
 2x - 2y = -2

All we need to do to solve this system is remove 2x from the second row via linear operations, and then substitute the value of y back into the first equation to find x.  Here, we use the first and second permitted gaussian operations together: we will add the row 1 (p1), multiplied by the scalar variable -1, to row 2 (p2):

        2x +    2y =  2                 (p1)
=>   -1*2x + -1*2y = -1*2             -1(p1)
=>     -2x -    2y = -2               -1(p1)
=>2x - 2x - 2y -2y = -2 - 2           -1(p1)+p2
=>             -4y = -4

Therefore, if we divide each side by -4, we find that y = 1:

 2x + 2y =  2
       y =  1

  If we substitute this back into the first equation, we discover that x must equal 0:

2x + (2*1) = 2
2x = (2 - 2) = 0

I'll finish this entry with a more complex problem which we'll solve next time, when we also the eventuality that a problem has no solutions.

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