\( \def\R{\mathbb{R}} \def\N{\mathbb{N}} \def\Z{\mathbb{Z}} \def\Q{\mathbb{Q}} \def\eps{\varepsilon} \def\epsilon{\varepsilon} \renewcommand{\geq}{\geqslant} \renewcommand{\leq}{\leqslant} \)

Chapter 1 - Linear Equations in Linear Algebra

1.2 Row Reduction and Echelon Forms


Main: Index
Previous: 1.1 - Systems of Linear Equations
Next: 1.3 - Vector Equations


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.