11.5: Elementary Row Operations and Gaussian Elimination

Last updated
Save as PDF

Page ID: 120065

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$

In this section and the next we will briefly go over the computational aspects from linear algebra necessary for chapter 10. If you have not had linear algebra, then you are unlikely to understand why everything is true, but you need only be able to perform the calculations to be able to solve the problems that occur in chapter 10. For a thorough understanding of these topics it is best to take a class in linear algebra - highly recommended for anyone studying mathematics, physics, engineering...or anything.

Consider the following system of equations: \[\begin{align}\begin{aligned} r+b+g&=30\\ r&=2g\\ b&=r+g\end{aligned}\end{align} \nonumber \]

Let’s rewrite these equations so that all variables are on the left of the equal sign and all constants are on the right. Also, for a bit more consistency, let’s list the variables in alphabetical order in each equation. Therefore we can write the equations as \[\begin{array}{ccccccc} b&+&g&+&r&=&30\\ &-&2g&+&r&=&0\\ -b&+&g&+&r&=&0 \end{array}.\label{eq:before_matrix} \]

There isn’t just one “right” way of finding the solution to this system of equations, but for simplicity we will only consider one very simple method.

Caution

The methods discussed below are not what we would do in linear algebra, though they suffice for our needs in this class.

First, lets add the first and last equations together, and write the result as a new third equation. This gives us:\[\begin{array}{ccccccc} b&+&g&+&r&=&30\\ &-&2g&+&r&=&0\\ & &2g&+&2r&=&30 \end{array}. \nonumber \] A nice feature of this is that the only equation with a $b$ in it is the first equation.

Now let’s multiply the second equation by $-\frac12$. This gives \[\begin{array}{ccccccc} b&+&g&+&r&=&30\\ & & g&-&1/2r&=&0\\ & &2g&+&2r&=&30 \end{array}. \nonumber \]

Let’s now do two steps in a row; our goal is to get rid of the $g$’s in the first and third equations. In order to remove the $g$ in the first equation, let’s multiply the second equation by $-1$ and add that to the first equation, replacing the first equation with that sum. To remove the $g$ in the third equation, let’s multiply the second equation by $-2$ and add that to the third equation, replacing the third equation. Our new system of equations now becomes \[\begin{array}{ccccccc} b&+& & &3/2r&=&30\\ & &g&-&1/2r&=&0\\ & & & &3r&=&30 \end{array}. \nonumber \]

Clearly we can multiply the third equation by $\frac13$ and find that $r=10$; let’s make this our new third equation, giving \[\begin{array}{ccccccc} b&+& & &3/2r&=&30\\ & &g&-&1/2r&=&0\\ & & & &r&=&10 \end{array}. \nonumber \]

Now let’s get rid of the $r$’s in the first and second equation. To remove the $r$ in the first equation, let’s multiply the third equation by $-\frac32$ and add the result to the first equation, replacing the first equation with that sum. To remove the $r$ in the second equation, we can multiply the third equation by $\frac12$ and add that to the second equation, replacing the second equation with that sum. This gives us: \[\begin{array}{ccccccc} b& & & & &=&15\\ & &g& & &=&5\\ & & & &r&=&10 \end{array}. \nonumber \] Clearly we have discovered our solution.

Let's consider the idea that all that really matters are the coefficients and the constants. There is nothing special about the letters $b$, $g$ and $r$; we could have used $x$, $y$ and $z$ or $x_1$, $x_2$ and $x_3$. And even then, since we wrote our equations so carefully, we really didn’t need to write the variable names at all as long as we put things “in the right place.”

Let’s look again at our system of equations in $\eqref{eq:before_matrix}$ and write the coefficients and the constants in a rectangular array. This time we won’t ignore the zeros, but rather write them out. \[\begin{array}{ccccccc} b&+&g&+&r&=&30\\ &-&2g&+&r&=&0\\ -b&+&g&+&r&=&0 \end{array} \quad \Leftrightarrow \quad \left[\begin{array}{cccc} 1&1&1&30\\ 0&-2&1&0\\ -1&1&1&0\end{array}\right] \nonumber \] Notice how even the equal signs are gone; we don’t need them, for we know that the last column contains the constants.

We have just created a matrix. The definition of matrix is remarkable only in how unremarkable it seems.

Definition: Matrix

