1.2: Gaussian Elimination

In the last section, we introduced augmented matrix. In order to construct an augmented matrix from a linear system, we created a coefficient matrix from the coefficients of the variables in the system, as well as a constant matrix from the constants. In this section, we will explore a less cumbersome way to find solutions. A matrix is simply a rectangular array of numbers. The size or dimension of a matrix is defined as \(m\times n\) where \(m\) is the number of rows and \(n\) is the number of columns. If a row consists entirely of zeros, we call that row is a zero row, otherwise we call the row is a non zero row.

Recall how we solved Example [exa:solvingasystemwithelementaryops]. We can do the exact same steps as above, except now in the context of an augmented matrix and using row operations. The augmented matrix of this system is \[\left[ \begin{array}{rrr|r} 1 & 3 & 6 & 25 \\ 2 & 7 & 14 & 58 \\ 0 & 2 & 5 & 19 \end{array} \right]\] Thus the first step in solving the system given by [solvingasystem1] would be to take \(\left( -2\right)\) times the first row of the augmented matrix and add it to the second row, \[\left[ \begin{array}{rrr|r} 1 & 3 & 6 & 25 \\ 0 & 1 & 2 & 8 \\ 0 & 2 & 5 & 19 \end{array} \right]\] Note how this corresponds to [solvingasystem2]. Next take \(\left( -2\right)\) times the second row and add to the third, \[\left[ \begin{array}{rrr|r} 1 & 3 & 6 & 25 \\ 0 & 1 & 2 & 8 \\ 0 & 0 & 1 & 3 \end{array} \right]\] This augmented matrix corresponds to the system \[\begin{array}{c} x+3y+6z=25 \\ y+2z=8 \\ z=3 \end{array}\] which is the same as [solvingasystem3]. By back substitution you obtain the solution \(x=1,y=2,\) and \(z=3.\)

Through a systematic procedure of row operations, we can simplify an augmented matrix and carry it to row-echelon form or reduced row-echelon form, which we define next. These forms are used to find the solutions of the system of equations corresponding to the augmented matrix.

In the following definitions, the term leading entry refers to the first nonzero entry of a row when scanning the row from left to right.

Definition: Row Echelon Form

A matrix is in a row-echelon form if

1. All nonzero rows are above any rows of zeros.
2. The first non zero entry from left in each row is \(1\), called leading \(1\).
3. Each leading \(1 \) is to the right of the leading \(1\) of any row above it.

For example, consider the linear system in Example [exa:solvingasystemwithelementaryops] \[\begin{array}{c} x+3y+6z=25 \\ 2x+7y+14z=58 \\ 2y+5z=19 \end{array}\] This system can be written as an augmented matrix, as follows \[\left[ \begin{array}{rrr|r} 1 & 3 & 6 & 25 \\ 2 & 7 & 14 & 58 \\ 0 & 2 & 5 & 19 \end{array} \right] \]

Notice that it has exactly the same information as the original system. Here it is understood that the first column contains the coefficients from \(x\) in each equation, in order, \(\left[ \begin{array}{r} 1 \\ 2 \\ 0 \end{array} \right] .\) Similarly, we create a column from the coefficients on \(y\) in each equation, \(\left[ \begin{array}{r} 3 \\ 7 \\ 2 \end{array} \right]\) and a column from the coefficients on \(z\) in each equation, \(\left[ \begin{array}{r} 6 \\ 14 \\ 5 \end{array} \right] .\) For a system of more than three variables, we would continue in this way constructing a column for each variable. Similarly, for a system of less than three variables, we simply construct a column for each variable.

Finally, we construct a column from the constants of the equations, \(\left[ \begin{array}{r} 25\\ 58\\ 19 \end{array} \right] .\)

The rows of the augmented matrix correspond to the equations in the system. For example, the top row in the augmented matrix, \(\left[ \begin{array}{rrrrr} 1 & 3 & 6 & | & 25 \end{array} \right]\) corresponds to the equation \[x+3y+6z=25.\]

