Gauss-Jordan Elimination

Section 4.1 Gauss-Jordan Elimination

We can also solve a system of linear equations using matrices. First, construct the augmented matrix by extracting the coefficients of the variables and placing the constants from the right-hand side of the equations as the last column. Then, perform elementary row operations to reduce this augmented matrix to reduced row echelon form (RREF). Finally, convert the matrix back into a system of equations to explicitly display the solutions.

🔗

In the following sections, we will demonstrate how to use Sage to carry out these steps, using our example from \(\textbf{Case I}\text{:}\)

🔗

\begin{gather*} \begin{array}{c} y - z = 0\\ x + 2y = 4\\ x + z = 4 \end{array} \end{gather*}

Section 4.1.1 Augmented Matrix

First, we create the augmented matrix for the system of equations. Each row in the augmented matrix lists the coefficients of the variables in an equation. While we do not directly manipulate the variables themselves, they indicate the position of each coefficient. The last column of the augmented matrix contains the constants from the right-hand side of each equation.

🔗

\begin{align*} \left[\begin{array}{ccc|c} 0 \amp 1 \amp -1 \amp 0 \\ 1 \amp 2 \amp 0 \amp 4 \\ 1 \amp 0 \amp 1 \amp 4 \end{array}\right] \end{align*}

Let’s define first the coefficient matrix, consisting of the coefficients extracted from the system of equations where each column corresponds to a variable:

🔗

Then, let’s define the constants vector:

🔗

Next, create the augmented matrix by passing the constants vector to the augment() method of the coefficient matrix.

🔗

Alternatively, we can enter all the coefficients of the augmented matrix directly.

🔗

Section 4.1.2 RREF

A matrix is in reduced row echelon form if:

The first nonzero number in the row is a leading \(1\text{.}\)
🔗

🔗
In any two consecutive rows that do not consist entirely of zeros, the leading \(1\) in the lower row occurs farther to the right than the leading \(1\) in the higher row.
🔗

🔗
Rows that consist entirely of zeros are at the bottom of the matrix.
🔗

🔗
Each column that contains a leading \(1\) has zeros everywhere else in that column.
🔗

🔗

🔗

We can perform some operations in a matrix to reduce it to this form. The following elementary operations transform a system of equations into another one with the same solution:

🔗

Scaling 🔗: A row is multiplied by a nonzero constant.
🔗

The rescale_row(i,s) method preforms this operation by multiplying row \(i\) by \(s\) in place.
🔗
Interchange 🔗: A row is swapped with another.
🔗

The swap_rows(r1, r2) method preforms this operation on a matrix by swapping rows r1 and r2.
🔗
Replacement 🔗: A row is added to a multiple of another.
🔗

The add_multiple_of_row(i, j, s) method preforms this operation on a matrix by adding \(s\) times row \(j\) to row \(i\text{.}\)
🔗

Keep in mind that all of the previous methods use zero-based indexing.

🔗

We will now perform elementary operations in our augmented matrix to transform it into reduced row echelon form. Recall that our augmented matrix is:

🔗

First, we will move the leading \(1\) from the second row to the first row.

🔗

The next step is to multiply the first row by \(-1\) and add it to the third row.

🔗

Next, multiple the second row by \(2\) and add it to the third row.

🔗

Multiply the third row by \(-1\) and add it to the second row.

🔗

Multiply the second row by \(-2\) and add it to the first row.

🔗

Multiply the third row in place by \(-1\text{.}\)

🔗

Notice that this matrix satisfies the definition of reduced row echelon form. Now that the matrix is in reduced row echelon form, we can translate it back into a system of equations to explicitly visualize the solution set of the system of equations:

\begin{gather*} \begin{array}{c} x = 4 \\ y = 0 \\ z = 0 \end{array} \end{gather*}

🔗

Alternatively, Sage has a built in method to do all the previous steps directly. The rref() method returns the reduced row echelon Form of a matrix.

🔗

Here is an example of rref() on \(\textbf{Case II}\text{,}\) with infinitely many solutions.

🔗

Observe that when we translate it back into a system of equations, we obtain:

🔗

\begin{gather*} \left\{ \begin{array}{l} x + 2z = 4\\ y - z = 0\\ 0 = 0 \end{array} \right. \hspace{6pt} \Rightarrow \hspace{6pt} \left\{ \begin{array}{l} x = -2z + 4\\ y = z\\ z = z \end{array} \right. \end{gather*}

We will see in the next section how to use Sage to interpret this solution.

🔗

Here is rref() on \(\textbf{Case III}\text{,}\) with no solutions:

🔗

Observe that when we translate it back into a system of equations, we obtain:

🔗

\begin{gather*} \begin{array}{c} x + 2z = 4\\ y - z = 0\\ 0 = 1 \end{array} \end{gather*}

This clearly shows a contradiction.

🔗

Prev Top Next