A matrix is a rectangular array of numbers.
The horizontal lines of numbers form rows and the vertical lines of numbers form columns. A matrix with $m$ rows and $n$ columns is said to be an $m\times n$ matrix (“an $m$ by $n$ matrix”).
The entries of an $m\times n$ matrix are indexed as follows: \[\left[\begin{array}{ccccc} a_{11}&a_{12}&a_{13}&\cdots&a_{1n}\\ a_{21}&a_{22}&a_{23}&\cdots&a_{2n}\\ a_{31}&a_{32}&a_{33}&\cdots&a_{3n}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ a_{m1}&a_{m2}&a_{m3}&\cdots&a_{mn} \end{array}\right]. \nonumber \]

That is, $a_{32}$ means “the number in the third row and second column.”

In the future, we’ll want to create matrices with just the coefficients of a system of linear equations and leave out the constants. Therefore, when we include the constants, we often refer to the resulting matrix as an augmented matrix.

We can use augmented matrices to find solutions to linear equations by using essentially the same steps we used above. Every time we used the word “equation” above, substitute the word “row,” as we show below. The comments explain how we get from the current set of equations (or matrix) to the one on the next line.

We can use a shorthand to describe matrix operations; let $R_1$, $R_2$ represent “row 1” and “row 2,” respectively. We can write “add row 1 to row 3, and replace row 3 with that sum” as “$R_1+R_3\rightarrow R_3$.” The expression “$R_1 \leftrightarrow R_2$” means “interchange row 1 and row 2.”

$\begin{array}{ccccccc} b&+&g&+&r&=&30\\ &-&2g&+&r&=&0\\ -b&+&g&+&r&=&0 \end{array}$	$\left[\begin{array}{cccc}{1}&{1}&{1}&{30} \\ {0}&{-2}&{1}&{0} \\ {-1}&{1}&{1}&{0}\end{array}\right]$
Replace equation 3 with the sum of equations 1 and 3	Replace row 3 with the sum of rows 1 and 3. $(R_{1}+R_{3}\to R_{3})$
$\begin{array}{ccccccc} b&+&g&+&r&=&30\\ &-&2g&+&r&=&0\\ & &2g&+&2r&=&30 \end{array}$	$\left[\begin{array}{cccc}{1}&{1}&{1}&{30} \\ {0}&{-2}&{1}&{0} \\ {0}&{2}&{2}&{30}\end{array}\right]$
Multiply equation 2 by $-\frac{1}{2}$	Multiply row 2 by $-\frac{1}{2}$ $\left(-\frac{1}{2}R_{2}\to R_{2}\right)$
$\begin{array}{ccccccc} b&+&g&+&r&=&30\\ &&g&+&-1/2r&=&0\\ & &2g&+&2r&=&30 \end{array}$	$\left[\begin{array}{cccc}{0}&{1}&{1}&{30}\\{0}&{1}&{-\frac{1}{2}}&{0}\\{0}&{2}&{2}&{30}\end{array}\right]$
Replace equation 1 with the sum of $(-1)$ times equation 2 plus equation 1; Replace equation 3 with the sum of $(-2)$ times equation 2 plus equation 3	Replace row 1 with the sum of $(-1)$ times row 2 plus row 1 $(-R_{2}+R_{1}\to R_{1})$; Replace row 3 with the sum of $(-2)$ times row 2 plus row 3 $(-2R_{2}+R_{3}\to R_{3})$
$\begin{array}{ccccccc} b&+& & &3/2r&=&30\\ & &g&-&1/2r&=&0\\ & & & &3r&=&30 \end{array}$	$\left[\begin{array}{cccc}{1}&{0}&{\frac{3}{2}}&{30}\\{0}&{1}&{-\frac{1}{2}}&{0}\\{0}&{0}&{3}&{30}\end{array}\right]$
Multiply equation 3 by $\frac{1}{3}$	Multiply row 3 by $\frac{1}{3}$ $\left(\frac{1}{3}R_{3}\to R_{3}\right)$
$\begin{array}{ccccccc} b&+& & &3/2r&=&30\\ & &g&-&1/2r&=&0\\ & & & &r&=&10 \end{array}$	$\left[\begin{array}{cccc}{1}&{0}&{\frac{3}{2}}&{30}\\{0}&{1}&{-\frac{1}{2}}&{0}\\{0}&{0}&{1}&{10}\end{array}\right]$
Replace equation 2 with the sum of $\frac{1}{2}$ times equation 3 plus equation 2; Replace equation 1 with the sum of $-\frac{3}{2}$ times equation 3 plus equation 1	Replace row 2 with the sum of $\frac{1}{2}$ times row 3 plus row 2 $\left(\frac{1}{2}R_{3}+R_{2}\to R_{2}\right)$; Replace row 1 with the sum of $-\frac{3}{2}$ times row 3 plus row 1 $\left(-\frac{3}{2}R_{3}+R_{1}\to R_{1}\right)$
$\begin{array}{ccccccc} b& & & & &=&15\\ & &g& & &=&5\\ & & & &r&=&10 \end{array}$	$\left[\begin{array}{cccc}{1}&{0}&{0}&{15}\\{0}&{1}&{0}&{5}\\{0}&{0}&{1}&{10}\end{array}\right]$