We also consider another reduced form of the augmented matrix which has one further condition.

Definition \(\PageIndex{4}\): Reduced Row-Echelon Form

An augmented matrix is in reduced row-echelon form if

1. All nonzero rows are above any rows of zeros.
2. Each leading entry of a row is in a column to the right of the leading entries of any rows above it.
3. Each leading entry of a row is equal to \(1\).
4. All entries in a column above and below a leading entry are zero.

Notice that the first three conditions on a reduced row-echelon form matrix are the same as those for row-echelon form.

Hence, every reduced row-echelon form matrix is also in row-echelon form. The converse is not necessarily true; we cannot assume that every matrix in row-echelon form is also in reduced row-echelon form. However, it often happens that the row-echelon form is sufficient to provide information about the solution of a system.

The following examples describe matrices in these various forms. As an exercise, take the time to carefully verify that they are in the specified form.

Example \(\PageIndex{5}\): Not in Row-Echelon Form

The following augmented matrices are not in row-echelon form (and therefore also not in reduced row-echelon form).

\[\left[ \begin{array}{rrr|r} 0 & 0 & 0 & 0 \\ 1 & 2 & 3 & 3 \\ 0 & 1 & 0 & 2 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{array} \right] ,\left[ \begin{array}{rr|r} 1 & 2 & 3 \\ 2 & 4 & -6 \\ 4 & 0 & 7 \end{array} \right] ,\left[ \begin{array}{rrr|r} 0 & 2 & 3 & 3 \\ 1 & 5 & 0 & 2 \\ 7 & 5 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{array} \right]\]

Example \(\PageIndex{6}\): Matrices in Row-Echelon Form

The following augmented matrices are in row-echelon form, but not in reduced row-echelon form. \[\left[ \begin{array}{rrrrr|r} 1 & 0 & 6 & 5 & 8 & 2 \\ 0 & 0 & 1 & 2 & 7 & 3 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{array} \right] ,\left[ \begin{array}{rrr|r} 1 & 3 & 5 & 4 \\ 0 & 1 & 0 & 7 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{array} \right], \left[ \begin{array}{rrr|r} 1 & 0 & 6 & 0 \\ 0 & 1 & 4 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \end{array} \right]\]

Notice that we could apply further row operations to these matrices to carry them to reduced row-echelon form. Take the time to try that on your own. Consider the following matrices, which are in reduced row-echelon form.

Example \(\PageIndex{7}\): Matrices in Reduced Row-Echelon Form

The following augmented matrices are in reduced row-echelon form. \[\left[ \begin{array}{rrrrr|r} 1 & 0 & 0 & 5 & 0 & 0 \\ 0 & 0 & 1 & 2 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{array} \right] ,\left[ \begin{array}{rrr|r} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{array} \right] , \left[ \begin{array}{rrr|r} 1 & 0 & 0 & 4 \\ 0 & 1 & 0 & 3 \\ 0 & 0 & 1 & 2 \end{array} \right]\]

One way in which the row-echelon form of a matrix is useful is in identifying the pivot positions and pivot columns of the matrix.

Definition \(\PageIndex{8}\): Pivot Position and Pivot Column

A pivot position in a matrix is the location of a leading entry in the row-echelon form of a matrix.

A pivot column is a column that contains a pivot position.

For example consider the following.

Example \(\PageIndex{9}\): Pivot Position

Let \[A=\left[ \begin{array}{rrr|r} 1 & 2 & 3 & 4 \\ 3 & 2 & 1 & 6 \\ 4 & 4 & 4 & 10 \end{array} \right]\] Where are the pivot positions and pivot columns of the augmented matrix \(A\)?

Solution

The row-echelon form of this matrix is \[\left[ \begin{array}{rrr|r} 1 & 2 & 3 & 4 \\ 0 & 1 & 2 & \frac{3}{2} \\ 0 & 0 & 0 & 0 \end{array} \right]\]

This is all we need in this example, but note that this matrix is not in reduced row-echelon form.

