Echelon forms Solutions of linear systems from reduced echelon forms Row reduction algorithm Summary

MATH 4A - Linear Algebra with Applications

Lecture 2: Row reduction and echelon forms

3 April 2019

Reading: §1.2-1.4 from Lay, 5th ed.

Recommended problems from §1.2: 1, 2, 3, 7, 11, 13, 15, 17, 21,
22, 25
Echelon forms Solutions of linear systems from reduced echelon forms Row reduction algorithm Summary

Lecture plan

1 Echelon forms

2 Solutions of linear systems from reduced echelon forms

3 Row reduction algorithm

4 Summary
Echelon forms Solutions of linear systems from reduced echelon forms Row reduction algorithm Summary

Motivation

Last time, we converted a linear system to a matrix (its

augmentation matrix). We described how to solve the linear system
in terms of row operations. The motto was “replace & eliminate.”

Goal today: make our “target” for the “replace & eliminate”
motto more precise by finding a canonical form for linear systems
called reduced row echelon form. This will result in an algorithm
that decides if a linear system is consistent, and, if so, describes
the entire set of solutions.
Echelon forms Solutions of linear systems from reduced echelon forms Row reduction algorithm Summary

Leading entries

A leading entry of a row in a matrix is the first nonzero entry

(from the left) of that row, e.g. the leading entries of
 
0 0 0 1
8 3 0 0
 
0 2 0 0
0 0 0 0

are 1, 8 and 2.

If the row is all 0s, then it doesn’t have a leading entry.

Echelon forms Solutions of linear systems from reduced echelon forms Row reduction algorithm Summary

Echelon form

A matrix is in echelon form if it has the following three properties:

1 Any rows that are entirely 0s are at the bottom.
2 Every leading entry of a nonzero row is to the right of the
leading entries above it.
3 All entries in a column below a leading entry are 0s.
A matrix in echelon form is sometimes called an echelon matrix.

“Echelon” comes from the French for “ladder rung.” This is apt
because an echelon matrix kind of looks like a ladder.
Echelon forms Solutions of linear systems from reduced echelon forms Row reduction algorithm Summary

Example

The matrices
 
0 0 0 1      
8 3 0 0 0 1 0 0 0
 
0 2 0 0 1 0 0 10 10
0 0 0 0

are not in echelon form, but the matrices

 
8 3 0 0    
0 2 0 0 1 0 0 10


0 0 0 1
 0 10
0 1 0 0
0 0 0 0

are echelon matrices.

Echelon forms Solutions of linear systems from reduced echelon forms Row reduction algorithm Summary

iClicker

Which of the following matrices are in echelon form?

(a) 10 52 38 0 1
 
10 52 38 0 1
(b)
0 23 1 0 0
 
10 52 38 0 1
(c)  0 0 1 0 0
0 23 1 0 0
 
10 52 38 0 1
10 52 38 0 1
(d) 
 0 23 1 0 0


0 23 1 0 0
(e) (a) and (b)
Echelon forms Solutions of linear systems from reduced echelon forms Row reduction algorithm Summary

Every matrix can be put in echelon form using row

operations

Just start at the top left corner and subtract off nonzero entries
below the leading entry, swap 0 rows to the bottom as necessary,
then move on to the next leading entry and repeat e.g.
   
10 52 38 0 1 10 52 38 0 1
10 52 38 0 1 R2 7→R2 −R1  0 0 0 0 0
 0 23 1 0 0 −−−−−−−→  0 23 1 0 0
   

0 23 1 0 0 0 23 1 0 0
   
10 52 38 0 1 10 52 38 0 1
R2 ↔R4  0 23 1 0 0  R3 ↔R3 −R2  0 23 1 0 0
 
−− −−→  0 23 1 0 0 −−−−−−−→  0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
Echelon forms Solutions of linear systems from reduced echelon forms Row reduction algorithm Summary

However, a matrix can have many echelon forms

e.g.  
10 52 38 0 1
10 52 38 0 1
 
0 23 1 0 0
0 23 1 0 0
is row equivalent to both of the echelon matrices
   
10 52 38 0 1 10 75 39 0 1
 0 23 1 0 0  0 23 1 0 0

0 0 0 and  
0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
Echelon forms Solutions of linear systems from reduced echelon forms Row reduction algorithm Summary

Reduced echelon form

An echelon matrix is in reduced echelon form if the following is

