Linear Algebra

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.

Gaussian Elimination Introduction

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?


Gaussian Elimination Introduction

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.

Gaussian Elimination Introduction

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?


Gaussian Elimination Introduction

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.

Gaussian Elimination Introduction

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{align*} x + 2y + 3z &= 8 \\ 2x + 4y + 5z &= 15 \\ 3x + 6y - z &= 14 \end{align*}\]

Gaussian Elimination Introduction

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.


Problem Loading...

Note Loading...

Set Loading...