Section 1.2 Gaussian Elimination
Definition: A rectangular matrix is in echelon form (or row echelon form) if it has the following three properties:
1. All rows consisting entirely of zeros are at the bottom.
2. The first nonzero entry in each nonzero row is a 1
3. Each leading 1 is to the right of all leading 1’s in rows above it.
If a matrix in echelon form satisfies the following additional condition, then
it is in reduced echelon form (or reduced row echelon form):
4. Each leading 1 is the only nonzero entry in its column.
(B) An echelon matrix (respectively, reduced echelon matrix) is one that is in echelon form (respectively, reduced echelon form.)
Theorem(fact): Every matrix can be brought to (reduced) echelon form by a sequence of elementary row operations.
Theorem(fact): (Uniqueness of the Reduced Echelon Form)
Each matrix is row equivalent to one and only one reduced echelon matrix.
Definition: A pivot position in a matrix [latex]A[/latex] is a location in [latex]A[/latex] that corresponds to a leading 1 in the reduced echelon form of [latex]A[/latex]. A pivot column is a column of [latex]A[/latex] that contains a pivot position.
Definition: The rank of a matrix [latex]A[/latex], denoted rank[latex]A[/latex], is the number of pivot positions in any echelon matrix obtained from [latex]A[/latex] by performing elementary row operations.
Definition: Suppose that the augmented matrix of a linear system has been
changed into the equivalent reduced echelon form:
$$\left[\begin{array}{cccc}1 & 0 & -1 & 4\\0 & 1 & 2 & 3\\0 & 0 & 0 &0 \end{array}\right]$$
There are 3 variables because the augmented matrix has four columns. The
associated system of equations is
$$\begin{array}{ccc}
x_{1}-x_{3} & = & 4\\
x_{2}+2x_{3} & = & 3
\end{array}$$
The variables [latex]x_{1}[/latex] and [latex]x_{2}[/latex] corresponding to pivot columns in the matrix are called basic variables. The other variable, [latex]x_{3}[/latex], is called a free variable. [latex]x_{3}[/latex] is free, [latex]x_{2} = 3-2x_{3}[/latex], and [latex]x_{1} = 4+x_{3}[/latex] is a parametric description of solutions sets in which the free variables act as parameters.
Fact: Whenever a system is consistent, the solution set can be described explicitly by solving the reduced system of equations for the basic variables in terms of the free variables. Each different choice of the free variable solution of the system, and every solution of the system is determined by a choice of the free variable.
Definition: Solving a linear system means to find a parametric description of the solution set or determine that the solution set is empty.
Fact: Whenever a system is consistent and has free variables, the solution set has many parametric descriptions. When a system is inconsistent, the solution set is empty, even when the system has free variables. In this case, the solution set has no parametric representation.
Example 1: Solve the linear system
$$\begin{array}{ccc}
x_{1}+x_{2}-x_{3} & = & 2\\
x_{1}+2x_{2}-x_{3} & = & 1\\
2x_{1}+2x_{2}-2x_{3} & = & 2
\end{array}$$
Exercise 1: Solve the linear system
$$\begin{array}{ccc}
-x_{1}+2x_{2}-x_{3} & = & 1\\
3x_{1}-6x_{2}+x_{3} & = & -3\\
2x_{1}-4x_{2}+2x_{3} & = & 1
\end{array}$$
Theorem : 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—i.e., if and only if an echelon form of the augmented matrix has no row of the form [0 . . . 0 b] with b nonzero.
Gaussian Elimination
To solve a system of linear equations proceed as follows:
1 Carry the augmented matrix to a reduced echelon matrix using
elementary row operations.
2 If a row of the form [00 ··· 0|1] occurs, the system is inconsistent.
3 Otherwise assign the non-leading variables (if any) parameters and use the equations corresponding to the reduced row-echelon matrix to solve for the leading variables in terms of the parameters.
Fact: 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.
Example 2: Solve the linear system
$$\begin{array}{ccc}
x_{1}-x_{2}-x_{3} & = & 2\\
2x_{1}-2x_{2}-2x_{3} & = & 4\\
3x_{1}-x_{2}+x_{3} & = & 1
\end{array}$$
Exercise 2: Solve the linear system
$$\begin{array}{ccc}
-2x_{1}+2x_{2}-4x_{3} & = & -4\\
3x_{1}-6x_{2}+3x_{3} & = & -3\\
x_{1}-x_{2}+2x_{3} & = & 2
\end{array}$$
Example 3: Solve the linear system
$$\begin{array}{ccc}
x_{1}-x_{2}-x_{3} & = & 2\\
2x_{1}+x_{2}-2x_{3} & = & 4\\
3x_{1}-x_{2}+x_{3} & = & 1
\end{array}$$
Exercise 3: Solve the linear system
$$\begin{array}{ccc}
-2x_{1}+x_{2}-2x_{3} & = & -4\\
3x_{1}-x_{2}+x_{3} & = & 1\\
x_{1}-x_{2}+2x_{3} & = & 2
\end{array}$$
Group Work 1: Mark each statement True or False. Justify each answer.
a. A matrix could be reduced to two different reduced echelon forms by using different row operations.
b. We can only apply row reduction algorithm to an augmented matrix of a
linear system
c. A basic variable in a linear system is a variable that corresponds to a
pivot column in the coefficient matrix.
d. Finding a parametric description of the solution set of a linear system is the same as solving the system.
e. If one row in an echelon form of an augmented matrix is [0 0 0 3 0], then
the associated linear system is inconsistent.
Group Work2: Suppose a [latex]4 \times 5[/latex] coefficient matrix of a system linear equations has a pivot position in every row. Is the system consistent? Why?
Group Work3: Consider a system of linear equations with augmented matrix [latex]A[/latex] and coefficient matrix [latex]C[/latex]. In each case either prove the statement or give an example showing that it is false.
a. If there is more than one solution, [latex]A[/latex] has a row of zeros.
b. If there is no solution, the row-echelon form of [latex]C[/latex] has a row of zeros.
c. If the row-echelon form of [latex]C[/latex] has a row of zeros, there is no solution.
d. If the system is consistent for some choice of constants, it is consistent for every choice of constants.
Now assume that the augmented matrix [latex]A[/latex] has 3 rows and 5 columns.
e. If the system is consistent, there is more than one solution.
f. The rank of [latex]A[/latex] is at most 3.
g. If rank [latex]A = 3[/latex], the system is consistent.
h. If rank [latex]C = 3[/latex], the system is consistent.
Group Work 4: Suppose a [latex]4 \times 6[/latex] augmented matrix of a system linear equations whose 6th column is not a pivot column. Is the system consistent? Why?
Group Work 5: Balance the chemical reaction given below involving tin (Sn),
hydrogen (H), and oxygen (O)
$$xSnO_{2}+yH_{2}\rightarrow zSn+wH_{2}O$$
