In this section we'll learn how to solve systems of linear equations using the Gauss-Jordan elimination procedure. A system of equations can be represented as a matrix of coefficients. The Gauss-Jordan elimination procedure converts any matrix into its reduced row echelon form (RREF). We can easily read off the solution of the system of equations from the RREF.

This section requires your full-on caffeinated attention because the procedures you will learn is somewhat tedious. Gauss-Jordan elimination involves a lot of repetitive mathematical manipulations of arrays of numbers. It is important for you to suffer through the steps, and verify each step presented below on your own with pen and paper. You shouldn't trust me—always verify!

Suppose you are asked to solve the following system of equations: \[ \begin{eqnarray} 1x_1 + 2x_2 & = & 5, \nl 3x_1 + 9x_2 & = & 21. \end{eqnarray} \] The standard approach would be to use substitution, elimination, or subtraction tricks to combine these equations and find the values of the two unknowns $x_1$ and $x_2$.

The names of the two unknowns are irrelevant to the solution of these equations. Indeed, the solution $(x_1,x_2)$ to the above equations would be the same as the solution $(s,t)$ in the following system of equations: \[ \begin{align*} 1s + 2t & = 5, \nl 3s + 9t & = 21. \end{align*} \] What is important in this equation are the coefficients in front of the variables and the numbers in the column of constants on the right-hand side of each equation.

Any system of linear equations can be written down as a matrix of numbers: \[ \left[ \begin{array}{cccc} 1 & 2 &| & 5 \nl 3 & 9 &| & 21 \end{array} \right], \] where the first column corresponds to the coefficients of the first variable, the second column is for the second variable and the last column corresponds to the numbers of the right-hand side of the equation. It is customary to draw a vertical line where the equal sign in the equation would normally appear. This line helps us to distinguish the coefficients of the equations from the column of constants on the right-hand side of the equations.

Once you have the augmented matrix, we can start to use row operations on its entries to simplify it.

In the last step, we use the correspondence between the augmented matrix and the systems of linear equations to read off the solution.

After “simplification by row operations,” the above augmented matrix will be: \[ \left[ \begin{array}{cccc} 1 & 0 &| & 1 \nl 0 & 1 &| & 2 \end{array} \right]. \] This augmented matrix corresponds to the following system of linear equations: \[ \begin{eqnarray} x_1 & = & 1, \nl x_2 & = & 2, \end{eqnarray} \] in which there is not much left to solve. Right?

The augmented matrix approach to manipulating systems of linear equations is very convenient when we have to solve equations with many variables.

We can manipulate each of the rows of the augmented matrix without chaining the solutions. We are allowed to perform the following three row operations:

1. Add a multiple of one row to another row
2. Swap two rows
3. Multiply a row by a constant

Let's trace the sequence of row operations we would need to solve the system of linear equations which we described above.

• We start with the augmented matrix:

\[\left[ \begin{array}{cccc} 1 & 2 &| & 5 \nl 3 & 9 &| & 21 \end{array} \right]. \]

• As a first step we will eliminate the first variable in the second row.

We can do this by subtracting three times the first row from the second row:

  \[\left[\begin{array}{cccc}1 & 2 & |  &5\\0 & 3 & |  &6\end{array}\right].\]
  We can denote this row operation as $R_2 \gets R_2 - 3R_1$.
* Next, to simplify the second row we divide it by three: $R_2 \gets \frac{1}{3}R_2$:
  \[\left[\begin{array}{cccc}1 & 2 & |  &5\\0 & 1 & |  &2\end{array}\right].\]
* The final step is to eliminate the second variable from the first row.
  We do by subtracting two times the second row from the first row
  $R_1 \gets R_1 - 2R_2$:
  \[\left[\begin{array}{cccc}1 & 0 & |  &1\\0 & 1 & |  &2\end{array}\right].\]
  From which we can read off the solution directly: $x_1 = 1$, $x_2=2$.

The procedure I used to find simplify the augmented matrix and get the solution were not random. I was following the Gauss-Jordan elimination algorithm brings the matrix into its the reduced row echelon form.

