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

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

Linear Algebra 101: Gaussian Elimination (1)

The first topic in linear algebra as it is generally taught is Gaussian elimination on linear systems. This is a simple algorithm which allows you to solve systems of linear equations. Before we can solve them, though, we should know what a system of linear equations actually is.

Conceptually quite simple, a system of linear equations is any collection of linear equations involving the same variables. A linear equation is any equation of the form

a₁x₁ + a₂x₂ + a₃x₃ ... + a_nx_n = b

Where a is a set of coefficients (such as 2, 7.5, 1/3, π), x is a set of variables and b is the solution. Thus, if

2x + 2y = 2

is a linear equation, a linear system might be

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

There are a few points to note about these systems:

1. You may have more equations than variables.
2. You may have more variables than equations.
3. Not every variable need appear in every equation.
4. A linear system may have one solution, no solutions, or an infinite number of solutions.

In the next post, we'll look at the Gaussian elimination algorithm itself and use it to solve this linear system.