In order to identify the pivot positions in the original matrix, we look for the leading entries in the row-echelon form of the matrix. Here, the entry in the first row and first column, as well as the entry in the second row and second column are the leading entries. Hence, these locations are the pivot positions. We identify the pivot positions in the original matrix, as in the following: \[\left[ \begin{array}{rrr|r} \fbox{1} & 2 & 3 & 4 \\ 3 & \fbox{2} & 1 & 6 \\ 4 & 4 & 4 & 10 \end{array} \right]\] Thus the pivot columns in the matrix are the first two columns.

The following is an algorithm for carrying a matrix to row-echelon form and reduced row-echelon form. You may wish to use this algorithm to carry the above matrix to row-echelon form or reduced row-echelon form yourself for practice.

Algorithm \(\PageIndex{10}\): Reduced Row-Echelon Form Algorithm

This algorithm provides a method for using row operations to take a matrix to its reduced row-echelon form. We begin with the matrix in its original form.

1. Starting from the left, find the first nonzero column. This is the first pivot column, and the position at the top of this column is the first pivot position. Switch rows if necessary to place a nonzero number in the first pivot position.
2. Use row operations to make the entries below the first pivot position (in the first pivot column) equal to zero.
3. Ignoring the row containing the first pivot position, repeat steps 1 and 2 with the remaining rows. Repeat the process until there are no more rows to modify.
4. Divide each nonzero row by the value of the leading entry, so that the leading entry becomes \(1\). The matrix will then be in row-echelon form.

   The following step will carry the matrix from row-echelon form to reduced row-echelon form.

5. Moving from right to left, use row operations to create zeros in the entries of the pivot columns which are above the pivot positions. The result will be a matrix in reduced row-echelon form.

Most often we will apply this algorithm to an augmented matrix in order to find the solution to a system of linear equations. However, we can use this algorithm to compute the reduced row-echelon form of any matrix which could be useful in other applications.

Consider the following example of Algorithm [algo:rrefalgorithm].

Example \(\PageIndex{11}\) Finding row-echelon form and
reduced row-echelon form of a Matrix

Let \[A = \left[ \begin{array}{rrr} 0 & -5 & -4 \\ 1 & 4 & 3 \\ 5 & 10 & 7 \end{array} \right]\] Find the row-echelon form of \(A\). Then complete the process until \(A\) is in reduced row-echelon form.

Solution

In working through this example, we will use the steps outlined in Algorithm [algo:rrefalgorithm].

1. The first pivot column is the first column of the matrix, as this is the first nonzero column from the left. Hence the first pivot position is the one in the first row and first column. Switch the first two rows to obtain a nonzero entry in the first pivot position, outlined in a box below. \[\left[ \begin{array}{rrr} \fbox{1} & 4 & 3 \\ 0 & -5 & -4 \\ 5 & 10 & 7 \end{array} \right]\]
2. Step two involves creating zeros in the entries below the first pivot position. The first entry of the second row is already a zero. All we need to do is subtract \(5\) times the first row from the third row. The resulting matrix is \[\left[ \begin{array}{rrr} 1 & 4 & 3 \\ 0 & -5 & -4 \\ 0 & 10 & 8 \end{array} \right]\]
3. Now ignore the top row. Apply steps \(1\) and \(2\) to the smaller matrix \[\left[ \begin{array}{rr} -5 & -4\\ 10 & 8 \end{array} \right]\] In this matrix, the first column is a pivot column, and \(-5\) is in the first pivot position. Therefore, we need to create a zero below it. To do this, add \(2\) times the first row (of this matrix) to the second. The resulting matrix is \[\left[ \begin{array}{rr} -5 & -4\\ 0 & 0 \end{array} \right]\] Our original matrix now looks like \[\left[ \begin{array}{rrr} 1 & 4 & 3 \\ 0 & -5 & -4 \\ 0 & 0 & 0 \end{array} \right]\] We can see that there are no more rows to modify.
4. Now, we need to create leading \(1\)s in each row. The first row already has a leading \(1\) so no work is needed here. Divide the second row by \(-5\) to create a leading \(1\). The resulting matrix is \[\left[ \begin{array}{rrr} 1 & 4 & 3 \\ 0 & 1 & \frac{4}{5} \\ 0 & 0 & 0 \end{array} \right]\] This matrix is now in row-echelon form.
5. Now create zeros in the entries above pivot positions in each column, in order to carry this matrix all the way to reduced row-echelon form. Notice that there is no pivot position in the third column so we do not need to create any zeros in this column! The column in which we need to create zeros is the second. To do so, subtract \(4\) times the second row from the first row. The resulting matrix is \[\left[ \begin{array}{rrr} 1 & 0 & - \frac{1}{5} \\ 0 & 1 & \frac{4}{5} \\ 0 & 0 & 0 \end{array} \right]\]

