Skip to main content
Logo image

Coordinated Linear Algebra

Anna Davis, Paul Zachlin, Allan Donsig, Levi Heath, Mikkel Munkholm

🔗

Section 2.3 Gaussian Elimination and Rank

🔗

Subsection 2.3.1 Row Echelon and Reduced Row Echelon Forms

🔗
In Section 2.2, we learned to write linear systems in augmented matrix form and use elementary row operations to transform an augmented matrix to row-echelon form and the reduced row-echelon form in order to solve linear systems.
🔗
🔗
Recall that a matrix (or augmented matrix) is 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.
🔗
A matrix in row-echelon form is said to be in reduced row-echelon form if it has the following additional properties
  • Each leading entry is a 1
  • All entries above each leading 1 are 0
🔗
Matrices in row-echelon form and reduced row-echelon form are ``convenient" because their corresponding systems of equations are easy to solve.
🔗
In this module we turn to the question of existence and uniqueness of the two echelon forms. Can every matrix (augmented matrix) be carried to a row-echelon form? If so, is the row-echelon form unique? Can every matrix be reduced to a reduced row-echelon form? If so, is the reduced row-echelon form unique? The answers we find will have long-lasting implications.
🔗

Exploration 2.3.1.

🔗
🔗
Solve the following system of equations.
x+2y−3z=1−5x+2y−3z=1x−2y+z=1
🔗
We create an augmented matrix corresponding to the system and apply row operations until the matrix is in row-echelon form.
[12−31−52−311−211]→R2+5R1→R3−R1[12−31012−1860−440]→R3+13R2
(2.3.1)[12−31012−18600−22]
🔗
Note that the elementary row operations that lead to (2.3.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.
[12−31−52−311−211]→R1↔R3[1−211−52−3112−31]
🔗
Next we would reduce this matrix to row-echelon form, perhaps in this way:
[1−211−52−3112−31]→R2+5R1→R3−R1[1−2110−82604−40]→R3+12R2
(2.3.2)[1−2110−82600−33]
🔗
The augmented matrices in (2.3.1) and (2.3.2) are clearly not the same, but both are in row-echelon form. If we write the systems of equations corresponding to (2.3.1) and (2.3.2), we can employ back substitution to solve them. The matrix in (2.3.1) corresponds to
x+2y−3z=112y−18z=6−2z=2
🔗
The matrix in (2.3.2) corresponds to
x−2y+z=1−8y+2z=6−3z=3
🔗
Because both systems are equivalent to the original system, it is not surprising that back substitution yields the same solution for both systems.
x=0,y=−1,z=−1
x=0,y=−1,z=−1
x=0,y=−1,z=−1
🔗
It is clear from Exploration 2.3.1 that a row-echelon form corresponding to a matrix is not unique. But what about the reduced row-echelon form?
🔗

Exploration 2.3.2.

🔗
🔗
In this problem we revisit the system
x+2y−3z=1−5x+2y−3z=1x−2y+z=1
🔗
Following the steps we took to get (2.3.1), but taking the process a little further, we get the reduced row-echelon form.
[12−31−52−311−211]→R2+5R1→R3−R1[12−31012−1860−440]→R3+13R2
[12−31012−18600−22]→112R2→−12R3[12−3101−3212001−1]→R1+3R3→R2+32R3
(2.3.3)[120−2010−1001−1]→R1−2R2[1000010−1001−1]
🔗
Do you think it is possible to start with (2.3.2) and obtain the same reduced row-echelon form? Try to justify your response. If possible, find the elementary row operations that take (2.3.2) to the reduced row-echelon form in (2.3.3).
[12−31−52−311−211]→R1↔R3[1−211−52−3112−31]
→R2+5R1→R3−R1[1−2110−82604−40]→R3+12R2
[1−2110−82600−33]⇝Elementary⇝Row Ops.[1000010−1001−1]
🔗
You will be asked to fill in the elementary row operations in Exercise 2.3.4.1.
🔗
Our observations in Exploration 2.3.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.
🔗
A proof of this result can be found in [2.3.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 5.3.6.
🔗

Subsection 2.3.2 Gaussian and Gauss-Jordan Elimination

🔗

Definition 2.3.2. 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:
🔗
Gaussian Algorithm guarantees that every matrix will have a row-echelon form.

Example 2.3.4.

Use the Gaussian Algorithm to find a row-echelon form of A if
A=[2412−1135]
Answer.
Following Step 2, we choose the first entry, 2, as our pivot. We then perform step 3, using the top row to get zeros in all entries below the 2.
[2412−1135]→R2−(1/2)R1→R3+(1/2)R1→R4−(3/2)R1[2400030−1]
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.
[2400030−1]→R2↔R3[2403000−1]→R4+13R2[24030000]
This time the algorithm terminates since row 3 and row 4 are zero rows.
🔗

Definition 2.3.5. 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 the reduced row-echelon form. For example, continuing with Example 2.3.4, we can start where we left off and compute rref(A). From our earlier computations we have:
[24−113512]⇝[24030000]
🔗
Now we create leading 1′s and use them to to wipe out all non-zero entries above them.
[24030000]→(1/2)R1→(1/3)R2[12010000]→R1−2R2[10010000]=rref(A)
🔗
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.
🔗
The algorithm is an essential tool in linear algebra. An fully detailed example is provided below.

Example 2.3.7.

Use the Gauss-Jordan Algorithm to solve the system
3x+y+7z=75x+3y+9z=132x+y+4z=5
Answer.
[3177539132145]→13R1[11/37/37/3539132145]→R2−5R1[11/37/37/304/3−8/34/32145]→R3−2R1[11/37/37/304/3−8/34/301/3−2/31/3]→34R2[11/37/37/301−2101/3−2/31/3]→R3−13R2[11/37/37/301−210000]→R1−13R2[103201−210000]
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.
x+3z=2y−2z=1
The solution is
x=2−3t,y=1+2t,z=t.
🔗
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 2.3.7 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 2.3.3 Rank

🔗
This section is an adaptation of Section 1.2 of Keith Nicholson’s Linear Algebra with Applications
 1 
open.umn.edu/opentextbooks/textbooks/linear-algebra-with-applications
.
🔗
As stated in Theorem 2.3.1, the reduced row-echelon form of a matrix A is uniquely determined by A. That is, no matter which series of row operations is used to transform A to its reduced row-echelon matrix, the result will always be the same matrix. In contrast, this is not true for row-echelon matrices: different sequences of row operations can transform the same matrix A to different row-echelon matrices. However, it is true that the number r of nonzero rows must be the same in each of these row-echelon matrices, as we will see in Theorem Definition 5.3.7. Hence, the number r depends only on A and not on the way in which A is carried to row-echelon form.

Example 2.3.8.

🔗

Definition 2.3.9.

🔗
The rank of matrix A, denoted by rank(A), is the number of nonzero rows that remain after we reduce A to row-echelon form by elementary row operations.
🔗
The rank a notion connected closely to the existence of solutions and other more nuanced notions emerging later on. We provide an example on how to compute it.

Example 2.3.10.

Compute the rank of
A=[11−14213001−58]
Answer.
A reduction of A to row-echelon form is
A=[11−14213001−58]⇝[11−140−15−80000]
Because the row-echelon form has two nonzero rows, rank(A)=2.

Proof.

The fact that the rank of the coefficient matrix is r means that there are exactly r leading variables in the coefficient matrix, and hence exactly n−r nonleading variables. The nonleading variables are called free variables. All free variables are assigned parameters, so the set of solutions involves exactly n−r parameters. Hence if r<n, there is at least one parameter, and so infinitely many solutions. If r=n, there are no parameters and the resulting solution is unique.
🔗
🔗
Theorem 2.3.11 shows that, for any system of linear equations, exactly three possibilities exist:
  1. Unique solution. This occurs when every variable is a leading variable.
  2. Infinitely many solutions. This occurs when the system is consistent and there is at least one nonleading variable, so at least one parameter is involved.
  3. No solution. This occurs when a row [00…01] appears in the row-echelon form. Such a row corresponds to an equation with no solutions. (See Example 2.2.5.)
🔗

Exercises 2.3.4 Exercises

🔗

Exercise Group.

🔗
🔗
Follow the indicated steps of the Gauss-Jordan algorithm to transform the matrix to its reduced row-echelon form.
[2113−101211−20]
🔗
2.
🔗
12R1→R1
Answer.
[11/21/23/2−101211−20]
🔗
3.
🔗
R1+R2→R2
Answer.
[11/21/23/201/23/27/211−20]
🔗
4.
🔗
R3−R1→R3
Answer.
[11/21/23/201/23/27/201/2−5/2−3/2]
🔗
5.
🔗
2R2→R2
Answer.
[11/21/23/2013701/2−5/2−3/2]
🔗
6.
🔗
R3−12R2→R3
Answer.
[11/21/23/2013700−4−5]
🔗
7.
🔗
−14R3→R3
Answer.
[11/21/23/201370015/4]
🔗
8.
🔗
R2−3R3→R2
Answer.
[11/21/23/201013/40015/4]
🔗
9.
🔗
R1−12R3→R1
Answer.
[11/207/801013/40015/4]
🔗
10.
🔗
R1−12R2→R1
Answer.
[100−3/401013/40015/4]
🔗

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.
[2113−101211−20]
🔗
11.
🔗
R1+R2→R1
Answer.
[1125−101211−20]
🔗
12.
🔗
R2+R3→R3
Answer.
[1125−101201−12]
🔗
13.
🔗
R1+R2→R1
Answer.
[0137−101201−12]
🔗
14.
🔗
R1−R3→R1
Answer.
[0045−101201−12]
🔗
15.
🔗
14R1→R1 and −R2→R2
Answer.
[0015/410−1−201−12]
🔗
16.
🔗
R1+R2→R2
Answer.
[0015/4100−3/401−12]
🔗
17.
🔗
R1+R3→R3
Answer.
[0015/4100−3/401013/4]
🔗
18.
🔗
Exchange rows.
Answer.
[100−3/401013/40015/4]
🔗

Exercise Group.

🔗
Find the rank of each matrix.
🔗
19.
🔗
A=[43−1−8−62]
Answer.
rank(A)=1
🔗
20.
🔗
B=[112−23−1]
Answer.
rank(B)=2
🔗
21.
🔗
C=[10121301−2]
Answer.
rank(C)=3
🔗
22.
🔗
D=[112−1−21105]
Answer.
rank(D)=2
🔗

23.

    🔗
    Suppose A is a 5×7 matrix. Which of the following can be true?
  • rank(A)=7
  • rank(A)=6
  • rank(A)=5
  • All of the above
🔗

24.

    🔗
    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
🔗

25.

    🔗
    Suppose A is a matrix such that rref(A) has 5 leading 1′s. What do we know to be true about A? Select ALL that apply.
  • rank(A)=5
  • A has at least 25 entries
  • Any row-echelon form of A will have exactly 5 nonzero rows
  • Some row-echelon forms of A may have more than 5 nonzero rows
  • Some row-echelon forms of A may have less than 5 nonzero rows
🔗

26.

🔗
🔗
In this problem we will discuss how the rank of the coefficient matrix associated with a linear system compares to the rank of the augmented matrix associated with the system.
  1. Explain why the rank of the augmented matrix has to be greater than or equal to the rank of the coefficient matrix.
  2. Prove that for a consistent system the rank of the coefficient matrix will be the same as the rank of the augmented matrix.
  3. Give an example of an inconsistent system for which the rank of the augmented matrix is greater than the rank of the coefficient matrix.
  4. Can the rank of an augmented matrix be greater than the number of variables?
  5. Is the following statement true?
    “If the rank of the augmented matrix associated with a linear system is greater than the rank of the coefficient matrix, then the system is inconsistent.”
🔗

References 2.3.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.
PrevTopNext