Row Reduction

At the end of this lesson, you should be able to:

•  know how to replace a linear system with its augmented matrix;
• know what the elementary row operations are and how to apply them to simplify a linear
  system;
• understand how the elimination method corresponds to performing row operations on an augmented matrix;
• find the Row Echelon Form (REF) and the Reduced Row Echelon Form (RREF) of an augmented matrix;
• recognize when a matrix is in REF and RREF;
• identify using elementary row operations when a linear system is inconsistent;
• recognize when a row of an REF or RREF comes from an inconsistent linear system;
• know what it means for two matrices to be row equivalent;
• know how to use the method of back substitution to solve a linear system;
• know how to identify when a linear system is consistent and inconsistent;
• know how to compute the number of free parameters in a solution set;
• know the three possible cases for the solution set of a linear system.

Augmented Matrix

A concise way of representing a linear system is by its augmented matrix. A matrix is an array or table consisting of rows and columns. The use of the matrices translates the study of a linear system into a more algebraic point of view.

Example 1: The augmented matrix of the linear system in the unknown variables $w$, $x$, $y$, and $z$
\begin{eqnarray*}
\begin{array}{ccccccccc}
5w&+&7x&+&3y&+&3z&=&2\\
&-& x&+& y&+& z&=&-1\\
& & x&-& y&-& z&=& 1\\
4w&+&5x&+&3y&+&3z&=&1
\end{array}
\end{eqnarray*}
is
\begin{eqnarray*}
\left[\begin{array}{rrrr|r}
5& 7 & 3 & 3 & 2\\
0& -1 & 1 & 1 & -1\\
0& 1 & -1 & -1 & 1\\
4& 5 & 3 & 3 & 1\\
\end{array}\right]
\end{eqnarray*}

Example 2: The augmented matrix of the linear system in the unknown variables $x_1$, $x_2$, $x_3$, and $x_4$
\begin{eqnarray*}
\begin{array}{ccccccccc}
x_1&-&x_2&-&x_3&+&x_4&=&4\\
3x_1&-&3x_2&-&2x_3&+&8x_4&=&10\\
4x_1&-&4x_2&-&5x_3&+&6x_4&=&18
\end{array}
\end{eqnarray*}
is
\begin{eqnarray*}
\left[\begin{array}{rrrr|r}
1 & -1 & -1 & 1 & 4\\
3 & -3 & -2 & 8 & 10\\
4 & -4 & -5 & 6 & 18
\end{array}\right]
\end{eqnarray*}

Example 3: The linear system in the unknown variables $x_1$, $x_2$, $x_3$, and $x_4$ corresponding to the augmented matrix

\begin{eqnarray*}
\left[\begin{array}{cccc|c}
5 & 7 & 3 & 3 & 2\\
0 &-1 & 1 & 1 &-1\\
0 & 1 &-1 &-1 & 1\\
4 & 5 & 3 & 3 & 1
\end{array}\right]
\end{eqnarray*}
is given by
\begin{eqnarray*}
\begin{array}{ccccccccc}
5x_1&+&7x_2&+&3x_3&+&3x_4&=&2\\
&-& x_2&+& x_3&+& x_4&=&-1\\
& & x_2&-& x_3&-& x_4&=& 1\\
4x_1&+&5x_2&+&3x_3&+&3x_4&=&1
\end{array}
\end{eqnarray*}

Elementary Row Operations

Elementary row operations are simple operations that allow us to transform a system of linear equations into an equivalent system, that is, into a new system of equations having the same solutions as the original system. The idea is to apply these operations iteratively to simplify the linear system to a point where one can easily write down the solution set.

There are three basic operations, called elementary operations, that can be performed on equations:

• Multiply an equation by a nonzero constant.
• Interchange two equations.
• Add a constant times one equation to another.

These operations on equations have their corresponding operations on the rows of the associated augmented matrix. The correspondence is given by the following.

• Multiplying the $i$-th equation of \eqref{linear-system} by a nonzero constant $c$ correponds to multiplying the $i$-th row of the augmented matrix by the same nonzero constant $c$.
• Interchanging the $i$-th equation with the $j$-th equation corresponds to interchanging the $i$-th row with the $j$-th row of the augmented matrix.
• Adding a multiple of the $i$-th equation to the $j$-equation of \eqref{linear-system} corresponds to adding the same multiple of the $i$ row of the augmented matrix to the $j$-th row of the augmented matrix.

