### Linear Algebra

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.

# Gaussian Elimination

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

# Gaussian Elimination

The previous problem illustrates a general process for solving systems:

1) Use an equation to eliminate a 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 another equation to eliminate another 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.

# Gaussian Elimination

Let’s return to the system \begin{aligned} x + 2y + 3z &= 24 \\ 2x - y + z &= 3 \\ 3x + 4y - 5z &= -6, \end{aligned} which we saw becomes \begin{aligned} -5y-5z&=-45 \\ -2y-14z&=-78. \end{aligned} 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?

# Gaussian Elimination

One potential issue is what if the first equation doesn’t have the first variable, like \begin{aligned} 4y + 6z &= 26 \\ 2x - y + 2z &= 6 \\ 3x + y - z &= 2. \end{aligned} Here, we can’t eliminate $x$ using the first equation. This is easily resolved by rearranging the equations: \begin{aligned} 2x - y + 2z &= 6 \\ 4y + 6z &= 26 \\ 3x + y - z &= 2. \end{aligned} 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.

# Gaussian Elimination

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 is the first that cannot be completed as described for the following system? \begin{aligned} x + 2y + 3z &= 8 \\ 2x + 4y + 5z &= 15 \\ 3x + 6y - z &= 14 \end{aligned}

# Gaussian Elimination

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.

×