Lecture 2: Row Echelon Form

Shenghao Yang
Spring 2023

1 Solving n × n Systems
Strict Triangular System

Definition 1. An n × n system is said to be strict triangular if for k = 1, ..., n,

• in the kth equation, the coefficients of the first k − 1 variables are all zero, and
• the coefficient of xk is nonzero.
Example 1. Solve the system

2x1 − x2 + 3x3 − 0x4 = 1

x2 − 2x3 + 3x4 = 2
4x3 + 3x4 = 3
4x4 = 4.

Remark 1. The procedure for solving a strict triangular system is called back substitution.
Example 2. The system of equations

x1 + 2x2 + 2x3 = 4  
1 2 2 4
x1 + 3x2 + 3x3 = 5  1 3 3 5 
2x1 + 6x2 + 5x3 = 6 2 6 5 6

can be solved using the following steps:

1. Use the first row to eliminate the entries in the first column of the following rows (row operation
III):
   
1 2 2 4 R2 →R2 −R1 1 2 2 4
R3 →R3 −2R1
 1 3 3 5 − −−−−−−−→  0 1 1 1 
2 6 5 6 0 2 1 −2

2. Use the second row to eliminate the last entry in the second column (row operation III):
   
1 2 2 4 1 2 2 4
R3 →R3 −2R2  
 0 1 1 1  −−−−−−−−→  0 1 1 1 
0 2 1 −2 0 0 -1 −4

3. Solving x3 : multiply −1 to the third row

4. Solving x2 :    
1 2 2 4 R2 →R2 −R3 1 2 0 −4
  R1 →R1 −2R3  
 0 1 1 1  −−−−−−−−→  0 1 0 −3 
0 0 1 4 0 0 1 4

1
 5. Solving x1 :    
1 2 0 −4 1 0 0 2
  R1 →R1 −2R2  
 0 1 0 −3  −−−−−−−−→  0 1 0 −3 
0 0 1 4 0 0 1 4

In general, given a system of n linear equations in n unknowns, we can try to use equation operations
to obtain an equivalent system that is of a triangular type.

Solving a System of Linear Equations:

1. Perform a sequence of elementary row operations to reduce the augmented matrix to one of a
triangular type.
2. Solve the corresponding triangular-type system.
3. The coefficient matrix of the solved system is also called the identity matrix.

     
∗ ∗ ∗ ∗ ∗ ■ ∗ ∗ ∗ ∗ ■ ∗ ∗ ∗ ∗
 ∗ ∗ ∗ ∗ ∗   ∗ ∗ ∗ ∗   ■ ∗ ∗ ∗ 
 → 0 → 0 
 ∗ ∗ ∗ ∗ ∗   0 ∗ ∗ ∗ ∗   0 0 ∗ ∗ ∗ 
∗ ∗ ∗ ∗ ∗ 0 ∗ ∗ ∗ ∗ 0 0 ∗ ∗ ∗
 
■ ∗ ∗ ∗ ∗
 0 ■ ∗ ∗ ∗ 
→
 0

0 ■ ∗ ∗ 
0 0 0 ■ ∗

Figure 1: Here ■ represents a nonzero number, and ∗ represents an arbitrary number.

     
■ ∗ ∗ ∗ ∗ ■ ∗ ∗ 0 ∗ ■ ∗ 0 0 ∗
 0 ■ ∗ ∗ 
∗   0 ■ ∗ 0 
∗   0 ■ 0 0 ∗ 
 → → 
 0 0 ■ ∗ ∗   0 0 ■ 0 ∗   0 0 1 0 ∗ 
0 0 0 ■ ∗ 0 0 0 1 ∗ 0 0 0 1 ∗
 
1 0 0 0 ∗
 0 1 0 0 ∗ 
→
 0

0 1 0 ∗ 
0 0 0 1 ∗

Figure 2: Here ■ represents a nonzero number, and ∗ represents an arbitrary number.

2 Row-Echelon Form of a General Matrix

In this section, we study how to transform a general matrix to a triangular form, which is equivalent to
the process of solving a general system of linear equations.

Some Terms

• A nonzero row (resp. column) in a matrix means a row (resp. column) that contains a least one
nonzero entry.
• A leading entry of a nonzero row refers to the left most nonzero entry.
• A zero entry in a row in called a leading zero entry if all the entries on the left of the zero entry
are zero.

2
  