These operations do not alter the solution set. In other words, performing row operations to an augmented matrix does not change the solution set of the corresponding linear system.

Since the elementary row operations do not alter the solution set, any linear system is equivalent to the linear system obtained by performing some elementary row operations to the initial system.

Example 4: Consider the following augmented matrix
$$\left[\begin{array}{rrrr|r}
5& 7 & 3 & 3 & 2\\
0& -1 & 1 & 1 & -1\\
2& 1 & -1 & -1 & 1\\
4& 5 & 3 & 3 & 1\\
\end{array}\right].$$

1. Multiply the third row by $3$:\begin{eqnarray*}
   \left[\begin{array}{rrrr|r}
   5& 7 & 3 & 3 & 2\\
   0& -1 & 1 & 1 & -1\\
   2& 1 & -1 & -1 & 1\\
   4& 5 & 3 & 3 & 1\\
   \end{array}\right]
   \, \underrightarrow{R_3 \to 3R_3}
   \left[\begin{array}{rrrr|r}
   5& 7 & 3 & 3 & 2\\
   0& -1 & 1 & 1 & -1\\
   6& 3 & -3 & -3 & 3\\
   4& 5 & 3 & 3 & 1\\
   \end{array}\right]
   \end{eqnarray*}
2. Add $3$ times the third row to the first row:\begin{eqnarray*}
   \left[\begin{array}{rrrr|r}
   5& 7 & 3 & 3 & 2\\
   0& -1 & 1 & 1 & -1\\
   2& 1 & -1 & -1 & 1\\
   4& 5 & 3 & 3 & 1\\
   \end{array}\right]
   \, \underrightarrow{R_1 \to R_1+3R_3}
   \left[\begin{array}{rrrr|r}
   11& 10 & 0 & 0 & 5\\
   0& -1 & 1 & 1 & -1\\
   2& 1 & -1 & -1 & 1\\
   4& 5 & 3 & 3 & 1\\
   \end{array}\right]
   \end{eqnarray*}
3. Interchange the second and the fourth row:\begin{eqnarray*}
   \left[\begin{array}{rrrr|r}
   5& 7 & 3 & 3 & 2\\
   0& -1 & 1 & 1 & -1\\
   2& 1 & -1 & -1 & 1\\
   4& 5 & 3 & 3 & 1\\
   \end{array}\right]
   \, \underrightarrow{R_2\leftrightarrow R_4}
   \left[\begin{array}{rrrr|r}
   5& 7 & 3 & 3 & 2\\
   4& 5 & 3 & 3 & 1\\
   2& 1 & -1 & -1 & 1\\
   0& -1 & 1 & 1 & -1\\
   \end{array}\right]
   \end{eqnarray*}

Example 5: Consider the augmented matrix
\begin{eqnarray*}
\left[\begin{array}{rrrr|r}
5 & -1 & -1 & 2 & 4\\
3 & -3 & -2 & 8 & 10\\
4 & -4 & -5 & 6 & 18
\end{array}\right]
\end{eqnarray*}
Find a single elementary row operation that will create a $1$ in the upper left corner of the given augmented matrix and not create any fractions in its first row.

\begin{eqnarray*}
\left[\begin{array}{rrrr|r}
5 & -1 & -1 & 2 & 4\\
3 & -3 & -2 & 8 & 10\\
4 & -4 & -5 & 6 & 18
\end{array}\right]\, \underrightarrow{R_1 \to R_1-R_3}
\left[\begin{array}{rrrr|r}
\boxed{ 1} & 3 & 4 & -4 & -14\\
3 & -3 & -2 & 8 & 10\\
4 & -4 & -5 & 6 & 18
\end{array}\right]
\end{eqnarray*}

Example 6: Consider the augmented matrix
\begin{eqnarray*}
\left[\begin{array}{rrrr|r}
0 & -1 & -1 & 2 & 4\\
1 & -3 & -2 & 8 & 10\\
4 & -4 & -5 & 6 & 18
\end{array}\right]
\end{eqnarray*}
Find a single elementary row operation that will create a $1$ in the upper left corner of the given augmented matrix and not create any fractions in its first row.

