Definition 1.2.1.
The first non-zero entry in a row of a matrix (when read from left to right) is called the leading entry. When the leading entry is 1, we call it a leading 1.
Section 1.2 Row Echelon Forms
In Section 1.1, we saw that systems of linear equations may not have a unique solution, but we did not discuss what to do about it. Now we will address all possible solutions of a system, including systems with no solution at all. In the first subsection, we work out what a “fully reduced” system should look like and then, in the second subsection, we describe how to use Gaussian elimination to get this form. Finally, the last subsection describes the solution set of the “fully reduced” matrix when the solution is not unique or when there is no solution.
Subsection 1.2.1 Row Echelon Form and Reduced Row Echelon Form
Before looking for a “reduced form”, we need a name for for the first non-zero entry in a row of a matrix. Using this name, we can then define the first special form for a matrix.
Definition 1.2.2. Row Echelon Form.
A matrix is said to be in row echelon form if:
- All entries below each leading entry are 0.
- Each leading entry is in a column to the right of the leading entries in the rows above it.
- All rows of zeros, if there are any, are located below non-zero rows.
The term row echelon form can be applied to matrices whether or not they are augmented matrices (matrices with the vertical bar). For example, both the coefficient matrix and the augmented matrix in (1.1.5) are in row echelon form. Note that the leading entries form a staircase pattern. All entries below the leading entries are zero, but the entries above the leading entries are not all zero.
Below are two more examples of matrices in row echelon form. The leading entries of each matrix are boxed.
\begin{equation*}
\begin{bmatrix}
\fbox{1}\amp 2\amp -1\amp -5\amp 0\amp 2\\0\amp 0\amp \fbox{3}\amp 1\amp 2\amp 0\\0\amp 0\amp 0\amp 0\amp \fbox{1}\amp 0
\end{bmatrix}\quad\text{and}\quad\begin{bmatrix}
\fbox{4}\amp 2\\0\amp \fbox{1}\\0\amp 0
\end{bmatrix}
\end{equation*}
The difference between the coefficient matrix in (1.1.5) and the coefficient matrix in (1.1.6) is that the leading entries of the matrix in (1.1.6) are all 1’s, and the matrix has zeros above each leading 1. This motivates our next definition.
Definition 1.2.3. Reduced Row Echelon Form.
A matrix that is already in row echelon form is said to be in reduced row echelon form if:
- Each leading entry is \(1\)
- All entries above and below each leading \(1\) are \(0\)
The following two matrices are in reduced row echelon form. Note that there are \(0\)’s below and above each leading \(1\text{.}\)
\begin{equation*}
\begin{bmatrix}
\fbox{1}\amp 0\amp -1\amp 0\amp 1\\0\amp \fbox{1}\amp 0\amp 0\amp 2\\0\amp 0\amp 0\amp \fbox{1}\amp 2
\end{bmatrix}\quad\text{and}\quad\begin{bmatrix}
\fbox{1}\amp 0\\0\amp \fbox{1}\\0\amp 0
\end{bmatrix}
\end{equation*}
When solving linear systems using the augmented matrix notation, our goal will be to transform the augmented matrix \(M=[A|\mathbf{b}]\) into a row echelon or reduced row echelon form. The reduced row echelon form of \(M\) is denoted by \(\mbox{rref}(M)\text{.}\) As we transform the augmented matrix \(M\) to its reduced row echelon form, the coefficient matrix \(A\) (the matrix to the left of the bar) also gets transformed to its reduced row echelon form, \(\mbox{rref}(A)\text{.}\)
Perhaps you may be asking some questions. Can every augmented matrix be reduced to a row echelon or reduced row echelon form? If so, is the row echelon or reduced row echelon form unique? We will answer the second question in this subsection and the first question in the next subsection.
Exploration 1.2.1.
Solve the following system of equations.
\begin{equation*}
\begin{array}{ccccccccc}
x \amp + \amp 2y\amp -\amp 3z\amp = \amp 1 \\
-5x\amp +\amp 2y\amp -\amp 3z\amp =\amp 1\\
x\amp - \amp 2y\amp +\amp z\amp =\amp 1
\end{array}
\end{equation*}
We create an augmented matrix corresponding to the system and apply row operations until the matrix is in row echelon form.
\begin{equation*}
\left[\begin{array}{ccc|c}
1\amp 2\amp -3\amp 1\\-5\amp 2\amp -3\amp 1\\1\amp -2\amp 1\amp 1
\end{array}\right]
\begin{array}{c}
\\
\xrightarrow{R_2+5R_1}\\
\xrightarrow{R_3-R_1}\\
\end{array}
\left[\begin{array}{ccc|c}
1\amp 2\amp -3\amp 1\\0\amp 12\amp -18\amp 6\\0\amp -4\amp 4\amp 0
\end{array}\right]
\begin{array}{c}
\\
\\
\xrightarrow{R_3+\frac{1}{3}R_2}\\
\end{array}
\end{equation*}
\begin{equation}
\left[\begin{array}{ccc|c}
1\amp 2\amp -3\amp 1\\0\amp 12\amp -18\amp 6\\0\amp 0\amp -2\amp 2
\end{array}\right]\tag{1.2.1}
\end{equation}
Note that the elementary row operations that lead to (1.2.1) were not prescribed. We may employ row-operations in a different manner and obtain a different matrix in row echelon form. For example, suppose for some reason we had begun by switching the first and third rows.
\begin{equation*}
\left[\begin{array}{ccc|c}
1\amp 2\amp -3\amp 1\\-5\amp 2\amp -3\amp 1\\1\amp -2\amp 1\amp 1
\end{array}\right]
\begin{array}{c}
\\
\xrightarrow{R_1\leftrightarrow R_3}\\
\\
\end{array}
\left[\begin{array}{ccc|c}
1\amp -2\amp 1\amp 1\\-5\amp 2\amp -3\amp 1\\1\amp 2\amp -3\amp 1
\end{array}\right]
\begin{array}{c}
\\
\\
\\
\end{array}
\end{equation*}
Next we would reduce this matrix to row echelon form, perhaps in this way:
\begin{equation*}
\left[\begin{array}{ccc|c}
1\amp -2\amp 1\amp 1\\-5\amp 2\amp -3\amp 1\\1\amp 2\amp -3\amp 1
\end{array}\right]
\begin{array}{c}
\\
\xrightarrow{R_2+5R_1}\\
\xrightarrow{R_3-R_1}\\
\end{array}
\left[\begin{array}{ccc|c}
1\amp -2\amp 1\amp 1\\0\amp -8\amp 2\amp 6\\0\amp 4\amp -4\amp 0
\end{array}\right]
\begin{array}{c}
\\
\\
\xrightarrow{R_3+\frac{1}{2}R_2}\\
\end{array}
\end{equation*}
\begin{equation}
\left[\begin{array}{ccc|c}
1\amp -2\amp 1\amp 1\\0\amp -8\amp 2\amp 6\\0\amp 0\amp -3\amp 3
\end{array}\right]\tag{1.2.2}
\end{equation}
The augmented matrices in (1.2.1) and (1.2.2) are clearly not the same, but both are in row echelon form. If we write the systems of equations corresponding to (1.2.1) and (1.2.2), we can employ back substitution to solve them. The matrix in (1.2.1) corresponds to
\begin{equation*}
\begin{array}{ccccccccc}
x \amp + \amp 2y\amp -\amp 3z\amp = \amp 1 \\
\amp \amp 12y\amp -\amp 18z\amp =\amp 6\\
\amp \amp \amp \amp -2z\amp =\amp 2
\end{array}
\end{equation*}
The matrix in (1.2.2) corresponds to
\begin{equation*}
\begin{array}{ccccccccc}
x \amp - \amp 2y\amp +\amp z\amp = \amp 1 \\
\amp \amp -8y\amp +\amp 2z\amp =\amp 6\\
\amp \amp \amp \amp -3z\amp =\amp 3
\end{array}
\end{equation*}
Because both systems are equivalent to the original system, it is not surprising that back substitution yields the same solution for both systems.
\begin{equation*}
x=0,\quad y=-1,\quad z=-1
\end{equation*}
\begin{equation*}
x=0, y=-1, z=-1
\end{equation*}
\begin{equation*}
x=0, y=-1, z=-1
\end{equation*}
It is clear from Exploration 1.2.1 that a row echelon form corresponding to a matrix is not unique. But what about the reduced row echelon form?
Exploration 1.2.2.
In this problem we revisit the system
\begin{equation*}
\begin{array}{ccccccccc}
x \amp + \amp 2y\amp -\amp 3z\amp = \amp 1 \\
-5x\amp +\amp 2y\amp -\amp 3z\amp =\amp 1\\
x\amp - \amp 2y\amp +\amp z\amp =\amp 1
\end{array}
\end{equation*}
Following the steps we took to get (1.2.1), but taking the process a little further, we get the reduced row echelon form.
\begin{equation*}
\left[\begin{array}{ccc|c}
1\amp 2\amp -3\amp 1\\-5\amp 2\amp -3\amp 1\\1\amp -2\amp 1\amp 1
\end{array}\right]
\begin{array}{c}
\\
\xrightarrow{R_2+5R_1}\\
\xrightarrow{R_3-R_1}\\
\end{array}
\left[\begin{array}{ccc|c}
1\amp 2\amp -3\amp 1\\0\amp 12\amp -18\amp 6\\0\amp -4\amp 4\amp 0
\end{array}\right]
\begin{array}{c}
\\
\\
\xrightarrow{R_3+\frac{1}{3}R_2}\\
\end{array}
\end{equation*}
\begin{equation*}
\left[\begin{array}{ccc|c}
1\amp 2\amp -3\amp 1\\0\amp 12\amp -18\amp 6\\0\amp 0\amp -2\amp 2
\end{array}\right]
\color{blue}
\begin{array}{c}
\\
\xrightarrow{\frac{1}{12}R_2}\\
\xrightarrow{-\frac{1}{2}R_3}\\
\end{array}
\left[\begin{array}{ccc|c}
1\amp 2\amp -3\amp 1\\0\amp 1\amp -\frac{3}{2}\amp \frac{1}{2}\\0\amp 0\amp 1\amp -1
\end{array}\right]
\begin{array}{c}
\xrightarrow{R_1+3R_3}\\
\xrightarrow{R_2+\frac{3}{2}R_3}\\
\\
\end{array}
\end{equation*}
\begin{equation}
\color{blue}
\left[\begin{array}{ccc|c}
1\amp 2\amp 0\amp -2\\0\amp 1\amp 0\amp -1\\0\amp 0\amp 1\amp -1
\end{array}\right]
\begin{array}{c}
\xrightarrow{R_1-2R_2}\\
\\
\\
\end{array}
\color{black}
\left[\begin{array}{ccc|c}
1\amp 0\amp 0\amp 0\\0\amp 1\amp 0\amp -1\\0\amp 0\amp 1\amp -1
\end{array}\right]\tag{1.2.3}
\end{equation}
Do you think it is possible to start with (1.2.2) and obtain the same reduced row echelon form? Try to justify your response. If possible, find the elementary row operations that take (1.2.2) to the reduced row echelon form in (1.2.3).
\begin{equation*}
\left[\begin{array}{ccc|c}
1\amp 2\amp -3\amp 1\\-5\amp 2\amp -3\amp 1\\1\amp -2\amp 1\amp 1
\end{array}\right]
\begin{array}{c}
\\
\xrightarrow{R_1\leftrightarrow R_3}\\
\\
\end{array}
\left[\begin{array}{ccc|c}
1\amp -2\amp 1\amp 1\\-5\amp 2\amp -3\amp 1\\1\amp 2\amp -3\amp 1
\end{array}\right]
\end{equation*}
\begin{equation*}
\begin{array}{c}
\\
\xrightarrow{R_2+5R_1}\\
\xrightarrow{R_3-R_1}\\
\end{array}
\left[\begin{array}{ccc|c}
1\amp -2\amp 1\amp 1\\0\amp -8\amp 2\amp 6\\0\amp 4\amp -4\amp 0
\end{array}\right]
\begin{array}{c}
\\
\\
\xrightarrow{R_3+\frac{1}{2}R_2}\\
\end{array}
\end{equation*}
\begin{equation*}
\left[\begin{array}{ccc|c}
1\amp -2\amp 1\amp 1\\0\amp -8\amp 2\amp 6\\0\amp 0\amp -3\amp 3
\end{array}\right]
\color{red}
\begin{array}{c}
\rightsquigarrow\text{Elementary}\rightsquigarrow\\
\text{Row Ops.}
\end{array}
\color{black}
\left[\begin{array}{ccc|c}
1\amp 0\amp 0\amp 0\\0\amp 1\amp 0\amp -1\\0\amp 0\amp 1\amp -1
\end{array}\right]
\end{equation*}
You will be asked to fill in the elementary row operations in Exercise 1.2.4.6.
Our observations in Exploration 1.2.2 are summarized in the following diagram.
We observed that a row echelon form associated with a matrix is not unique. In contrast, we also saw how different sequences of elementary row operations lead to the same solution set and the same reduced row echelon form. It turns out that the reduced row echelon form of a matrix is unique.
Theorem 1.2.4.
The reduced row echelon form of a matrix is unique.
A proof of this result can be found in [1.2.5.2].
The reduced row echelon form of a matrix is an instance of a row echelon form of the matrix. While a given matrix may have multiple row echelon forms, all row echelon forms will share one characteristic: the number of nonzero rows in a row echelon form of the given matrix will be the same. We will prove this result in Theorem 4.3.6, but we use it now to make the following definition:
Definition 1.2.5.
The rank of matrix \(A\text{,}\) denoted by \(\mbox{rank}(A)\text{,}\) is the number of nonzero rows in any row echelon form of \(A\text{.}\)
Subsection 1.2.2 Gaussian and Gauss-Jordan Elimination
Definition 1.2.6. Gaussian Elimination.
The process of using the elementary row operations on a matrix to transform it into row echelon form is called Gaussian Elimination.
As we saw in the previous section, it is possible to follow different sequences of row operations to arrive at various row echelon forms. However, it was not clear whether it is always possible to find a row echelon form. The following algorithm takes any matrix (or augmented matrix) and transforms it into row echelon form:
Algorithm 1.2.7. Gaussian Algorithm.
Let \(A\) be an \(m\times n\) matrix. Set \(i=1\) initially.
- Step 1. If \(A\) consists entirely of zeros, stop; \(A\) is already in row echelon form.
- Step 2. Otherwise, find the first column from the left containing a nonzero entry in row \(i\) or below row \(i\text{.}\) This column will be called a pivot column. Go down the pivot column, beginning with row \(i\text{.}\) Pick the topmost nonzero entry and call it \(a\text{.}\) If \(a\) is not in row \(i\text{,}\) switch rows so that \(a\) moves to row \(i\text{.}\) Now \(a\) is the leading entry in its row. We will also refer to \(a\) as a pivot.
- Step 3. By subtracting multiples of the row containing \(a\) from rows below it, make each entry below \(a\) zero.
- Step 4. Set \(i=i+1\text{.}\) If \(i\gt m\) then stop; \(A\) is in row echelon form.
Repeat steps 1--4 on the matrix consisting of the remaining rows. When the process stops, \(A\) will be in row echelon form.
Gaussian Algorithm guarantees that every matrix will have a row echelon form.
Example 1.2.8.
Use the Gaussian Algorithm to find a row echelon form of \(A\) if
\begin{equation*}
A=\begin{bmatrix}2\amp 4\\1\amp 2\\-1\amp 1\\3\amp 5\end{bmatrix}
\end{equation*}
Answer.
Following Step 2, we choose the first entry, \(2\text{,}\) as our pivot. We then perform step 3, using the top row to get zeros in all entries below the \(2\text{.}\)
\begin{equation*}
\begin{bmatrix} \fbox{\(2\)}\amp 4\\1\amp 2\\-1\amp 1\\3\amp 5\end{bmatrix}
\begin{array}{c}
\\
\xrightarrow{R_2-(1/2)R_1}\\
\xrightarrow{R_3+(1/2)R_1}\\
\xrightarrow{R_4-(3/2)R_1}\\
\end{array}
\begin{bmatrix}2\amp 4\\0\amp 0\\0\amp 3\\0\amp -1\end{bmatrix}
\end{equation*}
The first row is now complete, and we repeat the process on the rows below it. We identify \(3\) as a pivot entry in the second column and move the row containing \(3\) to be directly below the first completed row. We then use the \(3\) to make each entry below the \(3\) a zero.
\begin{equation*}
\begin{bmatrix}2\amp 4\\0\amp 0\\0\amp \fbox{\(3\)}\\0\amp -1\end{bmatrix}
\xrightarrow{R_2\leftrightarrow R_3}\\
\begin{bmatrix}2\amp 4\\0\amp \fbox{\(3\)}\\0\amp 0\\0\amp -1\end{bmatrix}
\begin{array}{c}
\\
\\
\\
\xrightarrow{R_4+\frac{1}{3}R_2}\\
\end{array}
\begin{bmatrix}2\amp 4\\0\amp 3\\0\amp 0\\0\amp 0\end{bmatrix}
\end{equation*}
This time the algorithm terminates since row 3 and row 4 are zero rows.
Definition 1.2.9. Gauss-Jordan Elimination.
The process of using the elementary row operations on a matrix to transform it into reduced row echelon form is called Gauss-Jordan elimination.
Given a matrix in row echelon form, it is easy to bring it to reduced row echelon form. For example, continuing with Example 1.2.8, we can start where we left off and compute \(\mbox{rref}(A)\text{.}\) From our earlier computations we have:
\begin{equation*}
\begin{bmatrix}2\amp 4\\-1\amp 1\\3\amp 5\\1\amp 2\end{bmatrix}\rightsquigarrow\begin{bmatrix}2\amp 4\\0\amp 3\\0\amp 0\\0\amp 0\end{bmatrix}
\end{equation*}
Now we create leading \(1's\) and use them to to wipe out all non-zero entries above them.
\begin{equation*}
\begin{bmatrix}2\amp 4\\0\amp 3\\0\amp 0\\0\amp 0\end{bmatrix}
\begin{array}{c}
\xrightarrow{(1/2)R_1}\\
\xrightarrow{(1/3)R_2}\\
\\
\\
\end{array}
\begin{bmatrix}1\amp 2\\0\amp 1\\0\amp 0\\0\amp 0\end{bmatrix}
\begin{array}{c}
\xrightarrow{R_1-2R_2}\\
\\
\\
\\
\end{array}
\begin{bmatrix}1\amp 0\\0\amp 1\\0\amp 0\\0\amp 0\end{bmatrix}=\mbox{rref}(A)
\end{equation*}
The following modification to the Gaussian Algorithm produces the reduced row echelon form of a matrix. This algorithm guarantees the existence of the reduced row echelon form.
Algorithm 1.2.10. Gauss-Jordan Algorithm.
Let \(A\) be an \(m\times n\) matrix. Follow the steps of the Gaussian Algorithm but modify Step 2 to create leading \(1's\) by multiplying the row containing \(a\) by \(\frac{1}{a}\text{.}\) When the Gaussian Algorithm terminates, subtract multiples of the rows containing leading \(1's\) from the rows above to make all entries above the pivots zero.
The algorithm is an essential tool in linear algebra. An fully detailed example is provided below.
Example 1.2.11.
Use the Gauss-Jordan Algorithm to solve the system
\begin{equation*}
\begin{array}{ccccccccc}
3x \amp + \amp y\amp +\amp 7z\amp = \amp 7 \\
5x\amp +\amp 3y\amp +\amp 9z\amp =\amp 13\\
2x\amp + \amp y\amp +\amp 4z\amp =\amp 5
\end{array}
\end{equation*}
Answer.
\begin{align*}
\amp \left[\begin{array}{ccc|c}
\fbox{\(3\)}\amp 1\amp 7\amp 7\\5\amp 3\amp 9\amp 13\\2\amp 1\amp 4\amp 5
\end{array}\right] \\
\begin{array}{c}
\xrightarrow{\frac{1}{3}R_1}\\
\\
\\
\end{array}
\amp \left[\begin{array}{ccc|c}
\fbox{\(1\)}\amp 1/3\amp 7/3\amp 7/3\\5\amp 3\amp 9\amp 13\\2\amp 1\amp 4\amp 5
\end{array}\right] \\
\begin{array}{c}
\\
\xrightarrow{R_2-5R_1}\\
\\
\end{array}
\amp \left[\begin{array}{ccc|c}
\fbox{\(1\)}\amp 1/3\amp 7/3\amp 7/3\\0\amp 4/3\amp -8/3\amp 4/3\\2\amp 1\amp 4\amp 5
\end{array}\right]\\
\begin{array}{c}
\\
\\
\xrightarrow{R_3-2R_1}\\
\end{array}\amp \left[\begin{array}{ccc|c}
1\amp 1/3\amp 7/3\amp 7/3\\0\amp \fbox{\(4/3\)}\amp -8/3\amp 4/3\\0\amp 1/3\amp -2/3\amp 1/3
\end{array}\right] \\
\begin{array}{c}
\\
\xrightarrow{\frac{3}{4}R_2}\\
\\
\end{array}
\amp \left[\begin{array}{ccc|c}
1\amp 1/3\amp 7/3\amp 7/3\\0\amp \fbox{\(1\)}\amp -2\amp 1\\0\amp 1/3\amp -2/3\amp 1/3
\end{array}\right] \\
\begin{array}{c}
\\
\\
\xrightarrow{R_3-\frac{1}{3}R_2}\\
\end{array}
\amp \left[\begin{array}{ccc|c}
1\amp 1/3\amp 7/3\amp 7/3\\0\amp \fbox{\(1\)}\amp -2\amp 1\\0\amp 0\amp 0\amp 0
\end{array}\right] \\
\begin{array}{c}
\xrightarrow{R_1-\frac{1}{3}R_2}\\
\\
\\
\end{array}
\amp \left[\begin{array}{ccc|c}
1\amp 0\amp 3\amp 2\\0\amp 1\amp -2\amp 1\\0\amp 0\amp 0\amp 0
\end{array}\right]
\end{align*}
We convert the reduced row echelon form to a system of equations and find the solution. The last equation contributes nothing to the system so we omit writing it down.
\begin{equation*}
\begin{array}{ccccccccc}
x \amp \amp \amp +\amp 3z\amp = \amp 2 \\
\amp \amp y\amp -\amp 2z\amp =\amp 1
\end{array}
\end{equation*}
The solution is
\begin{equation*}
x=2-3t,\quad y=1+2t,\quad z=t.
\end{equation*}
The Gauss-Jordan Algorithm guarantees the existence of the reduced row echelon form for all matrices. When doing computations by hand, however, the algorithm may not always be the optimal method of finding a row echelon form or the reduced row echelon form because the procedure often leads to fractions early in the process. The following video shows how to arrive at the same reduced row echelon form for the matrix in Example 1.2.11 without doing any fraction arithmetic. You will see that we still employ row operations, but in a different order.
The video highlights the fact that regardless of what sequence of elementary row operations we take to arrive at the reduced row echelon form, the end result is the same.
Subsection 1.2.3 Solutions to Systems of Equations
We now have an efficient and algorithmic way to solve systems of linear equations by row reducing a corresponding augmented matrix to its reduced row echelon form. Now we turn our attention to exploring how to use the reduced row echelon form to find solutions to systems of equations. Specifically, when there are infinitely many solutions or no solutions.
Exploration 1.2.3.
Let’s solve the system of equations below.
\begin{equation*}
\begin{array}{ccccccccc}
x \amp - \amp 2y\amp +\amp z\amp \amp \amp = \amp 2 \\
-2x\amp +\amp y\amp -\amp z\amp +\amp w\amp =\amp 0\\
x\amp +\amp 4y\amp \amp \amp +\amp w\amp =\amp 1
\end{array}
\end{equation*}
We begin by rewriting the system in the augmented matrix form.
\begin{equation*}
\left[\begin{array}{cccc|c}
1\amp -2\amp 1\amp 0\amp 2\\-2\amp 1\amp -1\amp 1\amp 0\\1\amp 4\amp 0\amp 1\amp 1
\end{array}\right]
\end{equation*}
Our goal is to convert this matrix to its reduced row echelon form by means of elementary row operations. To do this, we will proceed from left to right and use leading entries to wipe out all entries above and below them.
\begin{equation*}
\left[\begin{array}{cccc|c}
1\amp -2\amp 1\amp 0\amp 2\\-2\amp 1\amp -1\amp 1\amp 0\\1\amp 4\amp 0\amp 1\amp 1
\end{array}\right]
\begin{array}{c}
\\
\xrightarrow{R_2+2R_1}\\
\xrightarrow{R_3-R_1}\\
\end{array}\left[\begin{array}{cccc|c}
1\amp -2\amp 1\amp 0\amp 2\\0\amp -3\amp 1\amp 1\amp 4\\0\amp 6\amp -1\amp 1\amp -1
\end{array}\right]\begin{array}{c}
\\
\\
\xrightarrow{R_3+2R_2}\\
\end{array}
\end{equation*}
\begin{equation*}
\left[\begin{array}{cccc|c}
1\amp -2\amp 1\amp 0\amp 2\\0\amp -3\amp 1\amp 1\amp 4\\0\amp 0\amp 1\amp 3\amp 7
\end{array}\right]
\begin{array}{c}
\\
\xrightarrow{(-1/3)R_2}\\
\\
\end{array}\left[\begin{array}{cccc|c}
1\amp -2\amp 1\amp 0\amp 2\\0\amp 1\amp -1/3\amp -1/3\amp -4/3\\0\amp 0\amp 1\amp 3\amp 7
\end{array}\right]\begin{array}{c}
\xrightarrow{R_1+2R_2}\\
\\
\\
\end{array}
\end{equation*}
\begin{equation*}
\left[\begin{array}{cccc|c}
1\amp 0\amp 1/3\amp -2/3\amp -2/3\\0\amp 1\amp -1/3\amp -1/3\amp -4/3\\0\amp 0\amp 1\amp 3\amp 7
\end{array}\right]
\begin{array}{c}
\xrightarrow{R_1-(1/3)R_3}\\
\xrightarrow{R_2+(1/3)R_3}\\
\\
\end{array}\left[\begin{array}{cccc|c}
1\amp 0\amp 0\amp -5/3\amp -3\\0\amp 1\amp 0\amp 2/3\amp 1\\0\amp 0\amp 1\amp 3\amp 7
\end{array}\right]
\end{equation*}
Our final matrix may not be quite as nice as the one in (1.1.6), but it is in reduced row echelon form. Our next step is to convert our augmented matrix back to a system of equations. We have:
\begin{equation*}
\begin{array}{ccccccccc}
x \amp \amp \amp \amp \amp -\amp (5/3)w\amp = \amp -3 \\
\amp \amp y\amp \amp \amp +\amp (2/3)w\amp =\amp 1\\
\amp \amp \amp \amp z\amp +\amp 3w\amp =\amp 7
\end{array}
\end{equation*}
We will rewrite the system as follows:
\begin{equation*}
\begin{array}{ccccccccc}
x \amp \amp \amp \amp \amp \amp \amp = \amp -3+(5/3)w \\
\amp \amp y\amp \amp \amp \amp \amp =\amp 1-(2/3)w\\
\amp \amp \amp \amp z\amp \amp \amp =\amp 7-3w
\end{array}
\end{equation*}
Now we see that there are infinitely many solutions because we can assign any value to \(w\text{,}\) then compute \(x\text{,}\) \(y\) and \(z\) to obtain a solution to the system. For example, let \(w=0\text{,}\) then \(x=-3\text{,}\) \(y=1\) and \(z=7\text{,}\) so \((-3, 1, 7, 0)\) is a solution. If we let \(w=3\text{,}\) then \(x=2\text{,}\) \(y=-1\) and \(z=-2\text{,}\) so \((2, -1, -2, 3)\) is also a solution. To emphasize that we can let \(w\) be any real number, we call it a free variable.
We write the solution set to this system as the following:
\begin{align*}
x\amp =-3+\frac{5}{3}w \\
y\amp =1-\frac{2}{3}w \\
z\amp =7-3w \\
w\amp \text{ is free}
\end{align*}
This describes all the points in \(\mathbb{R}^4\) of the form
\begin{equation*}
\left(-3+\frac{5}{3}w, 1-\frac{2}{3}w, 7-3w, w\right) .
\end{equation*}
Observe that in Exploration 1.2.3, we called variable \(w\) a free variable because it can be any real number. Notice that the variables \(x\text{,}\) \(y\) and \(z\) correspond to the leading \(1's\) in the reduced row echelon. We say that \(x\text{,}\) \(y\) and \(z\) are the leading variables. The free variable \(w\) is not a leading variable. In fact, free variables always correspond to a column in the reduced row echelon form of the augmented matrix which does not have a leading 1. This gives us a method for identifying free variables.
Example 1.2.12.
Solve the system of equations.
\begin{equation*}
\begin{array}{ccccccc}
x \amp -\amp 3y\amp -\amp z\amp = \amp 3 \\
-3x\amp +\amp 5y\amp \amp \amp =\amp -2\\
x\amp + \amp y\amp +\amp 2z\amp =\amp -4
\end{array}
\end{equation*}
Answer.
We rewrite the system in the augmented matrix form and transform it to reduced row echelon form. We leave the details of the elementary row operations to the reader and state the final result.
\begin{equation*}
\left[\begin{array}{ccc|c}
1\amp -3\amp -1\amp 3\\-3\amp 5\amp 0\amp -2\\1\amp 1\amp 2\amp -4
\end{array}\right]\begin{array}{c}
\\
\rightsquigarrow\\
\\
\end{array}\left[\begin{array}{ccc|c}
1\amp 0\amp 5/4\amp -9/4\\0\amp 1\amp 3/4\amp -7/4\\0\amp 0\amp 0\amp 0
\end{array}\right]
\end{equation*}
The augmented column does not have a leading 1 in the reduced row echelon form, so we know the system is consistent. To write down the solution, we note that \(x\) and \(y\) are leading variables and \(z\) is a free variable. Converting the augmented matrix back to a system of equations we get
\begin{equation*}
\begin{array}{ccccccc}
x \amp + \amp 0y\amp +\amp (5/4)z\amp = \amp -9/4 \\
0x\amp +\amp y\amp +\amp (3/4)z\amp =\amp -7/4\\
0x\amp + \amp 0y\amp +\amp 0z\amp =\amp 0
\end{array}
\end{equation*}
To complete the problem, we solve for the leading variables in terms of the free variables. Since the last equation contributes nothing, we will remove it and rewrite the system as
\begin{equation*}
\begin{array}{ccccc}
x \amp \amp \amp = \amp -9/4-(5/4)z \\
\amp \amp y\amp =\amp -7/4-(3/4)z\\
\end{array}
\end{equation*}
Hence, the solutions to this system are points of the form
\begin{equation*}
\left(-\frac{9}{4}-\frac{5}{4}z, -\frac{7}{4}-\frac{3}{4}z, z\right)
\end{equation*}
We can also write the solutions as
\begin{align*}
x\amp =-\frac{9}{4}-\frac{5}{4}z \\
y\amp =-\frac{7}{4}-\frac{3}{4}z \\
z\amp \text{ is free}
\end{align*}
We now can solve and write down the solution to any consistent system using the reduced row echelon form of an augmented matrix. We can also use row echelon forms to determine if a system is inconsistent.
Exploration 1.2.4.
In this exploration, we will solve the system of equations below or determine that the system is inconsistent.
\begin{equation*}
\begin{array}{ccccccc}
2x \amp -\amp y\amp \amp \amp = \amp 2 \\
x\amp +\amp y\amp -\amp 2z\amp =\amp 0\\
-3x\amp \amp \amp +\amp 2z\amp =\amp -1
\end{array}
\end{equation*}
We rewrite the system in augmented matrix form and transform it to reduced row echelon form. We leave the details of the elementary row operations to the reader and state the final result.
\begin{equation}
\left[\begin{array}{ccc|c}
2\amp -1\amp 0\amp 2\\1\amp 1\amp -2\amp 0\\-3\amp 0\amp 2\amp -1
\end{array}\right]\begin{array}{c}
\\
\rightsquigarrow\\
\\
\end{array}\left[\begin{array}{ccc|c}
1\amp 0\amp -2/3\amp 0\\0\amp 1\amp -4/3\amp 0\\0\amp 0\amp 0\amp 1
\end{array}\right]\tag{1.2.4}
\end{equation}
Converting back to a system of linear equations, we get
\begin{equation}
\begin{array}{ccccccc}
0x \amp + \amp 0y\amp -\amp (2/3)z\amp = \amp 0 \\
0x\amp + \amp 0y\amp -\amp (4/3)z\amp =\amp 0\\
0x\amp + \amp 0y\amp +\amp 0z\amp =\amp 1
\end{array}\tag{1.2.5}
\end{equation}
The last equation in this system clearly has no solutions. We conclude that this system (and the original system) is inconsistent.
Observation 1.2.13.
Note that the last row of the reduced row echelon form in (1.2.4) looks like this
\begin{equation*}
\left[\begin{array}{ccc|c}
0\amp 0\amp 0\amp 1
\end{array}\right]
\end{equation*}
This row corresponds to the equation
\begin{equation*}
\begin{array}{ccccccc}
0x\amp + \amp 0y\amp +\amp 0z\amp =\amp 1
\end{array}
\end{equation*}
which clearly has no solutions.
In general, if the reduced row echelon form of the augmented matrix contains a row
\begin{equation*}
\left[\begin{array}{ccc|c}
0\amp \ldots\amp 0\amp 1
\end{array}\right]
\end{equation*}
we can conclude that the system is inconsistent.
Observation 1.2.14.
So long as the reduced row echelon form of an augmented matrix does not contain a leading 1 in the last column, the system is consistent. Furthermore, if the reduced row echelon form has a leading 1 in every column except the last column, then the system has a unique solution. If the reduced row echelon form has a leading 1 in the last column, but not in every other column, then the system has infinitely many solutions.
We can interpret this observation in terms of the ranks of coefficient matrix and of the augmented matrix. If the rank of coefficient matrix is less than the rank of the augmented matrix, then there is a 1 in the last column of the augmented matrix and the system is inconsistent. If the two ranks are both equal to the number of original variables, i.e., there are no are free variables, then the system has a unique solution. If the two ranks are equal and less than the number of original varialbes, then the systhem has infinitely many solutions.
Exercises 1.2.4 Exercises
Exercise Group.
Determine whether each augmented matrix shown below is in reduced row echelon form.
1.
\begin{equation*}
\left[\begin{array}{cccc|c}
0\amp 1\amp 1\amp 0\amp 2\\1\amp -3\amp 0\amp 1\amp 4\\0\amp 0\amp 1\amp 0\amp -1
\end{array}\right]
\end{equation*}
- Yes
- No
2.
\begin{equation*}
\left[\begin{array}{cc|c}
1\amp 1\amp 1\\0\amp 1\amp 0\\0\amp 0\amp 0
\end{array}\right]
\end{equation*}
- Yes
- No
3.
\begin{equation*}
\left[\begin{array}{cc|c}
1\amp 0\amp 1\\0\amp 1\amp 0\\0\amp 0\amp 0
\end{array}\right]
\end{equation*}
- Yes
- No
4.
\begin{equation*}
\left[\begin{array}{ccc|c}
1\amp 0\amp 1\amp 0\\0\amp 1\amp 0\amp 0\\0\amp 0\amp 0\amp 1
\end{array}\right]
\end{equation*}
- Yes
- No
5.
\begin{equation*}
\left[\begin{array}{ccc|c}
1\amp 1\amp 0\amp 2\\0\amp 1\amp 0\amp 9\\0\amp 0\amp 1\amp -1
\end{array}\right]
\end{equation*}
- Yes
- No
6.
Show that applying Gauss-Jordan elimination to the matrix in Exploration 1.2.2 yields the same reduced row-echelon form as the matrix we obtained in Exploration 1.2.1.
Exercise Group.
Follow the indicated steps of the Gauss-Jordan algorithm to transform the matrix to its reduced row-echelon form.
\begin{equation*}
\left[\begin{array}{ccc|c} 2\amp 1\amp 1\amp 3\\-1\amp 0\amp 1\amp 2\\1\amp 1\amp -2\amp 0 \end{array}\right]
\end{equation*}
7.
\(\frac{1}{2}R_1\rightarrow R_1\)
Answer.
\begin{equation*}
\left[\begin{array}{ccc|c} 1\amp 1/2\amp 1/2\amp 3/2\\-1\amp 0\amp 1\amp 2\\1\amp 1\amp -2\amp 0 \end{array}\right]
\end{equation*}
8.
\(R_1+R_2\rightarrow R_2\)
Answer.
\begin{equation*}
\left[\begin{array}{ccc|c} 1\amp 1/2\amp 1/2\amp 3/2\\0\amp 1/2\amp 3/2\amp 7/2\\1\amp 1\amp -2\amp 0 \end{array}\right]
\end{equation*}
9.
\(R_3-R_1\rightarrow R_3\)
Answer.
\begin{equation*}
\left[\begin{array}{ccc|c} 1\amp 1/2\amp 1/2\amp 3/2\\0\amp 1/2\amp 3/2\amp 7/2\\0\amp 1/2\amp -5/2\amp -3/2 \end{array}\right]
\end{equation*}
10.
\(2R_2\rightarrow R_2\)
Answer.
\begin{equation*}
\left[\begin{array}{ccc|c} 1\amp 1/2\amp 1/2\amp 3/2\\0\amp 1\amp 3\amp 7\\0\amp 1/2\amp -5/2\amp -3/2 \end{array}\right]
\end{equation*}
11.
\(R_3-\frac{1}{2}R_2\rightarrow R_3\)
Answer.
\begin{equation*}
\left[\begin{array}{ccc|c}
1\amp 1/2\amp 1/2\amp 3/2\\0\amp 1\amp 3\amp 7\\0\amp 0\amp -4\amp -5
\end{array}\right]
\end{equation*}
12.
\(-\frac{1}{4}R_3\rightarrow R_3\)
Answer.
\begin{equation*}
\left[\begin{array}{ccc|c} 1\amp 1/2\amp 1/2\amp 3/2\\0\amp 1\amp 3\amp 7\\0\amp 0\amp 1\amp 5/4 \end{array}\right]
\end{equation*}
13.
\(R_2-3R_3\rightarrow R_2\)
Answer.
\begin{equation*}
\left[\begin{array}{ccc|c}
1\amp 1/2\amp 1/2\amp 3/2\\0\amp 1\amp 0\amp 13/4\\0\amp 0\amp 1\amp 5/4
\end{array}\right]
\end{equation*}
14.
\(R_1-\frac{1}{2}R_3\rightarrow R_1\)
Answer.
\begin{equation*}
\left[\begin{array}{ccc|c}
1\amp 1/2\amp 0\amp 7/8\\0\amp 1\amp 0\amp 13/4\\0\amp 0\amp 1\amp 5/4
\end{array}\right]
\end{equation*}
15.
\(R_1-\frac{1}{2}R_2\rightarrow R_1\)
Answer.
\begin{equation*}
\left[\begin{array}{ccc|c}
1\amp 0\amp 0\amp -3/4\\0\amp 1\amp 0\amp 13/4\\0\amp 0\amp 1\amp 5/4
\end{array}\right]
\end{equation*}
Exercise Group.
The following reduction steps do not follow the algorithm but are easier for a human to carry out because they use fewer fractions. Follow the indicated steps to transform the matrix to its reduced row-echelon form. Steps will unfold automatically as you enter correct answers.
\begin{equation*}
\left[\begin{array}{ccc|c} 2\amp 1\amp 1\amp 3\\-1\amp 0\amp 1\amp 2\\1\amp 1\amp -2\amp 0
\end{array}\right]
\end{equation*}
16.
\(R_1+R_2\rightarrow R_1\)
Answer.
\begin{equation*}
\left[\begin{array}{ccc|c}
1\amp 1\amp 2\amp 5\\-1\amp 0\amp 1\amp 2\\1\amp 1\amp -2\amp 0
\end{array}\right]
\end{equation*}
17.
\(R_2+R_3\rightarrow R_3\)
Answer.
\begin{equation*}
\left[\begin{array}{ccc|c}
1\amp 1\amp 2\amp 5\\-1\amp 0\amp 1\amp 2\\0\amp 1\amp -1\amp 2
\end{array}\right]
\end{equation*}
18.
\(R_1+R_2\rightarrow R_1\)
Answer.
\begin{equation*}
\left[\begin{array}{ccc|c}
0\amp 1\amp 3\amp 7\\-1\amp 0\amp 1\amp 2\\0\amp 1\amp -1\amp 2
\end{array}\right]
\end{equation*}
19.
\(R_1-R_3\rightarrow R_1\)
Answer.
\begin{equation*}
\left[\begin{array}{ccc|c}
0\amp 0\amp 4\amp 5\\-1\amp 0\amp 1\amp 2\\0\amp 1\amp -1\amp 2
\end{array}\right]
\end{equation*}
20.
\(\frac{1}{4}R_1\rightarrow R_1\) and \(-R_2\rightarrow R_2\)
Answer.
\begin{equation*}
\left[\begin{array}{ccc|c}
0\amp 0\amp 1\amp 5/4\\1\amp 0\amp -1\amp -2\\0\amp 1\amp -1\amp 2
\end{array}\right]
\end{equation*}
21.
\(R_1+R_2\rightarrow R_2\)
Answer.
\begin{equation*}
\left[\begin{array}{ccc|c}
0\amp 0\amp 1\amp 5/4\\1\amp 0\amp 0\amp -3/4\\0\amp 1\amp -1\amp 2
\end{array}\right]
\end{equation*}
22.
\(R_1+R_3\rightarrow R_3\)
Answer.
\begin{equation*}
\left[\begin{array}{ccc|c}
0\amp 0\amp 1\amp 5/4\\1\amp 0\amp 0\amp -3/4\\0\amp 1\amp 0\amp 13/4
\end{array}\right]
\end{equation*}
23.
Exchange rows.
Answer.
\(\left[\begin{array}{ccc|c}
1\amp 0\amp 0\amp -3/4\\0\amp 1\amp 0\amp 13/4\\0\amp 0\amp 1\amp 5/4
\end{array}\right]\)
24.
Fill in the steps that lead to the reduced row echelon form in Exploration 1.2.4.
25.
Fill in the steps that lead to the reduced row echelon form in Example 1.2.12.
26.
Suppose a system of equations has the following reduced row echelon form
\begin{equation*}
\left[\begin{array}{ccc|c}
1\amp 0\amp 0\amp 4\\0\amp 1\amp -3\amp -6\\0\amp 0\amp 0\amp 1
\end{array}\right]
\end{equation*}
What can you say about the system?
- The system is inconsistent
- The system has infinitely many solutions
- The system has a unique solution
- We would have to examine the original system to make the final determination
Exercise Group.
Solve each system of equations.
27.
\begin{equation*}
\begin{array}{ccccccc}
x \amp +\amp 3y\amp -\amp 2z\amp = \amp -11 \\
2x\amp +\amp y\amp +\amp 4z\amp =\amp 12\\
x\amp -\amp y\amp -\amp z\amp =\amp 0
\end{array}
\end{equation*}
Answer.
\begin{equation*}
( 1, -2, 3)
\end{equation*}
28.
\begin{equation*}
\begin{array}{ccccccc}
3x \amp -\amp y\amp +\amp z\amp = \amp -5 \\
x\amp +\amp 2y\amp -\amp z\amp =\amp -3\\
x\amp -\amp 5y\amp +\amp 3z\amp =\amp 1
\end{array}
\end{equation*}
Answer.
\begin{equation*}
\left( -13/7- 1/7t, -4/7 + 4/7t, t \right)
\end{equation*}
29.
Suppose a linear system has \(4\) equations and \(5\) unknowns. Which of the following is NOT a possibility?
- The system has a unique solution
- The system has no solutions
- The system has infinitely many solutions
30.
Suppose that we have two systems of linear equations, call them System X and System Y, both with their right hand sides all zeros. If they are equivalent systems, meaning that they have the same solution set, then must there be a (finite) sequence of elementary row operations to get from System X to System Y? Justify your answer.
Hint.
What can you say about reduced row echelon forms of the two coefficient matrices?
References 1.2.5 References
[1]
W. Keith Nicholson, Linear Algebra with Applications, Lyryx 2018, Open Edition, p 15-17.
[2]
Thomas Yuster, The Reduced Row Echelon Form of a Matrix is Unique: a Simple Proof, Mathematics Magazine, vol. 57, no. 2 (Mar. 1984), pp. 93-94.
