Elimination and Echelon Forms

A matrix A is in Reduced Row-Echelon Form (RREF) if it has the following properties:

1. If a row does not consist entirely of zeroes, then the first nonzero entry in the row is a 1.

2. Any rows that consist entirely of zeroes are at the bottom of the matrix, below all nonzero rows.

3. For rows not consisting of all zeroes, the leading 1 in the lower row is to the right of the leading 1 in a higher row.

4. Each column that has a leading 1 has zeroes everywhere else.

The following are examples of a matrix in RREF:


  
  MatrixForm[{{1,0,0,4},{0,1,0,7},{0,0,1,-1}}]
  MatrixForm[IdentityMatrix[3]]
  MatrixForm[{{0,1,-2,0,1},{0,0,0,1,3},{0,0,0,0,0},{0,0,0,0,0}}]

An equivalent notion is that of Gauss Jordan Standard Form (GJSF), expressed in terms of "pivot columns". A nonzero mxn matrix is in GJSF if:

1. Column vectors e1, e2, . . . , er appear in pivot columns p1, p2, . . . , pr respectively, where 1<=p1<p2< . . . <pr<=n, r<=min{m,n}

2. If any column precedes column p1 it must be a zero column; any column following column p1 that is not a pivot column must be a linear combination of the pivot columns that precede it.

Note: A zero matrix is in GJSF. The vectors ek are the vectors with 1 in the kth slot and zero elsewhere.

Consider the third matrix above:


  MatrixForm[{{0,1,-2,0,1},{0,0,0,1,3},{0,0,0,0,0},{0,0,0,0,0}}]

Columns 2 and 4 are the pivot columns. Column 3 is a multiple of the first pivot column (hence a linear combination of it) and column 5 is a linear combination of the two pivot columns, 1(1st pivot column) + 3(second pivot column).

One puts a matrix in RREF or GJSF by using elementary row operations, which consist of left multiplying by the elementary matrices described previously (or doing the corresponding operations in your head or on paper).


  Clear[A]
  A={{0,0,-2,0,7,12},{2,4,-10,6,12,28},{2,4,-5,6,-5,-1}};
  MatrixForm[A]

1. Find the first nonzero column; this is the first pivot column. If necessary, swap rows to bring a nonzero entry to the top of this pivot column.

For the matrix A, this is column 1.


  A1=E1[1,2,3].A;
  MatrixForm[A1]

2. Introduce a leading 1 in the first pivot column by appropriate multiplication.

In our case, we multiply the first row by 1/2.


  A2=E2[1,1/2,3].A1;
  MatrixForm[A2]

3. Using Type III row operations, eliminate all entries in the pivot column except the leading 1.

In our case, we need to eliminate the 2 in the first pivot column, row 3.


  A3=E3[1,3,-2,3].A2;
  MatrixForm[A3]

4. Now, repeat this process (Steps 1, 2 and 3) for the submatrix formed by ignoring the row containing the leading 1.

Repeat

Step 1B.
Here the second pivot column is the third column of the resulting matrix. We do not need to swap rows here to get a zero; we have -2.

Step 2B.
Multiply the second row by -1/2 to get the leading 1.


  A4=E2[2,-1/2,3].A3;
  MatrixForm[A4]

Step 3B.
Now we eliminate all entries in the second pivot column (except the leading 1, of course).


  A5=E3[2,1,5,3].A4;
  MatrixForm[A5]
  A6=E3[2,3,-5,3].A5;
  MatrixForm[A6]

Repeat Again

Step 1C.
Now ignore the rows containing the first two leading 1's. The next pivot column is the fifth column of the resulting matrix. We do not need to swap rows here; we have 1/2.

Step 2C.
Multiply the third row by 2 to get the leading 1.


  A7=E2[3,2,3].A6;
  MatrixForm[A7]

Step 3C.
Now we eliminate all entries in the third pivot column (except the leading 1, of course).


  A8=E3[3,2,7/2,3].A7;
  MatrixForm[A8]
  A9=E3[3,1,23/2,3].A8;
  MatrixForm[A9]

This is the matrix A in reduced row echelon form or in GJSF. It is row equivalent to A.

Not only have we put the matrix A in GJSF, but we have a record of the row operations we needed to get there. Form a matrix E by left multiplying each elementary matrix (in the correct order!!!) that was used in finding the GJSF. The order and the LEFT multiplication are crucial.


  Elem=E3[3,1,23/2,3].E3[3,2,7/2,3].E2[3,2,3].E3[2,3,-5,3].E3[2,1,5,3].
     E2[2,-1/2,3].E3[1,3,-2,3].E2[1,1/2,3].E1[1,2,3];
  MatrixForm[Elem]

Does this work? It had better!
Remember, A9 was A in GJSF.


  MatrixForm[Elem.A]
  MatrixForm[A9]

This matrix Elem has important theoretical uses. It must be nonsingular, since it is the product of nonsingular matrices (the elementary matrices are nonsingular; remember?).

It may seem tedious to go through all these steps. I agree. Mathematica has a command to put a matrix in GJSF; it is called RowReduce.


  MatrixForm[RowReduce[A]]

What about the matrix Elem? With RowReduce and a little thought we can find that also. Remember that each elementary matrix comes from performing an elementary row operation on the identity matrix. If we perform the same row operations on the identity matrix that we do on A (to get to the GJSF of A), we will get Elem. How do we do that? Append the identity matrix to A and row reduce.

Note: To use append row, you need the Mathematica package "LinearAlgebra`MatrixManipulation`"]. Did you notice the command

Needs["LinearAlgebra`MatrixManipulation`"] at the beginning of this notebook? This is the reason for it.


  AI=AppendRows[A,IdentityMatrix[3]];
  MatrixForm[AI]

Let's do it.


  GJSFofAI=RowReduce[AI];
  MatrixForm[GJSFofAI]

You should note that this matrix is too large to fit on one screen. The end of the rows (the last columns) appear indented.

Let's get the last three columns; that will be Elem. Notice the TakeColumns command. The -3 means the last three columns. This command is in the same package as the AppendRows command. See the Guide to Standard Mathematica Packages for more fun stuff.


  MatrixForm[TakeColumns[GJSFofAI,-3]]

Does this give you Elem? Let's see.


  MatrixForm[Elem]

Up to Linear Algebra Part I