\begin{eqnarray*}
\left[\begin{array}{rrrr|r}
0 & -1 & -1 & 2 & 4\\
1 & -3 & -2 & 8 & 10\\
4 & -4 & -5 & 6 & 18
\end{array}\right]\, \underrightarrow{R_1 \leftrightarrow R_2}
\left[\begin{array}{rrrr|r}
\boxed{ 1} & -3 & -2 & 8 & 10\\
0 & -1 & -1 & 2 & 4\\
4 & -4 & -5 & 6 & 18
\end{array}\right]
\end{eqnarray*}

Example 7: Consider the augmented matrix
\begin{eqnarray*}
\left[\begin{array}{rrrr|r}
-2 & -2 & -6 & 2 & 4\\
7 & -3 & -2 & 2 & 10\\
-5 & -2 & -5 & 6 & 1
\end{array}\right]
\end{eqnarray*}
Find a single elementary row operation that will create a $1$ in the upper left corner of the given augmented matrix and will not create any fractions in its first row.

\begin{eqnarray*}
\left[\begin{array}{rrrr|r}
-2 & -2 & -6 & 2 & 4\\
7 & -3 & -2 & 2 & 10\\
-5 & -2 & -5 & 6 & 1
\end{array}\right]\, \underrightarrow{R_1 \to -\frac{1}{2} R_2}
\left[\begin{array}{rrrr|r}
\boxed{ 1} & 1 & 3 & -1 & -2\\
7 & -3 & -2 & 2 & 10\\
-5 & -2 & -5 & 6 & 1
\end{array}\right]
\end{eqnarray*}

Example 8: Find all values of $k$ for which the given augmented matrix corresponds to a consistent linear system.

\begin{eqnarray*}
\left[\begin{array}{cc|c}
1 & k & -4 \\
4 & 8 & 2
\end{array}\right]
\end{eqnarray*}

\begin{eqnarray*}
\left[\begin{array}{cc|c}
1 & k & -4 \\
4 & 8 & 2
\end{array}\right]\, \underrightarrow{R_2 \to – 4R_1}
\left[\begin{array}{cc|c}
1 & k & -4 \\
0 & 8-4k & 18
\end{array}\right]
\end{eqnarray*}

Going back to the linear system, we have
\begin{eqnarray*}
\begin{array}{ccccccc}
x&+&ky&=&-4\\
&&(8-4k)y&=&18
\end{array}
\end{eqnarray*}

If $8-2k=0$, that is $k=2$, then the second equation becomes
$$0=18$$
which is a contradiction. Hence the system will be inconsistent when $k=2$. Therefore the system is consistent if and only if $k\neq 2$.

Example 9: Find all values of $k$ for which the given
augmented matrix corresponds to a consistent linear system.

\begin{eqnarray*}
\left[\begin{array}{cc|c}
k & 1 & -2 \\
4 & -1 & 2
\end{array}\right]
\end{eqnarray*}

\begin{eqnarray*}
&&\left[\begin{array}{cc|c}
k & 1 & -2 \\
4 & -1 & 2
\end{array}\right]\, \underrightarrow{R_1 \leftrightarrow R_1}
\left[\begin{array}{cc|c}
4 & -1 & 2\\
k & 1 & -2 \\
\end{array}\right]
\, \underrightarrow{R_1 \to \frac{1}{4} R_1}
\left[\begin{array}{cc|c}
1 & -\frac{1}{4} & \frac{1}{2}\\
k & 1 & -2 \\
\end{array}\right]\\
&&\, \underrightarrow{R_2 \to R_2-k R_1}
\left[\begin{array}{cc|c}
1 & -\frac{1}{4} & \frac{1}{2}\\
0 & 1+\frac{k}{4} & -2-\frac{k}{2} \\
\end{array}\right]
\end{eqnarray*}

Going back to the linear system, we have
\begin{eqnarray*}
\begin{array}{ccccccc}
x&-&\frac{1}{4} y&=&\frac{1}{2}\\
&&\left(1+\frac{k}{4}\right) y&=&-2-\frac{k}{2}
\end{array}
\end{eqnarray*}