The reduced row echelon form is in some sense the simplest form for a matrix. Each row contains a leading one which is also sometimes called a pivot. The pivot of each column is used to eliminate all other numbers below and above in the same column until we obtain an augmented matrix of the form: \[ \left[ \begin{array}{cccc|c} 1 & 0 & * & 0 & * \nl 0 & 1 & * & 0 & * \nl 0 & 0 & 0 & 1 & * \end{array} \right] \]

• The solution to a system of linear equations in the

variables $x_1,x_2$ is the set of values $\{ (x_1,x_2) \}$

  that satisfy //all// the equations.
* The //pivot// for row $j$ of a matrix is the left-most
  non-zero entry in the row $j$.
  Any //pivot// can be converted into a //leading one// by an appropriate scaling.
* //Gaussian elimination// is the process of bringing a matrix into //row echelon form//.
* A matrix is said to be in //row echelon form// (REF) if
  all the entries below the leading ones are zero.
  This can be obtained by adding or subtracting the row with the leading one from the rows below it.
* //Gaussian-Jordan elimination// is the process of branding any matrix into the //reduced row echelon form//.
* A matrix is said to be in //reduced row echelon form// (RREF) if
  all the entries below //and above// the leading ones are zero.
  Starting from the REF form, we can obtain the RREF form by
  subtracting the row which contains the leading one for that 
  column from the rows above it.

Forward phase (left to right):

1. Get a pivot (leading one) in the left most column.
2. Subtract this row from all rows below this one

to get zeros below in the entire column.

1. Look for a leading one in the next column and repeat.

NOINDENT Backward phase (right to left):

1. Find the rightmost pivot and use it to eliminate all the

numbers above it in the column.

1. Move one step to the left and repeat

We are asked to solve the following system of equations \[ \begin{align*} 1x + 2y +3 z = 14, \nl 2x + 5y +6 z = 30, \nl -1x +2y +3 z = 12. \end{align*} \]

Your first step is to write the corresponding augmented matrix \[\left[\begin{array}{ccccc}{\color{blue}1} & 2 & 3 & |& 14\\2 & 5 & 6 & |& 30\\-1 & 2 & 3 & |& 12\end{array}\right].\]

Conveniently, we already have a $1$ at the top of the first column.

• The first step is to clear the entire column below this leading one.

The two row operations are $R_2 \gets R_2 - 2R_1$ and

  $R_3 \gets R_3 + R_1$ to obtain:
  \[\left[\begin{array}{ccccc}1 & 2 & 3 & |& 14\\0 & {\color{blue}1} & 0 & |& 2\\0 & 4 & 6 & |& 26\end{array}\right].\]
  We now shift our attention to the second column, second row.
* Using the leading one for the second column, we set the number in the column 
  below to zero: $R_3 \gets R_3 - 4R_2$.
  \[\left[\begin{array}{ccccc}1 & 2 & 3 & |&  14\\0 & 1 & 0 & |&  2\\0 & 0 & {\color{red}6} & |& 18\end{array}\right].\]
  We move to the third column now, and look for a leading one on the third row.
* There is a six there, which is we can turn into a leading one as follows: $R_3 \gets \frac{1}{6}R_3$
  \[\left[\begin{array}{ccccc} 1 & 2 & 3 & |&14\\0 & 1 & 0 & |&2\\0 & 0 & {\color{blue}1} & |&3\end{array}\right].\]

The forward phase of the Gauss-Jordan elimination procedure is complete now. We have our three pivots and we used them to systematically set the entries below them to zero. The matrix is now in row echelon form.

We now start the backward phase, during which we work right to left and set all that numbers above the pivots to zero:

• The first step is $R_1 \gets R_1 -3R_3$, which leads to:

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

• The final step is $R_1 \gets R_1 -2R_2$, which gives:

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

From the reduced row echelon form we can read off the solution: $x=1$, $y=2$ and $z=3$.

A system of $3$ linear equations in $3$ variables could have:

• One solution: If the RREF for of a matrix has a single $1$ in each

