Gaussian Elimination and Back Substitution

# Gaussian Elimination

Consider the system of linear equations:

(1)

If we take what is known as the augmented matrix of this system, that is, the matrix corresponding the coefficients and constants of the system, $\begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} & b_1\\ a_{21} & a_{22} & \cdots & a_{2n} & b_2\\ \vdots & \vdots & & \vdots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} & b_{m} \end{bmatrix}$ and reduce it to Row Echelon Form, then we will be able to solve the system rather easily.

For example, consider the following system of linear equations:

(2)
\begin{align} 2x + 3y -z = 2 \\ 2x + 4y +z = 4 \\ x + 2y +z = 1 \\ \end{align}

The augmented matrix for this system is $\begin{bmatrix} 2 & 3 & -1 & 2\\ 2 & 4 & 1 & 4\\ 1 & 2 & 1 & 1 \end{bmatrix}$. If we reduce this matrix to REF, we obtain the following matrix (as you should verify):

(3)
\begin{bmatrix} 1 & 0 & 0 & -9\\ 0 & 1 & 0 & 6\\ 0 & 0 & 1 & -2 \end{bmatrix}

From this matrix we can extract the following set of linear equations that is much easier to work with:

(4)
\begin{align} x + 0y + 0z = -9 \\ 0x + y + 0z = 6 \\ 0x + 0y + z = -2 \end{align}

Clearly we can see a solution $(x, y, z) = (-9, 6, -2)$ to the original system of linear equations. Sometimes we may have to use the algebraic technique of back substitution as well which we will now describe.

# Back Substitution

Consider the following augmented matrix for a system of 3 linear equations and 4 unknowns $x_1, x_2, x_3, x_4$ that has already been put into REF:

(5)
\begin{bmatrix} 1 & 0 & 0 & 4 & -1\\ 0 & 1 & 0 & 2 & 6\\ 0 & 0 & 1 & 3 & 2 \end{bmatrix}

From this we obtain the following linear equations:

(6)
\begin{align} x_1 + 0x_2 + 0x_3 + 4x_4 = -1 \\ 0x_1 + x_2 + 0x_3 + 2x_4 = 6 \\ 0x_1 + 0x_2 + x_3 + 3x_4 = 2 \end{align}

The variables $x_1, x_2, x_3$ correspond to leading $1$s in the matrix, so we call them leading variables, while the variable $x_4$ is called a free variable or a pivot.

To solve this system, we let our free variables equal some arbitrary value, say $t$. So let $x_4 = t$ for $t \in \mathbb{R}$. Therefore we obtain a general solution:

(7)
\begin{align} x_1 = -1 - 4t \\ x_2 = 6 - 2t \\ x_3 = 2 - 3t \\ x_4 = t \end{align}

That is for all $t \in \mathbb{R}$, there exists a solution $(x_1, x_2, x_3, x_4) = (-1 - 4t, 6 - 2t, 2 - 3t, t)$. For for any value of $t \in \mathbb{R}$ we get a corresponding solution to the system, and so this system has infinitely many solutions.

## Example 1

Given the following REF matrix that represents a system of 3 linear equations in 3 variables $x_1, x_2, x_3$, find a solution.

(8)
\begin{bmatrix} 1 & 1 & 0 & 4\\ 0 & 1 & 1 & 2\\ 0 & 0 & 1 & 3 \end{bmatrix}

We obtain the following system of linear equations:

(9)
\begin{align} x_1 + x_2 = 4 \\ x_2 + x_3 = 2 \\ x_3 = 4 \end{align}

We first note that $x_3 = 4$. We can back-substitute this into the second equation to get that:

(10)
\begin{align} x_2 + x_3 = 2 \\ x_2 + (4) = 2 \\ x_2 = -2 \end{align}

Therefore $x_2 = -2$. Lastly, we can substitute this information into the first equation to get that:

(11)
\begin{align} x_1 + x_2 = 4 \\ x_1 + (-2) = 4 \\ x_1 = 6 \end{align}

Therefore we have one solution to our system, namely $(x_1, x_2, x_3) = (6, -2, 4)$