# Row-Echelon Form


## Row Echelon Form

Some systems, after following elimination, result in cases where strict triangular form cannot be reached. For example:

$$
\begin{cases}
  x_1 + 2x_2 = 3 \\
  2x_1 + 4x_2 = 7
\end{cases}
$$

After going through elimination, the result is this matrix:

$$
\left[
  \begin{array}{cc|c}
    1 & 2 & 3 \\
    0 & 0 & 1
  \end{array}
\right]
$$

Which shows that the system is **inconsistent** (as it states that $0 = 1$).

These kind of matrices which are not triangular but result in a decreasing amount of non-zero coefficients are in **row-echelon** form. 

~~Example 1

$$
\left[
  \begin{array}{ccccc|c}
    1 & 1 & 1 & 1 & 1 & 1 \\
    -1 & -1 & 0 & 0 & 1 & -1 \\
    -2 & -2 & 0 & 0 & 5 & 1 \\
    0 & 0 & 1 & 1 & 3 & 1 \\
    1 & 1 & 2 & 2 & 4 & 2 \\
  \end{array}
\right]
$$

Following elimination to get rid of the first column, we get:

$$
\left[
  \begin{array}{ccccc|c}
    1 & 1 & 1 & 1 & 1 & 1 \\
    0 & 0 & 1 & 1 & 2 & 0 \\
    0 & 0 & 2 & 2 & 7 & 3 \\
    0 & 0 & 1 & 1 & 3 & 1 \\
    0 & 0 & 1 & 1 & 3 & 1 \\
  \end{array}
\right]
$$

Which already has a problem. There is no row to work from for the second column! Instead, we can start on column three.

$$
\left[
  \begin{array}{ccccc|c}
    1 & 1 & 1 & 1 & 1 & 1 \\
    0 & 0 & 1 & 1 & 2 & 0 \\
    0 & 0 & 0 & 0 & 3 & 3 \\
    0 & 0 & 0 & 0 & 1 & 1 \\
    0 & 0 & 0 & 0 & 1 & 1 \\
  \end{array}
\right]
$$

And then simplifying the third row to get a cleaner matrix, and subtracting from the last two rows to eliminate them:

$$
\left[
  \begin{array}{ccccc|c}
    1 & 1 & 1 & 1 & 1 & 1 \\
    0 & 0 & 1 & 1 & 2 & 0 \\
    0 & 0 & 0 & 0 & 1 & 1 \\
    0 & 0 & 0 & 0 & 0 & 0 \\
    0 & 0 & 0 & 0 & 0 & 0 \\
  \end{array}
\right]
$$

This is about as simple as we can get this system, but it is not in strict triangular form. Instead it is in **row-echelon form**.

~~

> **Definition:** Row-Echelon Form  
> A matrix in row-echelon form requires that:
> 1. The first non-zero entry in every row is 1
> 2. The number of leading zero entries in each row is greater than the one above it
> 3. The all-zero rows are below all other rows (which contain at least one non-zero entry)

Once we reach RE form, looking at the last few rows can quickly tell us if there are no solutions, or many solutions. If any row contains all zero coefficients, but is equal to a non-zero constant, there is no solution (as no value of $x_n$ will result in that constant).

If all the rows are all zero or have non-zero coefficients, then the system has many solutions, which can be found by substitution back into equations and solving for the variables that can be solved (lead variables) and leaving the others (free variables) undetermined, as they can be any number.

> **Definition:**  
> **Lead variables** are variables which correspond to the first non-zero coefficient in one row. 
> **Free variables** are variables which have no row where they have the first non-zero coefficient.

Solving for the lead variables and substituting a free constant for the free variables allows us to reach a solution (which represents infinitely many solutions because the constants can have any value).

> **Definition:** Gaussian Elimination  
> The process of transforming a matrix into RE form.

~~Example 2

$$
\left[
  \begin{array}{ccccc|c}
    1 & 1 & 1 & 1 & 1 & 1 \\
    0 & 0 & 1 & 1 & 2 & 0 \\
    0 & 0 & 0 & 0 & 1 & 1 \\
    0 & 0 & 0 & 0 & 0 & 0 \\
    0 & 0 & 0 & 0 & 0 & 0 \\
  \end{array}
\right]
$$

Taking the result we reached earlier, the lead variables are $x_1$, $x_3$, and $x_5$, and the free ones are $x_2$ and $x_4$.

$$
\begin{cases}
\begin{aligned}
  x_1 + x_2 + x_3 + x_4 + x_5 = 1 \\
  x_3 + x_4 + 2x_5 = 0 \\
  x_5 = 1 \\