If $1+\frac{k}{4}=0$ and $-2-\frac{k}{2}\neq 0$, then the second equation becomes
$$0=-2-\frac{k}{2}\neq 0$$
which is a contradiction. Hence the system will be inconsistent. Therefore the system is inconsistent if and only if $1+\frac{k}{4}=0$ and $-2-\frac{k}{2}\neq 0$. That is, $k= -4$ and $k\neq -4$. This is impossible since we cannot simultaneously have $k=-4$ and $k\neq -4$. This means there is no value of $k$ for which the system is inconsistent. Therefore it is consistent with any value of $k$.

Row Echelon Form and Gaussian Elimination

Example 10: The following matrices are in Reduced Row Echelon Form:

$$\left[\begin{array}{rrr|r}
1&0&0&0\\
0&1&0&0\\
0&0&1&8
\end{array}\right],\qquad
\left[\begin{array}{rrr|r}
1&2&0&6\\
0&0&1&7
\end{array}\right],\qquad
\left[\begin{array}{rrr|r}
1&8&-2&6
\end{array}\right]
,\qquad
\left[\begin{array}{rrr|r}
0&0&0&1\\
0&0&0&0
\end{array}\right]
$$

$$\left[\begin{array}{rrrr|r}
0&0&0&0&0\\
0&0&0&0&0\\
0&0&0&0&0
\end{array}\right],\qquad
\left[\begin{array}{rrr|r}
1\\
0\\
0\\
0
\end{array}\right]
,\qquad
\left[\begin{array}{rrrr|r}
0&0&1&0&-3\\
0&0&0&0&0
\end{array}\right]
,\qquad
\left[\begin{array}{rrrr|r}
0&1&2&0&6\\
0&0&0&1&7\\
0&0&0&0&0
\end{array}\right]$$

Example 11: The following matrices are in Row Echelon Form but not in Reduced Row Echelon Form:

$$\left[\begin{array}{rrr|r}
1&2&0&0\\
0&1&0&0\\
0&0&1&8
\end{array}\right],\qquad
\left[\begin{array}{rrr|r}
1&2&-1&6\\
0&0&1&7
\end{array}\right],\qquad
\left[\begin{array}{rrrr|r}
0&1&8&-2&6\\
0&0&0&0&1\\
\end{array}\right].
$$

Example 12: The following matrices are not in Row Echelon Form (and therefore, they are not in Reduced Row Echelon Form):

$$\left[\begin{array}{rrr|r}
1&2&0&0\\
0&0&1&8\\
0&1&0&0
\end{array}\right],\qquad
\left[\begin{array}{rrr|r}
1&2&-1&6\\
0&0&2&7
\end{array}\right],\qquad
\left[\begin{array}{rrrr|r}
0&1&8&-2&6\\
0&0&0&0&5\\
\end{array}\right]
,\qquad
\left[\begin{array}{rrr|r}
0&0&0&0\\
0&0&0&1
\end{array}\right]
$$

Row Reduction Algorithm

Given any matrix, there is a procedure that finds an REF and the RREF. The following algorithm describes the steps to find an REF and the RREF.

Algorithm to find an REF

1. Begin with an $m\times n$ matrix $A$. If $A=0$, then go to step $7$.
2. Determine the leftmost non-zero column.
3. Use elementary row operations to put a $1$ in this column’s topmost position (we call this position pivot position).
4. Use elementary row operations to make all entries in the column below the \textbf{pivot} equal to zero.Recommendation: use only elementary row operations of the type $R_i\to R_i+c\cdot R_1$.
5. If there are no more non-zero rows (strictly) below the pivot position, then go to Step 7.
6. Repeat Step 2-5 to the submatrix consisting of the rows that lie
   (strictly below) the pivot position.
7. The resulting matrix is in Row Echelon Form.

Further, proceeding as follows, we can reduce a Row Echelon Form to the Reduced Row Echelon Form.

Algorithm to find the RREF

1. Find the Row Echelon Form as above.
2. Determine all the leading ones in the Row Echelon Form obtained in Step 1.
3. Eliminate all nonzero entries above each pivot, starting with the last pivot.
4. The resulting matrix is in Reduced Row Echelon Form.