0 1 1 2
0 0 2 0
0 0 0 0
There is only one leading entry of a nonzero row, but there can be multiple leading zeros.
Definition 2. A matrix is said to be in row echelon form if
(i) If row k is nonzero, the number of leading zero entries of row k + 1 is greater than the number of
leading zero entries in row k.
(ii) If there are rows whose entries are all zero, they are below any nonzero rows.
Example 3. Matrices are in echelon form
 
  0 ■ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗
■ ∗ ∗ ∗ 0
0 0 0 ■ ∗ ∗ ∗ ∗ ∗ ∗
 ■ ∗ ∗,

0

0  0 0 0 ■ ∗ ∗ ∗ ∗ ∗
0 0 0 0 0 0 0 0 ■ ∗ ∗ ∗ ∗
0 0 0 0
0 0 0 0 0 0 0 0 ■ ∗

Example 4. The following matrices are not in row echelon form:

[ ] [ ]
0 0 0 0 1
, .
0 1 0 1 0

Remarks

• Leading entry and leading zero are defined for a general matrix, not necessarily in row echelon form.
The definition of row echelon form is given in terms of leading entries and leading zeros.
• General properties of a matrix in row echelon form
– Each non-zero row has a strictly increasing number of leading zeros than the previous row.
– Each non-zero row has one leading entry.
– Each column has at most one leading entry.
• We can use Elementary Row Operation I and III to transform any matrix to row echelon form.
This process is called Gaussian elimination.

Gaussian Elimination: Column I

• Find a non-zero entry in the first column, called a pivot.

– Pivots are entries of a matrix specified during the Gaussian elimination process.
– After Gaussian elimination, the matrix is in row echelon from and the pivots are also the
leading entries.
• If necessary, interchange rows so that the pivotal row (the row containing the pivot) is the first row.
• Apply row operations to eliminate all entries below the pivot.
   
∗ ∗ ∗ ∗ ∗ ■ ∗ ∗ ∗ ∗
 ■ ∗ ∗ ∗ ∗  R1 ↔R2  ∗ ∗ ∗ ∗ ∗ 
  −−−−−→  
 ∗ ∗ ∗ ∗ ∗   ∗ ∗ ∗ ∗ ∗ 
∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗ ∗
 
■ ∗ ∗ ∗ ∗
Ri ↔Ri −αi R1
 0 ∗ ∗ ∗ ∗ 
−−−−−−−−−→  
i=2,3,4
 0 ∗ ∗ ∗ ∗ 
0 ∗ ∗ ∗ ∗

3
Gaussian Elimination: Column II
• Find a pivot in the second column, below the first pivot row.
• If necessary, interchange rows so that the 2nd pivotal row is the 2nd row.
• Apply row operations to eliminate all entries below the pivot.
   
■ ∗ ∗ ∗ ∗ ■ ∗ ∗ ∗ ∗
 0 ∗ ∗ ∗ ∗  R2 ↔R3  0 ■ ∗ ∗ ∗ 
  −−−−−→  
 0 ■ ∗ ∗ ∗   0 ∗ ∗ ∗ ∗ 
0 ∗ ∗ ∗ ∗ 0 ∗ ∗ ∗ ∗
 
Ri ↔Ri −βi R2
■ ∗ ∗ ∗ ∗
 0 ■ ∗ ∗ ∗ 
−−−−−−−−−→  
i=3,4
 0 0 ∗ ∗ ∗ 
0 0 ∗ ∗ ∗

Gaussian Elimination: Special Case

• If no pivot can be found for a column, continue with the next column.
• The ith pivotal row is always the ith row after row interchanging.
   
0 ■ ∗ ∗ ∗ 0 ■ ∗ ∗ ∗
 0 ∗ ∗ ∗ ∗   0 0 ∗ ∗ ∗ 
 →
 0 ∗ ∗ ∗ ∗   0 0 ∗ ∗ ∗ 
0 ∗ ∗ ∗ ∗ 0 0 ∗ ∗ ∗
   
■ ∗ ∗ ∗ ∗ ■ ∗ ∗ ∗ ∗
 0 0 ■ ∗ ∗   0 0 ■ ∗ ∗ 
 → 
 0 0 ∗ ∗ ∗   0 0 0 ∗ ∗ 
0 0 ∗ ∗ ∗ 0 0 0 ∗ ∗

Further Observations
• It is not necessary that each column has a pivot.
• Each column can has at most one pivot.
[ ] [ ]
0 11 1 0 1
→
1 01 0 1 1
[ ] [ ]
0 1 1 0 1 1
→
0 2 1 0 0 −1
     
0 2 1 1 1 1
 0 1 →  0 1 →  0 1 
1 1 0 2 0 0

Transform the following matrices to row echelon form

 
2 1 7 −7 2
• −3 4 −5 −6 3
1 1 4 −5 2
 
