Row Reduction and Echelon Forms

Any matrix satisfying properties P1 and P2 is said to be in row echelon form (REF). In
REF, the leftmost nonzero entry in a row is called a leading entry:
 
1 5 0 −2 −1 7 −4
 0 2 −2 0 0 3 0
 
 0 0 0 −9 −1 1 −1
 
0 0 0 0 5 1 5
0 0 0 0 0 0 0
A consequence of property P2 is that every entry below a leading entry is zero:
 
1 5 0 −2 −4 −1 −7
0 2 −2 0 0 3 0
 
0 0 0 −9 −1 1 −1
 
0 0 0 0 5 1 5
0 0 0 0 0 0 0
We can perform elementary row operations, or row reduction, to transform a matrix into
REF.

Example 2.1. Explain why the following matrices are not in REF. Use elementary row
operations to put them in REF.
   
3 −1 0 3 7 5 0 −3
M = 0 0 0 0 N = 0 3 −1 1 
0 1 3 0 0 6 −5 2
Solution. Matrix M fails property P1. To put M in REF we interchange R2 with R3 :
   
3 −1 0 3 3 −1 0 3
R ↔R3
M = 0 0 0 0 −−2−−→ 0 1 3 0
0 1 3 0 0 0 0 0
The matrix N fails property P2. To put N in REF we perform the operation −2R2 + R3 →
R3 :    
7 5 0 −3 7 5 0 −3
−2R2 +R3
0 3 −1 1  − −−−−→ 0 3 −1 1 
0 6 −5 2 0 0 −3 0

Why is REF useful? Certain properties of a matrix can be easily deduced if it is in REF.
For now, REF is useful to us for solving a linear system of equations. If an augmented matrix
is in REF, we can use back substitution to solve the system, just as we did in Lecture 1.
For example, consider the system

8x1 − 2x2 + x3 = 4
3x2 − x3 = 7
2x3 = 4

12
 Lecture 2

whose augmented matrix is already in REF:

 
8 −2 1 4
0 3 −1 7
0 0 2 4
From the last equation we obtain that 2x3 = 4, and thus x3 = 2. Substituting x3 = 2 into
the second equation we obtain that x2 = 3. Substituting x3 = 2 and x2 = 3 into the first
equation we obtain that x1 = 1.

2.2 Reduced row echelon form (RREF)

Although REF simplifies the problem of solving a linear system, later on in the course we
will need to completely row reduce matrices into what is called reduced row echelon form
(RREF). A matrix is in RREF if it is in REF (so it satisfies properties P1 and P2) and in
addition satisfies the following properties:

P3. The leading entry in each nonzero row is a 1.

P4. All the entries above (and below) a leading 1 are all zero.

A leading 1 in the RREF of a matrix is called a pivot. For example, the following matrix
in RREF:  
1 6 0 3 0 0
0 0 1 −4 0 5
0 0 0 0 1 7
has three pivots:  
1 6 0 3 0 0
0 0 1 −4 0 5
0 0 0 0 1 7

Example 2.2. Use row reduction to transform the matrix into RREF.
 
0 3 −6 6 4 −5
 3 −7 8 −5 8 9 
3 −9 12 −9 6 15
Solution. The first step is to make the top leftmost entry nonzero:
   
0 3 −6 6 4 −5 3 −9 12 −9 6 15
R3 ↔R1
3 −7 8 −5 8 9  − −−−→ 3 −7 8 −5 8 9 
3 −9 12 −9 6 15 0 3 −6 6 4 −5
Now create a leading 1 in the first row:
   
3 −9 12 −9 6 15 1
R1
1 −3 4 −3 2 5
3 −7 8 −5 8 9  −3−→ 3 −7 8 −5 8 9 
0 3 −6 6 4 −5 0 3 −6 6 4 −5

13
Row Reduction and Echelon Forms

Create zeros under the newly created leading 1:

   
1 −3 4 −3 2 5 1 −3 4 −3 2 5
−3R1 +R2
3 −7 8 −5 8 9  − −−−−→ 0 2 −4 4 2 −6
0 3 −6 6 4 −5 0 3 −6 6 4 −5

Create a leading 1 in the second row:

   
1 −3 4 −3 2 5 1
R2
1 −3 4 −3 2 5
0 2 −4 4 2 −6 −2−→ 0 1 −2 2 1 −3
0 3 −6 6 4 −5 0 3 −6 6 4 −5

Create zeros under the newly created leading 1:

   
1 −3 4 −3 2 5 1 −3 4 −3 2 5
−3R2 +R3
0 1 −2 2 1 −3 − −−−−→ 0 1 −2 2 1 −3
0 3 −6 6 4 −5 0 0 0 0 1 4