Example 13: Find an REF, then the RREF of the matrix $\left[\begin{array}{rrrr|r}
0 & 1 & 4 & 1 & 3\\
0 & 1 & 4 & -3 & 1\\
0 & 0 & 0 & 1 & 0\\
2 & 0 & 0 & 6 & -2
\end{array}\right]$.

We have:
\begin{eqnarray*}
&&\left[\begin{array}{rrrr|r}
0 & 1 & 4 & 1 & 3\\
0 & 1 & 4 & -3 & 1\\
0 & 0 & 0 & 1 & 0\\
2 & 0 & 0 & 6 & -2
\end{array}\right]
\, \underrightarrow{R_1 \leftrightarrow R_4}
\left[\begin{array}{rrrr|r}
2 & 0 & 0 & 6 & -2\\
0 & 1 & 4 & -3 & 1\\
0 & 0 & 0 & 1 & 0\\
0 & 1 & 4 & 1 & 3
\end{array}\right]
\, \underrightarrow{R_1\to \dfrac{1}{2} R_1}
\\
& &
\left[\begin{array}{rrrr|r}
1 & 0 & 0 & 3 & -1\\
0 & 1 & 4 & -3 & 1\\
0 & 0 & 0 & 1 & 0\\
0 & 1 & 4 & 1 & 3
\end{array}\right]
\, \underrightarrow{R_3\to R_3- R_2}
\left[\begin{array}{rrrr|r}
1 & 0 & 0 & 3 & -1\\
0 & 1 & 4 & -3 & 1\\
0 & 0 & 0 & 1 & 0\\
0 & 0 & 0 & 4 & 2
\end{array}\right]\, \underrightarrow{R_4\to R_4-4 R_3}
\\
&&
\left[\begin{array}{rrrr|r}
1 & 0 & 0 & 3 & -1\\
0 & 1 & 4 & -3 & 1\\
0 & 0 & 0 & 1 & 0\\
0 & 0 & 0 & 0 & 2
\end{array}\right]
\, \underrightarrow{R_4\to \dfrac{1}{2} R_4}
\left[\begin{array}{rrrr|r}
1 & 0 & 0 & 3 & -1\\
0 & 1 & 4 & -3 & 1\\
0 & 0 & 0 & 1 & 0\\
0 & 0 & 0 & 0 & 1
\end{array}\right]\qquad\mbox{REF}\\
&&\begin{array}{r}\, \underrightarrow{R_2\to R_2-R_4}\\
R_1\to R_1+R_4\\
{}
\end{array}
\left[\begin{array}{rrrr|r}
1 & 0 & 0 & 3 & 0\\
0 & 1 & 4 & -3 & 0\\
0 & 0 & 0 & 1 & 0\\
0 & 0 & 0 & 0 & 1
\end{array}\right]
\begin{array}{r}\, \underrightarrow{R_2\to R_2+3R_3}\\
R_1\to R_1-3R_3\\
{}
\end{array}
\left[\begin{array}{rrrr|r}
1 & 0 & 0 & 0 & 0\\
0 & 1 & 4 & 0 & 0\\
0 & 0 & 0 & 1 & 0\\
0 & 0 & 0 & 0 & 1
\end{array}\right]\\
&&\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\mbox{RREF}
\end{eqnarray*}

Example 14: Find the RREF of the matrix $\left[\begin{array}{rrrr|r}
1 & -1 & -1 & 2 & 4\\
3 & -3 & -2 & 8 & 10\\
4 & -4 & -5 & 6 & 18
\end{array}\right]$.