The final matrix contains the same solution information as we have on the left in the form of equations. Recall that the first column of our matrices held the coefficients of the $b$ variable; the second and third columns held the coefficients of the $g$ and $r$ variables, respectively. Therefore, the first row of the matrix can be interpreted as “$b+0g+0r=15$,” or more concisely, “$b=15$.”

Let’s practice this idea again.

Example $\PageIndex{1}$

Find a solution to the following system of linear equations by simultaneously manipulating the equations and the corresponding augmented matrices. \[\begin{array}{ccccccc} x_1&+&x_2&+&x_3&=&0\\ 2x_1&+&2x_2&+&x_3&=&0\\ -1x_1&+&x_2&-&2x_3&=&2 \end{array} \nonumber \]

Solution

We’ll first convert this system of equations into a matrix, then we’ll proceed by manipulating the system of equations (and hence the matrix) to find a solution. Again, there is not just one “right” way of proceeding; we’ll choose a method that is pretty efficient, but other methods certainly exist (and may be “better”). The method we use here, though, is the method that we will be using in chapter 10.

The given system and its corresponding augmented matrix are seen below.

Original system of equations	Corresponding matrix
$\begin{array}{ccccccc} x_1&+&x_2&+&x_3&=&0\\ 2x_1&+&2x_2&+&x_3&=&0\\ -1x_1&+&x_2&-&2x_3&=&2\end{array}$	$\left[\begin{array}{cccc}{1}&{1}&{1}&{0}\\{2}&{2}&{1}&{0}\\{-1}&{1}&{-2}&{2}\end{array}\right]$

We’ll proceed by trying to get the $x_1$ out of the second and third equation.

Replace equation 2 with the sum of $(-2)$ times equation 1 plus equation 2; Replace equation 3 with the sum of equation 1 and equation 3	Replace row 2 with the sum of $(-2)$ times row 1 plus row 2 $(-2R_{1}+R_{2}\to R_{2})$; Replace row 3 with the sum of row 1 and row 3 $(R_{1}+R_{3}\to R_{3})$
$\begin{array}{ccccccc} x_1&+&x_2&+&x_3&=&0\\ & & & &-x_3&=&0\\ & &2x_2&-&x_3&=&2 \end{array}$	$\left[\begin{array}{cccc}{1}&{1}&{1}&{0}\\{0}&{0}&{-1}&{0}\\{0}&{2}&{-1}&{2}\end{array}\right]$

Notice that the second equation no longer contains $x_2$. We’ll exchange the order of the equations so that we can follow the convention of solving for the second variable in the second equation.

Interchange equations 2 and 3	Interchange rows 2 and 3 $R_{2}\leftrightarrow R_{3}$
$\begin{array}{ccccccc} x_1&+&x_2&+&x_3&=&0\\ & &2x_2&-&x_3&=&2\\ & & & &-x_3&=&0 \end{array}$	$\left[\begin{array}{cccc}{1}&{1}&{1}&{0}\\{0}&{2}&{-1}&{2}\\{0}&{0}&{-1}&{0}\end{array}\right]$
Multiply equation 2 by $\frac{1}{2}$	Multiply row 2 by $\frac{1}{2}$ $\left(\frac{1}{2}R_{2}\to R_{2}\right)$
$\begin{array}{ccccccc} x_1&+&x_2&+&x_3&=&0\\ & &x_2&-&\frac12x_3&=&1\\ & & & &-x_3&=&0 \end{array}$	$\left[\begin{array}{cccc}{1}&{1}&{1}&{0}\\{0}&{1}&{-\frac{1}{2}}&{1}\\{0}&{0}&{-1}&{0}\end{array}\right]$
Multiply equation 3 by $-1$	Multiply row 3 by $-1$ $(-1R_{3}\to R_{3})$
$\begin{array}{ccccccc} x_1&+&x_2&+&x_3&=&0\\ & &x_2&-&\frac12x_3&=&1\\ & & & &x_3&=&0 \end{array}$	$\left[\begin{array}{cccc}{1}&{1}&{1}&{0}\\{0}&{1}&{-\frac{1}{2}}&{1}\\{0}&{0}&{1}&{0}\end{array}\right]$

Notice that the last equation (and also the last row of the matrix) show that $x_3=0$. Knowing this would allow us to simply eliminate the $x_3$ from the first two equations. However, we will formally do this by manipulating the equations (and rows) as we have previously.

