Search for probability and statistics terms on Statlect
StatLect

Gauss Jordan elimination algorithm

by , PhD

Gauss Jordan elimination is an algorithm that allows us to transform a linear system into an equivalent system in reduced row echelon form.

The main difference with respect to Gaussian elimination is illustrated by the following diagram.

A diagram illustrating the differences between the Gaussian and Gauss Jordan elimination algorithms

In this lecture we are going to assume that the reader is already familiar with Gaussian elimination and aware of the differences between row echelon form and reduced row echelon form.

Table of Contents

Overview

The aim of the Gauss Jordan elimination algorithm is to transform a linear system of K equations in $L$ unknowns [eq1]into an equivalent system (i.e., a system having the same solutions) in reduced row echelon form.

The system can be written as[eq2]where A is the $K	imes L$ coefficient matrix, x is the $L	imes 1$ vector of unknowns and $b$ is a Kx1 constant vector.

Remember that a system is in reduced row echelon form if its coefficient matrix A has the following properties:

Gauss Jordan elimination consists in a sequence of elementary row operations:

  1. interchanging the order of the equations, so as to make sure that the zero rows are at the bottom of the matrix;

  2. multiplying (or dividing) the equations by non-zero constants, so as to make the pivots equal to 1;

  3. adding multiples of some equations to other equations, so as to annihilate the entries above and below the pivots.

Steps of the algorithm

The Gauss Jordan algorithm is very similar to Gaussian elimination. Therefore, we are not going to explain its steps in detail, but we are only going to comment on the differences with respect to Gaussian elimination. Please refer to the lecture on Gaussian elimination for detailed explanations.

Before laying out the algorithm, we warn the reader that the coefficient matrix of the system will be denoted by A both before and after performing an elementary row operation, even if the matrix resulting from the operation is in principle a different matrix.

The steps are listed below:

  1. Start from $k=0$ and $l=0$.

  2. Increment k by one unit.

  3. Increment $l$ by one unit.

  4. Stop the algorithm if $l>L$. Else proceed to the next step.

  5. If $A_{il}=0$ for $i=k,ldots ,K$, return to step 3. Else proceed to the next step.

  6. Interchange the k-th equation with any equation i (with $i>k$) such that $A_{il}
eq 0$ (if $i=k$ there is no need to perform an interchange).

  7. Divide the k-th equation by $A_{kl}$.

  8. For $i=1,ldots ,k-1$ and $i=k+1,ldots ,K$, subtract the k-th equation multiplied by $A_{il}$ from the i-th equation.

  9. If $k<K$, return to step 2. Else stop the algorithm.

The differences with respect to Gaussian elimination are the following:

Examples

We present below an example of Gauss Jordan elimination.

In order to simplify the notation, we are going to use augmented matrices to represent linear systems.

Example Consider the system of three equations in four unknowns represented by the augmented matrix[eq3]We start from row $k=1$ and column $l=1$. Since [eq4], we do not perform any interchange of rows. We divide the first row by $A_{11}=-1$ and obtain[eq5]In order to annihilate the entries below the pivot $A_{11}$, we subtract the first row multiplied by $3$ from the second and multiplied by 1 from the third:[eq6] We move to row $k=2$ and column $l=2$. Since $A_{kl}=A_{22}=0$, but $A_{32}
eq 0$, we interchange the second row with the third:[eq7]We divide the second row by $A_{22}=2$:[eq8]We add the second row multiplied by $2$ to the first:[eq9] We move to row $k=3$ and column $l=3$. We divide the third row by the value of its pivot $A_{33}=18$:[eq10] We add $-6$ times the third row to the second and the third:[eq11]The matrix is now in reduced row echelon form.

Gauss Jordan elimination with pivoting

As in Gaussian elimination, in order to improve the numerical stability of the algorithm, we usually perform partial pivoting in step 6, that is, we always choose the row interchange that moves the largest element (in absolute value) to the pivotal position. If we also exchange columns in order to maximize the absolute value of the pivot, then we are doing complete pivoting. See the lecture on Gaussian elimination for more details on partial and complete pivoting.

Solved exercises

Below you can find some exercises with explained solutions.

Exercise 1

Transform the system[eq12]into an equivalent system in reduced row echelon form. Use the Gauss Jordan elimination algorithm with partial pivoting.

Solution

The entry $A_{11}$ is non-zero and it is already the largest entry in the first column. Therefore, it is used as pivot. Divide the first row by $A_{11}=2$:[eq13]Annihilate the entries below the pivot $A_{11}$:[eq14]Interchange the second row with the third, so that the largest element moves to the pivotal position:[eq15]Divide the second row by $A_{22}=5/2$:[eq16]Annihilate the entries above and below the pivot $A_{22}$:[eq17]Interchange the third row with the fourth:[eq18]Divide the third row by $A_{33}=7$:[eq19]All the elements above and below the pivot $A_{33}$ are already zero, so we can move to the last row. There are no row interchanges to consider because there are no rows below the last. Furthermore, $A_{44}$ is a pivot and it is already equal to 1. Therefore, we only need to annihilate the elements above it:[eq20]The system is now in reduced row echelon form.

How to cite

Please cite as:

Taboga, Marco (2021). "Gauss Jordan elimination algorithm", Lectures on matrix algebra. https://www.statlect.com/matrix-algebra/Gauss-Jordan-elimination.

The books

Most of the learning materials found on this website are now available in a traditional textbook format.