Linear Algebra/Row Reduction and Echelon Forms

Introduction

Many of the problems you will solve in linear algebra require that a matrix be converted into one of two forms, the Row Echelon Form (ref) and its stricter variant the Reduced Row Echelon Form (rref) . These two forms will help you see the structure of what a matrix represents. If the matrix represents a system of linear equations, these forms allow one to write the solutions to the system.

Every Computer Algebra System and most scientific or graphing calculators have commands which produce these forms for any matrix. The commands are often of the form rref(A), for example.

The Row Echelon Form

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

• All nonzero rows are above any rows of all zeros
• Each leading entry of a row is in a column to the right of the leading entry of the row above it
• All entries of a column below a leading entry are zeros

This matrix is in row echelon form:

${\begin{bmatrix}1&&0&&3&&3\\0&&1&&0&&4\\0&&0&&0&&1\end{bmatrix}}$

The Reduced Row Echelon Form

If a matrix in echelon form satisfies the following conditions, then it is in reduced row echelon form:

• The matrix is in row-echelon form
• Each leading 1 is the only nonzero entry in its column

This matrix is in reduced row echelon form:

${\begin{bmatrix}1&&0&&0\\0&&1&&0\\0&&0&&1\end{bmatrix}}$

and the rref of the matrix in the previous section is:

${\begin{bmatrix}1&&0&&3&&0\\0&&1&&0&&0\\0&&0&&0&&1\end{bmatrix}}$

Changing A Matrix Into REF Or RREF Form

A system of linear equations can be solved by reducing its augmented matrix into reduced echelon form.

A matrix can be changed to its reduced row echelon form, or row reduced to its reduced row echelon form using the elementary row operations. These are:

1. Interchange one row of the matrix with another of the matrix.
2. Multiply one row of the matrix by a nonzero scalar constant.
3. Replace the one row with the one row plus a constant times another row of the matrix.

For example, given the following linear system with corresponding augmented matrix:

${\begin{aligned}3x_{2}-6x_{3}+6x_{4}+4x_{5}&=-5\\3x_{1}-7x_{2}+8x_{3}-5x_{4}+8x_{5}&=9\\3x_{1}-9x_{2}+12x_{3}-9x_{4}+6x_{5}&=15\end{aligned}}$

$\left[{\begin{array}{rrrrrr}0&3&-6&6&4&-5\\3&-7&8&-5&8&9\\3&-9&12&-9&6&15\end{array}}\right]$

To solve this system, the matrix has to be reduced into reduced echelon form.

Step 1: Switch row 1 and row 3. All leading zeros are now below non-zero leading entries.

$\left[{\begin{array}{rrrrrr}3&-9&12&-9&6&15\\3&-7&8&-5&8&9\\0&3&-6&6&4&-5\end{array}}\right]$

Step 2: Set row 2 to row 2 plus (−1) times row 1. In other words, subtract row 1 from row 2. This will eliminate the first entry of row 2.

$\left[{\begin{array}{rrrrrr}3&-9&12&-9&6&15\\0&2&-4&4&2&-6\\0&3&-6&6&4&-5\end{array}}\right]$

Step 3: Multiply row 2 by 3 and row 3 by 2. This will eliminate the first entry of row 3.

$\left[{\begin{array}{rrrrrr}3&-9&12&-9&6&15\\0&6&-12&12&6&-18\\0&6&-12&12&8&-10\end{array}}\right]$

Step 4: Set row 3 to row 3 plus (-1) times row 2. In other words, subtract row 2 from row 3. This will eliminate the second entry of row 3.

$\left[{\begin{array}{rrrrrr}3&-9&12&-9&6&15\\0&6&-12&12&6&-18\\0&0&0&0&2&8\end{array}}\right]$

Step 5: Multiply each row by the reciprocal of its first non-zero value. This will make every row start with a 1.

$\left[{\begin{array}{rrrrrr}1&-3&4&-3&2&5\\0&1&-2&2&1&-3\\0&0&0&0&1&4\end{array}}\right]$

The matrix is now in row echelon form: All nonzero rows are above any rows of all zeros (there are no zero rows), each leading entry of a row is in a column to the right of the leading entry of the row above it and all entries in a column below a leading entry are zeros.

As can and will be shown later, from this form one can observe that the system has infinitely many solutions. To get those solutions, the matrix is further reduced into reduced echelon form.

Step 6: Set row 2 to row 2 plus (-1) times row 3 and row 1 to row 1 plus (-2) times row 3. This will eliminate the entries above the leading entry of row 3.
${\begin{bmatrix}1&-3&4&-3&0&-3\\0&1&-2&2&0&-7\\0&0&0&0&1&4\end{bmatrix}}$

Step 7: Set row 1 to row 1 plus 3 times row 2. This eliminates the entry above the leading entry of row 2.
${\begin{bmatrix}1&0&-2&3&0&-24\\0&1&-2&2&0&-7\\0&0&0&0&1&4\end{bmatrix}}$

This is a reduced echelon form, since the leading entry in each nonzero row is 1 and each leading 1 is the only nonzero entry in its column.

From this the solution of the system can be read:
$x_{1}-2x_{3}+3x_{4}=-24$
$x_{2}-2x_{3}+2x_{4}=-7$
$x_{5}=4$
Those equations can be solved for $x_{1}$, $x_{2}$ and $x_{5}$:
$x_{1}=2x_{3}-3x_{4}-24$
$x_{2}=2x_{3}-2x_{4}-7$
$x_{5}=4$
This is the solution of the system. The variables $x_{3}$ and $x_{4}$ can take any value and are so called free variables. The solution is valid for any $x_{3}$ and $x_{4}$.

Understanding The Two Forms

Any nonzero matrix may be row reduced into more than one matrix in echelon form, by using different sequences of row operations. However, no matter how one gets to it, the reduced row echelon form of every matrix is unique.

Theorem e: Uniqueness of the Reduced 2 Echelon Form
Each matrix is row equivalent to one and only one reduced echelon matrix

If matrix A is row equivalent to an echelon matrix B, we call matrix B an echelon form of A, if B is in reduced echelon form, we call B the reduced echelon form of A.

Pivot Positions

A pivot position in a 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.