Gauss and Gauss-Jordan Elimination

There are two methods of solving systems of linear equations are:

• Gauss Elimination
• Gauss-Jordan Elimination

They are both based on the observation that systems of equations are equivalent if they have the same solution set and performing simple operations on the rows of a matrix, known as the Elementary Row Operations or (EROs).

There are 3 EROs:

1. Scaling: Multiplying a row by a scalar (meaning, multiplying every element in the row by the same scalar). This is written sr_i⟶r_i, which indicates that row i is modified by multiplying it by a scalar s.
2. Interchange: Interchanging the locations of two rows. This is written as r_i⟵⟶r_jwhich indicates that rows i and j are interchanged.
3. Replacement: Replacing all of the elements in one row with that row plus or minus a scalar multiplied by another row. This is written as r_i± sr_j⟶r_i.

Example

An example of interchanging rows would be r₁⟵⟶r₃.

Now, starting with this matrix, an example of scaling would be: 2r₂⟶r₂,which describes all items in row 2 are multiplied by 2.

Now, starting with this matrix, an example of a replacement would be: r₃-2r₂⟶r₃.Element-by-element, row 3, is replaced by the element in row 3 minus 2 * the corresponding items in row 2. These yields:

Both the Gauss and Gauss-Jordan methods begin with the matrix form Ax = b of a system of equations, and then augment the coefficient matrix A with the column vector b.

Gauss Elimination

The Gauss Elimination method is a method for solving the matrix equation Ax=b for x.

The process is:

1. It starts by augmenting the matrix A with the column vector b.
2. It executes EROs to convert this augmented matrix into an upper triangular form.
3. It uses back-substitution to solve for the unknowns in x.

Example

Use a 2 x 2 system, the augmented matrix would be:

Then, EROs are used to get the augmented matrix into an upper triangular form:

So, it is simply to replace a₂₁ with 0. Here, the primes indicate that the values have been change.

Putting this back into the equation form yield

Executing this matrix multiplication for each row results in:

So, the solution is:

Similarly, for the 3x3 system, the augmented matrix is reduced to an upper triangular form:

This will be done orderly by first getting a₀in the a₂₁ position, then a₃₁, and finally a₃₂.

Then, the solution will be:

Consider the following 2x2 system of equations:

x₁+2x₂=2
2x₁+2x₂=6

As the matrix equation Ax = b, this is:

The first process is to augment the coefficient matrix A with b to get an augmented matrix [A| b]:

For the forward elimination, we need to get a₀ in the a₂₁ position. To accomplish this, we can change the second line in the matrix by subtracting from it 2 * the first row.

The way we would write this ERO is:

Now, putting it back in the matrix equation form:

says that the second equation is now -2x₂= 2 so x₂ = -1. Plugging into the first equation:

x₁+2(-1)=2
x₁=4.

This is called a back-substitution.

Gauss-Jordan Elimination

The Gauss-Jordan Elimination method start the similar technique that the Gauss Elimination method does, but then the instead of back-substitution, the elimination continues.

The Gauss-Jordan method consists of:

• Creating the augmented matrix [A b]
• Forward elimination by implementing EROs to get an upper triangular form
• Back removal to a diagonal process which yields the solution

Example

Use 2x 2 system, the augmented matrix would be:

Use 3x 3 system, the augmented matrix would be:

Note: The resulting diagonal form does not include the right-most column.

For example, for the 2x2 system, forward elimination yielded the matrix:

Now, to continue with back elimination, we want a₀in the a₁₂position.

So, the solution is

Here is an example of a 3x3 system:

In matrix form, the augmented matrix [A|b] is

Forward substitution (done orderly by first getting a₀in the a₂₁position, then a₃₁ , and finally a₃₂):

For the Gauss technique, this is followed by back-substitution:

For the Gauss-Jordan technique, this is instead followed by back elimination:

Here's an example of operating these substitutions using MATLAB:

>> a = [1 3 0; 2 1 3; 4 2 3]
a =
       1     3     0
       2     1     3
       4     2     3 >> b = [1 6 3]'
b=
       1
       6
       3
>> ab = [a b]
ab = 
          1    3    0   1 
          2    1    3   6
          4    2    3   3
>> ab(2, :) = ab(2,:) ? 2*ab(1,:)
ab=
         1    3    0    1
         0    -5   3    4
        4     2    3    3
>> ab(3,:) = ab(3,:) ? 4 * ab(1,:)
ab =

           1  3   0   1 
          0 ?5   3   4 
          0 ?10   3 ?1
>> ab(3,:) = ab(3,:) ? 2 * ab(2,:)
ab=
	1    3    0   1
            0    -5   3    4
	0    0    -3  -9
>> ab(2,:) = ab(2,:) + ab(3,:)
ab=
	1   3   0   1 
            0 ?5   0 ?5 
            0   0  ?3 ?9
>> ab(1,:) = ab(1,:) + 3/5*ab(2,:) ab=
	1   0   0  ?2 
            0 ?5   0  ?5 
            0   0  ?3 ?9