Gaussian Elimination and Gauss Jordan Elimination: An Introduction

We introduce Gaussian elimination and Gauss Jordan Elimination, more commonly known as the elimination method, and learn to use these methods to solve linear equations with several unknown variables. We also introduce the row echelon form of a matrix and discuss the difference between Gaussian elimination and Gauss Jordan elimination.

Gaussian Elimination Method

Gaussian Elimination is a method for solving systems of linear equations with several unknown variables. It works by bringing the matrix representing the equations into row echelon form and resolving the unknown variables by back-substitution.

Let’s say you have the following two equations and your goal is to find x and y. To resolve this system, you need to get to a point where one equation only has one unknown variable.

x + 3y = 10 (Eq1)

x – 2y = -5  (Eq2)

5y = 15 (Eq1 – Eq2) You can eliminate x by subtracting  Eq2 from Eq1

y = 3      Now you can simply divide by 5 to obtain y

x + 3 x 3 = 10      Plugging y into Eq1 gives you x

x = 1 

You can represent this system of equations as a matrix vector multiplication where x and y become your vector b and the coefficients are represented in a matrix A.

Ab = c

  \begin{bmatrix}
    1 & 3 \\
    1 & -2 \\
  \end{bmatrix}


  \begin{bmatrix}
    x \\
    y \\
  \end{bmatrix}

=

  \begin{bmatrix}
    10 \\
    -5 \\
  \end{bmatrix}

Row Echelon Form

The row echelon form is a diagonal matrix where all entries below a leading coefficient are zero. Some textbooks also state that the leading coefficient must equal one.

The following matrix is in row echelon form with the leading coefficients in each row along the main diagonal and the everything below them equal to zero.

  \begin{bmatrix}
    1 & a_{12} & a_{13} \\
    0 & 3 & a_{23} \\
    0 & 0 & 2 \\
  \end{bmatrix}

The goal of Gaussian elimination is to bring the given set of equations into the following matrix format. The leading coefficients given on the main diagonal are illustrative and will be different in every example

   \begin{bmatrix}
    1 & a_{12} & a_{13} \\
    0 & 3 & a_{23} \\
    0 & 0 & 2 \\
  \end{bmatrix}
  \begin{bmatrix}
    x  \\
    y \\
    z  \\
  \end{bmatrix}
= 
  \begin{bmatrix}
    b_1  \\
    b_2 \\
    b_3  \\
  \end{bmatrix}

Example of Gaussian Elimination with the Row Echelon Form

To solve our linear system of equations in matrix format, we can apply the Gaussian elimination method according to the same principles. Let’s use an example with a 3×3 matrix A, and a vector b  

Ab = c

  \begin{bmatrix}
    1 & 3 & 1\\
    1 & -2 & -1 \\
    2 & 1 & 2 \\
  \end{bmatrix}


  \begin{bmatrix}
    x \\
    y \\
    z \\
  \end{bmatrix}
=

  \begin{bmatrix}
    10 \\
    -6 \\
    10 \\
  \end{bmatrix}

  \begin{bmatrix}
    1 & 3 & 1\\
    0 & -5 & -2 \\
    0 & -5 & 0 \\
  \end{bmatrix}


  \begin{bmatrix}
    x \\
    y \\
    z \\
  \end{bmatrix}
=

  \begin{bmatrix}
    10 \\
    -16 \\
    -10 \\
  \end{bmatrix}

perform Row2 + Row3   &    swap Row2 with Row3

  \begin{bmatrix}
    1 & 3 & 1\\
    0 & -5 & 0 \\
    0 & 0 & -2 \\
  \end{bmatrix}


  \begin{bmatrix}
    x \\
    y \\
    z \\
  \end{bmatrix}
=

  \begin{bmatrix}
    10 \\
    -10 \\
    -6 \\
  \end{bmatrix}

perform Row3 / -2.  &.  Row2 / -5

  \begin{bmatrix}
    1 & 3 & 1\\
    0 & 1 & 0 \\
    0 & 0 & 1 \\
  \end{bmatrix}


  \begin{bmatrix}
    x \\
    y \\
    z \\
  \end{bmatrix}
=
  \begin{bmatrix}
    10 \\
    2 \\
    3 \\
  \end{bmatrix}

Now in our matrix A we have attained a so called row echelon form. 

From the row echelon form, it is easy to figure out that z = 3 and y = 2. By Back Substituting z and y into the first equation obtained by multiplying the first row of the matrix with our vector, we get x.

1x + 3y + 1z = 10  \,\,	 -> \,\,	1x + 6 + 3 = 10	\,\, ->   \,\,	x = 1

Augmented Matrix

As you may have realised, during Gaussian elimination the vector b was not relevant. Therefore we can represent our linear system of equations in an augmented matrix consisting only of the coefficients. Our previous example would look like this:

\left[
  \begin{matrix}
    1 & 3 & 1\\
    1 & -2 & -1 \\
    2 & 1 & 2 \\
  \end{matrix}
  \left|
    \,
    \begin{matrix}
      10  \\
      -6  \\
      10  \\
    \end{matrix}
  \right.
\right]

The elimination process is easier since you don’t have to care about x, y, and z. You only need to turn this augmented matrix into row echelon form, and then you can bring your variables back in.

Gaussian Elimination vs Gauss Jordan Elimination

Gauss Jordan Elimination, more commonly known as the elimination method, is a process to solve systems of linear equations with several unknown variables. It works by bringing the equations that contain the unknown variables into reduced row echelon form. It is an extension of Gaussian Elimination which brings the equations into row-echelon form.

Reduced Row Echelon Form

A matrix in reduced row echelon form exhibits the following properties:

• The matrix is in row-echelon form
• The leading coefficient in every non-zero row equals 1
• Every column that contains a leading 1 has zero entries everywhere else

  \begin{bmatrix}
    1 & 0 & a_{13} \\
    0 & 1 & a_{23} \\
    0 & 0 & 0 \\
  \end{bmatrix}

The goal of Gauss Jordan Elimination is to bring a system of equations into the following format:

  \begin{bmatrix}
    1 & 0 & a_{13} \\
    0 & 1 & a_{23} \\
    0 & 0 & 0 \\
  \end{bmatrix}
  \begin{bmatrix}
    x  \\
    y \\
    z  \\
  \end{bmatrix}
= 
  \begin{bmatrix}
    b_1  \\
    b_2 \\
    b_3  \\
  \end{bmatrix}

The procedure is similar to Gaussian elimination.

This post is part of a series on linear algebra for machine learning. To read other posts in this series, go to the index.