Search for probability and statistics terms on Statlect
StatLect
Index > Matrix algebra

Gaussian elimination

by , PhD

Gaussian elimination is an algorithm that allows us to transform a system of linear equations into an equivalent system (i.e., a system having the same solutions as the original one) in row echelon form. Elementary row operations are performed on the system until the system is in row echelon form. Then, it can be easily solved by back-substitution.

Table of Contents

Preliminaries

Before reading this lecture, you should be familiar with:

Aim

We are given a linear system of K equations in $L$ unknowns [eq1]that can be represented in matrix form as[eq2]where A is the $K imes L$ matrix of coefficients, $b$ is the Kx1 vector of constants and x is the $L imes 1$ vector of unknowns.

The aim is to reduce it to an equivalent system in row echelon form, that is, an equivalent system whose coefficient matrix A has the following characteristics:

The aim is achieved by repeatedly performing two elementary row operations:

  1. interchanging the order of two equations;

  2. adding a multiple of one equation to another equation.

Note: for the sake of simplicity, we are going to denote the coefficient matrix of the system by A both before and after performing an elementary row operation, even if strictly speaking they are two different matrices.

Steps of the algorithm

We first present the steps of the Gaussian elimination algorithm in a rigorous manner, by listing them as if we were writing a computer program. We then explain them carefully.

The steps are as follows:

  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. For $i=k+1,ldots ,K$, add $-A_{il}/A_{kl}$ times the k-th equation to the i-th equation.

  8. If $k<K-1$, return to step 2. Else stop the algorithm.

In order to better understand the algorithm, note the following things:

Examples

We now present several examples to show how Gaussian elimination works in practice.

Throughout this section, we will use augmented matrices to parsimoniously represent systems of linear equations. If you are not familiar with the concept of augmented matrix, you should revise it before reading the examples.

Example Consider the system of three equations in three unknowns[eq3]The augmented matrix of the system is[eq4]We start from row $k=1$ and column $l=1$. We have [eq5], so we do not need to interchange rows. We add [eq6]times the first row to the second, and obtain[eq7]We add[eq8]times the first row to the third, and get[eq9]We now go to row $k=2$ and column $l=2$. We have $A_{kl}=A_{22}=0$. However, [eq10], so we interchange the second row with the third:[eq11]The only entry below $A_{22}$ is already zero, so we do not need to perform row additions. We are done with the penultimate row, so the Gaussian elimination algorithm stops. The matrix of coefficients (to the left of the vertical line) is in row echelon form because all of its rows have a pivot. The pivots are $A_{11}$, $A_{22}$ and $A_{33}$.

Example Consider the system of three equations in four unknowns[eq12]The augmented matrix of the system is[eq13]We start from row $k=1$ and column $l=1$. We have [eq5], so we do not need to interchange rows. We add [eq15]times the first row to the second, and obtain[eq16]All of the entries below $A_{11}$ are zero, so we are done with the first column. We now go to row $k=2$ and column $l=2$. We have that $A_{kl}$ and all of the entries below it are zero. Therefore, we cannot perform any row operation. Thus, the second column is a non-basic column and we need to go to the next column, without changing row. So, $k=2$ and $l=3$. We have that [eq17], so there is no need to interchange rows. We add [eq18]times the second row to the third, and obtain[eq19]We are done with the penultimate row, so the Gaussian elimination algorithm stops. The matrix of coefficients is in row echelon form because all of its rows have a pivot. The pivots are $A_{11}$, $A_{23}$ and $A_{3,4}$.

Gaussian elimination with partial pivoting

Note that in step 6 of the Gaussian elimination algorithm we have not specified a criterion for choosing which row to interchange with the current row (in case there is more than one possibility).

When we implement the Gaussian elimination algorithm on a computer, the criterion we usually follow is to choose the interchange that moves the largest element (in absolute value) to the pivotal position. This is done to improve the numerical stability of the algorithm: since in step 7 we compute the ratio $-A_{il}/A_{kl}$, we want $A_{kl}$ to be as far from zero as possible (to avoid division by zero problems caused by numerical round-off); as a consequence, we choose the row interchange so as to make the absolute value of $A_{kl}$ as large as possible.

This method of choosing the pivot is called partial pivoting.

Gaussian elimination with complete pivoting

Another version of the algorithm is the so-called Gaussian elimination with complete pivoting, in which the absolute value of the pivot is maximized not only by exchanging rows, but also by exchanging columns (i.e., by changing the order of the unknowns). In step 6 of this algorithm we search all the quadrant of the coefficient matrix below and to the right of the pivotal position for the element that has the largest absolute value and then we move that element to the pivotal position with a row and a column interchange.

Solved exercises

Below you can find some exercises with explained solutions.

Exercise 1

Use the Gaussian elimination algorithm with partial pivoting to reduce the system[eq20]to row echelon form.

Solution

We start from row $k=1$ and column $l=1$. The largest element in the first column is $A_{4,1}=-4$. So, we interchange the fourth row with the first:[eq21]We add [eq22]times the first row to the fourth row:[eq23]We move to row $k=2$ and column $k=2$. The largest element in the second column is $A_{3,2}=2$. So, we interchange the third row with the second:[eq24]We add [eq25]times the second row to the third row:[eq26]We add [eq27]times the second row to the fourth row:[eq28]The system is now in row echelon form: its last row is zero; all the rows above it are non-zero and have a pivot.

How to cite

Please cite as:

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

The books

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

Featured pages
Explore
Main sections
About
Glossary entries
Share
  • To enhance your privacy,
  • we removed the social buttons,
  • but don't forget to share.