Linear Algebra – Systems of linear equations – Row reduction and echelon forms

Definition: A matrix is in echelon form if it has the following two properties:

  1. All nonzero rows are above any rows of all zeroes;

  2. Every nonzero row starts with more zeros than the row above it.

The matrix is in reduced echelon form if it also satifies the additional conditions:

  1. Every nonzero leading entry (pivot) in a (non-zero) row is \(1\);

  2. In each column containing such a \(1\) (pivot column) all other entries are zero (both above and below it).

A matrix in echelon form is also called an echelon matrix and a matrix in reduced echelon form is also called a reduced echelon matrix.

Theorem: Each matrix is row equivalent to one and only one reduced echelon matrix.

Proof: See Appendix A in Lay (this is skipped).

We use elementary row operations to transform a matrix into a row equivalent (reduced) echelon matrix. A row reduction process that leads to an echelon matrix is called Gauss elimination and a process that leads to a reduced echelon matrix is sometimes called Gauss-Jordan elimination. The first nonzero entry in a row, that is used during the row reduction process to create zeros below it, is called a pivot (this is the pivot of the computation).

Definition: A pivot position in a matrix is a location that corresponds to a pivot \(1\) in the reduced echelon form of the matrix. A column containing such a pivot position is called a pivot column.

For a system of linear equations we have three possibilities which can be illustrated using a reduced echelon form:

1) no solutions (an inconsistent system): \(\left(\left.\begin{array}{ccc}\fbox{1}&0&0\\[2.5mm]0&\fbox{1}&0\\[2.5mm]0&0&0\end{array}\;\right|\;\begin{array}{c}1\\[2.5mm]2\\[2.5mm]3\end{array}\right):\quad 0\cdot x_1+0\cdot x_2+0\cdot x_3=3\) is called a false equation.