This matrix is now in reduced row-echelon form.

The above algorithm gives you a simple way to obtain the row-echelon form and reduced row-echelon form of a matrix. The main idea is to do row operations in such a way as to end up with a matrix in row-echelon form or reduced row-echelon form. This process is important because the resulting matrix will allow you to describe the solutions to the corresponding linear system of equations in a meaningful way.

In the next example, we look at how to solve a system of equations using the corresponding augmented matrix.

Example \(\PageIndex{12}\): Finding the Solution to a System

Give the complete solution to the following system of equations \[\begin{array}{c} 2x+4y-3z=-1\\ 5x+10y-7z=-2\\ 3x+6y+5z=9 \end{array}\]

Solution

The augmented matrix for this system is \[\left[ \begin{array}{rrr|r} 2 & 4 & -3 & -1 \\ 5 & 10 & -7 & -2 \\ 3 & 6 & 5 & 9 \end{array} \right]\]

In order to find the solution to this system, we wish to carry the augmented matrix to . We will do so using Algorithm [algo:rrefalgorithm]. Notice that the first column is nonzero, so this is our first pivot column. The first entry in the first row, \(2\), is the first leading entry and it is in the first pivot position. We will use row operations to create zeros in the entries below the \(2\). First, replace the second row with \(-5\) times the first row plus \(2\) times the second row. This yields \[\left[ \begin{array}{rrr|r} 2 & 4 & -3 & -1 \\ 0 & 0 & 1 & 1 \\ 3 & 6 & 5 & 9 \end{array} \right]\] Now, replace the third row with \(-3\) times the first row plus to \(2\) times the third row. This yields \[\left[ \begin{array}{rrr|r} 2 & 4 & -3 & -1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 21 \end{array} \right]\] Now the entries in the first column below the pivot position are zeros. We now look for the second pivot column, which in this case is column three. Here, the \(1\) in the second row and third column is in the pivot position. We need to do just one row operation to create a zero below the \(1\).

Taking \(-1\) times the second row and adding it to the third row yields \[\left[ \begin{array}{rrr|r} 2 & 4 & -3 & -1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 20 \end{array} \right]\]

We could proceed with the algorithm to carry this matrix to row-echelon form or reduced row-echelon form. However, remember that we are looking for the solutions to the system of equations. Take another look at the third row of the matrix. Notice that it corresponds to the equation \[0x+0y+0z=20\] There is no solution to this equation because for all \(x,y,z\), the left side will equal \(0\) and \(0\neq 20.\) This shows there is no solution to the given system of equations. In other words, this system is inconsistent.

The following is another example of how to find the solution to a system of equations by carrying the corresponding augmented matrix to reduced row-echelon form.

Example \(\PageIndex{13}\): An Infinite Set of Solutions

Give the complete solution to the system of equations \[\begin{array}{c} 3x-y-5z=9 \\ y-10z=0 \\ -2x+y=-6 \end{array}\]

Solution

