Skip to main content

Section2.2Row Reduction

Objectives
  1. Learn to replace a system of linear equations by an augmented matrix.
  2. Learn how the elimination method corresponds to performing row operations on an augmented matrix.
  3. Understand when a matrix is in (reduced) row echelon form.
  4. Learn which row reduced matrices come from inconsistent linear systems.
  5. Recipe: the row reduction algorithm.
  6. Vocabulary words: row operation, row equivalence, matrix, augmented matrix, pivot, (reduced) row echelon form.

In this section, we will present an algorithm for “solving” a system of linear equations.

Subsection2.2.1The Elimination Method

We will solve systems of linear equations algebraically using the elimination method. In other words, we will combine the equations in various ways to try to eliminate as many variables as possible from each equation. There are three valid operations we can perform on our system of equations:

  • Scaling: we can multiply both sides of an equation by a nonzero number.
    Cx+2y+3z=62x−3y+2z=143x+y−z=−2multiply1stby−3−−−−−−−−−→C−3x−6y−9z=−182x−3y+2z=143x+y−z=−2
  • Replacement: we can add a multiple of one equation to another, replacing the second equation with the result.
    Cx+2y+3z=62x−3y+2z=143x+y−z=−22nd=2nd−2×1st−−−−−−−−−−→Cx+2y+3z=6−7y−4z=23x+y−z=−2
  • Swap: we can swap two equations.
    Cx+2y+3z=62x−3y+2z=143x+y−z=−23rd←→1st−−−−−−→C3x+y−z=−22x−3y+2z=14x+2y+3z=6
Example
Augmented Matrices and Row Operations

Solving equations by elimination requires writing the variables x,y,z and the equals sign = over and over again, merely as placeholders: all that is changing in the equations is the coefficient numbers. We can make our life easier by extracting only the numbers, and putting them in a box:

Cx+2y+3z=62x−3y+2z=143x+y−z=−2becomes−−−−→A12362−321431−1−2B.

This is called an augmented matrix. The word “augmented” refers to the vertical line, which we draw to remind ourselves where the equals sign belongs; a matrix is a grid of numbers without the vertical line. In this notation, our three valid ways of manipulating our equations become row operations:

  • Scaling: multiply all entries in a row by a nonzero number.
    A12362−321431−1−2BR1=R1×−3−−−−−→A−3−6−9−182−321431−1−2B
    Here the notation R1 simply means “the first row”, and likewise for R2,R3, etc.
  • Replacement: add a multiple of one row to another, replacing the second row with the result.
    A12362−321431−1−2BR2=R2−2×R1−−−−−−−→A12360−7−4231−1−2B
  • Swap: interchange two rows.
    A12362−321431−1−2BR1←→R3−−−−→A31−1−22−32141236B
Remark
Example

The process of doing row operations to a matrix does not change the solution set of the corresponding linear equations!

Indeed, the whole point of doing these operations is to solve the equations using the elimination method.

Definition

Two matrices are called row equivalent if one can be obtained from the other by doing some number of row operations.

So the linear equations of row-equivalent matrices have the same solution set.

Example(An Inconsistent System)

Subsection2.2.2Echelon Forms

In the previous subsection we saw how to translate a system of linear equations into an augmented matrix. We want to find an algorithm for “solving” such an augmented matrix. First we must decide what it means for an augmented matrix to be “solved”.

Definition

A matrix is in row echelon form if:

  1. All zero rows are at the bottom.
  2. The first nonzero entry of a row is to the right of the first nonzero entry of the row above.
  3. Below the first nonzero entry of a row, all entries are zero.

Here is a picture of a matrix in row echelon form:

DHHFAAAAA0AAAA000AA00000EIIGA=anynumberA=anynonzeronumber
Remark(Why the word “echelon”?)
Definition

A pivot is the first nonzero entry of a row of a matrix in row echelon form.

A matrix in row-echelon form is generally easy to solve using back-substitution. For example,

A12360124001030Bbecomes−−−−→Cx+2y+3z=6y+2z=410z=30.

We immediately see that z=3, which implies y=4−2·3=−2 and x=6−2(−2)−3·3=1. See this example.

Definition

A matrix is in reduced row echelon form if it is in row echelon form, and in addition:

  1. Each pivot is equal to 1.
  2. Each pivot is the only nonzero entry in its column.

Here is a picture of a matrix in reduced row echelon form:

DHF10A0A01A0A0001A00000EIGA=anynumber1=pivot

A matrix in reduced row echelon form is in some sense completely solved. For example,

A1001010−20013Bbecomes−−−−→Nx=1y=−2z=3.
Example

When deciding if an augmented matrix is in (reduced) row echelon form, there is nothing special about the augmented column(s). Just ignore the vertical line.

If an augmented matrix is in reduced row echelon form, the corresponding linear system is viewed as solved. We will see below why this is the case, and we will show that any matrix can be put into reduced row echelon form using only row operations.

Remark(Why the word “pivot”?)

Subsection2.2.3The Row Reduction Algorithm

We will give an algorithm, called row reduction or Gaussian elimination, which demonstrates that every matrix is row equivalent to at least one matrix in reduced row echelon form.

Remark(On the name “Gaussian elimination”)

The uniqueness statement is interesting—it means that, no matter how you row reduce, you always get the same matrix in reduced row echelon form. We deduce it in Section 3.5.

This assumes, of course, that you only do the three legal row operations, and you don’t make any arithmetic errors.

Example

Here is the row reduction algorithm, summarized in pictures.

AAAAAAAAAAAAAAAADHFEIG1AAAAAAAAAAAAAAADHFEIG1AAA01AA0AAA0AAADHFEIG1AAA01AA0AAA0AAADHFEIG1AAA01AA000A000ADHFEIG1AAA01AA000A000ADHFEIG1AAA01AA0001000ADHFEIG1AAA01AA00010000DHFEIG1AAA01AA00010000DHFEIG1AA001A000010000DHFEIG10A001A000010000DHFEIGGeta1hereCleardownGeta1hereCleardown(maybethesearealreadyzero)Geta1hereCleardownMatrixisinREFClearupClearupMatrixisinRREF

It will be very important to know where are the pivots of a matrix after row reducing; this is the reason for the following piece of terminology.

Definition

A pivot position of a matrix is an entry that is a pivot of a row echelon form of that matrix.

A pivot column of a matrix is a column that contains a pivot position.

Example(Pivot Positions)
Example(An Inconsistent System)

In the above example, we saw how to recognize the reduced row echelon form of an inconsistent system.

In other words, the row reduced matrix of an inconsistent system looks like this:

A10AA001AA000001B

We have discussed two classes of matrices so far:

  1. When the reduced row echelon form of a matrix has a pivot in every non-augmented column, then it corresponds to a system with a unique solution:
    A1001010−20013Btranslatesto−−−−−−→Nx=1y=−2z=3.
  2. When the reduced row echelon form of a matrix has a pivot in the last (augmented) column, then it corresponds to a system with a no solutions:
    K150001Ltranslatesto−−−−−−→Jx+5y=00=1.

What happens when one of the non-augmented columns lacks a pivot? This is the subject of Section 2.3.

Example(A System with Many Solutions)