Skip to main content

# Section1.2Row Reduction¶ permalink

##### 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.

# Subsection1.2.1The Elimination Method¶ permalink

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.
• Replacement: we can add a multiple of one equation to another, replacing the second equation with the result.
• Swap: we can swap two equations.
##### Augmented Matrices and Row Operations

Solving equations by elimination requires writing the variables 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:

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.
Here the notation simply means “the first row”, and likewise for etc.
• Replacement: add a multiple of one row to another, replacing the second row with the result.
• Swap: interchange two rows.

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.

# Subsection1.2.2Echelon Forms¶ permalink

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:

##### 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,

We immediately see that which implies and 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:

A matrix in reduced row echelon form is in some sense completely solved. For 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.

# Subsection1.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.

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.

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

We will not prove uniqueness, but maybe you can!

Here is the row reduction algorithm, summarized in pictures.

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.

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:

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

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