Skip to main content

Section 4.3 Gaussian Elimination

Observation 4.3.1.

We can use substitution in a more general way to solve linear systems. For example, a natural approach to the system
\begin{equation*} \begin{alignedat}{3} x \amp {} + {} \amp 2y \amp {}={} \amp 1 \\ 2x\amp {}+{} \amp 3y \amp {}={} \amp 3. \\ \end{alignedat} \end{equation*}
is to use the first equation to express \(x\) in terms of \(y\text{:}\)
\begin{equation*} x = 1-2y \end{equation*}
and then substitute this into the second equation and simplify:
\begin{equation*} \begin{alignedat}{2} 2x + 3y \amp {}= \amp 3 \\ 2(1-2y) + 3y \amp {}={} \amp 3 \\ 2-4y + 3y \amp {}={} \amp 3 \\ -y \amp {}={} \amp 1 \\ y \amp {}={} \amp -1 \\ \end{alignedat} \end{equation*}
From here, we can substitute \(y=-1\) into the first equation to arrive at the solution \((x,y)=(3,-1)\text{.}\)
However, the two-step process of solving for \(x\) in terms of \(y\) and substituting into the second equation may be performed more efficiently by adding a multiple of the first equation to the second. In this case, we will multiply the first equation by -2 and add to the second equation
\begin{equation*} \begin{array}{cr} \amp -2(\text{equation 1}) \\ + \amp \text{equation 2} \\ \hline \end{array} \end{equation*}
to obtain
\begin{equation*} \begin{array}{cr} \amp -2(x+2y=1) \\ + \amp 2x+3y = 3 \\ \hline \\ \end{array} \end{equation*}
which gives us
\begin{equation*} \begin{array}{crcr} \amp -2x-4y \amp = \amp -2 \\ + \amp 2x+3y \amp = \amp 3 \\ \hline \amp -y \amp = \amp 1. \\ \end{array} \end{equation*}
In this way, the system
\begin{equation*} \begin{alignedat}{3} x \amp {} + {} \amp 2y \amp {}={} \amp 1 \\ 2x\amp {}+{} \amp 3y \amp {}={} \amp 3 \\ \end{alignedat} \end{equation*}
is transformed into the new triangular system
\begin{equation*} \begin{alignedat}{3} x \amp {} + {} \amp 2y \amp {}={} \amp 1 \\ \amp \amp -y \amp {}={} \amp 1. \\ \end{alignedat} \end{equation*}
Of course, the choice to multiply the first equation by -2 was made so that the terms involving \(x\) in the two equations will cancel leading to a triangular system that can be solved using back substitution.
Based on these observations, we take note of three operations that transform a system of linear equations into a new system of equations having the same solution space. Our goal is to create a new system whose solution space is the same as the original system’s and may be easily described.
Scaling
We can multiply one equation by a nonzero number. For instance,
\begin{equation*} 2x -4y = 6 \end{equation*}
has the same set of solutions as
\begin{equation*} \frac12(2x-4y=6) \end{equation*}
or
\begin{equation*} x-2y=3\text{.} \end{equation*}
Interchange
Interchanging equations will not change the set of solutions. For instance,
\begin{equation*} \begin{alignedat}{3} 2x \amp {}+{} \amp 4y \amp {}={} \amp 1 \\ x \amp {}-{} \amp 3y \amp {}={} \amp 0 \\ \end{alignedat} \end{equation*}
has the same set of solutions as
\begin{equation*} \begin{alignedat}{3} x \amp {}-{} \amp 3y \amp {}={} \amp 0 \\ 2x \amp {}+{} \amp 4y \amp {}={} \amp 1. \\ \end{alignedat} \end{equation*}
Replacement
As we saw above, we may multiply one equation by a real number and add it to another equation. We call this process replacement.

Example 4.3.2.