We have:
\begin{eqnarray*}
& & \left[\begin{array}{rrrr|r}
1 & -1 & -1 & 2 & 4\\
3 & -3 & -2 & 8 & 10\\
4 & -4 & -5 & 6 & 18
\end{array}\right]
\begin{array}{r}
\\
\underrightarrow{R_2\to R_2-3R_1}\\
R_3\to R_3-4R_1\\
{}
\end{array}
\left[\begin{array}{rrrr|r}
1 & -1 & -1 & 2 & 4\\
0 & 0 & 1 & 2 & -2\\
0 & 0 & -1 & -2 & 2
\end{array}\right]\\
& &\begin{array}{r}
\\
\\
\underrightarrow{R_3\to R_3+R_2}\\
{}\\
{}
\end{array}
\left[\begin{array}{rrrr|r}
1 & -1 & -1 & 2 & 4\\
0 & 0 & 1 & 2 & -2\\
0 & 0 & 0 & 0 & 0
\end{array}\right]\qquad \mbox{REF}\\
&&
\begin{array}{r}
\\
\\
\underrightarrow{R_1\to R_1+R_2}\\
{}\\
{}
\end{array}
\left[\begin{array}{rrrr|r}
\boxed{1} & -1 & 0 & 4 & 2\\
0 & 0 & \boxed{1} & 2 & -2\\
0 & 0 & 0 & 0 & 0
\end{array}\right]\qquad \mbox{RREF}
\end{eqnarray*}

Example 15: Find the RREF of the matrix
$\begin{bmatrix}
0 & 2 & 2\\
2 & 6 & 4\\
1 & 1 & 1
\end{bmatrix}$.

We have:
\begin{eqnarray*}
& & \begin{bmatrix}
0 & 2 & 2\\
2 & 6 & 4\\
1 & 1 & 1
\end{bmatrix}
\begin{array}{r}
\\
\underrightarrow{R_1\leftrightarrow R_3 }\\
{}
\end{array}
\begin{bmatrix}
1 & 1 & 1\\
2 & 6 & 4\\
0 & 2 & 2
\end{bmatrix}
\begin{array}{r}
\\
\underrightarrow{R_2 \to R_2-2R_1}\\
{}
\end{array}
\begin{bmatrix}
1 & 1 & 1\\
0 & 4 & 2\\
0 & 2 & 2
\end{bmatrix}
\begin{array}{r}
\\
\underrightarrow{R_3 \to R_3-\frac{1}{2} R_2}\\
{}
\end{array}\\
&&
\begin{bmatrix}
1 & 1 & 1\\
0 & 4 & 2\\
0 & 0 & 1
\end{bmatrix}
\begin{array}{r}
\\
\underrightarrow{R_2 \to \frac{1}{4} R_2}\\
{}
\end{array}
\begin{bmatrix}
1 & 1 & 1\\
0 & 1 & \frac{1}{2}\\
0 & 0 & 1
\end{bmatrix}
\begin{array}{r}
\\
\underrightarrow{R_1 \to R_1-R_2}\\
{}
\end{array}
\begin{bmatrix}
1 & 0 & \frac{1}{2}\\
0 & 1 & \frac{1}{2}\\
0 & 0 & 1
\end{bmatrix}\\
&&
\begin{array}{r}
\\
\underrightarrow{R_2 \to R_2-\frac{1}{2} R_3}\\
{}
\end{array}
\begin{bmatrix}
1 & 0 & \frac{1}{2}\\
0 & 1 & 0\\
0 & 0 & 1
\end{bmatrix}
\begin{array}{r}
\\
\underrightarrow{R_1 \to R_1-\frac{1}{2} R_3}\\
{}
\end{array}
\begin{bmatrix}
1 & 0 & 0\\
0 & 1 & 0\\
0 & 0 & 1
\end{bmatrix}\quad \mbox{RREF}
\end{eqnarray*}

The uniqueness of the RREF is interesting. This means no matter how you row reduce; you always get the same matrix in reduced row echelon form. But we can have different REFs for a matrix.

Gaussian Elimination

We can solve a linear system using back-substitution or Gaussian Elimination. The procedure is the following.

1. Convert the augmented matrix of the linear system into its REF.
2. Set each \textbf{free variable} as a parameter.
3. Solve for the \textbf{leading variables} in terms of the free variables.

We illustrate this with an example.

Example 16: Suppose that the augmented matrix for a linear system has been reduced by row operations to Row Echelon Form
$\left[\begin{array}{rrrr|r}
1 & -1 & -1 & 2 & 4\\
0 & 0 & 1 & 2 & -2\\
0 & 0 & 0 & 0 & 0
\end{array}\right]$. Solve the linear system.