−7 −6 −12 −33
• 5 5 7 24 
1 1 4 10
 
1 −1 2 1
• 2 1 1 8 
1 1 0 5

4
Gaussian Elimination for an m × n Matrix
• Initialize i = 1.
• For each j from 1 to n, repeat the following operations:
– Find a nonzero element as the pivot from the entries in the jth column, rows i through m, of
the matrix.
– If there exits no such a pivot found, continue with the next value of j (i.e., j + 1).
– If necessary, we interchange rows so that the pivotal row (the row containing the pivot) is the
ith row.
– Multiples of the pivotal row are then added to the rows i + 1 through m so as to eliminate all
entries below the pivot (in the jth column).
– Increase i by 1. If i > m, halt the process.
• After the process ends, the matrix is reduced to row echelon form.
A proof is deserved to show that a matrix is reduced to row echelon form by Gaussian elimination,
but omitted here. Try the above algorithm for the matrix in Example 5.
Example 5. Reduce the following matrix to row echelon form:
 
1 1 1 1 1
 −1 −1 0 0 1 
 
 −2 −2 0 0 3 
 
 0 0 1 1 3 
1 1 2 2 4
   
1 1 1 1 1 1 1 1 1 1
 −1 −1 0 0 1   1 
   0 0 1 2 
 −2 −2 0 0 3 → 
   0 0 2 2 5 
 0 0 1 1 3   0 0 1 1 3 
1 1 2 2 4 0 0 1 1 3
   
1 1 1 1 1 1 1 1 1 1
 0 0 1 1 2   0 0 1 1 2 
   
→
 0 0 0 0 1 →
  0 0 0 0 1 

 0 0 0 0 1   0 0 0 0 0 
0 0 0 0 1 0 0 0 0 0

3 Reduced Row-Echelon Form

Definition 3. If a matrix in row echelon form satisfies the following additional condition, the matrix is
said to be in reduced row echelon form:
(iii) The leading entry in each nonzero row is 1.
(iv) Each leading 1 is the only nonzero entry in its column.
Example 6. Matrices are in reduced row echelon form
 
  0 1 ∗ 0 0 0 ∗ ∗ 0 ∗
1 0 ∗ ∗ 0 0 0
 0 1 ∗ ∗  1 0 0 ∗ ∗ 0 ∗

   0 ∗ ∗ ∗
 0 0 0 0 ,  0 0 0 0 1 0 
0 0 0 0 0 1 ∗ ∗ 0 ∗
0 0 0 0
0 0 0 0 0 0 0 0 1 ∗
Example 7. The following matrices are in row echelon form, but not reduced row echelon form:
     
2 4 6 1 4 2 1 3 1 0
 0 3 5  ,  0 0 1 ,  0 0 1 3  .
0 0 4 0 0 0 0 0 0 0

5
Uniqueness of Reduced Row Echelon Form

• A matrix A is row equivalent to a unique matrix U of reduced row echelon form.

– Suppose A is row equivalent to U ′ in reduced row echelon form.

– U and U ′ are row equivalent.
– Show that two row-equivalent matrices in reduced row echelon form must be the same.
• A matrix A can be row equivalent to multiple matrices of row echelon form.
[ ] [ ] [ ]
1 1 1 1 1 0
→ →
2 3 0 1 0 1

• The process of using elementary row operations to transform a matrix into reduced row echelon
form is called Gaussian-Jordan elimination.

– Transform the matrix to row echelon form by Gaussian elimination.

– Perform backward substitution.
• Consider a matrix of the reduced row echelon form. The submatrix formed by the nonzero rows
and the columns with leading entries is an identity matrix, i.e., for all i, the (i, i) entry is 1, and
all other entries are 0.

Transform the following matrices to reduced row echelon form

 
1 1 4 −5 2
• 0 1 1 −3 2 
0 0 0 0 −5
 
1 1 4 10
• 0 1 16 37 
0 0 −13 −26
 
1 −1 2 1
• 0 1 −1 2
0 0 0 0

Gauss-Jordan Elimination

• Reduce an m × n matrix to row echelon form.

• For i from m down to 1, repeat the following operations:
– Find the leading entry in row i. If all entries in row i are 0, continue with the next value of i
(i.e., i − 1).
– Multiply the ith row by a constant so that the leading entry is 1.
– Multiples of row i is added to row 1 through row i − 1 so as to eliminate all the elements
above the leading entry of the ith row.
• When the process stops, the matrix is in reduced row echelon form.

Try the above algorithm for the matrix in Example 5.