×
Linear Algebra

# Gaussian Elimination: The Full Story

In the previous quiz, we started looking at an algorithm for solving systems of linear equations, called Gaussian elimination. In this quiz, we’ll take a deeper look at this algorithm, why it works, and how we can speed it up.

To save ourselves some effort, let’s introduce some new notation. Instead of having to write $$x, y, z$$ (or whatever the variables are) multiple times, we can simplify things using matrix notation:

\begin{align*} x + 2y + 3z &= 6 \\ 3x + 4y + z &= 8 \implies \begin{pmatrix}1&2&3\\3&4&1\\2&-1&1\end{pmatrix}\begin{pmatrix}x\\y\\z\end{pmatrix}=\begin{pmatrix}6\\8\\2\end{pmatrix}. \\ 2x - y + z &= 2 \end{align*}

Here, the first block is the coefficients of the equations, one equation per row. The second block is the variables, one per row and listed in the same order as the coefficients. Finally, the last block is the RHS of each equation, one per row. This lets us represent the whole system in just one equation!

Which values of $$x, y,$$ and $$z$$ make the above matrix equation true?

As with systems, some matrix equations are equivalent, which is important because some matrix equations are easier to solve than others. As a result, we can often transform a difficult matrix system into one that is much easier to solve. Over the next three problems, we’ll see the three fundamental ways to do this, using elementary matrix operations

The first type of equivalence is fairly simple: since each row of a matrix system represents an equation, nothing changes if we swap the rows around.

Which of the following represents the same system as this matrix equation: $\begin{pmatrix}1&-1&1\\2&3&-2\\-3&3&3\end{pmatrix} \begin{pmatrix}x\\y\\z\end{pmatrix} = \begin{pmatrix}2\\-1\\12\end{pmatrix}?$

A. $$\quad \begin{pmatrix}2&3&-2\\1&-1&1\\-3&3&3\end{pmatrix}\begin{pmatrix}x\\y\\z\end{pmatrix} = \begin{pmatrix}2\\-1\\12\end{pmatrix}$$

B. $$\quad \begin{pmatrix}-3&3&3\\2&3&-2\\1&-1&1\end{pmatrix}\begin{pmatrix}x\\y\\z\end{pmatrix} = \begin{pmatrix}2\\-1\\12\end{pmatrix}$$

C. $$\quad \begin{pmatrix}1&-1&1\\-3&3&3\\2&3&2\end{pmatrix}\begin{pmatrix}x\\y\\z\end{pmatrix} = \begin{pmatrix}2\\-1\\12\end{pmatrix}$$

D. $$\quad \begin{pmatrix}2&3&-2\\-3&3&3\\1&-1&1\end{pmatrix}\begin{pmatrix}x\\y\\z\end{pmatrix} = \begin{pmatrix}-1\\12\\2\end{pmatrix}$$

Just as we can multiply both sides of an equation by the same amount, we can multiply any of the rows of the matrices by constants (as long as we do it to both sides).

Which of the following represents the same system as this matrix equation: $\begin{pmatrix}1&-1&1\\2&3&-3\\-3&3&3\end{pmatrix} \begin{pmatrix}x\\y\\z\end{pmatrix} = \begin{pmatrix}2\\-1\\12\end{pmatrix}?$

A. $$\quad \begin{pmatrix}2&-2&2\\2&3&-3\\-3&3&3\end{pmatrix}\begin{pmatrix}x\\y\\z\end{pmatrix} = \begin{pmatrix}2\\-1\\12\end{pmatrix}$$

B. $$\quad \begin{pmatrix}1&-1&1\\4&6&-6\\-3&3&3\end{pmatrix}\begin{pmatrix}x\\y\\z\end{pmatrix} = \begin{pmatrix}2\\-1\\12\end{pmatrix}$$

C. $$\quad \begin{pmatrix}1&-1&1\\2&3&-3\\-6&6&6\end{pmatrix}\begin{pmatrix}x\\y\\z\end{pmatrix} = \begin{pmatrix}2\\-1\\12\end{pmatrix}$$

D. $$\quad \begin{pmatrix}2&-2&2\\4&6&-6\\-6&6&6\end{pmatrix}\begin{pmatrix}x\\y\\z\end{pmatrix} = \begin{pmatrix}4\\-2\\24\end{pmatrix}$$

Finally, just as we can add two equations together, we can add one row of a matrix to another. As always, we have to be careful to add the corresponding RHS!

Which of the following represents the same system as this matrix equation: $\begin{pmatrix}1&-1&1\\2&3&-3\\-3&3&3\end{pmatrix} \begin{pmatrix}x\\y\\z\end{pmatrix} = \begin{pmatrix}2\\-1\\12\end{pmatrix}?$

A. $$\quad \begin{pmatrix}1&-1&1\\3&2&-2\\-3&3&3\end{pmatrix}\begin{pmatrix}x\\y\\z\end{pmatrix} = \begin{pmatrix}2\\-1\\14\end{pmatrix}$$