Replace equation 1 with the sum of $(-1)$ times equation 3 plus equation 1; Replace equation 2 with the sum of $\frac{1}{2}$ times equation 3 plus equation 2	Replace row 1 with the sum of $(-1)$ times row 3 plus row 1 $(-R_{3}+R_{1}\to R_{1})$; Replace row 2 with the sum of $\frac{1}{2}$ times row 3 plus row 2 $\left(\frac{1}{2}R_{3}+R_{2}\to R_{2}\right)$
$\begin{array}{ccccccc} x_1&+&x_2&&&=&0\\ & &x_2&&&=&1\\ & & & &x_3&=&0 \end{array}$	$\left[\begin{array}{cccc}{1}&{1}&{0}&{0}\\{0}&{1}&{0}&{1}\\{0}&{0}&{1}&{0}\end{array}\right]$

Notice how the second equation shows that $x_2 = 1$. All that remains to do is to solve for $x_1$.

Replace equation 1 with the sum of $(-1)$ times equation 2 plus equation 1	Replace row 1 with the sum of $(-1)$ times row 2 plus row 1 $(-R_{2}+R_{1}\to R_{1})$
$\begin{array}{ccccccc} x_1& & &&&=&-1\\ & &x_2&&&=&1\\ & & & &x_3&=&0 \end{array}$	$\left[\begin{array}{cccc}{1}&{0}&{0}&{-1}\\{0}&{1}&{0}&{1}\\{0}&{0}&{1}&{0}\end{array}\right]$

Obviously the equations on the left tell us that $x_1 = -1$, $x_2 = 1$ and $x_3=0$, and notice how the matrix on the right tells us the same information.

We didn’t justify our ability to manipulate our equations in the above three ways; it seems rather obvious that we should be able to do that. In that sense, these operations are “elementary.” These operations are elementary in another sense; they are fundamental – they form the basis for much of what we will do. Since these operations are so important, we list them again here in the context of matrices.

Key Idea $\PageIndex{1}$: Elementary Row Operations

Add a scalar multiple of one row to another row, and replace the latter row with that sum
Multiply one row by a nonzero scalar
Swap the position of two rows

Given any system of linear equations, we can find a solution (if one exists) by using these three row operations. Elementary row operations give us a new linear system, but the solution to the new system is the same as the old. We can use these operations as much as we want and not change the solution. This brings to mind two good questions:

Since we can use these operations as much as we want, how do we know when to stop? (Where are we supposed to “go” with these operations?)
Is there an efficient way of using these operations? (How do we get “there” the fastest?)

We’ll answer the first question first. Most of the time we will want to take our original matrix and, using the elementary row operations, put it into something called reduced row echelon form. This is our “destination,” for this form allows us to readily identify whether or not a solution exists, and in the case that it does, what that solution is.

When we manipulated matrices above to find solutions, we were unwittingly putting the matrix into reduced row echelon form. However, not all solutions come in such a simple manner as we'll see shortly.

Definition: Reduced Row Echelon Form

A matrix is in reduced row echelon form if its entries satisfy the following conditions.

The first nonzero entry in each row is a 1 (called a leading 1).
Each leading 1 comes in a column to the right of the leading 1s in rows above it.
All rows of all 0s come at the bottom of the matrix.
If a column contains a leading 1, then all other entries in that column are 0.

A matrix that satisfies the first three conditions is said to be in row echelon form.

Example $\PageIndex{2}$

Which of the following matrices is in reduced row echelon form?

$\left[\begin{array}{cc}1&0\\0&1\end{array}\right]$
$\left[\begin{array}{ccc}{1}&{0}&{1}\\{0}&{1}&{2}\end{array}\right]$
$\left[\begin{array}{cc} 0&0\\0&0\end{array}\right]$
$\left[\begin{array}{ccc} 1&1&0\\0&0&1\end{array}\right]$
$\left[\begin{array}{cccc}1&0&0&1\\0&0&0&0\\0&0&1&3\end{array}\right]$
$\left[\begin{array}{cccc}1&2&0&0 \\0&0&3&0\\0&0&0&4\end{array}\right]$
$\left[\begin{array}{cccccc}0&1&2&3&0&4\\ 0&0&0&0&1&5\\0&0&0&0&0&0\end{array}\right]$
$\left[\begin{array}{ccc}1&1&0\\ 0&1&0\\0&0&1\end{array}\right]$

Solution

The matrices in a), b), c), d) and g) are all in reduced row echelon form. Check to see that each satisfies the necessary conditions.