The augmented matrix of this system is \[\left[ \begin{array}{rrr|r} 3 & -1 & -5 & 9 \\ 0 & 1 & -10 & 0 \\ -2 & 1 & 0 & -6 \end{array} \right]\] In order to find the solution to this system, we will carry the augmented matrix to reduced row-echelon form, using Algorithm [algo:rrefalgorithm]. The first column is the first pivot column. We want to use row operations to create zeros beneath the first entry in this column, which is in the first pivot position. Replace the third row with \(2\) times the first row added to \(3\) times the third row. This gives

\[\left[ \begin{array}{rrr|r} 3 & -1 & -5 & 9 \\ 0 & 1 & -10 & 0 \\ 0 & 1 & -10 & 0 \end{array} \right]\]

Now, we have created zeros beneath the \(3\) in the first column, so we move on to the second pivot column (which is the second column) and repeat the procedure. Take \(-1\) times the second row and add to the third row. \[\left[ \begin{array}{rrr|r} 3 & -1 & -5 & 9 \\ 0 & 1 & -10 & 0 \\ 0 & 0 & 0 & 0 \end{array} \right]\] The entry below the pivot position in the second column is now a zero. Notice that we have no more pivot columns because we have only two leading entries.

At this stage, we also want the leading entries to be equal to one. To do so, divide the first row by \(3\). \[\left[ \begin{array}{rrr|r} 1 & - \frac{1}{3} & - \frac{5}{3} & 3 \\ 0 & 1 & -10 & 0 \\ 0 & 0 & 0 & 0 \end{array} \right]\]

This matrix is now in row-echelon form.

Let’s continue with row operations until the matrix is in reduced row-echelon form. This involves creating zeros above the pivot positions in each pivot column. This requires only one step, which is to add \(\frac{1}{3}\) times the second row to the first row. \[\left[ \begin{array}{rrr|r} 1 & 0 & -5 & 3 \\ 0 & 1 & -10 & 0 \\ 0 & 0 & 0 & 0 \end{array} \right]\]

This is in reduced row-echelon form, which you should verify using Definition [def:rref]. The equations corresponding to this reduced row-echelon form are \[\begin{array}{c} x - 5z=3 \\ y - 10z = 0 \end{array}\] or \[\begin{array}{c} x=3+5z \\ y = 10z \end{array}\]

Observe that \(z\) is not restrained by any equation. In fact, \(z\) can equal any number. For example, we can let \(z = t\), where we can choose \(t\) to be any number. In this context \(t\) is called a parameter . Therefore, the solution set of this system is \[\begin{array}{c} x=3+5t \\ y=10t \\ z=t \end{array}\] where \(t\) is arbitrary. The system has an infinite set of solutions which are given by these equations. For any value of \(t\) we select, \(x, y,\) and \(z\) will be given by the above equations. For example, if we choose \(t=4\) then the corresponding solution would be \[\begin{array}{c} x = 3 + 5 (4) = 23\\ y = 10(4)=40 \\ z=4 \end{array}\]

In Example [exa:infinitesetofsoln] the solution involved one parameter. It may happen that the solution to a system involves more than one parameter, as shown in the following example.

Example \(\PageIndex{1}\): A Two Parameter Set of Solutions

Find the solution to the system \[\begin{array}{c} x+2y-z+w=3 \\ x+y-z+w=1 \\ x+3y-z+w=5 \end{array}\]

Solution

The augmented matrix is \[\left[ \begin{array}{rrrr|r} 1 & 2 & -1 & 1 & 3 \\ 1 & 1 & -1 & 1 & 1 \\ 1 & 3 & -1 & 1 & 5 \end{array} \right]\] We wish to carry this matrix to row-echelon form. Here, we will outline the row operations used. However, make sure that you understand the steps in terms of Algorithm [algo:rrefalgorithm].

Take \(-1\) times the first row and add to the second. Then take \(-1\) times the first row and add to the third. This yields \[\left[ \begin{array}{rrrr|r} 1 & 2 & -1 & 1 & 3 \\ 0 & -1 & 0 & 0 & -2 \\ 0 & 1 & 0 & 0 & 2 \end{array} \right]\]

