Chapter 1 - Linear Equations in Linear Algebra
1.2 Row Reduction and Echelon Forms
Results
Echelon and Reduced Echelon form
Echelon means "steplike". An example of a matrix one echelon form:
$$
\begin{bmatrix*}[rrrr]
2 & -3 & 2 & 1 \\
0 & 1 & -4 & 8 \\
0 & 0 & 0 & 5/2
\end{bmatrix*}
$$
For every nonzero, leading elements, all elements below are 0.
Reduced row echelon form (RREF) or just reduced echelon form
takes it one step further:
$$
\begin{bmatrix*}[rrrr]
1 & 0 & 0 & 29\\
0 & 1 & 0 & 16\\
0 & 0 & 1 & 3
\end{bmatrix*}
$$
Now all values above leading elements are also 0, and the leading numbers
are set to 1.
Theorem 1.1: Uniqueness of the RREF
Each matrix is row equivalent to one and only one reduced echelon matrix.
(Note: my numbering. Book refers to this as Theorem 1, but starts a new counter
in each chapter).
Some terminology: a
pivot position in a matrix A is a location
in A that corresponds to a leading 1 in the RREF. A
pivot column
is a column of A that contains a pivot position. The leading non-zero
elements in echelon matrices are called
pivots.
Theorem 1.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 the RREF matrix has no row of the form
$$
[\;0\;\;\cdots\;\;0\;\; 1\;]
$$
If a linear system is consistent, then the solution set has either (i)
a unique solution, when there are no free variables, or (ii) infinitely
many solutions, when there is at least one free variable.
Solutions of Linear Systems
As we have already seen, if we start with some augmented matrix we
can find the RREF which might look like this:
$$
\begin{bmatrix*}[rrrr]
1 & 0 & -5 & 1 \\
0 & 1 & 1 & 4 \\
0 & 0 & 0 & 0
\end{bmatrix*}
$$
There are three variables because the augmented matrix has four columns.
The associated system of linear equations is:
$$
\begin{array}{rcccccr}
x_1 & & & - & 5x_3 & = & 1 \\
& & x_2 & + & x_3 & = & 4 \\
& & & & 0 & = & 0
\end{array}
$$
Variables $x_1, x_2$ are called
basic variables while $x_3$
is called a
free variable. This means that the solution is
true for any value of $x_3$, and so there are an infinite number
of solutions.
We can write the parametric description of the solution set as follows:
$$
\left\{
\begin{array}{l}
x_1 = 1 + 5x_3 \\
x_2 = 4 - x_3 \\
x_3 \;\text{is free}
\end{array}
\right.
$$
Exercise 4
Find the RREF and list the pivot columns.
$$
\begin{bmatrix*}[rrrr]
1 & 3 & 5 & 7 \\
3 & 5 & 7 & 9 \\
5 & 7 & 9 & 1
\end{bmatrix*}
$$
Answer
Applying row operations. II = II - 3I, III = III - 5I
$$
\begin{bmatrix*}[rrrr]
1 & 3 & 5 & 7 \\
0 & -4 & -8 & -12 \\
0 & -8 & -16 & -34
\end{bmatrix*}
$$
(-1/4)II, (-1/8)III
$$
\begin{bmatrix*}[rrrr]
1 & 3 & 5 & 7 \\
0 & 1 & 2 & 3 \\
0 & 1 & 2 & 4.25
\end{bmatrix*}
$$
III = III - II
$$
\begin{bmatrix*}[rrrr]
1 & 3 & 5 & 7 \\
0 & 1 & 2 & 3 \\
0 & 0 & 0 & 1.25
\end{bmatrix*}
$$
Obviously row equivalent to:
$$
\begin{bmatrix*}[rrrr]
1 & 0 & 5 & 0 \\
0 & 1 & 2 & 0 \\
0 & 0 & 0 & 1
\end{bmatrix*}
$$
The pivot columns are 1, 2 and 4. This system appears to be inconsistent.
■
Exercise 7
Find the general solution for the augmented matrix:
$$
\begin{bmatrix*}[rrrr]
1 & 3 & 4 & 7 \\
3 & 9 & 7 & 6
\end{bmatrix*}
$$
Answer
II - 3I
$$
\begin{bmatrix*}[rrrr]
1 & 3 & 4 & 7 \\
0 & 0 & -5 & -15
\end{bmatrix*}
$$
(-1/5)II
$$
\begin{bmatrix*}[rrrr]
1 & 3 & 4 & 7 \\
0 & 0 & 1 & 3
\end{bmatrix*}
$$
I - 4II
$$
\begin{bmatrix*}[rrrr]
1 & 3 & 0 & -5 \\
0 & 0 & 1 & 3
\end{bmatrix*}
$$
Solution set:
$$
\left\{
\begin{array}{l}
x_1 = -5 - 3x_2 \\
x_2 \;\text{is free} \\
x_3 = 3
\end{array}
\right.
$$
Verifying, using $x_2 = 0$, so $x_1 = -5$ and $x_3 = 3$.
$$
(-5) + 3(0) + 4(3) = -5 + 12 = 7
$$
$$
3(-5) + 9(0) + 7(3) = -15 + 21 = 6
$$
■
Exercise 12
Find the general solution for the augmented matrix:
$$
\begin{bmatrix*}[rrrrr]
1 & -7 & 0 & 6 & 5 \\
0 & 0 & 1 & -2 & -3 \\
-1 & 7 & -4 & 2 & 7
\end{bmatrix*}
$$
Answer
III + I
$$
\begin{bmatrix*}[rrrrr]
1 & -7 & 0 & 6 & 5 \\
0 & 0 & 1 & -2 & -3 \\
0 & 0 & -4 & 8 & 12
\end{bmatrix*}
$$
(-1/4)III
$$
\begin{bmatrix*}[rrrrr]
1 & -7 & 0 & 6 & 5 \\
0 & 0 & 1 & -2 & -3 \\
0 & 0 & 1 & -2 & -3
\end{bmatrix*}
$$
III - II
$$
\begin{bmatrix*}[rrrrr]
1 & -7 & 0 & 6 & 5 \\
0 & 0 & 1 & -2 & -3 \\
0 & 0 & 0 & 0 & 0
\end{bmatrix*}
$$
Solution set:
$$
\left\{
\begin{array}{l}
x_1 = 5 + 7x_2 - 6x_4 \\
x_2 \;\text{is free} \\
x_3 = -3 + 2x_4 \\
x_4 \;\text{is free}
\end{array}
\right.
$$
■
Exercise 14
Find the general solution for the augmented matrix:
$$
\begin{bmatrix*}[rrrrrr]
1 & 2 & -5 & -6 & 0 & -5 \\
0 & 1 & -6 & -3 & 0 & 2 \\
0 & 0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 0
\end{bmatrix*}
$$
Answer
I - 2II
$$
\begin{bmatrix*}[rrrrrr]
1 & 0 & 7 & 0 & 0 & -9 \\
0 & 1 & -6 & -3 & 0 & 2 \\
0 & 0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 0
\end{bmatrix*}
$$
RREF. Solution set:
$$
\left\{
\begin{array}{l}
x_1 = -9 - 7x_3 \\
x_2 = 2 + 6x_3 + 3x_4 \\
x_3 \;\text{is free} \\
x_4 \;\text{is free} \\
x_5 = 0
\end{array}
\right.
$$
■
Exercise 21
Verifying statements
(a)
In some cases, a matrix may be row reduced to more than one matrix in RREF, using
different sequences of operations.
Answer: False. By theorem 1.1, all matrices have a completely unique RREF.
(b)
The row reduction algorithm applies only to augmented matrices for a linear system.
Answer: False. To solve a linear system, yes, but it can also be used on a coefficient matrix
to see certaint properties of the matrix.
(c)
A basic variable in a linear system is a variable that corresponds to a pivot
column in the coefficient matrix.
Answer: Yes, this is true. Free variables will never be pivots.
(d)
Finding a parametric description of the solution set of a linear system
is the same as solving the system.
Answer: True. We find a set of values that satisfy the original system.
(e)
If one row in an echelon form of an augmented matrix is [0 0 0 5 0], then
the associated system is inconsistent.
Answer: False. This row simply means that $x_5 = 0$ is part of the solution.
■
Exercise 22
Verifying statements
(a)
The echelon form of a matrix is unique.
Answer: False. The RREF is unique, but there are many ways to have an echelon form.
(b)
The pivot positions in a matrix depend on whether row interchanges are used in
the row reduction process.
Answer: False. The pivot position is linked to the RREF which by Thm 1.1 is unqiue.
(c)
Reducing a matrix to echelon form is called the forward phase of the row
reduction process.
Answer: True. The backwards phase is going from echelon to RREF.
(d)
Whenever a system has free variables, the solution set contains many solutions.
Answer: True. A free variable means it can be anything and will have a unique, associated
solution set.
(e)
A general solution of a system is an explicit description all solutions of the system.
Answer: True. This is correct. :)
■
Exercise 23
Suppose a 3x5 coefficient matrix for a system has three pivot columns.
Is the system consistent?
Answer
Yes, but it also has free variables and an infinite number of solutions.
■
Exercise 24
Suppose a 3x5 augmented matrix whose fifth column is a pivot column.
Is the system consistent?
Answer
No, this means that there is a contradiction. The system is inconsistent.
■
The rest of the exercises are skipped.