---

title: Systems: Gaussian Elimination

Gaussian elimination

Theorem 2.18 is a useful insight, but it lacks an important feature: it does not directly instruct us how to simplify any given linear system. (In Example 2.19, we did end up with a particularly simple linear system, but we did not have any a priori guarantee for this to happen. If we had chosen some “stupid” elementary operations instead, we would not have simplified the system.) Gaussian elimination is an algorithmic process that does just that: it is a simple procedure that is guaranteed to yield the simplest possible equivalent form of any given linear system.

In view of the correspondence between linear systems and matrices, we will first phrase this process in terms of matrices, and then translate it back to the problem of solving linear systems.

Among the myriad of all possible matrices, the following matrices are the “nice guys”.

Definition 2.27 (Related exercises: Exercise 3.7, Exercise 3.15, Exercise 3.6, Exercise 3.26, Exercise 2.21, Exercise 2.20, Exercise 2.3, Exercise 2.15, Exercise 2.14, Exercise 2.4, Exercise 2.23, Exercise 2.9, Exercise 2.8, Exercise 2.13, Exercise 2.7, Exercise 2.5, Exercise 2.11, Exercise 3.23)

A matrix is in row-echelon form (or is called a row-echelon matrix) if the following conditions are satisfied:

1. If there are any zero rows (i.e., consisting only of zeros), then these are at the bottom of the matrix.

2. In a non-zero row, the first non-zero (starting from the left) is a 1. (It is called the leading 1.)

3. Each leading 1 is to the right of all the leading 1’s in the rows above it.

If, in addition to the above conditions, each leading 1 is the only non-zero entry in its column, then the matrix is in reduced row-echelon form.

Maybe saying more than a thousand words is this picture of a row-echelon form. Here, the asterisks indicate an arbitrary number. If, in addition, all the underlined asterisks are zero, then the matrix is a reduced row-echelon matrix.

\[ \left ( \begin{array}{ccccccc} 0 & 1 & * & \underline * & \underline * & * & \underline * \\ 0 & 0 & 0 & 1 & \underline * & * & \underline * \\ 0 & 0 & 0 & 0 & 1 & * & \underline * \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{array} \right ). \]

In view of the correspondence between linear systems and matrices, we transport the language of elementary operations (Definition 2.17) to matrices as follows.

Definition 2.28 (Related exercises: Exercise 3.7, Exercise 4.4, Exercise 4.7, Exercise 2.24, Exercise 4.47, Exercise 3.28, Exercise 3.6, Exercise 2.22, Exercise 2.9)

The following operations on a given matrix \(A\) are called elementary row operations:

1. interchange any two rows,

2. multiply any row by a non-zero (!) number,

3. add a multiple of any row to a different (!) row.

Method 2.29 (Related exercises: Exercise 3.7, Exercise 4.4, Exercise 4.47, Exercise 3.6, Exercise 3.26, Exercise 2.12, Exercise 2.22, Exercise 2.21, Exercise 2.20, Exercise 2.15, Exercise 2.14, Exercise 2.4, Exercise 2.23, Exercise 2.8, Exercise 2.13, Exercise 2.11, Exercise 3.29, Exercise 3.23)

(Gaussian algorithm or Gaussian eliminiation) Every matrix can be brought to reduced row-echelon form by a sequence of elementary row operations. This can be achieved using the following algorithmic process:

1. If the matrix consists only of zeros, stop: then the matrix is in reduced row-echelon form.

2. Otherwise, find the first column from the left having a non-zero entry. Call this entry \(a\). Interchange this row (elementary operation 1.) so that it is in the top position.

3. Multiply the new top row by \(\frac 1 a\) (elementary operation 2.; note this is possible since \(a \ne 0\), see also Remark 2.5). Thus the first row has a leading 1.

4. By adding appropriate multiples of the first row to the remaining rows (elementary operation 3.), ensure that the entry between the leading 1 are all zero.

From this point on, the first row is not touched anymore, and the four steps above are applied to the matrix consisting of the remaining rows.

This produces a (possibly not reduced) row-echelon form. It can be finally brought into reduced row-echelon form by adding appropriate multiples of rows with leading 1’s to the rows above them (elementary operation 3.), beginning at the bottom.

Example 2.30

We apply the Gaussian algorithm to the matrix