Let’s illustrate the use of these operations to find the solution space to the system of equations:
\begin{equation*} \begin{alignedat}{4} x \amp {}+{} \amp 2y \amp \amp \amp {}={} \amp 4 \\ 2x \amp {}+{} \amp y \amp {}-{} \amp 3z \amp {}={} \amp 11 \\ -3x \amp {}-{} \amp 2y \amp {}+{} \amp z \amp {}={} \amp -10 \\ \end{alignedat} \end{equation*}
We will first transform the system into a triangular system so we start by eliminating \(x\) from the second and third equations.
We begin with a replacement operation where we multiply the first equation by -2 and add the result to the second equation.
\begin{equation*} \begin{alignedat}{4} x \amp {}+{} \amp 2y \amp \amp \amp {}={} \amp 4 \\ \amp \amp -3y \amp {}-{} \amp 3z \amp {}={} \amp 3 \\ -3x \amp {}-{} \amp 2y \amp {}+{} \amp z \amp {}={} \amp -10 \\ \end{alignedat} \end{equation*}
Another replacement operation eliminates \(x\) from the third equation. We multiply the first equation by 3 and add to the third.
\begin{equation*} \begin{alignedat}{4} x \amp {}+{} \amp 2y \amp \amp \amp {}={} \amp 4 \\ \amp \amp -3y \amp {}-{} \amp 3z \amp {}={} \amp 3 \\ \amp \amp 4y \amp {}+{} \amp z \amp {}={} \amp 2 \\ \end{alignedat} \end{equation*}
Scale the second equation by multiplying it by \(-1/3\text{.}\)
\begin{equation*} \begin{alignedat}{4} x \amp {}+{} \amp 2y \amp \amp \amp {}={} \amp 4 \\ \amp \amp y \amp {}+{} \amp z \amp {}={} \amp -1 \\ \amp \amp 4y \amp {}+{} \amp z \amp {}={} \amp 2 \\ \end{alignedat} \end{equation*}
Eliminate \(y\) from the third equation by multiplying the second equation by -4 and adding it to the third. Notice that we now have a triangular system that can be solved using back substitution.
\begin{equation*} \begin{alignedat}{4} x \amp {}+{} \amp 2y \amp \amp \amp {}={} \amp 4 \\ \amp \amp y \amp {}+{} \amp z \amp {}={} \amp -1 \\ \amp \amp \amp \amp -3z \amp {}={} \amp 6 \\ \end{alignedat} \end{equation*}
After scaling the third equation by \(-1/3\text{,}\) we have found the value for \(z\text{.}\)
\begin{equation*} \begin{alignedat}{4} x \amp {}+{} \amp 2y \amp \amp \amp {}={} \amp 4 \\ \amp \amp y \amp {}+{} \amp z \amp {}={} \amp -1 \\ \amp \amp \amp \amp z \amp {}={} \amp -2 \\ \end{alignedat} \end{equation*}
We eliminate \(z\) from the second equation by multiplying the third equation by -1 and adding to the second.
\begin{equation*} \begin{alignedat}{4} x \amp {}+{} \amp 2y \amp \amp \amp {}={} \amp 4 \\ \amp \amp y \amp \amp \amp {}={} \amp 1 \\ \amp \amp \amp \amp z \amp {}={} \amp -2 \\ \end{alignedat} \end{equation*}
Finally, multiply the second equation by -2 and add to the first to obtain:
\begin{equation*} \begin{alignedat}{3} x \amp {}={} \amp 2 \\ y \amp {}={} \amp 1 \\ z \amp {}={} \amp -2. \\ \end{alignedat} \end{equation*}
Now that we have arrived at a decoupled system, we know that there is exactly one solution to our original system of equations, which is \((x,y,z) = (2,1,-2)\text{.}\)

Activity 4.3.1. Gaussian Elimination.

For each of the following linear systems, use Gaussian elimination to describe the solutions to the following systems of linear equations. In particular, determine whether each linear system has exactly one solution, infinitely many solutions, or no solutions.
  1. \(\displaystyle \begin{alignedat}{4} x \amp {}+{} \amp y \amp {}+{} \amp 2z \amp {}={} \amp 1 \\ 2x \amp {}-{} \amp y \amp {}-{} \amp 2z \amp {}={} \amp 2 \\ -x \amp {}+{} \amp y \amp {}+{} \amp z \amp {}={} \amp 0 \\ \end{alignedat}\)
  2. \(\displaystyle \begin{alignedat}{4} -x \amp {}-{} \amp 2y \amp {}+{} \amp 2z \amp {}={} \amp -1 \\ 2x \amp {}+{} \amp 4y \amp {}-{} \amp z \amp {}={} \amp 5 \\ x \amp {}+{} \amp 2y \amp \amp \amp {}={} \amp 3 \\ \end{alignedat}\)
  3. \(\displaystyle \begin{alignedat}{4} -x \amp {}-{} \amp 2y \amp {}+{} \amp 2z \amp {}={} \amp -1 \\ 2x \amp {}+{} \amp 4y \amp {}-{} \amp z \amp {}={} \amp 5 \\ x \amp {}+{} \amp 2y \amp \amp \amp {}={} \amp 2 \\ \end{alignedat}\)
