×
Back

# Gaussian Elimination Introduction

Over the last two quizzes, we’ve seen how to deal with systems involving two and three variables. We’ve also seen that systems sometimes fail to have a solution, or sometimes have “redundant” equations that lead to an infinite family of solutions. The natural question then becomes twofold: how can we solve general systems of equations, and how can we easily determine if a system has a unique solution?

In this and the next quiz, we’ll develop a method to do precisely that, called Gaussian elimination.

Let’s start by revisiting a 3-variable system, say \begin{align*} x + 2y + 3z &= 24 \\ 2x - y + z &= 3 \\ 3x + 4y - 5z &= -6. \end{align*} Which of the following 2-variable systems is necessarily true?

The previous problem illustrates a general process for solving systems:

1) Use the first equation to eliminate the first variable from the other equations. If there are $$n$$ equations in $$n$$ variables, this gives a system of $$n - 1$$ equations in $$n - 1$$ variables.

2) Repeat the process, using the second equation to eliminate the second variable from the new system, etc.

3) Eventually, the system “should” collapse to a 1-variable system, which in other words is the value of one of the variables. The remaining values then follow fairly easily.

For example, the previous problem showed how to reduce a 3-variable system to a 2-variable system. Repeating the process would reduce that 2-variable system to a 1-variable system, at which point we find out the value of $$z$$. This can be used to find $$y$$, then $$x$$, giving the full solution.

Let’s return to the system \begin{align*} x + 2y + 3z &= 24 \\ 2x - y + z &= 3 \\ 3x + 4y - 5z &= -6, \end{align*} which we saw becomes \begin{align*} -5y-5z&=-45 \\ -2y-14z&=-78. \end{align*} Repeating the process and eliminating $$y$$, we get the value of $$z$$. This can be plugged back into the second equation to get $$y$$, which can be plugged back into the first equation to get $$x$$. What is the solution to this system?

One potential issue is what if the first equation doesn’t have the first variable, like \begin{align*} 4y + 6z &= 26 \\ 2x - y + 2z &= 6 \\ 3x + y - z &= 2. \end{align*} Here, we can’t eliminate $$x$$ using the first equation. This is easily resolved by rearranging the equations: \begin{align*} 2x - y + 2z &= 6 \\ 4y + 6z &= 26 \\ 3x + y - z &= 2. \end{align*} So as long as one of the equations has a given variable, we can always rearrange them so that equation is “on top.” But if none of the equations have a given variable, we have an issue.

For a 3-variable system, the algorithm says the following:

1) Eliminate $$x$$ from the second and third equations, using the first equation.

2) Eliminate $$y$$ from the third equation using the second equation.

3) Plug the value of $$z$$ into the second equation to get the value of $$y$$.

4) Plug the values of $$y$$ and $$z$$ into the first equation to get the value of $$x$$.

Which of these steps fail for the following system? \begin{align*} x + 2y + 3z &= 8 \\ 2x + 4y + 5z &= 15 \\ 3x + 6y - z &= 14 \end{align*}

In this quiz, we introduced the idea of Gaussian elimination, an algorithm to solve systems of equations. In the next quiz, we’ll take a deeper look at this algorithm, when it fails, and how we can use matrices to speed things up.

×