row, then we can read off the values of the solution by inspection:

  \[
  \left[ \begin{array}{ccc|c}
   1 & 0 & 0  &  c_1 \nl
   0 & 1 & 0 &  c_2 \nl
   0 & 0 & 1   & c_3 
  \end{array}\right].
  \]
  The //unique// solution is $x_1=c_1$, $x_2=c_2$ and $x_3=c_3$.
* **Infinitely many solutions**: If one of the equations is redundant, 
  this will lead to a row of zeros when the matrix is brought to the RREF.
  A row of zeros means that one of the original equations given was
  a linear combination of the others. This means that we are really solving 
  //two// equations in three variables, which in turn means that we
  won't be able to pin down one of the variables. It will be a free variable:
  \[
  \left[ \begin{array}{ccc|c}
   1 & 0 & a_1  &  c_1 \nl
   0 & 1 & a_2  &  c_2 \nl
   0 & 0 & 0    & 0 
  \end{array}\right].
  \]
  The free variable is the one that doesn't have a //leading one// in its column.
  To indicate that $x_3$ is free, we will give it a special name $x_3=t$
  and we define $t$ which ranges from $-\infty$ to $+\infty$. In other words,
  $t$ being free, means that $t$ could be //any// number $t \in \mathbb{R}$.
  The first and second equation can now be used to obtain $x_1$ and $x_2$ 
  in terms of the $c$-constants and $t$ so we get the final solution:
  \[
   \left\{
   \begin{array}{rl}
   x_1 & = c_1 -a_1\:t \nl
   x_2 & = c_2 - a_2\:t \nl
   x_3 & = t
   \end{array}, \quad
   \forall t \in \mathbb{R}
   \right\}
   = 
   \left\{
   \begin{bmatrix} c_1 \nl c_2 \nl 0 \end{bmatrix}
   + t \!
   \begin{bmatrix} -a_1 \nl -a_2 \nl 1 \end{bmatrix},\quad
   \forall t \in \mathbb{R}
   \right\},
  \]
  which corresponds to [[lines_and_planes|the equation of a line]] with direction
  vector $(-a_1,-a_2,1)$ passing through the point $(c_1,c_2,0)$. \\ \\
  Note that it is also possible to have  a two-dimensional solution space,
  if there is only a single leading one. This is the case in the following example:
  \[
  \left[ \begin{array}{ccc|c}
   0 & 1 & a_2  &  c_2 \nl
   0 & 0 & 0   &  0 \nl
   0 & 0 & 0    & 0 
  \end{array}\right].
  \]
  There are //two// free variables ($x_1$ and $x_3$) and therefore the solution
  space is two-dimensional. The solution corresponds to the set
  \[
   \left\{
   \begin{array}{rl}
   x_1 & = s \nl
   x_2 & = c_2 - a_2\:t \nl
   x_3 & = t
   \end{array}, \quad
   \forall s,t \in \mathbb{R}
   \right\}
   = 
   \left\{
   \begin{bmatrix} 0 \nl c_2 \nl 0 \end{bmatrix}
   + s\! 
   \begin{bmatrix} 1 \nl 0 \nl 0 \end{bmatrix}
   + t \!
   \begin{bmatrix} 0 \nl -a_2 \nl 1 \end{bmatrix},\quad
   \forall s,t \in \mathbb{R}
   \right\}.
  \]
  This is the explicit parametrisation of the plane: $0x + 1y + a_2z = c_2$ in $\mathbb{R}^3$.