Answer.
  1. There is a single solution \((1,2,-1)\text{.}\)
  2. There are infinitely many solutions.
  3. There are no solutions.
Solution.
  1. Our aim is to apply a sequence of scaling, interchange, and replacement operations to first put the system into a triangular form. We begin by multiplying the first equation by \(-2\) and adding it to the second equation. Next, we add the first equation to the third. This leads us to:
    \begin{equation*} \begin{alignedat}{4} x \amp {}+{} \amp y \amp {}+{} \amp 2z \amp {}={} \amp 1 \\ \amp \amp -3y \amp {}-{} \amp 6z \amp {}={} \amp 0 \\ \amp \amp 2y \amp {}+{} \amp 3z \amp {}={} \amp 1 \\ \end{alignedat} \end{equation*}
    We will now apply a scaling operation to make the coefficient of \(y\) equal \(1\) in the second equation.
    \begin{equation*} \begin{alignedat}{4} x \amp {}+{} \amp y \amp {}+{} \amp 2z \amp {}={} \amp 1 \\ \amp \amp y \amp {}+{} \amp 2z \amp {}={} \amp 0 \\ \amp \amp 2y \amp {}+{} \amp 3z \amp {}={} \amp 1 \\ \end{alignedat} \end{equation*}
    Another replacement operation brings the system into a triangular form.
    \begin{equation*} \begin{alignedat}{4} x \amp {}+{} \amp y \amp {}+{} \amp 2z \amp {}={} \amp 1 \\ \amp \amp y \amp {}+{} \amp 2z \amp {}={} \amp 0 \\ \amp \amp \amp \amp -z \amp {}={} \amp 1 \\ \end{alignedat} \end{equation*}
    From here, we begin the process of back substitution seeking a decoupled system.
    \begin{equation*} \begin{alignedat}{4} x \amp {}+{} \amp y \amp \amp \amp {}={} \amp 3 \\ \amp \amp y \amp \amp \amp {}={} \amp 2 \\ \amp \amp \amp \amp z \amp {}={} \amp -1 \\ \end{alignedat} \end{equation*}
    Finally, we have the decoupled system
    \begin{equation*} \begin{alignedat}{4} x \amp \amp \amp \amp \amp {}={} \amp 1 \\ \amp \amp y \amp \amp \amp {}={} \amp 2 \\ \amp \amp \amp \amp z \amp {}={} \amp -1, \\ \end{alignedat} \end{equation*}
    which tells us that the solution space consists of the single solution \((1,2,-1)\text{.}\)
  2. Once again, we begin with a sequence of replacement and scaling operations that lead to the triangular system
    \begin{equation*} \begin{alignedat}{4} -x \amp {}-{} \amp 2y \amp {}+{} \amp 2z \amp {}={} \amp -1 \\ \amp \amp \amp \amp z \amp {}={} \amp 1 \\ \amp \amp \amp \amp 0 \amp {}={} \amp 0 \\ \end{alignedat} \end{equation*}
    Back substitution gives us the system
    \begin{equation*} \begin{alignedat}{4} x \amp {}+{} \amp 2y \amp \amp \amp {}={} \amp 3 \\ \amp \amp \amp \amp z \amp {}={} \amp 1 \\ \amp \amp \amp \amp 0 \amp {}={} \amp 0 \\ \end{alignedat} \end{equation*}
    The third equation does not impose a restriction on the solutions since it is satisfied for any \((x,y,z)\text{.}\) The second equation tells us that \(z\) must equal \(1\text{;}\) however, there are infinitely many solutions to the first equation that have \(z=1\text{.}\) Therefore, this system has infinitely many solutions.
  3. After applying two replacement and one scaling operation, we find
    \begin{equation*} \begin{alignedat}{4} -x \amp {}-{} \amp 2y \amp {}+{} \amp 2z \amp {}={} \amp -1 \\ \amp \amp \amp \amp z \amp {}={} \amp 1 \\ \amp \amp \amp \amp 2z \amp {}={} \amp 1 \\ \end{alignedat} \end{equation*}
    Another replacement operation leads to the system
    \begin{equation*} \begin{alignedat}{4} -x \amp {}-{} \amp 2y \amp {}+{} \amp 2z \amp {}={} \amp -1 \\ \amp \amp \amp \amp z \amp {}={} \amp 1 \\ \amp \amp \amp \amp 0 \amp {}={} \amp 1 \\ \end{alignedat} \end{equation*}
    Since the third equation has no solutions, the original system can have no solutions as well.