The Echelon Forms

Echelon: [Old French eschele] A ladder rung

Goal: Put a Matrix into Echelon form.
The ability to 'read' the Row Echelon Forms of a matrix

I. The Upper Triangular System and Matrix

The method of elimination that we have used so far has been a bit haphazard. We begin now to look for refinements in the method in order to develop an efficient algorithm. What is the most efficient way to solve a system of linear equations?

We are interested developing a systematic procedure for elimination. Our first goal is to manipulate a given linear system into an upper triangular system, in words we will begin with and eliminate all the variables underneath it. Then we go to and eliminate the variables below it, and we continue along the diagonal.

Put the system into Upper Triangular Form

The Augmented Matrix

We manipulate this system and arrive at the equivalent system:

The Upper Triangular System

The Upper Triangular Matrix

This example amounts to the elimination of two variables in the bottom row and one variable in the middle row. From the last equation we see that , we substitute this value into the second equation to find and then substitute both of these values into the first equation to find . This is called back-substitution.

From this point on, we use the augmented and coefficient matrices to represent systems of linear equations.

So what could go wrong with this method? What if some of the pivots are zero?

Problem: Solve the following system of linear equations by putting it into upper tiangular form.

Since it is not possible to eliminate any of the entries below the leading zero in the first row, we simply switch with another row that has a nonzero value in the pivot position, an E1 operation. We interchange row 1 and row 2.

When we use an element in a row to eliminate the nonzero entries below it, we refer to that element as a pivot, and the row containing the pivot as the pivotal row.

We arrive at:

Use back-substitution to find the solution set to this system.

II. Row Echelon Form

This last matrix can be put into what is refered to as Row Echelon Form if we make each of the leading entries equal to 1.

The Upper Triangular Matrix

E2 Operations

Row Echelon Form

Both of these matrices are equivalent to the original augmented matrix.

Definition: Row Echelon Form

A matrix is said to be in Row Echelon Form if
i) The first nonzero entry in each row is 1.
ii) In a given row, the entries in the column below the leading 1 are all equal to 0.
iii) Rows of all zeros are below rows with any nonzero entries.

A. Given an augmented matrix S, use the elementary row operations to put S into Row Echelon Form.

Students do this!

B. Given an mxn matrix S, write an algorithm of the steps used by the Method of Elimination to create an Row Echelon Matrix. Entitle your solution "The Gaussian Elimination Algorithm"

The Process of using the three elemenatry row operations to put a system of linear equations into row echelon form is refered to as Gaussian Elimination. We now consider another Echelon form, the Reduced Row Echelon Form.

III. Reduced Row Echelon Form

An important variation of the row echelon form is the Reduced Row Echelon form which is the matrix form of Gauss-Jordan Reduction.

Definition: Reduced Row Echelon Form

A matrix is said to be in Reduced Row Echelon Form if:
i) The matrix is in echelon form;
ii) The first nonzero entry in each row is the only nonzero entry in its column.

Put the following matrices into Reduced Row Echelon Form.

Question: What do the Echelon Forms reveal about the various types of solutions sets for the related System of Linear Equations?

Akamai: Practice reading echelon forms!

IV. Overdetermined Systems

Suppose we have a system of equations with the augmented Matrix S, as shown below.

Write the System of Equations represented by S.

Experiment by changing the entries of S and observing the graphs below.

The matrix S represents 3 equations in 2 unknowns. A linear system with more equations than unknowns is called overdetermined.

The Row Reduced Echelon Form of S is given by:

What does this say?

V. Underdetermined Systems

If there are fewer equations than unknowns, a linear system is Underdetermined.

Consider the augmented matrix S for an underdetermined linear system.

This says

But what about , , ?

We do not have enough equations to find unique value for , , .

In this case we have two free variables

and

Thus, for any real numbers a and b, the 5-tuple

is a parametric solution to the system. Why?

VI. Homogeneous Systems

A system of linear equations is said to be homogeneous if the constants on the right-hand side are all zero.

.
:

An mxn homogeneous linear system

Notice, the solution of this system is all the . This is called the trivial solution. Is the trivial solution the only solution to a homogeneous system?

Theorem 1.2.1: An mxn homogeneous system of linear equations has a nontrivial solution if n>m .

Proof: (Direct) If n>m, there are more variables than equations and the system is underdetermined. Consequently, there exist some free variables. For each different assignment of a number to a free variable we obtain a solution. If we assign to one of the free variables a nonzero value, we obtain a nontrivial solution.

For example, if and and

In the case where the system is underdetermined and there must be free variables. In this case y works as a free variable.

In this case a nontrivial solution is given by:

Is this the only nontrivial Solution?

____________________________________________________

Lecture 2 Notes