also true:
1 The leading entry of every nonzero row is 1.
2 Each leading 1 is the only nonzero entry in its column.
Echelon forms Solutions of linear systems from reduced echelon forms Row reduction algorithm Summary

Examples

 
  0 1 10 0 0 0 420 8 0 10
1 0 −3 2
0
0 0 0 1 0 0 −1 0 0 0 
1 5921 0  

0
 0 0 0 0 1 0 −3 −1 0 0 
0 0 0 
0

0 0 0 0 1 1 0 0 0 
0 0 0 0
0 0 0 0 0 0 0 0 1 −420

Non-examples: on the previous slides, there’s exactly one matrix in

reduced row echelon form; so all of the rest are non-examples.
Echelon forms Solutions of linear systems from reduced echelon forms Row reduction algorithm Summary

Today’s most important slide

Theorem
Every matrix is row equivalent to a unique reduced echelon matrix.
If A is a matrix, and U is the reduced echelon matrix row
equivalent to A, we call U the reduced echelon form of A.

This theorem really says two things:

1 every matrix is row equivalent to some reduced echelon
matrix, AND
2 that is the only such reduced echelon matrix.
In other words, the theorem is both an existence statement (a
reduced echelon form exists) and a uniqueness statement (there is
only one reduced echelon form). To prove the theorem, you would
have to prove both statements separately. We’ll prove the
existence statement later today, but not the uniqueness statement.
Echelon forms Solutions of linear systems from reduced echelon forms Row reduction algorithm Summary

Why is the theorem so important?

As we will see at the end of class, the proof of the “existence part”
of the theorem is algorithmic: given any matrix A, we can follow a
specific set of instructions that provides a sequence of row
operations that puts A in its reduced echelon form U.

Once we have U, it is easy to describe the solution set (to both U

and A, since they are equivalent), as we will see momentarily.
Echelon forms Solutions of linear systems from reduced echelon forms Row reduction algorithm Summary

First: consistency can be determined from any echelon

form

Let A be a matrix, thought of as the augmentation matrix of a

linear system, and let E be any echelon form of A (E could be the
unique reduced echelon matrix U, but doesn’t have to be).
Theorem
The linear system described by A is consistent if and only if E does
not have any row of the form


0 0 ··· 0 b

where b 6= 0.
Echelon forms Solutions of linear systems from reduced echelon forms Row reduction algorithm Summary

If A is consistent, why can’t such a row exist?

Suppose A is an m × (n + 1) matrix, so that A is the augmented
matrix of a linear system with n variables x1 , x2 , . . . , xn and m
equations.
If E did have a row


0 0 ··· 0 b

where b 6= 0, then this would say the linear system associated to A

is equivalent to a linear system involving the equation

0 · x1 + 0 · x2 + · · · 0 · xn = b,

which forces b = 0.
But we said b 6= 0, which means A is inconsistent!
Thus, if A is consistent,

then E can’t have a row of the form
0 0 · · · 0 b for some b 6= 0. (This proves “half” of the
theorem. The other “half” will follow from the rest of today’s
discussion.)
Echelon forms Solutions of linear systems from reduced echelon forms Row reduction algorithm Summary

Some jargon: pivots

A pivot position in the matrix A is a location in A that corresponds

to a leading 1 in the reduced echelon form of A. A pivot column is
a column of A that contains a pivot position.
Echelon forms Solutions of linear systems from reduced echelon forms Row reduction algorithm Summary

iClicker
Consider the matrices
   
0 −3 −6 4 9 1 4 5 −9 −7
−1 −2 −1 3 1 0 2 4 −6 −6
A= −2 −3 0
 and E =  ,
3 −1 0 0 0 −5 0 
1 4 5 −9 −7 0 0 0 0 0

which is an (unreduced) echelon matrix. Note that A is row

equivalent to E . What is the entry of A at the pivot position for
the third pivot column?
(a) 0
(b) 3
(c) -2
(d) -3
(e) -5
Echelon forms Solutions of linear systems from reduced echelon forms Row reduction algorithm Summary

Some more jargon: pivots and variables

Recall that if a m × (n + 1) matrix A is the augmented matrix of a

linear system in the n variables x1 , x2 , . . . , xn , then each of the first
n columns of A corresponds to one of the variables.

If the i th column of A is a pivot column of A, we say xi is a basic