First, we write down the linear system corresponding to the given REF
$$\left[\begin{array}{rrrr|r}
1 & -1 & -1 & 2 & 4\\
0 & 0 & 1 & 2 & -2\\
0 & 0 & 0 & 0 & 0
\end{array}\right],$$
and we obtain the following:
\begin{eqnarray*}
\begin{array}{cccccccc}
x_1&-&x_2&- &x_3 &+&2x_4=&4\\
& & & &x_3&+&2x_4=&-2
\end{array}
\end{eqnarray*}
There are two leading $1$s: in the first and third columns. Hence the variables $x_1$ and $x_3$ are leading variables. The remaining variables ($x_2$ and $x_4$) are free variables, so they can be set as parameters. Let $x_2=t$ and $x_4=s$. It follows that
\begin{eqnarray*}
x_3&=&-2-2x_4=-2-2s\\
x_1&=&4+x_2+x_3-2x_4=4+t-2-2s-2s=2+t-4s.
\end{eqnarray*}
Hence the parametric solutions are
\begin{eqnarray*}
x_1&=&2+t-4s\\
x_2&=&t\\
x_3&=&-2-2s\\
x_4&=&s,\qquad\qquad\qquad t,s\in\mathbb{R}.
\end{eqnarray*}

Gauss-Jordan Elimination

We can solve a linear system by a method called Gauss-Jordan Elimination. The procedure is the following.

1. Convert the augmented matrix of the linear system into its RREF.
2. Set each free variable as a parameter.
3. Solve for the leading variables in terms of the free variables.

Example 17: Use the Gauss-Jordan elimination method to find the parametric form of the solution set for the following linear system:
\[\begin{array}{rrrrrrrrr}
x_1&-&x_2&-&x_3&+&2x_4&=&4\\
3x_1&-&3x_2&-&2x_3&+&8x_4&=&10\\
4x_1&-&4x_2&-&5x_3&+&6x_4&=&4\\
\end{array}\]

Since we are asked to solve the given linear system by the Gauss-Jordan method, we need to find the RREF. Applying row operations to the augmented matrix of the system, we get \begin{eqnarray*}
& & \left[\begin{array}{rrrr|r}
1 & -1 & -1 & 2 & 4\\
3 & -3 & -2 & 8 & 10\\
4 & -4 & -5 & 6 & 18
\end{array}\right]
\begin{array}{r}
\\
\underrightarrow{R_2\to R_2-3R_1}\\
R_3\to R_3-4R_1\\
{}
\end{array}
\left[\begin{array}{rrrr|r}
1 & -1 & -1 & 2 & 4\\
0 & 0 & 1 & 2 & -2\\
0 & 0 & -1 & -2 & 2
\end{array}\right]\\
& &\begin{array}{r}
\\
\\
\underrightarrow{R_3\to R_3+R_2}\\
{}\\
{}
\end{array}
\left[\begin{array}{rrrr|r}
1 & -1 & -1 & 2 & 4\\
0 & 0 & 1 & 2 & -2\\
0 & 0 & 0 & 0 & 0
\end{array}\right]
\begin{array}{r}
\\
\\
\underrightarrow{R_1\to R_1+R_2}\\
{}\\
{}
\end{array}\\
&&
\left[\begin{array}{rrrr|r}
\boxed{1} & -1 & 0 & 4 & 2\\
0 & 0 & \boxed{1} & 2 & -2\\
0 & 0 & 0 & 0 & 0
\end{array}\right]\qquad\qquad\mbox{RREF}
\end{eqnarray*}

There are two leading $1$s: in the first and third columns. Hence $x_1$ and $x_3$ are \textbf{leading variables}, and the remaining variables, $x_2$ and $x_4$ are free variables. Since $x_2$ and $x_4$ are free variables, we can set them as parameters. So we let $x_2=t$ and $x_4=s$ and solve for $x_1$ and $x_3$ in terms of the parameters $s$ and $t$. Then
\begin{eqnarray*}
x_1&=&x_2-4x_4+2=t-4s+2\\
x_3&=&-2x_4-2=-2s-2
\end{eqnarray*}

Therefore the parametric solutions are:
\begin{eqnarray*}
x_1&=&t-4s+2\\
x_2&=&t\\
x_3&=&-2s-2\\
x_4&=&s,\qquad\qquad \mbox{$s$, $t$ in $\mathbb{R}$}.
\end{eqnarray*}