the leading entry in each non-zero row is $1$,
each leading $1$ is the only non-zero entry in its column
The Gauss Elimination method employed in the previous lecture used elementary row operations $$\left[\begin{array}{cc}0 & 1 & 1 & 4 \\ 3 & 6 & -3 & 3 \\ -2 & -3 & 7 & 10 \end{array} \right] \xrightarrow{ R_1 \leftrightarrow R_2 } \left[\begin{array}{cc}3 & 6 & -3 & 3 \\ 0 & 1 & 1 & 4 \\ -2 & -3 & 7 & 10 \end{array} \right] \xrightarrow{ \frac{1}{3}R_1 \rightarrow R_1' } \left[\begin{array}{cc}1 & 2 & -1 & 1 \\ 0 & 1 & 1 & 4 \\ -2 & -3 & 7 & 10 \end{array} \right] \xrightarrow{ 2R_1 + R_3 \rightarrow R_3' } \left[\begin{array}{cc}1 & 2 & -1 & 1 \\ 0 & 1 & 1 & 4 \\ 0 & 1 & 5 & 12 \end{array} \right]$$ to row reduce an augmented matrix to echelon form because then the solutions of the linear system could be read off by back substitution. From both a conceptual and computational point of view, however, the trouble with using the echelon form is that a matrix can be equivalent to several different echelon forms. For example, the row reduction above can be continued: $$ \xrightarrow{ R_3- R_2 \rightarrow R_3' } \left[\begin{array}{cc}1 & 2 & -1 & 1 \\ 0 & 1 & 1 & 4 \\ 0 & 0 & 4 & 8 \end{array} \right] \xrightarrow{ \frac{1}{4}R_3 \rightarrow R_3' } \left[\begin{array}{cc}1 & 2 & -1 & 1 \\ 0 & 1 & 1 & 4 \\ 0 & 0 & 1 & 2 \end{array} \right] \xrightarrow{ R_2 - R_3 \rightarrow R_2' } \left[\begin{array}{cc}1 & 2 & -1 & 1 \\ 0 & 1 & 0 & 2 \\ 0 & 0 & 1 & 2 \end{array} \right] \xrightarrow{ R_1 - 2R_2 \rightarrow R_1' } \left[\begin{array}{cc}1 & 0 & -1 & -3 \\ 0 & 1 & 0 & 2 \\ 0 & 0 & 1 & 2 \end{array} \right] $$ producing a new echelon form at each stage - in other words, there may be NO UNIQUE echelon form for a matrix thereby complicating the writing of code for row reduction. So when should we stop before using back substitution, for instance? This leads us to introduce a key definition.
|
Definition 4.1: a matrix is said
to be in
REDUCED ROW ECHELON FORM if it is in row echelon form and
|
Typical structures for a matrix in Reduced Row Echelon Form are thus
$$\left[\begin{array}{cc} 1 & \ast & 0 & 0 & \ast & 0 & \ast & \cdots & \ast \\ 0 & 0 & 1 & 0 & \ast & 0 & \ast & \cdots & \ast \\ 0 & 0 & 0 & 1 & \ast & 0 & \ast & \cdots & \ast \\ 0 & 0 & 0 & 0 & 0 & 1 & \ast & \cdots & \ast\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & \cdots & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & \cdots & 0 \end{array}\right], \qquad \qquad \left[\begin{array}{cc} 0 & 1 & \ast & 0 & 0 & \ast & 0 & \ast & \cdots & \ast \\ 0 & 0 & 0 & 1 & 0 & \ast & 0 & \ast & \cdots & \ast \\ 0 & 0 & 0 & 0 & 1 & \ast & 0 & \ast & \cdots & \ast \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & \ast & \cdots & \ast\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \cdots & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \cdots & 0 \end{array}\right]$$where the $*$ entry can be any number. Note that such matrices are still in echelon form but each pivot value is 1, and all the entries in a pivot column are 0 except for the pivot itself. What more row operations are needed? The next result should now come as no surprise:
| Main Reduced Row Echelon Theorem: each matrix is row equivalent to one and only one reduced row echelon matrix. This unique reduced row echelon matrix associated with a matrix $A$ is usually denoted by $\text{rref}(A)$. |
On the other hand, with one more row operation in the earlier sequence of row operations, for instance, we see that $$\text{rref}\,\left[\begin{array}{cc} 0 & 1 & 1 & 4 \\ 3 & 6 & -3 & 3 \\ -2 & -3 & 7 & 10 \end{array} \right] \ = \ \left[\begin{array}{cc}1 & 0 & 0 & -1 \\ 0 & 1 & 0 & 2 \\ 0 & 0 & 1 & 2 \end{array} \right].$$
Uniqueness of the reduced row echelon form is a property we'll make fundamental use of as the semester progresses because so many concepts and properties of a matrix $A$ can then be described in terms of $\text{rref}(A)$. But first let's investigate how the presence of the 1 and 0's in the pivot column affects the Gauss Elimination method for solving the three systems of linear equations.
|
Problem 4.1: solve for $x,\, y$ and $z$ in $$\begin{array}{cc} \phantom{\ \quad \quad} y +z & = & 4\,, \\ 3x + 6y -3z & = & 3\,, \\ -2x -3y + 7z & = & 10\,.\end{array} $$
Solution : the associated augmented matrix is $$[ A \ \ {\bf b}]\ = \ \left[\begin{array}{cc} 0 & 1 & 1 & 4 \\ 3 & 6 & -3 & 3 \\ -2 & -3 & 7 & 10\end{array} \right], $$ whose reduced row echelon form is $$\text{rref}[A \ \ {\bf b}] \ = \ \left[\begin{array}{cc}1 & 0 & 0 & -1 \\ 0 & 1 & 0 & 2 \\ 0 & 0 & 1 & 2 \end{array} \right]\,.$$ But this is the augemented matrix associated with the equivalent system $$ x \ = \ -1\,, \qquad y \ = \ 2\,, \qquad z \ = \ 2\,.$$ These solutions are exactly the same as before, of course, because elementary row operations produce equivalent systems. The point is that the 1's and 0 in the pivot columns eliminate the need for back substitution when computing $x,\, y$ and $z$. |
Problem 4.2: solve for $x,\, y$ and $z$ in $$\begin{array}{cc} \phantom{\ \quad \quad} y +z & = & 4\,, \\ 3x + 6y -3z & = & 3\,, \\ -2x -3y + 3z & = & 10\,.\end{array} $$Solution: the associated augmented matrix is $$[ A\ \ {\bf b}] \ = \ \left[\begin{array}{cc} 0 & 1 & 1 & 4 \\ 3 & 6 & -3 & 3 \\ -2 & -3 & 3 & 10\end{array} \right], $$ and $$\text{rref}([ A\ \ {\bf b}])\ = \ \left[\begin{array}{cc} 1 & 0 & -3 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1\end{array} \right], $$ associated with the equivalent system $$\begin{array}{cc} x \phantom{\ \qquad } - 3 z & = & 0\,, \\ \phantom{\ \ \quad \quad} y +z & = & 0\,, \\ \phantom{ \qquad \qquad} 0z & = & 1\,.\end{array} $$ But there is no value of $z$ such that $0 z = 1$, so the system is Inconsistent. Notice that $\text{rref}([ A\ \ {\bf b}])$ has three pivot columns, but the column of right hand sides is one of them!! |
|
Problem 4.3: solve for $x,\, y$ and $z$ in $$\begin{array}{cc} \phantom{\ \quad \quad} y +z & = & 4\,, \\ 3x + 6y -3z & = & 3\,, \\ -2x -3y + 3z & = & 2\,.\end{array} $$ Solution: the associated augmented matrix is $$[ A\ \ {\bf b}] \ = \ \left[\begin{array}{cc} 0 & 1 & 1 & 4 \\ 3 & 6 & -3 & 3 \\ -2 & -3 & 3 & 2\end{array} \right], $$ and, as calculations show, $$\text{rref}\,([ A\ \ {\bf b}])\ = \ \left[\begin{array}{cc} 1 & 0 & -3 & 7 \\ 0 & 1 & 1 & 4 \\ 0 & 0 & 0 & 0\end{array} \right]. $$ |
Thus $\text{rref}\,[A \ \ {\bf b}]$ is the augmented matrix associated with the equivalent system $$\begin{array}{cc} x \phantom{\ \qquad } -3z & = & 7\,, \\ \phantom{\ \ \quad } y +z & = & 4\,.\end{array} $$ But now there is no equation to specify $z$, so $z$ is a free variable: $$\quad x \,=\, 7 +3 t\,, \quad y \,=\, 4-t\,, \quad z \,=\, t\,, \ \ (t \ \text{arbitrary}).$$ Notice that in $\text{rref}\,[ A\ \ {\bf b}]$ the $x$- and $y$-columns are the only pivot columns, while $z$ is a free variable. |
This refinement of Gaussian Elimination using the the Reduced Row Echelon Form of the Augmented matrix instead of the Echelon Form is usually called Gauss-Jordan Elimination after the German mathematician Wilhelm Jordan who used it extensively in his writings. Whether the extra work to avoid back substitution is worthwhile in simple hand calculations is a matter of personal preference. Nonetheless, from the point of view of theory and numerical compution generally, the idea of performing row operations both downwards and upwards to produce $\text{rref}(A)$ will become very important as we shall soon see. Since most hand calculators and computer algebra systems like SageMath and WolframAlpha have built-in routines, it's usually quicker to compute $\text{rref}(A)$ with technology when it's readily available. Gauss-Jordan Elimination thus puts the finishing touches to Gauss Elimination and provides the convenient algorithm that we had been seeking for solving a general system:
|
Gauss-Jordan Elimination: given a general system of $m$ linear equations in $n$
variables,
|
Since computation of $\text{rref}([A\ \ {\bf b}])$ usually requires more row operations than finding an Echelon Form of $[A\ \ {\bf b}]$ on which back substitution can be used, however, computations for huge linear systems might still use Gauss Elimination together with some 'clever tricks' to reduce still further the number of operations required.
There's one important family of linear systems in which all the right hand sides are zero, i.e. ${\bf b} = {\bf 0}$.
|
Definition 4.2: a linear system is said to be HOMOGENEOUS when the right hand sides are all zero, i.e. when the linear system has the form $A\,{\bf x} = {\bf 0}$. Since $A\,{\bf 0} = {\bf 0}$, a homogeneous system always has the TRIVIAL solution ${\bf x} = {\bf 0}$, hence is always consistent, but it will have infinitely many solutions when the system has a free variable. |
Such a system can occur, for instance, when finding the linear equation of the plane passing through three points in ${\mathbb R}^3$.
|
Problem 4.5: determine as a linear equation the unique plane passing through the points $$Q(-2,\,1,\,2),\quad R(0,\,2,\,2),\quad S(1,\,1,\,4)\,. $$ Solution: The general linear equation in $3$ variables is $$ ax + by + cz + d\, =\, 0\,.$$ As a plane it will contain $Q,\, R,\, S$ when $a,\, b, \, c$ and $d$ satisfy the homogeneous system $$\begin{array}{cc} -2 a\, +\, b\, +\,2c\, +\, d & = & 0, \\ 0 a\, +\, 2b\, +\, 2 c\, +\, d \ & = & 0, \\ a\ +\ b\ + \ 4c\, +\ d & = & 0\,,\end{array}$$ which as an augmented matrix is $$[A \ \ {\bf 0}] \ = \ \left[\begin{array}{cc} -2 & 1 & 2 & 1 & 0 \\ 0 & 2 & 2 & 1 & 0 \\ 1 & 1 & 4 & 1 & 0\end{array} \right]. $$ |
But
$$ \text{rref}\,([A \ \ {\bf 0}]) \ = \
\left[\begin{array}{cc} 1 & 0 & 0 & -\textstyle{\frac{1}{7}} & 0 \\
0 & 1 & 0 & \textstyle{\frac{2}{7}} & 0 \\
0 & 0 & 1 & \textstyle{\frac{3}{14}} & 0\end{array}
\right].$$
Thus $d$ is a free variable, say $d = t$, and
$$a \,=\, \frac{1}{7}t, \quad b \,=\, -\frac{2}{7}t, \quad c \,=\,
-\frac{3}{14} t\,,$$
so the equation of the plane is
$$ 2x - 4y - 3z + 14 \ = \ 0\,,$$
setting $t = 14$.
We could have chosen any value for $t,$ $t \ne 0$. So does this mean the plane is not unique? NO!! We could cancel out the common factor from the resulting equation and still get the same equation! |
The inter-relation between the number of pivots in $\text{rref}(A)$ and solutions of general systems suggests the following key conceptual definition.
|
Definition 4.3: the RANK of a matrix $A$ is the number of leading $1$'s in the rows of $\text{rref}(A)$, i.e., the number of pivot columns. For an $m \times n$ matrix $A$, $$\text{Rank}(A) \ \le \ \min\{m,\, n\}\,.$$ |
A number of the earlier results can be expressed in terms of rank. There will be many others.
|
Theorem 4.1: if $A$ is the coefficient matrix for a system of $m$ linear equations in $n$ variables, then the linear system In particular, when $m < n$, a system of $m$ linear equations in $n$ variables has either no solutions, or infinitely many. |
|
Proof: $\ \text{Rank}(A) = m$: since $\text{rref}(A)$ then has $m$ rows and $m$ leading $1$'s, there must be a leading $1$ in every row of $\text{rref}(A)$. In this case, $\text{rref}([A\ \ {\bf b}])$ cannot contain a row $$[0 \ \ 0 \ \ \cdots \ \ 0 \ \ 1]$$ for any ${\bf b}$ in ${\mathbb R}^m$, so the linear system is consistent. |
$\ \text{Rank}(A) = n$: every column is a pivot column, so the linear system has no free variables, hence has at most one solution. $\ \text{Rank}(A) < n$: now there are free variables. But then the linear system has either infinitely many solutions or no solutions. |
form the associated augmented matrix $[ A\ \ {\bf b}]$ and compute $\text{rref}([ A\ \ {\bf b}])$,