2) infinitely many solutions: \(\left(\left.\begin{array}{ccc}\fbox{1}&0&0\\[2.5mm]0&\fbox{1}&0\\[2.5mm]0&0&0\end{array}\;\right|\;\begin{array}{c}1\\[2.5mm]2\\[2.5mm]0\end{array}\right):\quad \left\{\begin{array}{l}x_1=1\\[2.5mm]x_2=2\\[2.5mm]x_3\;\text{is free.}\end{array}\right.\quad\) \(x_1\) and \(x_2\) are called basic variables and \(x_3\) is called a free variable..

3) exaclty one solution (a unique solution): \(\left(\left.\begin{array}{ccc}\fbox{1}&0&0\\[2.5mm]0&\fbox{1}&0\\[2.5mm]0&0&\fbox{1}\end{array}\;\right|\;\begin{array}{c}1\\[2.5mm]2\\[2.5mm]3\end{array}\right):\quad \left\{\begin{array}{l}x_1=1\\[2.5mm]x_2=2\\[2.5mm]x_3=3.\end{array}\right.\quad\) Now \(x_1\), \(x_2\) and \(x_3\) are all basic variables.

Example 1: Find the solution of the system of linear equations \(\left\{\begin{array}{rrrcl}&-2x_2&+4x_3&=&0\\[2.5mm] x_1&+x_2&+3x_3&=&1\\[2.5mm]-3x_1&+2x_2&-14x_3&=&2.\end{array}\right.\)

Solution:

\begin{align*} &\left(\left.\begin{array}{ccc}0&-2&4\\[2.5mm]1&1&3\\[2.5mm]-3&2&-14\end{array}\;\right|\;\begin{array}{r}0\\[2.5mm]1\\[2.5mm]2\end{array}\right) \sim\left(\left.\begin{array}{ccc}\fbox{1}&1&3\\[2.5mm]0&-2&4\\[2.5mm]-3&2&-14\end{array}\;\right|\;\begin{array}{r}1\\[2.5mm]0\\[2.5mm]2\end{array}\right) \sim\left(\left.\begin{array}{ccc}\fbox{1}&1&3\\[2.5mm]0&-2&4\\[2.5mm]0&5&-5\end{array}\;\right|\;\begin{array}{r}1\\[2.5mm]0\\[2.5mm]5\end{array}\right)\\[2.5mm] &{}\sim\left(\left.\begin{array}{ccc}\fbox{1}&1&3\\[2.5mm]0&\fbox{1}&-2\\[2.5mm]0&1&-1\end{array}\;\right|\;\begin{array}{r}1\\[2.5mm]0\\[2.5mm]1\end{array}\right) \sim\left(\left.\begin{array}{ccc}\fbox{1}&0&5\\[2.5mm]0&\fbox{1}&-2\\[2.5mm]0&0&\fbox{1}\end{array}\;\right|\;\begin{array}{r}1\\[2.5mm]0\\[2.5mm]1\end{array}\right) \sim\left(\left.\begin{array}{ccc}\fbox{1}&0&0\\[2.5mm]0&\fbox{1}&0\\[2.5mm]0&0&\fbox{1}\end{array}\;\right|\;\begin{array}{r}-4\\[2.5mm]2\\[2.5mm]1\end{array}\right)\quad\Longrightarrow\quad \left\{\begin{array}{l}x_1=-4\\[2.5mm]x_2=2\\[2.5mm]x_3=1.\end{array}\right. \end{align*}

Example 2: Consider the system of linear equations \(\left\{\begin{array}{rrrcr}x_1&-x_2&-x_3&=&2\\[2.5mm] -x_1&+2x_2&-3x_3&=&-4\\[2.5mm]2x_1&&+\alpha x_3&=&\beta\end{array}\right.\quad(\alpha,\beta\in\mathbb{R}).\)

For which value(s) of \(\alpha\) and \(\beta\) does the system have no solutions, infinitely many solutions or exactly one solution?

Solution:

\[\left(\left.\begin{array}{ccc}\fbox{1}&-1&-1\\[2.5mm]-1&2&-3\\[2.5mm]2&0&\alpha\end{array}\;\right|\;\begin{array}{c}2\\[2.5mm]-4\\[2.5mm]\beta\end{array}\right) \sim\left(\left.\begin{array}{ccc}\fbox{1}&-1&-1\\[2.5mm]0&\fbox{1}&-2\\[2.5mm]0&2&\alpha+2\end{array}\;\right|\;\begin{array}{c}2\\[2.5mm]-2\\[2.5mm]\beta-4\end{array}\right) \sim\left(\left.\begin{array}{ccc}\fbox{1}&0&-3\\[2.5mm]0&\fbox{1}&-2\\[2.5mm]0&0&\alpha+6\end{array}\;\right|\;\begin{array}{c}0\\[2.5mm]-2\\[2.5mm]\beta\end{array}\right).\]

We see that there are no solutions if \(\alpha+6=0\) and \(\beta\neq0\), hence if \(\alpha=-6\) and \(\beta\neq0\).

There are infinitely many solutions if \(\alpha+6=0\) and \(\beta=0\), hence if \(\alpha=-6\) and \(\beta=0\):

\[\left(\left.\begin{array}{ccc}\fbox{1}&0&-3\\[2.5mm]0&\fbox{1}&-2\\[2.5mm]0&0&0\end{array}\;\right|\;\begin{array}{c}0\\[2.5mm]-2\\[2.5mm]0\end{array}\right) \quad\Longrightarrow\quad\left\{\begin{array}{l}x_1-3x_3=0\\[2.5mm]x_2-2x_3=-2\\[2.5mm]x_3\;\text{is free}\end{array}\right. \quad\Longrightarrow\quad\left\{\begin{array}{l}x_1=3x_3\\[2.5mm]x_2=-2+2x_3\\[2.5mm]x_3\;\text{is free.}\end{array}\right.\]

There is exactly one solution if \(\alpha+6\neq0\) (and \(\beta\) arbitrary) or equivalently if \(\alpha=-6\):

\[\left(\left.\begin{array}{ccc}\fbox{1}&0&-3\\[2.5mm]0&\fbox{1}&-2\\[2.5mm]0&0&\alpha+6\end{array}\;\right|\;\begin{array}{c}0\\[2.5mm]-2\\[2.5mm]\beta\end{array}\right) \sim\left(\left.\begin{array}{ccc}\fbox{1}&0&-3\\[2.5mm]0&\fbox{1}&-2\\[2.5mm]0&0&\fbox{1}\end{array}\;\right|\;\begin{array}{c}0\\[2.5mm]-2\\[2.5mm]\frac{\beta}{\alpha+6}\end{array}\right) \sim\left(\left.\begin{array}{ccc}\fbox{1}&0&0\\[2.5mm]0&\fbox{1}&0\\[2.5mm]0&0&\fbox{1}\end{array}\;\right|\;\begin{array}{c}\frac{3\beta}{\alpha+6}\\[2.5mm]-2+\frac{2\beta}{\alpha+6}\\[2.5mm]\frac{\beta}{\alpha+6}\end{array}\right) \quad\Longrightarrow\quad\left\{\begin{array}{l}x_1=\frac{3\beta}{\alpha+6}\\[2.5mm]x_2=-2+\frac{2\beta}{\alpha+6}\\[2.5mm]x_3=\frac{\beta}{\alpha+6}.\end{array}\right.\]
Last modified on March 22, 2021
© Roelof Koekoek

Metamenu