The matrix in e) is not in reduced row echelon form since the row of all zeros is not at the bottom. The matrix in f) is not in reduced row echelon form since the first nonzero entries in rows 2 and 3 are not 1. Finally, the matrix in h) is not in reduced row echelon form since the first entry in column 2 is not zero; the second 1 in column 2 is a leading one, hence all other entries in that column should be 0.

We’ve just answered the first question: most of the time we are “going to” reduced row echelon form. This brings us to the second question, “How do we get there quickly?” We address the second question now.

There is no one “right” way of using these operations to transform a matrix into reduced row echelon form. However, there is a general technique that works very well in that it is very efficient (so we don’t waste time on unnecessary steps). This technique is called Gaussian elimination. It is named in honor of the great mathematician Karl Friedrich Gauss.

While this technique isn’t very difficult to use, it is one of those things that is easier understood by watching it being used than explained as a series of steps. With this in mind, we will go through one more example highlighting important steps and then we’ll explain the procedure in detail.

Example $\PageIndex{3}$

Put the augmented matrix of the following system of linear equations into reduced row echelon form. \[\begin{array}{ccccccc} -3x_1&-&3x_2&+&9x_3&=&12\\ 2x_1&+&2x_2&-&4x_3&=&-2\\ &&-2x_2&-&4x_3&=&-8 \end{array} \nonumber \]

Solution

We start by converting the linear system into an augmented matrix.

\[\left[\begin{array}{cccc}\fbox{$-3$}&-3&9&12\\ 2&2&-4&-2\\0&-2&-4&-8\end{array}\right] \nonumber \]

Our next step is to change the entry in the box to a 1. To do this, let’s multiply row 1 by $-\frac13$.

$-\frac{1}{3}R_{1}\to R_{1}$

$\left[\begin{array}{cccc}{1}&{1}&{-3}&{-4}\\{2}&{2}&{-4}&{-2}\\{0}&{-2}&{-4}&{-8}\end{array}\right]$

We have now created a leading 1; that is, the first entry in the first row is a 1. Our next step is to put zeros under this 1. To do this, we’ll use the elementary row operation given below.

$-2R_{1}+R_{2}\to R_{2}$

$\left[\begin{array}{cccc}{1}&{1}&{-3}&{-4}\\{0}&{\fbox{0}}&{2}&{6}\\{0}&{-2}&{-4}&{-8}\end{array}\right]$

Once this is accomplished, we shift our focus from the leading one down one row, and to the right one column, to the position that is boxed. We again want to put a 1 in this position. We can use any elementary row operations, but we need to restrict ourselves to using only the second row and any rows below it. Probably the simplest thing we can do is interchange rows 2 and 3, and then scale the new second row so that there is a 1 in the desired position.

$R_{2}\leftrightarrow R_{3}$	$\left[\begin{array}{cccc}{1}&{1}&{-3}&{-4}\\{0}&{\fbox{-2}}&{-4}&{-8}\\{0}&{0}&{2}&{6}\end{array}\right]$
$-\frac{1}{2}R_{2}\to R_{2}$	$\left[\begin{array}{cccc}{1}&{1}&{-3}&{-4}\\{0}&{1}&{2}&{4}\\{0}&{0}&{\fbox{2}}&{6}\end{array}\right]$

We have now created another leading 1, this time in the second row. Our next desire is to put zeros underneath it, but this has already been accomplished by our previous steps. Therefore we again shift our attention to the right one column and down one row, to the next position put in the box. We want that to be a 1. A simple scaling will accomplish this.

$\frac{1}{2}R_{3}\to R_{3}$

$\left[\begin{array}{cccc}{1}&{1}&{-3}&{-4}\\{0}&{1}&{2}&{4}\\{0}&{0}&{1}&{3}\end{array}\right]$

This ends what we will refer to as the forward steps. Our next task is to use the elementary row operations and go back and put zeros above our leading 1s. This is referred to as the backward steps. These steps are given below.

$3R_{3}+R_{1}\to R_{1}$ $-2R_{3}+R_{2}\to R_{2}$	$\left[\begin{array}{cccc}{1}&{1}&{0}&{5}\\{0}&{1}&{0}&{-2}\\{0}&{0}&{1}&{3}\end{array}\right]$
$-R_{2}+R_{1}\to R_{1}$	$\left[\begin{array}{cccc}{1}&{0}&{0}&{7}\\{0}&{1}&{0}&{-2}\\{0}&{0}&{1}&{3}\end{array}\right]$

It is now easy to read off the solution as $x_1 = 7$, $x_2 = -2$ and $x_3 = 3$.

In all of our practice so far, we’ve only encountered systems of linear equations with exactly one solution. Is this always going to be the case? Could we ever have systems with more than one solution? If so, how many solutions could there be? Could we have systems without a solution? These are some of the questions we’ll address now.