\[ \left ( \begin{array}{cccc} 1 & 2 & 5 & 7 \\ 2 & 1 & 4 & 2 \\ 5 & 4 & 13 & 11 \end{array} \right ). \]

The first three steps don’t change the matrix (since the top-left entry is already 1). Step (4): add \(-2\) times the first row to the second row; and add \(-5\) times the first row to the third, which gives

\[ \left ( \begin{array}{cccc} 1 & 2 & 5 & 7 \\ 0 & \underline{-3} & -6 & -12 \\ 0 & -6 & -12 & -24 \end{array} \right ) \]

The remaining steps only affect the second and third row. Step (2) picks the second row, and \(a = -3\) (underlined). It is already in the top position (the first row being discarded for the remainder of the algorithm), so Step (2) does not change the matrix. Step (3) gives the matrix

\[ \left ( \begin{array}{cccc} 1 & 2 & 5 & 7 \\ 0 & 1 & 2 & 4 \\ 0 & -6 & -12 & -24 \end{array} \right ) \]

Step (4) adds \(-6\) times the second row to the third, which gives

\[ \left ( \begin{array}{cccc} 1 & 2 & 5 & 7 \\ 0 & 1 & 2 & 4 \\ 0 & 0 & 0 & 0 \end{array} \right ). \]

At this point also the second row is discarded, which leaves only the last row, which consists of zeros. By Step (1), the algorithm stops at this point.

This matrix is in row-echelon form, but not yet reduced. To reduce it, add \(-2\) times the second row to the first, which gives

\[ \left ( \begin{array}{cccc} 1 & 0 & 1 & -1 \\ 0 & 1 & 2 & 4 \\ 0 & 0 & 0 & 0 \end{array} \right ) \]

When applied to matrices associated to linear systems, Gaussian eliminiation becomes very useful for solving linear systems:

Method 2.31 (Related exercises: Exercise 3.12, Exercise 3.22, Exercise 7.4, Exercise 7.26, Exercise 3.17, Exercise 4.9, Exercise 4.16, Exercise 4.3, Exercise 4.4, Exercise 2.24, Exercise 4.9, Exercise 4.46, Exercise 4.47, Exercise 3.14, Exercise 3.28, Exercise 2.12, Exercise 2.22, Exercise 2.21, Exercise 2.20, Exercise 2.3, Exercise 2.15, Exercise 2.14, Exercise 2.4, Exercise 2.23, Exercise 2.9, Exercise 2.8, Exercise 2.13, Exercise 2.7, Exercise 2.5, Exercise 2.11)

1. Form the augmented matrix corresponding to the given linear system.

2. Perform Gaussian elimination to that matrix (Method 2.29), giving a reduced row-echelon matrix.

3. If a row of the form

\[ 0 \ 0 \ \dots \ 0 \ 1 \]

occurs, the system has no solutions.

1. Otherwise, we call the variables corresponding to the columns not containing a leading 1 free variables. The values of these variables can be chosen to be arbitrary real numbers. The variables that correspond to columns that do contain a leading 1 are uniquely specified by these free variables. Their values can be determined by solving the equations corresponding to the row-echelon matrix for the leading variables.

Example 2.32

Consider the system

\[ \begin{align*} x + 2y + 5 z & = 7 \\ 2x + y + 4 z & = 2 \\ 5 x + 4 y + 13 z & = 11. \end{align*} \]

The augmented matrix associated to this is the one in Example 2.30. Gaussian algorithm brings it into the reduced row-echelon form

\[ \left ( \begin{array}{cccc} 1 & 0 & 1 & -1 \\ 0 & 1 & 2 & 4 \\ 0 & 0 & 0 & 0 \end{array} \right ). \]

This matrix corresponds to the linear system

\[ \begin{align*} x + z & = -1 \\ y + 2z & = 4 \\ 0 & = 0. \end{align*} \]

According to Theorem 2.18, this linear system has the same solution set as the original one.

The leading variables are \(x\) and \(y\), so that \(z\) is a free variable. Solving the second equation for \(y\) then gives

\[ y = 4-2z, \]

and similarly

\[ x = -1-z. \]

We obtain that the solution set to the original linear system consists of triples of the form

\[ (x = -1-z, y = 4-2z, z), \]

in which \(z\) is an arbitrary number (and \(x\) and \(y\) are determined by \(z\) as indicated).