Introduction to 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 x+2y+3z=242xy+z=33x+4y5z=6.\begin{aligned} x + 2y + 3z &= 24 \\ 2x - y + z &= 3 \\ 3x + 4y - 5z &= -6. \end{aligned} Which of the following represents a reduction of this 3-variable system to a 2-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 nn equations in nn variables, this gives a system of n1n - 1 equations in n1n - 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 zz. This can be used to find yy, then xx, giving the full solution.

Gaussian Elimination


Let’s return to the system x+2y+3z=242xy+z=33x+4y5z=6,\begin{aligned} x + 2y + 3z &= 24 \\ 2x - y + z &= 3 \\ 3x + 4y - 5z &= -6, \end{aligned} which we saw becomes 5y5z=452y14z=78.\begin{aligned} -5y-5z&=-45 \\ -2y-14z&=-78. \end{aligned} Repeating the process and eliminating yy, we get the value of zz. This can be plugged back into the second equation to get yy, which can be plugged back into the first equation to get xx. 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 4y+6z=262xy+2z=63x+yz=2.\begin{aligned} 4y + 6z &= 26 \\ 2x - y + 2z &= 6 \\ 3x + y - z &= 2. \end{aligned} Here, we can’t eliminate xx using the first equation. This is easily resolved by rearranging the equations: 2xy+2z=64y+6z=263x+yz=2.\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 xx from the second and third equations, using the first equation.

2) Eliminate yy from the third equation using the second equation.

3) Plug the value of zz into the second equation to get the value of yy.

4) Plug the values of yy and zz into the first equation to get the value of xx.

Which of these steps is the first that cannot be completed as described for the following system? x+2y+3z=82x+4y+5z=153x+6yz=14\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.

Gaussian Elimination


Problem Loading...

Note Loading...

Set Loading...