Echelon form

leading and free variables

In each row of a system, the first variable with a nonzero coefficient is the row’s leading (basic) variable.

A system is in Echelon form if each leading variable is to the right of the leading variable in the row above it, except for the leading variable in the first row, and any all-zero rows are at the bottom.

The above form we will call Upper Triangular form. Many software tools give the Reduced Echelon form, described a bit later, when Echelon form is called. There is little difference between the computational complexity of Echelon and Reduced Echelon form. There are multiple advantages to have the Reduced form at hand. In certain ways in the $L U$ decomposition the Echelon form and not the Reduced Echelon form appears. This is subject for a different time.

The system of linear equations

\begin{matrix} x_{1} & + 3 x_{2} & + 3 x_{3} & + 2 x_{4} & + x_{5} & = & 7 \\ 3 x_{1} & + 9 x_{2} & - 6 x_{3} & + 4 x_{4} & + 3 x_{5} & = & -7 \\ 2 x_{1} & + 6 x_{2} & - 4 x_{3} & + 2 x_{4} & + 2 x_{5} & = & -4 \end{matrix}

is not in Echelon Form. Every equation has the same leading variable namely $x_{1}$ .

The augmented matrix of the above system of linear equations is

(\begin{matrix} 1 & 3 & 3 & 2 & 1 & 7 \\ 3 & 9 & -6 & 4 & 3 & -7 \\ 2 & 6 & -4 & 2 & 2 & -4 \end{matrix})

Lets identify the positions of leading variables with $*$ (meaning a non-zero value) and put a placeholder $\times$ (this is any value) in place of all other coefficients.

(\begin{matrix} * & \times & \times & \times & \times & \times \\ * & \times & \times & \times & \times & \times \\ * & \times & \times & \times & \times & \times \end{matrix})

The system of linear equations

\begin{matrix} x_{1} & + 3 x_{2} & + 3 x_{3} & + 2 x_{4} & + x_{5} & = & 7 \\ -15 x_{3} & - 2 x_{4} & = & -28 \\ -10 x_{3} & -2 x_{4} & = & -18 \end{matrix}

is not in Echelon Form. First equation has leading variable $x_{1}$ . The leading variable of the second and third equations are both $x_{3}$ .

As before write the augmented matrix and substitute with $*$ and $\times$ but write coefficients that are zeroes.

(\begin{matrix} * & \times & \times & \times & \times & \times \\ 0 & 0 & * & \times & \times & \times \\ 0 & 0 & * & \times & \times & \times \end{matrix})

The system of linear equations

\begin{matrix} x_{1} & + 3 x_{2} & + 3 x_{3} & + 2 x_{4} & + x_{5} & = & 7 \\ -15 x_{3} & - 2 x_{4} & = & -28 \\ \frac{-2}{3} x_{4} & = & \frac{2}{3} \\ 0 & = & 1 \end{matrix}

is in Echelon form. First equation has leading variable $x_{1}$ . The leading variable of the second is $x_{3}$ and the leading variable of the third equation is $x_{4}$ . There are no other leading variables.

As before write the augmented matrix and substitute with $*$ , $\times$ and $0$ .

(\begin{matrix} * & \times & \times & \times & \times & \times \\ 0 & 0 & * & \times & \times & \times \\ 0 & 0 & 0 & * & \times & \times \\ 0 & 0 & 0 & 0 & 0 & \times \end{matrix})

The dotted lines result in a inverted stair shape which indicates the system is in Echelon form.

The system of linear equations

\begin{matrix} x_{1} & + 3 x_{2} & + x_{5} & = & 3 \\ x_{3} & = & 2 \\ x_{4} & = & -1 \end{matrix}

is in Echelon form. First equation has leading variable $x_{1}$ . The leading variable of the second is $x_{3}$ and the leading variable of the third equation is $x_{4}$ . This system of linear equation is in Reduced Echelon form: each leading variable occurs with non-zero coefficient in exactly one row and every coefficient in front of the leading variable is one. Its shape is still an inverted stair shape but with extra zeroes.

(\begin{matrix} 1 & \times & 0 & 0 & \times & \times \\ 0 & 0 & 1 & 0 & \times & \times \\ 0 & 0 & 0 & 1 & \times & \times \end{matrix})

The non-leading variable in an Echelon form are called free variables.

In the last example the free variables and $x_{2}$ and $x_{5}$ . In Echelon form the number of leading variable plus the number of free variables equals the number of variables in the system of linear equations.