We have now completed the top-to-bottom phase of the row reduction algorithm. In the
next phase, we work bottom-to-top and create zeros above the leading 1’s. Create zeros
above the leading 1 in the third row:
   
1 −3 4 −3 2 5 1 −3 4 −3 2 5
−R3 +R2
0 1 −2 2 1 −3 − −−−−→ 0 1 −2 2 0 −7
0 0 0 0 1 4 0 0 0 0 1 4
   
1 −3 4 −3 2 5 1 −3 4 −3 0 −3
−2R3 +R1
0 1 −2 2 0 −7 − −−−−→ 0 1 −2 2 0 −7
0 0 0 0 1 4 0 0 0 0 1 4
Create zeros above the leading 1 in the second row:
   
1 −3 4 −3 0 −3 1 0 −2 3 0 −24
3R +R1
0 1 −2 2 0 −7 −−2−−→ 0 1 −2 2 0 −7 
0 0 0 0 1 4 0 0 0 0 1 4

This completes the row reduction algorithm and the matrix is in RREF.

Example 2.3. Use row reduction to solve the linear system.

2x1 + 4x2 + 6x3 = 8

x1 + 2x2 + 4x3 = 8
3x1 + 6x2 + 9x3 = 12

Solution. The augmented matrix is

 
2 4 6 8
1 2 4 8 
3 6 9 12

14
 Lecture 2

Create a leading 1 in the first row:

   
2 4 6 8 1
R1
1 2 3 4
1 2 4 8  −2−→ 1 2 4 8 
3 6 9 12 3 6 9 12
Create zeros under the first leading 1:
   
1 2 3 4 1 2 3 4
−R1 +R2
1 2 4 8 −−−−−→ 0
  0 1 4
3 6 9 12 3 6 9 12
   
1 2 3 4 1 2 3 4
−3R +R3
0 0 1 4  −−−1−−→ 0 0 1 4
3 6 9 12 0 0 0 0
The system is consistent, however, there are only 2 nonzero rows but 3 unknown variables.
This means that the solution set will contain 3 − 2 = 1 free parameter. The second row
in the augmented matrix is equivalent to the equation:

x3 = 4.

The first row is equivalent to the equation:

x1 + 2x2 + 3x3 = 4

and after substituting x3 = 4 we obtain

x1 + 2x2 = −8.

We now must choose one of the variables x1 or x2 to be a parameter, say t, and solve for the
remaining variable. If we set x2 = t then from x1 + 2x2 = −8 we obtain that

x1 = −8 − 2t.

We can therefore write the solution set for the linear system as
x1 = −8 − 2t
x2 = t (2.1)
x3 = 4
where t can be any real number. If we had chosen x1 to be the parameter, say x1 = t,
then the solution set can be written as
x1 = t
x2 = −4 − 12 t (2.2)
x3 = 4

Although (2.1) and (2.2) are two different parameterizations, they both give the same solution
set.

15
Row Reduction and Echelon Forms

In general, if a linear system has n unknown variables and the row reduced augmented
matrix has r leading entries, then the number of free parameters d in the solution set is

d = n − r.

Thus, when performing back substitution, we will have to set d of the unknown variables
to arbitrary parameters. In the previous example, there are n = 3 unknown variables and
the row reduced augmented matrix contained r = 2 leading entries. The number of free
parameters was therefore
d = n − r = 3 − 2 = 1.
Because the number of leading entries r in the row reduced coefficient matrix determine the
number of free parameters, we will refer to r as the rank of the coefficient matrix:

r = rank(A).

Later in the course, we will give a more geometric interpretation to rank(A).

Example 2.4. Solve the linear system represented by the augmented matrix
 
1 −7 2 −5 8 10
0 1 −3 3 1 −5
0 0 0 1 −1 4

Solution. The number of unknowns is n = 5 and the augmented matrix has rank r = 3
(leading entries). Thus, the solution set is parameterized by d = 5 − 3 = 2 free variables,
call them t and s. The last equation of the augmented matrix is x4 − x5 = 4. We choose x5
to be the first parameter so we set x5 = t. Therefore, x4 = 4 + t. The second equation of
the augmented matrix is
x2 − 3x3 + 3x4 + x5 = −5

and the unassigned variables are x2 and x3 . We choose x3 to be the second parameter, say
x3 = s. Then

x2 = −5 + 3x3 − 3x4 − x5
= −5 + 3s − 3(4 + t) − t
= −17 − 4t + 3s.

We now use the first equation of the augmented matrix to write x1 in terms of the other
variables:

x1 = 10 + 7x2 − 2x3 + 5x4 − 8x5

= 10 + 7(−17 − 4t + 3s) − 2s + 5(4 + t) − 8t
= −89 − 31t + 19s

16
 Lecture 2

Thus, the solution set is

x1 = −89 − 31t + 19s

x2 = −17 − 4t + 3s
x3 =s
x4 =4+t
x5 =t

where t and s are arbitrary real numbers.. Choose arbitrary numbers for t and s and
substitute the corresponding list (x1 , x2 , . . . , x5 ) into the system of equations to verify that
it is a solution.

2.3 Existence and uniqueness of solutions

The REF or RREF of an augmented matrix leads to three distinct possibilities for the
solution set of a linear system.

Theorem 2.5: Let [A b] be the augmented matrix of a linear system. One of the following
distinct possibilities will occur:

1. The augmented matrix will contain an inconsistent row.

2. All the rows of the augmented matrix are consistent and there are no free parameters.

3. All the rows of the augmented matrix are consistent and there are d ≥ 1 variables
that must be set to arbitrary parameters

In Case 1., the linear system is inconsistent and thus has no solution. In Case 2., the linear
system is consistent and has only one (and thus unique) solution. This case occurs when
r = rank(A) = n since then the number of free parameters is d = n − r = 0. In Case 3., the
linear system is consistent and has infinitely many solutions. This case occurs when r < n
and thus d = n − r > 0 is the number of free parameters.

After this lecture you should know the following:

• what the REF is and how to compute it
• what the RREF is and how to compute it
• how to solve linear systems using row reduction (Practice!!!)
• how to identify when a linear system is inconsistent
• how to identify when a linear system is consistent
• what is the rank of a matrix
• how to compute the number of free parameters in a solution set
• what are the three possible cases for the solution set of a linear system (Theorem 2.5)

17
Row Reduction and Echelon Forms

18
 Lecture 3

Lecture 3

Vector Equations

In this lecture, we introduce vectors and vector equations. Specifically, we introduce the
linear combination problem which simply asks whether it is possible to express one vector
in terms of other vectors; we will be more precise in what follows. As we will see, solving
the linear combination problem reduces to solving a linear system of equations.

3.1 Vectors in Rn
Recall that a column vector in Rn is a n × 1 matrix. From now on, we will drop the
“column” descriptor and simply use the word vectors. It is important to emphasize that a
vector in Rn is simply a list of n numbers; you are safe (and highly encouraged!) to forget
the idea that a vector is an object with an arrow. Here is a vector in R2 :
 
3
v= .
−1

Here is a vector in R3 :  
−3
v =  0 .
11

Here is a vector in R6 : 
9
0
 
−3
 6 .
v= 
 
0
3
To indicate that v is a vector in Rn , we will use the notation v ∈ Rn . The mathematical
symbol ∈ means “is an element of”. When we write vectors within a paragraph, we willwrite

−1
them using list notation instead of column notation, e.g., v = (−1, 4) instead of v = .
4

19
Vector Equations

We can add/subtract vectors, and multiply vectors by numbers or scalars. For example,
here is the addition of two vectors:
     
0 4 4
−5 −3 −8
  +   =  .
9 0 9
2 1 3
And the multiplication of a scalar with a vector:
   
1 3
3 −3 = −9 .
5 15
And here are both operations combined:
         
4 −2 −8 −6 −14
−2 −8 + 3  9  =  16  +  27  =  43  .
3 4 −6 12 6
These operations constitute “the algebra” of vectors. As the following example illustrates,
vectors can be used in a natural way to represent the solution of a linear system.

Example 3.1. Write the general solution in vector form of the linear system represented
by the augmented matrix
 
  1 −7 2 −5 8 10
A b = 0 1 −3 3 1 −5
0 0 0 1 −1 4
Solution. The number of unknowns is n = 5 and the associated coefficient matrix A has
rank r = 3. Thus, the solution set is parametrized by d = n − r = 2 parameters. This
system was considered in Example 2.4 and the general solution was found to be

x1 = −89 − 31t1 + 19t2

x2 = −17 − 4t1 + 3t2
x3 = t2
x4 = 4 + t1
x5 = t1

where t1 and t2 are arbitrary real numbers. The solution in vector form therefore takes the
form          
x1 −89 − 31t1 + 19t2 −89 −31 19
x2   −17 − 4t1 + 3t2  −17  −4  3
         
x3  =  t2
x=    =  0  + t1  0  + t2  1 
      
x4   4 + t1   4   1  0
x5 t1 0 1 0

20