Row Reduction and Echelon Forms

Given a matrix, a leading entry of a row refers to the leftmost nonzero entry in a nonzero row.

Echelon form and reduced echelon form

A rectangular matrix is in echelon form (or 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 in a column below a leading entry are zeros.

If a matrix in echelon form satisfies the following additional conditions, then it is in reduced echelon form (or reduced row echelon form).

• The leading entry in each nonzero row is 1.
• Each leading 1 is the only nonzero entry in its column.

Example)

A matrix in echelon form

A matrix in reduced echelon form

Theorem 1. Uniqueness of the Reduced Echelon Form

Each matrix is row equivalent to one and only one reduced echelon matrix.

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.

A pivot is a nonzero number in a pivot position that is used as needed to create zeros via row operations.

The Row Reduction Algorithm

This algorithm produces a matrix in echelon form.

1. Begin with the leftmost nonzero column. This is a pivot column. The pivot position is at the top.
2. Select a nonzero entry in the pivot column as a pivot. If necessary, interchange rows to move this entry into the pivot position.
3. Use row replacement operations to create zeros in all positions below the pivot.
4. Cover (or ignore) the row containing the pivot position and cover all rows, if any, above it. Apply steps 1-3 to the submatrix that remains. Repeat the process until there are no more nonzero rows to modify.
5. Beginning with the rightmost pivot and working upward and to the left, create zeros above each pivot. If a pivot is not 1, make it 1 by a scaling operation.

Example

Step 1. Pivot column is the leftmost column which contains {0, 3, 3}.

Step 2. Interchange rows 1 and 3. Pivot is the ’3′ of row 1.

Step 3. Add -1 times row 1 to row 2.

Step 4. Cover row 1 because it contains the pivot position. The next pivot is ’2′ of row 2 for step 2.

Add -3/2 times the row 2 to the row 1 for step 3, and repeat the process until there are no more nonzero rows to modify.

Step 5. Create zeros above the rightmost pivot in row 3 by applying row 1 + (-6)*row 3 and row 2 + (-2)*row 3.

Makes the next pivot 1. Scale the row 2 by 1/2.

Create a zero above the pivot by adding 9 times row 2 to row 1.

Scale row 1 to make the last pivot 1.

Solutions of Linear Systems

Basic variables and free variables

Consider the following linear system.

The variables and corresponding to pivot columns in the matrix are called basic variables. The other variable, x_{3}, is called a free variable.

The above system has the following solution which gives an explicit description of all solutions. These solutions are called general solutions.

Existence and Uniqueness Questions

Theorem 2. Existence and Uniqueness Theorem

A linear system is consistent if and only if the rightmost column of the augmented matrix is not a pivot column – that is, if and only if an echelon form of the augmented matrix has no row of the form

[ 0 ... 0 b ] with b nonzero

If a linear system is consistent, then the solution set contains either (i) a unique solution, when there are no free variables, or (ii) infinitely many solutions, when there is at least one free variable.

Systems of Linear Equations

Basic Notations

Linear equation

An equation that can be written in the following form

…

A system of linear equations (linear system)

Collection of one or more linear equations involving the same variables

ex)

Solution of a linear system

A list (…) of numbers that makes each equation a true statement when the values … are substituted for … respectively.

Equivalent

Two linear systems are called equivalent if they have the same solution set.

Consistency and inconsistency

A linear system is consistent if it has either one or infinitely many solutions; a system is inconsistent if it has no solution.

Matrix Notations

Coefficient matrix and augmented matrix

Given the system

the matrix

is called the coefficient matrix of the above system, and

is called the augmented matrix of the system.

Solving a Linear System

The basic strategy to solve a linear system is to replace one system with an equivalent system that is easier to solve.

Elementary Row Operations

1. (Replacement) Replace one row by the sum of itself and a multiple of another row.
2. (Interchange) Interchange two rows.
3. (Scaling) Multiply all entries in a row by a nonzero constant.

Given two matrices, if there is a sequence of elementary row operations that transforms one matrix into the other, they are row equivalent.

If the augmented matrices of two linear systems are row equivalent, then the two systems have the same solution set.

Existence and Uniqueness Questions

It is needed to determine that a particular linear system contains either no solution, one solution, or infinitely many solutions.

If the system has one or infinitely many solutions, the system is consistent. Otherwise, it is inconsistent.