variable. Any variable whose column is not a pivot column is called
a free variable.
Echelon forms Solutions of linear systems from reduced echelon forms Row reduction algorithm Summary

Example

Using the matrices from before:

   
0 −3 −6 4 9 1 4 5 −9 −7
−1 −2 −1 3 1  0 2 4 −6 −6
A= −2 −3 0 and E =  ,
3 −1 0 0 0 −5 0 
1 4 5 −9 −7 0 0 0 0 0

we see that the basic variables of A are x1 , x2 and x4 . The only

free variable is x3 .
Echelon forms Solutions of linear systems from reduced echelon forms Row reduction algorithm Summary

Solutions of linear systems in reduced echelon form

It is easy to write down the set of solutions to any consistent linear

system that is in reduced echelon form, e.g. let
 
1 0 −5 1
U = 0 1 1 4  .
0 0 0 0

(Note that U is, in fact, consistent.)

Let’s write down the associated system of equations:

x1 − 5x3 = 1
x2 + x3 = 4
0=0
Echelon forms Solutions of linear systems from reduced echelon forms Row reduction algorithm Summary

We can toss out the 0 = 0 equation because it doesn’t matter:

x1 − 5x3 = 1
x2 + x3 = 4

Because U is in reduced echelon form, each of these equations

contains precisely one basic variable. So, in each equation, we
solve for the basic variable in terms of the free variables:
x1 = 5x3 + 1
x2 = −x3 + 4.

Now we know all of the solutions to U: x3 is a free variable, so it

can be any real number. x1 and x2 , on the other hand, each
depend on x3 according to the equations above.
Echelon forms Solutions of linear systems from reduced echelon forms Row reduction algorithm Summary

We write our final description of the solutions to U as follows:


x3 is free

x1 = 5x3 + 1

x2 = −x3 + 4.


Given any matrix in reduced echelon form, we can apply these

same rules to determine the solution set.
Echelon forms Solutions of linear systems from reduced echelon forms Row reduction algorithm Summary

Another example
Let  
1 6 0 3 0 0
U = 0 0 1 −4 0 5 .
0 0 0 0 1 7
The associated linear system is
x1 + 6x2 + 3x4 = 0
x3 − 4x4 = 5.
x5 = 7
We solve this as follows:



 x2 , x4 are free

x = −6x − 3x
1 2 4


 x3 = 4x4 + 5

x = 7.
5
Echelon forms Solutions of linear systems from reduced echelon forms Row reduction algorithm Summary

Free variables imply infinitely many solutions

Theorem
Every consistent linear system falls into exactly one of the
following two cases:
1 the system has no free variables. In this case, the system has
a unique solution.
2 the system has at least one free variable. In this case, the
system has infinitely many solutions.
Echelon forms Solutions of linear systems from reduced echelon forms Row reduction algorithm Summary

iClicker

Consider the echelon matrix

 
1 4 5 −9 −7
0 2 4 −6 −6
E = 
0 0 0 −5 0 
0 0 0 0 0

How many solutions does the associated linear system have?

(a) 0, because it is inconsistent
(b) 1, because there are no free variables
(c) 1, because there is one free variable
(d) 2, because there are two free variables
(e) infinitely many, because there are some free variables
Echelon forms Solutions of linear systems from reduced echelon forms Row reduction algorithm Summary

Summarizing so far

We have shown how to solve linear systems in reduced echelon

form, and we know–in theory—that every linear system has a
reduced echelon form.

Thus, to solve arbitrary linear systems, we just need to describe

how to put matrices in reduced echelon form.

We basically already did this yesterday, but let’s spell it out a little
more carefully.
Echelon forms Solutions of linear systems from reduced echelon forms Row reduction algorithm Summary

Begin with the leftmost nonzero column; the pivot position

is at the top.

We’ll apply the algorithm to the matrix:

 
0 3 −6 6 4 −5
3 −7 8 −5 8 9 
3 −9 12 −9 6 15

It’s first nonzero column is the first column

 
0
3 .
3
Echelon forms Solutions of linear systems from reduced echelon forms Row reduction algorithm Summary

Select a nonzero entry in the column as a pivot, and, if

necessary, swap rows to put the entry at the pivot position.

The pivot position might have a 0 entry, which is why we must

perform this step.
   
0 3 −6 6 4 −5 3 −9 12 −9 6 15
R1 ↔R3
3 −7 8 −5 8 9  − −−−→ 3 −7 8 −5
 8 9
