Pre-Class Warmup

Example

Consider the following system, where \(k\) is an unknown parameter:

\[\left\{ \begin{array}{r *{5}{Cr}} 2x_1 &-& 3x_2 &=& 7 \\ x_1 &+& kx_2 &=& 3 \end{array} \right.\]

For what values of \(k\) does this system have...

(i) ...a unique solution?
(ii) ...infinitely many solutions?
(iii) ...no solutions?

Today we're going to take the elimination method for solving systems of linear equations and turn it into an algorithmic process called Gaussian elimination. (This is named after Carl Gauss (1777–1855), an extraordinarily influential mathematician once called the "prince of mathematics.") To do this, we will first discuss certain systems which are particularly easy to solve: those in triangular form or echelon form. Then, the goal of Gaussian elimination will be to take any given system and turn it into an equivalent one in triangular or echelon form.

Triangular form

Recall the goal of the elimination method: combine our equations (by adding a multiple of one equation to another) in order to eliminate variables; eventually we will get down to an equation with only one variable, which we can easily solve. In a general system, after doing enough elimination, the result will often be in triangular form. To define triangular form, we first need the notion of leading variables:

Definition

In a system of linear equations, the leading variable of an equation is the leftmost variable that appears in that equation (with nonzero coefficient).

For example, in the system

\[\left\{ \begin{array}{r *{5}{Cr}} x_1 &-& x_2 &+& 4x_3 &-& x_4 &=& 7 \\ && && x_3 &-& 3x_4 &=& 3 \\ && 5x_2 &+& 2x_3 &+& x_4 &=& -1 \end{array} \right.\]

the first equation has leading variable \(x_1\), the second equation has leading variable \(x_3\), and the third equation has leading variable \(x_2\). (An equation that looks like \(0 = c\), where \(c\) is a constant, does not have a leading variable.)

Definition

A system of equations is said to be in triangular form if the number of equations equals the number of variables, the first equation has leading variable \(x_1\), the second equation has leading variable \(x_2\), and so on.

We call such a system a triangular system.

In other words: in a triangular system, the leading variables form a straight line going down the diagonal, at a 45-degree angle from top-left to bottom-right, and nothing is present below the diagonal.

Example

The following is a triangular system:

\[\left\{ \begin{array}{r *{5}{Cr}} x_1 &-& 2x_2 &+& 3x_3 &+& x_4 &=& 2 \\ && x_2 && &-& 2x_4 &=& 0 \\ &&&& 5x_3 &+& 2x_4 &=& 20 \\&& && && 3x_4 &=& 15 \end{array} \right.\]

Notice that variables can be missing (that is, coefficients can be equal to zero) above the diagonal of leading variables, but not below.

Triangular systems are easy to solve. In fact, triangular systems always have a unique solution! Why? Well, given any triangular system, we can solve it (and get a unique solution) using back-substitution:

1. The last equation will always have the form \(ax_n = b\), where \(a\) is nonzero (because \(x_n\) is the leading variable in the last equation). Then we can simply divide by \(a\) to solve for \(x_n\).
2. Once we know the value of \(x_n\), we can back-substitute into the equation directly above it and use that to solve for \(x_{n-1}\).
3. Then, we can back-substitute the values of both \(x_{n-1}\) and \(x_n\) into the equation above that and solve for \(x_{n-2}\).
4. Repeat this until we have found the values of all the variables.

Example

Let's solve the triangular system from the above example by back-substitution:

• The fourth equation is \(3x_4 = 15\), so dividing by 3 gives \(x_4 = 5\).
• The third equation becomes \(5x_3 + 2(5) = 20\), which gives \(x_3 = 2\).
• The second equation becomes \(x_2 - 2(5) = 0\), which gives \(x_2 = 10\).
• Finally, the first equation becomes \(x_1 - 2(10) + 3(2) + 5 = 2\), which gives \(x_1 = 11\).

Therefore, the system has the unique solution \((x_1,x_2,x_3,x_4) = (11,10,2,5).\)

Echelon form

Unfortunately, not every system can be turned into one in triangular form. Why is that? Here are two reasons:

• Many systems don't have the same number of equations as variables. (Our elimination method can't change the number of equations, besides possibly removing equations of the form \(0=0\).)
• All triangular systems have a unique solution, and we know that not all systems have a unique solution!

Instead, Gaussian elimination will convert any system into one in a slightly more general / less "nice" form called echelon form.

Definition

A system of equations is said to be in echelon form if, when the equations are read from top to bottom, the leading variables of each equation proceed strictly from left to right. (Any rows without variables must be at the bottom of the system.)

For a system in echelon form, the leading variables may not form a perfect 45-degree diagonal, but instead they form a "descending staircase" shape. (In fact, the word "echelon" comes from French échelon, meaning a rung of a ladder.)

Example

The following system is not in triangular form, but is in echelon form:

\[\left\{ \begin{array}{r *{5}{Cr}} x_1 &-& 2x_2 && &+& 3x_4 &=& 4 \\ && x_2 &-& 2x_3 &-& x_4 &=& 5 \\&& && && 2x_4 &=& 6 \\ && && && 0 &=& 0 \end{array} \right.\]

It is in echelon form because the leading variables are (in order) \(x_1\), \(x_2\), \(x_4\), and none.

Systems in echelon form may not have a unique solution, but it is still easy to solve them! The procedure is similar to that for triangular systems, except we need to account for the fact that some of the variables are free variables: variables that aren't the leading variable for any equation.

1. First, deal with all the equations without variables. If any are contradictory (e.g. \(0=1\)), then there are no solutions. Otherwise, all of them just say \(0=0\), so we can ignore them.
2. For each free variable \(x_i\), we can set its value to a free parameter, which can be any real number.
3. In each equation, move all the parameters to the right-hand side.
4. Then the remaining variables will form a triangular system, which we can solve by back-substitution. We will get a parametrization of the solutions in terms of all free parameters.

Example

Let's solve the above echelon-form system. We can ignore the last equation, which is always true. Notice that there is one free variable, \(x_3\), so we set \(x_3 = t\) where \(t\) is any real number. Then, by adding \(2t\) to both sides of the second equation, we can rewrite the system to

\[\left\{ \begin{array}{r *{5}{Cr}} x_1 &-& 2x_2 &+& 3x_4 &=& 4 \\ && x_2 &-& x_4 &=& 5+2t \\&& && 2x_4 &=& 6 \end{array} \right.\]

This is now a triangular system with respect to the three leading variables \(x_1\), \(x_2\), \(x_4\). We solve it using back-substitution:

• \(2x_4 = 6\) gives \(x_4=3\).
• Then \(x_2 - 3 = 5 + 2t\), so \(x_2 = 8 + 2t\).
• Finally, \(x_1 - 2(8+2t) + 3(3) = 4\), or equivalently \(x_1 - 7 - 4t = 4\), so we get \(x_1 = 11 + 4t\).

Therefore, the solution set for the original system is \((x_1, x_2, x_3, x_4) = (11+4t, 8+2t, t, 3)\) where \(t\) is any real number.

Gaussian elimination

Now that we understand what it means for a system to be in echelon form, we can describe the process of Gaussian elimination, which takes any system and converts it to one in echelon form with the same solution set. Therefore, to solve a system, we can first apply Gaussian elimination, and then solve the echelon-form system using what we learned above.

Augmented matrices

For both practical and theoretical reasons, Gaussian elimination is not generally applied to a system of linear equations itself, but instead to an object that represents the system called an augmented matrix.

Definition

A matrix is a two-dimensional array of numbers, enclosed in either parentheses or square brackets (depending on your preference). We generally use capital letters to denote matrices, such as

\[A = \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{pmatrix}.\]

This is a \(2 \times 3\) matrix (we write the number of rows first, then the number of columns).

Given a matrix \(A\), we typically use the notation \(A_{i,j}\) to mean the entry in the \(i\)th row (from the top) and \(j\)th column (from the left). Therefore, \(A_{1,1} = 1\) and \(A_{2,3} = 6\).

Please note: the plural of "matrix" is matrices! (Just like how the plural of "vertex" is "vertices," or the plural of "index" is "indices.")

Given a system of linear equations, we represent it using an augmented matrix which just contains all the numbers in the system, so that we don't need to keep rewriting the variable names. For example, here is a system and the corresponding augmented matrix:

\[\left\{ \begin{array}{r *{5}{Cr}} x_1 &-& 2x_2 &+& x_3 &=& 4 \\ x_1 &-& 2x_2 &-& 5x_3 &=& 10 \\ -2x_1 &+& 6x_2 &-& 4x_3 &=& 5 \end{array} \right. \qquad \longleftrightarrow \qquad \left( \begin{matrix} 1 & -2 & 1 \\ 1 & -2 & -5 \\ -2 & 6 & -4\end{matrix} \,\left|\, \begin{matrix} 4 \\ 10 \\ 5 \end{matrix} \right. \right)\]

Therefore, each equation in the system corresponds to a row in the augmented matrix. (The vertical line between the coefficients of the variables and the constants is just to help us keep track of what this matrix means.)

Notice that a leading variable of an equation in the system corresponds to a leftmost nonzero entry in a row of the augmented matrix. We call these pivots of the matrix; we will say that the augmented matrix itself is in echelon form if when the rows are read from top to bottom, the locations of the pivots go strictly from left to right.

Row operations

Given an augmented matrix, Gaussian elimination performs a sequence of row operations on the matrix to turn it into echelon form. These correspond to ways that we can manipulate equations in a system when using the elimination method. The different kinds of row operations are:

1. Switching two rows. This corresponds to switching the order of the equations in the system.
2. Multiplying the numbers in a row by a nonzero constant. This corresponds to scaling one of the equations in the system.
3. Adding a multiple of one row to another row. This is the key operation, and corresponds to adding a multiple of an equation to another.

Example

Let's see how we can use these row operations to turn the matrix from above

\[\left( \begin{matrix} 1 & -2 & 1 \\ 1 & -2 & -5 \\ -2 & 6 & -4\end{matrix} \,\left|\, \begin{matrix} 4 \\ 10 \\ 5 \end{matrix} \right. \right)\]

into echelon form. The first row of the matrix has a pivot in the first column. In echelon form, the pivots need to go strictly from left to right, so we need to eliminate all the other (nonzero) entries in the first column. To do this, we add multiples of the first row to the other rows to turn those entries into zeros. Specifically, we add \(-1\) times the first row to the second row, which gives us

\[\left( \begin{matrix} 1 & -2 & 1 \\ 0 & 0 & -6 \\ -2 & 6 & -4\end{matrix} \,\left|\, \begin{matrix} 4 \\ 6 \\ 5 \end{matrix} \right. \right),\]

and we add \(2\) times the first row to the third row, which gives us

\[\left( \begin{matrix} 1 & -2 & 1 \\ 0 & 0 & -6 \\ 0 & 2 & -2\end{matrix} \,\left|\, \begin{matrix} 4 \\ 6 \\ 13 \end{matrix} \right. \right).\]

Now, the first row and first column look good, so we can "ignore" those and focus on the rest of the matrix.

The second row has a pivot in the third column, but this won't work, because the third row has a nonzero entry in the second column, and we need the pivots to go from left to right. To fix this, we need to put a nonzero entry in position \((2, 2)\), and we can do this by switching the second and third row:

\[\left( \begin{matrix} 1 & -2 & 1\\ 0 & 2 & -2 \\ 0 & 0 & -6 \end{matrix} \,\left|\, \begin{matrix} 4 \\ 13 \\ 6 \end{matrix} \right. \right)\]

Now, we would need to add multiples of the second row to the rows below it, but this is not necessary: we have gotten our matrix into echelon form, and the procedure is completed.

With this example in mind, here is the general description of Gaussian elimination:

Gaussian elimination

Starting with an (augmented) matrix \(A\):

1. Find the leftmost column of \(A\) with any nonzero entries. (Usually this is the first column.)
2. If necessary, switch rows such that the first row of \(A\) has a nonzero entry in this column. This will be the pivot for the first row.
3. By adding a multiple of the first row of \(A\) to other rows below it, ensure that all other rows have zeros in this column. (Therefore, no other row will have a pivot in the first column.)
4. We have finished with the first row and leftmost column, so we can "ignore" these and repeat the procedure, focusing only on the remainder of the matrix \(A\).
5. Continue until \(A\) has reached echelon form.

Note: You may have noticed that we did not actually use the second of the row operations (multiplying a row by a nonzero constant). Although this is a valid row operation (in that the solutions of the corresponding system stay the same when you perform the operation), this is not actually necessary for Gaussian elimination as we have described it. Instead, we will see it used when we talk about Gauss-Jordan elimination, a variation that goes a little further.