Example $\PageIndex{4}$

Find the solution to the linear system

\[\begin{array}{ccccc} x_1 & +& x_2 & = & 1\\ 2x_1 & + & 2x_2 & = &2\end{array} . \nonumber \]

Solution

Create the corresponding augmented matrix, and then put the matrix into reduced row echelon form.

\[\left[\begin{array}{ccc}{1}&{1}&{1}\\{2}&{2}&{2}\end{array}\right]\qquad\overrightarrow{\text{rref}}\qquad\left[\begin{array}{ccc}{1}&{1}&{1}\\{0}&{0}&{0}\end{array}\right] \nonumber \]

Now convert the reduced matrix back into equations. In this case, we only have one equation, \[x_1+x_2=1 \nonumber \] or, equivalently, \[\begin{align}\begin{aligned} x_1 &=1-x_2\\ x_2&\text{ is free}. \end{aligned}\end{align} \nonumber \]

We have just introduced a new term, the word free. It is used to stress that idea that $x_2$ can take on any value; we are “free” to choose any value for $x_2$. Once this value is chosen, the value of $x_1$ is determined. We have infinite choices for the value of $x_2$, so therefore we have infinite solutions.

For example, if we set $x_2 = 0$, then $x_1 = 1$; if we set $x_2 = 5$, then $x_1 = -4$.

Let’s try another example, one that uses more variables.

Example $\PageIndex{5}$

Find the solution to the linear system \[\begin{array}{ccccccc} & &x_2&-&x_3&=&3\\ x_1& & &+&2x_3&=&2\\ &&-3x_2&+&3x_3&=&-9\\ \end{array}. \nonumber \]

Solution

To find the solution, put the corresponding matrix into reduced row echelon form.

\[\left[\begin{array}{cccc}{0}&{1}&{-1}&{3}\\{1}&{0}&{2}&{2}\\{0}&{-3}&{3}&{-9}\end{array}\right]\qquad\overrightarrow{\text{rref}}\qquad\left[\begin{array}{cccc}{1}&{0}&{2}&{2}\\{0}&{1}&{-1}&{3}\\{0}&{0}&{0}&{0}\end{array}\right] \nonumber \]

Now convert this reduced matrix back into equations. We have \[\begin{align}\begin{aligned} x_1 + 2x_3 &= 2 \\ x_2-x_3&=3 \end{aligned}\end{align} \nonumber \] or, equivalently, \[\begin{align}\begin{aligned} x_1 &= 2-2x_3 \\ x_2&=3+x_3\\x_3&\text{ is free.} \end{aligned}\end{align} \nonumber \]

These two equations tell us that the values of $x_1$ and $x_2$ depend on what $x_3$ is. As we saw before, there is no restriction on what $x_3$ must be; it is “free” to take on the value of any real number. Once $x_3$ is chosen, we have a solution. Since we have infinite choices for the value of $x_3$, we have infinite solutions.

As examples, $x_1 = 2$, $x_2 = 3$, $x_3 = 0$ is one solution; $x_1 = -2$, $x_2 = 5$, $x_3 = 2$ is another solution. Try plugging these values back into the original equations to verify that these indeed are solutions.

We have now seen examples of systems with exactly one solution and others with infinite solutions. How will we recognize that a system does not have a solution? Let’s find out through an example.

Example $\PageIndex{3}$

Find the solution to the linear system \[\begin{array}{ccccccc} x_1&+&x_2&+&x_3&=&1\\ x_1&+&2x_2&+&x_3&=&2\\ 2x_1&+&3x_2&+&2x_3&=&0\\ \end{array}. \nonumber \]

Solution

We start by putting the corresponding matrix into reduced row echelon form.

\[\left[\begin{array}{cccc}{1}&{1}&{1}&{1}\\{1}&{2}&{1}&{2}\\{2}&{3}&{2}&{0}\end{array}\right]\qquad\overrightarrow{\text{rref}}\qquad\left[\begin{array}{cccc}{1}&{0}&{1}&{0}\\{0}&{1}&{0}&{0}\\{0}&{0}&{0}&{1}\end{array}\right] \nonumber \]

Now let us take the reduced matrix and write out the corresponding equations. The first two rows give us the equations \[\begin{align}\begin{aligned} x_1+x_3&=0\\ x_2 &= 0.\\ \end{aligned}\end{align} \nonumber \] So far, so good. However the last row gives us the equation \[0x_1+0x_2+0x_3 = 1 \nonumber \] or, more concisely, $0=1$. Obviously, this is not true; we have reached a contradiction. Therefore, no solution exists.