3 −9 12 −9 6 15 0 3 −6 6 4 −5
Echelon forms Solutions of linear systems from reduced echelon forms Row reduction algorithm Summary

Use row replacement to clear all of the entries below the

pivot

   
3 −9 12 −9 6 15 3 −9 12 −9 6 15
R2 7→R2 −R1
3 −7 8 −5 8 9  − −−−−−−→ 0 2 −4 4 2 −6
0 3 −6 6 4 −5 0 3 −6 6 4 −5
Echelon forms Solutions of linear systems from reduced echelon forms Row reduction algorithm Summary

Move on to the next nested submatrix, and repeat the

previous steps. Do this until there aren’t any more
submatrices.

Apply the previous steps to the submatrix

 
2 −4 4 2 −6
3 −6 6 4 −5

in  
3 −9 12 −9 6 15
0 2 −4 4 2 −6 .
0 3 −6 6 4 −5
Echelon forms Solutions of linear systems from reduced echelon forms Row reduction algorithm Summary

Move on to the next nested submatrix, and repeat the

previous steps. Do this until there aren’t any more
submatrices.

The previous steps take the submatrix to

 
2 −4 4 2 −6
0 0 0 1 4

if we use the top left entry as the pivot, so the whole matrix goes
to  
3 −9 12 −9 6 15
0 2 −4 4 2 −6
0 0 0 0 1 4
Echelon forms Solutions of linear systems from reduced echelon forms Row reduction algorithm Summary

Move on to the next nested submatrix, and repeat the

previous steps. Do this until there aren’t any more
submatrices.

The next nested submatrix is

0 0 1 4

inside  
3 −9 12 −9 6 15
0 2 −4 4 2 −6 .
0 0 0 0 1 4
Since this submatrix is already in echelon form, we are done.
Echelon forms Solutions of linear systems from reduced echelon forms Row reduction algorithm Summary

We now have a matrix in echelon form. Put it in reduced

echelon form by scaling the rows and clearing away
non-pivot entries from each pivot column using row
replacement.

You should start from the bottom right pivot position, moving up
and to the left one pivot column at a time.
   
3 −9 12 −9 6 15 3 −9 12 −9 0 −9
R1 7→R1 −6R3
0 2 −4 4 2 −6 − −−−−−−− → 0 2 −4 4 0 −14
R2 7→R2 −2R3
0 0 0 0 1 4 0 0 0 0 1 4
Echelon forms Solutions of linear systems from reduced echelon forms Row reduction algorithm Summary

We now have a matrix in echelon form. Put it in reduced

echelon form by scaling the rows and clearing away
non-pivot entries from each pivot column using row
replacement.

You should start from the bottom right pivot position, moving up
and to the left one pivot column at a time.

   
3 −9 12 −9 0 −9 3 −9 12 −9 0 −9
R2 7→0.5R2
0 2 −4 4 0 −14 − −−−−−→ 0 1 −2 2 0 −7
0 0 0 0 1 4 0 0 0 0 1 4
 
3 0 −6 9 0 −72
R 7→R +9R2
−−1−−−1−−−
→ 0 1 −2 2 0 −7 
0 0 0 0 1 4
Echelon forms Solutions of linear systems from reduced echelon forms Row reduction algorithm Summary

We now have a matrix in echelon form. Put it in reduced

echelon form by scaling the rows and clearing away
non-pivot entries from each pivot column using row
replacement.

You should start from the bottom right pivot position, moving up
and to the left one pivot column at a time.
   
3 0 −6 9 0 −72 R 7→ 1 R 1 0 −2 3 0 −24
1 (3) 1
0 1 −2 2 0 −7  −−−−−−−→ 0 1 −2 2 0 −7 
0 0 0 0 1 4 0 0 0 0 1 4
Echelon forms Solutions of linear systems from reduced echelon forms Row reduction algorithm Summary

Summary: Using row reduction to solve a linear system

1 Write the augmented matrix of the system.

2 Use the row reduction algorithm to obtain an equivalent
augmented matrix in (not-necessarily-reduced) echelon form.
Decide if the system is consistent. If not, you’re done;
otherwise, go to the next step.
3 Continue row reduction to put the system in reduced echelon
form.
4 Write the system of equations corresponding to the reduced
echelon form.
5 Rewrite each one of these equations so that its basic variable
is expressed in terms of any free variables in the equation.