\end{aligned}
\end{cases}
$$

Solving for the lead variables gives us:

$$x_5 = 1$$
$$x_3 = - x_4 - 2$$
$$x_1 = 2 - x_2$$

And substituting $s$ and $t$ for the free variables, we reach the solution:

$$(2-t,t,-s-2,s,1)$$

Note that there are infinitely many solutions, as both $s$ and $t$ can be any value.

~~

### Reduced RE Form

So how about instead of using back substitution, we continue to operate on the matrix to reach a **reduced RE form**. 

> **Definition:** Reduced RE Form  
> A matrix which is:
> 1. In RE form
> 2. Each lead variable entry is the only non-zero entry in its column

To reach this form, we use elimination to remove all entries which are in the same column as lead variable entries.

~~Example 3

$$
\begin{array}{c}
A \\ B \\ C \\ D \\ E
\end{array}
\left[
  \begin{array}{ccccc|c}
    1 & 1 & 1 & 1 & 1 & 1 \\
    0 & 0 & 1 & 1 & 2 & 0 \\
    0 & 0 & 0 & 0 & 1 & 1 \\
    0 & 0 & 0 & 0 & 0 & 0 \\
    0 & 0 & 0 & 0 & 0 & 0 \\
  \end{array}
\right]
$$

Again starting with the matrix from earlier, we attempt to clean up the columns with lead variables so that they only have one non-zero entry. So, first we manipulate the rows with $A - C$ and $B - 2C$. This yields:

$$
\begin{array}{c}
A \\ B \\ C \\ D \\ E
\end{array}
\left[
  \begin{array}{ccccc|c}
    1 & 1 & 1 & 1 & 0 & 0 \\
    0 & 0 & 1 & 1 & 0 & -2 \\
    0 & 0 & 0 & 0 & 1 & 1 \\
    0 & 0 & 0 & 0 & 0 & 0 \\
    0 & 0 & 0 & 0 & 0 & 0 \\
  \end{array}
\right]
$$

Next, we can do $A - B$ to eliminate more of the elements:

$$
\begin{array}{c}
A \\ B \\ C \\ D \\ E
\end{array}
\left[
  \begin{array}{ccccc|c}
    1 & 1 & 0 & 0 & 0 & 2 \\
    0 & 0 & 1 & 1 & 0 & -2 \\
    0 & 0 & 0 & 0 & 1 & 1 \\
    0 & 0 & 0 & 0 & 0 & 0 \\
    0 & 0 & 0 & 0 & 0 & 0 \\
  \end{array}
\right]
$$

This is in **reduced RE form**. Now after back-substitution, it is simple to solve for the lead variables:

$$
\begin{cases}
x_1 + x_2 = 2 \\
x_3 + x_4 = -2 \\
x_5 = 1
\end{cases}
$$

To get the solution:

$$(2-t,t,-2-s,s,1)$$

~~

So when solving a linear system, once a RE form is reached, you can solve it either through back substitution or reduced RE form. They will both yield the same solution.

~~Example 4: more detail

$$
\left[
  \begin{array}{ccc|c}
    1 & -1 & 2 & 3 \\
    1 & 1 & 3 & 6 \\
    2 & 0 & b & 9
  \end{array}
\right]
$$

With this matrix, we can find for which values of $b$ the system has:
1. 1 solution
2. $\infty$ solutions
3. 0 solutions

So, working through the process, we result in:

$$
\left[
  \begin{array}{ccc|c}
    1 & -1 & 2 & 3 \\
    0 & 1 & \frac{1}{2} & \frac{3}{2} \\
    0 & 0 & b-5 & 0
  \end{array}
\right]
$$

From here we can divide by $b-5$ (as long as $b \ne 5$):

$$
\left[
  \begin{array}{ccc|c}
    1 & -1 & 2 & 3 \\
    0 & 1 & \frac{1}{2} & \frac{3}{2} \\
    0 & 0 & 1 & 0
  \end{array}
\right]
$$

Which has one solution. In the case that $b = 5$, we get:

$$
\left[
  \begin{array}{ccc|c}
    1 & -1 & 2 & 3 \\
    0 & 1 & \frac{1}{2} & \frac{3}{2} \\
    0 & 0 & 0 & 0
  \end{array}
\right]
$$

Which has infinitely many solutions

~~

<script src="/source/texme.js"></script>
<link rel="stylesheet" href="/source/theme.css">