Now add the second row to the third row and divide the second row by \(-1\). \[\left[ \begin{array}{rrrr|r} 1 & 2 & -1 & 1 & 3 \\ 0 & 1 & 0 & 0 & 2 \\ 0 & 0 & 0 & 0 & 0 \end{array} \right] \label{twoparameters1}\]

This matrix is in row-echelon form and we can see that \(x\) and \(y\) correspond to pivot columns, while \(z\) and \(w\) do not. Therefore, we will assign parameters to the variables \(z\) and \(w\). Assign the parameter \(s\) to \(z\) and the parameter \(t\) to \(w.\) Then the first row yields the equation \(x+2y-s+t=3\), while the second row yields the equation \(y=2\). Since \(y=2\), the first equation becomes \(x+4-s+t=3\) showing that the solution is given by \[\begin{array}{c} x=-1+s-t \\ y=2 \\ z=s \\ w=t \end{array}\] It is customary to write this solution in the form \[\left[ \begin{array}{c} x \\ y \\ z \\ w \end{array} \right] =\left[ \begin{array}{c} -1+s-t \\ 2 \\ s \\ t \end{array} \right] \label{twoparameters2}\]

This example shows a system of equations with an infinite solution set which depends on two parameters. It can be less confusing in the case of an infinite solution set to first place the augmented matrix in reduced row-echelon form rather than just row-echelon form before seeking to write down the description of the solution.

In the above steps, this means we don’t stop with the row-echelon form in equation [twoparameters1]. Instead we first place it in reduced row-echelon form as follows. \[\left[ \begin{array}{rrrr|r} 1 & 0 & -1 & 1 & -1 \\ 0 & 1 & 0 & 0 & 2 \\ 0 & 0 & 0 & 0 & 0 \end{array} \right]\] Then the solution is \(y=2\) from the second row and \(x=-1+z-w\) from the first. Thus letting \(z=s\) and \(w=t,\) the solution is given by [twoparameters2].

You can see here that there are two paths to the correct answer, which both yield the same answer. Hence, either approach may be used. The process which we first used in the above solution is called Gaussian Elimination This process involves carrying the matrix to row-echelon form, converting back to equations, and using back substitution to find the solution. When you do row operations until you obtain reduced row-echelon form, the process is called Gauss-Jordan Elimination.

We have now found solutions for systems of equations with no solution and infinitely many solutions, with one parameter as well as two parameters. Recall the three types of solution sets which we discussed in the previous section; no solution, one solution, and infinitely many solutions. Each of these types of solutions could be identified from the graph of the system. It turns out that we can also identify the type of solution from the reduced row-echelon form of the augmented matrix.

• No Solution: In the case where the system of equations has no solution, the row-echelon form of the augmented matrix will have a row of the form \[\left[ \begin{array}{rrrrr} 0 & 0 & 0 & | & 1 \end{array} \right]\]

  This row indicates that the system is inconsistent and has no solution.

• One Solution: In the case where the system of equations has one solution, every column of the coefficient matrix is a pivot column. The following is an example of an augmented matrix in for a row-echelon form system of equations with one solution. \[\left[ \begin{array}{rrr|r} 1 & 0 & 0 & 5 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 2 \end{array} \right]\]
• Infinitely Many Solutions: In the case where the system of equations has infinitely many solutions, the solution contains parameters. There will be columns of the coefficient matrix which are not pivot columns. The following are examples of augmented matrices in reduced row-echelon form for systems of equations with infinitely many solutions. \[\left[ \begin{array}{rrr|r} 1 & 0 & 0 & 5 \\ 0 & 1 & 2 & -3 \\ 0 & 0 & 0 & 0 \end{array} \right]\] or \[\left[ \begin{array}{rrr|r} 1 & 0 & 0 & 5 \\ 0 & 1 & 0 & -3 \end{array} \right]\]

Contributors and Attributions

Kuttler, K. (2020, August 12). Book: A First Course in Linear Algebra (Kuttler). Retrieved from https://chem.libretexts.org/@go/page/14495

Pamini Thangarajah (Mount Royal University, Calgary, Alberta, Canada)