\(\begin{array}{ccccccc} b&+&g&+&r&=&30\\ &-&2g&+&r&=&0\\ -b&+&g&+&r&=&0 \end{array}\)	\(\left[\begin{array}{cccc}{1}&{1}&{1}&{30} \\ {0}&{-2}&{1}&{0} \\ {-1}&{1}&{1}&{0}\end{array}\right]\)
Replace equation 3 with the sum of equations 1 and 3	Replace row 3 with the sum of rows 1 and 3. \((R_{1}+R_{3}\to R_{3})\)
\(\begin{array}{ccccccc} b&+&g&+&r&=&30\\ &-&2g&+&r&=&0\\ & &2g&+&2r&=&30 \end{array}\)	\(\left[\begin{array}{cccc}{1}&{1}&{1}&{30} \\ {0}&{-2}&{1}&{0} \\ {0}&{2}&{2}&{30}\end{array}\right]\)
Multiply equation 2 by \(-\frac{1}{2}\)	Multiply row 2 by \(-\frac{1}{2}\) \(\left(-\frac{1}{2}R_{2}\to R_{2}\right)\)
\(\begin{array}{ccccccc} b&+&g&+&r&=&30\\ &&g&+&-1/2r&=&0\\ & &2g&+&2r&=&30 \end{array}\)	\(\left[\begin{array}{cccc}{0}&{1}&{1}&{30}\\{0}&{1}&{-\frac{1}{2}}&{0}\\{0}&{2}&{2}&{30}\end{array}\right]\)
Replace equation 1 with the sum of \((-1)\) times equation 2 plus equation 1; Replace equation 3 with the sum of \((-2)\) times equation 2 plus equation 3	Replace row 1 with the sum of \((-1)\) times row 2 plus row 1 \((-R_{2}+R_{1}\to R_{1})\); Replace row 3 with the sum of \((-2)\) times row 2 plus row 3 \((-2R_{2}+R_{3}\to R_{3})\)
\(\begin{array}{ccccccc} b&+& & &3/2r&=&30\\ & &g&-&1/2r&=&0\\ & & & &3r&=&30 \end{array}\)	\(\left[\begin{array}{cccc}{1}&{0}&{\frac{3}{2}}&{30}\\{0}&{1}&{-\frac{1}{2}}&{0}\\{0}&{0}&{3}&{30}\end{array}\right]\)
Multiply equation 3 by \(\frac{1}{3}\)	Multiply row 3 by \(\frac{1}{3}\) \(\left(\frac{1}{3}R_{3}\to R_{3}\right)\)
\(\begin{array}{ccccccc} b&+& & &3/2r&=&30\\ & &g&-&1/2r&=&0\\ & & & &r&=&10 \end{array}\)	\(\left[\begin{array}{cccc}{1}&{0}&{\frac{3}{2}}&{30}\\{0}&{1}&{-\frac{1}{2}}&{0}\\{0}&{0}&{1}&{10}\end{array}\right]\)
Replace equation 2 with the sum of \(\frac{1}{2}\) times equation 3 plus equation 2; Replace equation 1 with the sum of \(-\frac{3}{2}\) times equation 3 plus equation 1	Replace row 2 with the sum of \(\frac{1}{2}\) times row 3 plus row 2 \(\left(\frac{1}{2}R_{3}+R_{2}\to R_{2}\right)\); Replace row 1 with the sum of \(-\frac{3}{2}\) times row 3 plus row 1 \(\left(-\frac{3}{2}R_{3}+R_{1}\to R_{1}\right)\)
\(\begin{array}{ccccccc} b& & & & &=&15\\ & &g& & &=&5\\ & & & &r&=&10 \end{array}\)	\(\left[\begin{array}{cccc}{1}&{0}&{0}&{15}\\{0}&{1}&{0}&{5}\\{0}&{0}&{1}&{10}\end{array}\right]\)

Replace equation 2 with the sum of \((-2)\) times equation 1 plus equation 2; Replace equation 3 with the sum of equation 1 and equation 3	Replace row 2 with the sum of \((-2)\) times row 1 plus row 2 \((-2R_{1}+R_{2}\to R_{2})\); Replace row 3 with the sum of row 1 and row 3 \((R_{1}+R_{3}\to R_{3})\)
\(\begin{array}{ccccccc} x_1&+&x_2&+&x_3&=&0\\ & & & &-x_3&=&0\\ & &2x_2&-&x_3&=&2 \end{array}\)	\(\left[\begin{array}{cccc}{1}&{1}&{1}&{0}\\{0}&{0}&{-1}&{0}\\{0}&{2}&{-1}&{2}\end{array}\right]\)