B. $$\quad \begin{pmatrix}1&-1&1\\2&3&-3\\-2&2&4\end{pmatrix}\begin{pmatrix}x\\y\\z\end{pmatrix} = \begin{pmatrix}2\\1\\12\end{pmatrix}$$

C. $$\quad \begin{pmatrix}1&-1&1\\2&3&-3\\-1&6&0\end{pmatrix}\begin{pmatrix}x\\y\\z\end{pmatrix} = \begin{pmatrix}2\\-1\\11\end{pmatrix}$$

D. $$\quad \begin{pmatrix}-2&2&4\\2&3&-3\\-3&3&3\end{pmatrix}\begin{pmatrix}x\\y\\z\end{pmatrix} = \begin{pmatrix}1\\-1\\12\end{pmatrix}$$

Now we can finally restate Gaussian elimination in matrix form. First let’s simplify the notation even further, dropping the variables completely: \begin{align*} x + 2y + 3z &= 6 \\ 3x + 4y + z &= 8 \implies \begin{pmatrix}1&2&3&6\\3&4&1&8\\2&-1&1&2\end{pmatrix}, \\ 2x - y + z &= 2 \end{align*} where the last column represents the RHS of each equation. Now we follow this algorithm:

• Determine a “pivot,” i.e. the top leftmost number that isn’t in a row/column already used.
• Subtract the appropriate multiple of the row the pivot is in from the rows below it (so that they are left with zeros in that column).
• Repeat until there are no more pivots. At this point, the matrix will have all 0s in the lower left triangle.

For example, starting with the above matrix, we have \begin{align*} \begin{pmatrix}\color{blue}{1}&2&3&6\\3&4&1&8\\2&-1&1&2\end{pmatrix} &\implies \begin{pmatrix}\color{blue}{1}&2&3&6\\0&-2&-8&-10\\0&-5&-5&-10\end{pmatrix} \\ &\implies \begin{pmatrix}\color{blue}{1}&2&3&6\\0&\color{blue}{-2}&-8&-10\\0&0&15&15\end{pmatrix} &\implies \begin{pmatrix}\color{blue}{1}&2&3&6\\0&\color{blue}{-2}&-8&-10\\0&0&\color{blue}{15}&15\end{pmatrix}. \end{align*} Here, the pivots are shown in blue. Now let’s look at that last row--the equation it represents is $$15z = 15$$, or $$z = 1$$. Then we can find $$y$$ and $$x$$ directly.

The “simple” matrices we saw in the last pane have a special name: row-echelon form. They are defined as matrices with the following two properties:

1. Every row containing a nonzero number is above all the rows that only have zeros.
2. Every row’s pivot (i.e. leftmost nonzero number) is to the right of the pivot in the row above it.

For example, $\begin{pmatrix}1&3&2&4&0\\0&0&8&2&1\\0&0&0&3&-1\end{pmatrix}$ Is in row-echelon form. As we saw, these are important because they are easy to solve, and Gaussian elimination is useful because it produces precisely these matrices.

Which of the following is a row-echelon form of this matrix: $\begin{pmatrix}1&5&4&3\\2&6&3&4\\1&2&6&2\end{pmatrix}?$

A. $$\quad \begin{pmatrix}1&5&4&3\\0&-4&-5&-2\\0&-3&2&-1\end{pmatrix}$$

B. $$\quad \begin{pmatrix}1&5&4&3\\0&-4&-5&-2\\0&0&23&2\end{pmatrix}$$

C. $$\quad \begin{pmatrix}1&5&4&3\\0&-4&-5&-2\\0&0&0&12\end{pmatrix}$$

D. $$\quad \begin{pmatrix}1&5&4&3\\0&0&3&4\\0&0&12&2\end{pmatrix}$$

We’ve now seen how Gaussian elimination provides solutions to matrix equations of the form $Ax = b,$ where $$A$$ is the matrix of coefficients, $$x$$ is the matrix of variables, and $$b$$ is the matrix of RHSs.

As we know, not all systems have solutions. Is there a matrix for $$b$$ that guarantees there is a solution for $$x$$, regardless of what $$A$$ is?

In the previous problem, we saw that $$Ax=0$$ always has at least one solution, namely $$x=0$$. But in some cases, there might be more solutions as well. For instance, if $A = \begin{pmatrix}1&2&-3\\2&-2&-3\end{pmatrix},$ then $$x = \begin{pmatrix}4\\1\\2\end{pmatrix}$$ is a solution as well (try it!).

Now let’s go back to the more general $$Ax=b$$ $$($$for the same $$A$$ as above$$),$$ and suppose $$b = \begin{pmatrix}3\\0\end{pmatrix}$$. Notice that $$x = \begin{pmatrix}1\\1\\0\end{pmatrix}$$ is a solution to this equation.

Which of the following is also a solution?

In this chapter, we saw how Gaussian elimination translates naturally to the language of matrices, which provides a natural starting point into their exploration. Indeed, linear algebra is all about solving the equation $$Ax = b$$!

We also saw the special importance of the case where $$b = 0$$, which naturally leads into the topic of vector spaces--as we will see in the next chapter!

×