* **No solutions**: If there are no numbers $(x_1,x_2,x_3)$ that simultaneously 
  satisfy all three of the equations, then the system of equations has no solution.
  An example of equations with no solution would be $x_1+x_2 = 4$, $x_1+x_2=44$.
  There are no numbers $(x_1,x_2)$ that satisfy both of these equations.
  You can recognize when this happens in an augmented matrix, by a row zero coefficients 
  with a non-zero constant in the right-hand side.
  \[
  \left[ \begin{array}{ccc|c}
   1 & 0 & 0  &  c_1 \nl
   0 & 1 & 0 &  c_2 \nl
   0 & 0 & 0   & c_3 
  \end{array}\right].
  \]
  If $c_3 \neq 0$, then this system of equations is impossible to satisfy (has //no// solutions). 
  This is because there are no numbers $(x_1,x_2,x_3)$ such that $0x_1+0x_2+0x_3=c_3$.

Note that the notion of solution for a system of linear equations is more general than what you are used to. You are used to solutions being just sets of points in space, but in linear algebra the solutions could be entire spaces.

Equations of the form $ax + by = c$ correspond to lines in $\mathbb{R}^2$. Thus, solving systems of equations of the form: \[ \begin{eqnarray} a_1 x + b_1 y & = & c_1, \nl a_2 x + b_2 y & = & c_2. \end{eqnarray} \] corresponds to finding the point $(x,y) \in \mathbb{R}^2$ where these lines intersect. There are three possibilities for the solution set:

• One solution if the two lines intersect at a point.
• Infinitely many solutions if the lines are superimposed.
• No solution: If the two lines are parallel,

then they will never intersect.

Equations of the form $Ax + By + Cz = D$ corresponds to planes in $\mathbb{R}^3$. When we are solving three such equations simultaneously: \[ \begin{eqnarray} a_1 x + b_1 y + c_1 z & = & c_1, \nl a_2 x + b_2 y + c_2 z & = & c_2, \nl a_3 x + b_3 y + c_3 z & = & c_3, \end{eqnarray} \] we are looking for the set of points $(x,y,z)$ that satisfy all three of the equations. There are four possibilities for the solution set:

• One solution: Three non-parallel planes in $\mathbb{R}^3$ intersect at a point.
• Infinitely many solutions 1: If one of the plane equations is redundant, then

we are looking for the intersection of two planes. Two non-parallel planes intersect on a line.

• Infinitely many solutions 2: If two of the equations are redundant, then

the solution space is a plane.

• No solution: If two (or more) of the planes are parallel,

then they will never intersect.

The computer algebra system at http://live.sympy.org can be used to compute the reduced row echelon form of any matrix. Here is an example of how to create a sympy Matrix object.

>>> from sympy.matrices import Matrix
>>> A = Matrix( [[2,-3,-8, 7],
                 [-2,-1,2,-7],
                 [1 ,0,-3, 6]])
>>> A
[ 2, -3, -8,  7]
[-2, -1,  2, -7]
[ 1,  0, -3,  6]

To compute the reduced row echelon form of a matrix, call its rref method:

>>> A.rref()
([1, 0, 0,  0]  # RREF of A 
 [0, 1, 0,  3]                    # locations of pivots
 [0, 0, 1, -2],                   [0, 1, 2]              )

In this case sympy returns a tuple containing the RREF of $A$ and an array that tells us the 0-based indices of the columns which contain the leading ones.

Since usually we just want to find the RREF of $A$, you can select the first (index zero) element of the tuple:

>>> Arref = A.rref()[0]
>>> Arref
[1, 0, 0,  0]
[0, 1, 0,  3]
[0, 0, 1, -2]

The Gauss-Jordan elimination algorithm for simplifying matrices which you learned in this section is one of the most important computational tools of linear algebra. It is applicable not only to systems of linear equations but much more broadly in many contexts. We will discuss other applications of the Gauss-Jordan elimination algorithm the section Applications of Gauss-Jordan elimination.

Verify that you can carry out the Gauss-Jordan elimination procedure by hand and obtain the RREF of the following matrix: \[ \left[\begin{array}{ccc|c} 2 & -3 & -8 & 7\nl -2 & -1 & 2 & -7\nl 1 & 0 & -3 & 6 \end{array}\right] \quad - \ \textrm{ G-J elimination} \to \quad \left[\begin{array}{ccc|c} 1 & 0 & 0 & 0\nl 0 & 1 & 0 & 3\nl 0 & 0 & 1 & -2 \end{array}\right]. \] If solution to the system of equations which corresponds to this augmented matrix is $(0,3,-2)$.