Interchange equations 2 and 3	Interchange rows 2 and 3 \(R_{2}\leftrightarrow R_{3}\)
\(\begin{array}{ccccccc} x_1&+&x_2&+&x_3&=&0\\ & &2x_2&-&x_3&=&2\\ & & & &-x_3&=&0 \end{array}\)	\(\left[\begin{array}{cccc}{1}&{1}&{1}&{0}\\{0}&{2}&{-1}&{2}\\{0}&{0}&{-1}&{0}\end{array}\right]\)
Multiply equation 2 by \(\frac{1}{2}\)	Multiply row 2 by \(\frac{1}{2}\) \(\left(\frac{1}{2}R_{2}\to R_{2}\right)\)
\(\begin{array}{ccccccc} x_1&+&x_2&+&x_3&=&0\\ & &x_2&-&\frac12x_3&=&1\\ & & & &-x_3&=&0 \end{array}\)	\(\left[\begin{array}{cccc}{1}&{1}&{1}&{0}\\{0}&{1}&{-\frac{1}{2}}&{1}\\{0}&{0}&{-1}&{0}\end{array}\right]\)
Multiply equation 3 by \(-1\)	Multiply row 3 by \(-1\) \((-1R_{3}\to R_{3})\)
\(\begin{array}{ccccccc} x_1&+&x_2&+&x_3&=&0\\ & &x_2&-&\frac12x_3&=&1\\ & & & &x_3&=&0 \end{array}\)	\(\left[\begin{array}{cccc}{1}&{1}&{1}&{0}\\{0}&{1}&{-\frac{1}{2}}&{1}\\{0}&{0}&{1}&{0}\end{array}\right]\)

Replace equation 1 with the sum of \((-1)\) times equation 3 plus equation 1; Replace equation 2 with the sum of \(\frac{1}{2}\) times equation 3 plus equation 2	Replace row 1 with the sum of \((-1)\) times row 3 plus row 1 \((-R_{3}+R_{1}\to R_{1})\); Replace row 2 with the sum of \(\frac{1}{2}\) times row 3 plus row 2 \(\left(\frac{1}{2}R_{3}+R_{2}\to R_{2}\right)\)
\(\begin{array}{ccccccc} x_1&+&x_2&&&=&0\\ & &x_2&&&=&1\\ & & & &x_3&=&0 \end{array}\)	\(\left[\begin{array}{cccc}{1}&{1}&{0}&{0}\\{0}&{1}&{0}&{1}\\{0}&{0}&{1}&{0}\end{array}\right]\)

Replace equation 1 with the sum of \((-1)\) times equation 2 plus equation 1	Replace row 1 with the sum of \((-1)\) times row 2 plus row 1 \((-R_{2}+R_{1}\to R_{1})\)
\(\begin{array}{ccccccc} x_1& & &&&=&-1\\ & &x_2&&&=&1\\ & & & &x_3&=&0 \end{array}\)	\(\left[\begin{array}{cccc}{1}&{0}&{0}&{-1}\\{0}&{1}&{0}&{1}\\{0}&{0}&{1}&{0}\end{array}\right]\)

\(R_{2}\leftrightarrow R_{3}\)	\(\left[\begin{array}{cccc}{1}&{1}&{-3}&{-4}\\{0}&{\fbox{-2}}&{-4}&{-8}\\{0}&{0}&{2}&{6}\end{array}\right]\)
\(-\frac{1}{2}R_{2}\to R_{2}\)	\(\left[\begin{array}{cccc}{1}&{1}&{-3}&{-4}\\{0}&{1}&{2}&{4}\\{0}&{0}&{\fbox{2}}&{6}\end{array}\right]\)

\(3R_{3}+R_{1}\to R_{1}\) \(-2R_{3}+R_{2}\to R_{2}\)	\(\left[\begin{array}{cccc}{1}&{1}&{0}&{5}\\{0}&{1}&{0}&{-2}\\{0}&{0}&{1}&{3}\end{array}\right]\)
\(-R_{2}+R_{1}\to R_{1}\)	\(\left[\begin{array}{cccc}{1}&{0}&{0}&{7}\\{0}&{1}&{0}&{-2}\\{0}&{0}&{1}&{3}\end{array}\right]\)

Caution

Definition: Matrix

Example \(\PageIndex{1}\)

Solution

Key Idea \(\PageIndex{1}\): Elementary Row Operations

Definition: Reduced Row Echelon Form

Example \(\PageIndex{2}\)

Solution

Example \(\PageIndex{3}\)

Solution

Example \(\PageIndex{4}\)

Solution

Example \(\PageIndex{5}\)

Solution

Example \(\PageIndex{3}\)

Solution