Skip to main content

Understanding Linear Algebra: Data Science Edition

Randall Pruim

Section 2.2 Finding solutions to linear systems

In the previous section, we looked at systems of linear equations from a graphical perspective. Since the equations had only two or three variables, we could study the solution spaces as the intersections of lines and planes.
Because we will eventually consider systems with many equations and many variables, this graphical approach will not generally be a useful strategy. Instead, we will approach this problem algebraically and develop a technique to describe the solution spaces of general linear systems.

Subsection 2.2.1 Gaussian elimination

We will develop an algorithm, which is usually called Gaussian elimination, that allows us to describe the solution space of a linear system. This algorithm plays a central role in much of what is to come.

Preview Activity 2.2.1.

In this activity, we will consider some simple examples that will guide us in finding a more general approach.
  1. Give a description of the solution space to the linear system:
    \begin{equation*} \begin{alignedat}{3} x \amp = \amp 2 \\ y \amp = \amp -1 \\ \end{alignedat} \end{equation*}
  2. Give a description of the solution space to the linear system:
    \begin{equation*} \begin{alignedat}{4} -x \amp {} + {} \amp 2y \amp {}-{} \amp z \amp {}={} \amp -3 \\ \amp \amp 3y \amp {}+{} \amp z \amp {}={} \amp -1 \\ \amp \amp \amp \amp 2z \amp {}={} \amp 4 \\ \end{alignedat} \end{equation*}
  3. Give a description of the solution space to the linear system:
    \begin{equation*} \begin{alignedat}{3} x \amp {}+{} \amp 3y \amp {}={} \amp -1 \\ 2x\amp {}+{} \amp y \amp {}={} \amp 3 \\ \end{alignedat} \end{equation*}
  4. Describe the solution space to the linear equation \(0x = 0\text{.}\)
  5. Describe the solution space to the linear equation \(0x = 5\text{.}\)
Answer.
  1. \((x,y) = (2,-1)\text{.}\)
  2. \((x,y,z) = (-1,-1,2)\text{.}\)
  3. \((x,y) = (2,-1)\text{.}\)
  4. Any real number is a solution.
  5. There are no solutions.
Solution.
  1. The equations tell us the value of both variables so there is only one solution \((x,y) = (2,-1)\text{.}\)
  2. We first use the third equation to determine that \(z=2\text{.}\) We next substitute this value into the first two equations to obtain
    \begin{equation*} \begin{alignedat}{3} -x \amp {} + {} \amp 2y \amp {}={} \amp -1 \\ \amp \amp 3y \amp {}={} \amp -3 \\ \end{alignedat} \end{equation*}
    Now we can use the second equation to determine that \(y=-1\text{,}\) substitute that value into the first equation, and determine that \(x=-1\text{.}\) This tells us that the linear system has one solution \((x,y,z) = (-1,-1,2)\text{.}\)
  3. Notice that we can rewrite the first equation as \(x=-1-3y\) and substitute this into the second equation to obtain
    \begin{equation*} 2(-1-3y)+y = -2 -5y = 3. \end{equation*}
    This tells us that \(y=-1\) and \(x=-1-3y = 2\text{.}\) The linear system therefore has one solution \((x,y) = (2,-1)\text{.}\)
  4. No matter the value of \(x\text{,}\) we have \(0x = 0\text{.}\) Therefore, the solution space to the equation \(0x=0\) is all real numbers \(x\text{.}\) In other words, this equation does not place a restriction on the value of \(x\text{.}\)
  5. By contrast, the equation \(0x=5\) has no solutions since no value of \(x\text{,}\) when multiplied by \(0\text{,}\) can produce \(5\text{.}\)
These examples lead to a few observations that motivate a general approach to finding solutions of linear systems.

Observation 2.2.1.

First, finding the solution space to some systems is simple. For example, because each equation in the following system
\begin{equation*} \begin{alignedat}{3} x \amp {}={} \amp -4 \\ y \amp {}={} \amp 2 \\ \end{alignedat} \end{equation*}
has only one variable, it prescribes a specific value for that variable. We therefore see that there is exactly one solution, which is \((x,y) = (-4,2)\text{.}\) We call such a system decoupled.

Observation 2.2.2.

Second, there is a process that can be used to find solutions to certain types of linear systems. For instance, let’s consider the system
\begin{equation*} \begin{alignedat}{4} x \amp {} + {} \amp 2y \amp {}-{} \amp 2z \amp {}={} \amp -4 \\ \amp \amp -y \amp {}+{} \amp z \amp {}={} \amp 3 \\ \amp \amp \amp \amp 3z \amp {}={} \amp 3 \\ \end{alignedat} \end{equation*}
Multiplying both sides of the last equation by \(1/3\) gives us
\begin{equation*} \begin{alignedat}{4} x \amp {} + {} \amp 2y \amp {}-{} \amp 2z \amp {}={} \amp -4 \\ \amp \amp -y \amp {}+{} \amp z \amp {}={} \amp 3 \\ \amp \amp \amp \amp z \amp {}={} \amp 1 \\ \end{alignedat} \end{equation*}
Any solution to this linear system must then have \(z=1\text{.}\)
Once we know that, we can substitute \(z=1\) into the first and second equations and simplify to obtain a new system of equations having the same solutions:
\begin{equation*} \begin{alignedat}{3} x \amp {} + {} \amp 2y {}={} \amp\amp -2 \\ \amp \amp -y {}={} \amp\amp 2 \\ \end{alignedat} \end{equation*}
The second equation, after multiplying both sides by \(-1\text{,}\) tells us that \(y=-2\text{.}\) We can then substitute this value into the first equation to determine that \(x=2\text{.}\)
In this way, we arrive at a decoupled system, which shows that there is exactly one solution, namely \((x,y,z)=(2,-2,1)\text{.}\)
Our original system,
\begin{equation*} \begin{alignedat}{4} x \amp {} + {} \amp 2y \amp {}-{} \amp 2z \amp {}={} \amp -4 \\ \amp \amp -y \amp {}+{} \amp z \amp {}={} \amp 3 \\ \amp \amp \amp \amp 3z \amp {}={} \amp 3 \\ \end{alignedat} \end{equation*}
is called a triangular system due to the shape formed by the coefficients. As this example demonstrates, triangular systems are easily solved by this process, which is called back substitution.

Observation 2.2.3.

We can use substitution in a more general way to solve linear systems. For example, a natural approach to the system
\begin{equation*} \begin{alignedat}{3} x \amp {} + {} \amp 2y \amp {}={} \amp 1 \\ 2x\amp {}+{} \amp 3y \amp {}={} \amp 3 \\ \end{alignedat} \end{equation*}
is to use the first equation to express \(x\) in terms of \(y\text{:}\)
\begin{equation*} x = 1-2y \end{equation*}
and then substitute this into the second equation and simplify:
\begin{equation*} \begin{alignedat}{2} 2x + 3y \amp {}= \amp 3 \\ 2(1-2y) + 3y \amp {}={} \amp 3 \\ 2-4y + 3y \amp {}={} \amp 3 \\ -y \amp {}={} \amp 1 \\ y \amp {}={} \amp -1 \\ \end{alignedat} \end{equation*}
From here, we can substitute \(y=-1\) into the first equation to arrive at the solution \((x,y)=(3,-1)\text{.}\)
However, the two-step process of solving for \(x\) in terms of \(y\) and substituting into the second equation may be performed more efficiently by adding a multiple of the first equation to the second. In this case, we will multiply the first equation by -2 and add to the second equation
\begin{equation*} \begin{array}{cr} \amp -2(\text{equation 1}) \\ + \amp \text{equation 2} \\ \hline \end{array} \end{equation*}
to obtain
\begin{equation*} \begin{array}{cr} \amp -2(x+2y=1) \\ + \amp 2x+3y = 3 \\ \hline \\ \end{array} \end{equation*}
which gives us
\begin{equation*} \begin{array}{crcr} \amp -2x-4y \amp = \amp -2 \\ + \amp 2x+3y \amp = \amp 3 \\ \hline \amp -y \amp = \amp 1 \\ \end{array} \end{equation*}
In this way, the system
\begin{equation*} \begin{alignedat}{3} x \amp {} + {} \amp 2y \amp {}={} \amp 1 \\ 2x\amp {}+{} \amp 3y \amp {}={} \amp 3 \\ \end{alignedat} \end{equation*}
is transformed into the new triangular system
\begin{equation*} \begin{alignedat}{3} x \amp {} + {} \amp 2y \amp {}={} \amp 1 \\ \amp \amp -y \amp {}={} \amp 1 \\ \end{alignedat} \end{equation*}
Notice that this process can be reversed. Beginning with the triangular system, we can recover the original system by multiplying the first equation by 2 and adding it to the second. Because of this, the two systems have the same solution space. We will revisit this point later and give what may be a more convincing explanation.
Of course, the choice to multiply the first equation by -2 was made so that the terms involving \(x\) in the two equations will cancel leading to a triangular system that can be solved using back substitution.
Based on these observations, we take note of three operations that transform a system of linear equations into a new system of equations having the same solution space. These are called the three elementary row operations. Our goal is to create a new system whose solution space is the same as the original system’s and may be easily described.
Scaling
(\(s R_i \to R_i \))
We can multiply one equation by a nonzero number. For instance,
\begin{equation*} 2x -4y = 6 \end{equation*}
has the same set of solutions as
\begin{equation*} \frac12(2x-4y=6) \end{equation*}
or
\begin{equation*} x-2y=3\text{.} \end{equation*}
Interchange
(\(R_i \leftrightarrow R_j\))
Interchanging equations will not change the set of solutions. For instance,
\begin{equation*} \begin{alignedat}{3} 2x \amp {}+{} \amp 4y \amp {}={} \amp 1 \\ x \amp {}-{} \amp 3y \amp {}={} \amp 0 \\ \end{alignedat} \end{equation*}
has the same set of solutions as
\begin{equation*} \begin{alignedat}{3} x \amp {}-{} \amp 3y \amp {}={} \amp 0 \\ 2x \amp {}+{} \amp 4y \amp {}={} \amp 1 \\ \end{alignedat} \end{equation*}
Replacement
(\(s R_i + R_j \to R_j\))
As we saw above, we may multiply one equation by a real number and add it to another equation. We call this process replacement.

Example 2.2.4.

Let’s illustrate the use of these operations to find the solution space to the system of equations:
\begin{equation*} \begin{alignedat}{4} x \amp {}+{} \amp 2y \amp \amp \amp {}={} \amp 4 \\ 2x \amp {}+{} \amp y \amp {}-{} \amp 3z \amp {}={} \amp 11 \\ -3x \amp {}-{} \amp 2y \amp {}+{} \amp z \amp {}={} \amp -10 \\ \end{alignedat} \end{equation*}
We will first transform the system into a triangular system so we start by eliminating \(x\) from the second and third equations.
We begin with a replacement operation where we multiply the first equation by -2 and add the result to the second equation. (\(-2 R_1 + R_2 \to R_2\))
\begin{equation*} \begin{alignedat}{4} x \amp {}+{}\amp 2y \amp \amp \amp {}={} \amp 4 \\ \amp {}-{}\amp 3y \amp {}-{} \amp 3z \amp {}={} \amp 3 \\ -3x \amp {}-{}\amp 2y \amp {}+{} \amp z \amp {}={} \amp -10 \\ \end{alignedat} \end{equation*}
Another replacement operation eliminates \(x\) from the third equation. We multiply the first equation by 3 and add to the third. (\(3 R_1 + R_3 \to R_3\))
\begin{equation*} \begin{alignedat}{4} x \amp {}+{} \amp 2y \amp \amp \amp {}={} \amp 4 \\ \amp {}-{} \amp 3y \amp {}-{} \amp 3z \amp {}={} \amp 3 \\ \amp {}+{} \amp 4y \amp {}+{} \amp z \amp {}={} \amp 2 \\ \end{alignedat} \end{equation*}
Scale the second equation by multiplying it by \(-1/3\text{.}\) (\(- \frac13 R_2 \to R_2\))
\begin{equation*} \begin{alignedat}{4} x \amp {}+{} \amp 2y \amp \amp \amp {}={} \amp 4 \\ \amp \amp y \amp {}+{} \amp z \amp {}={} \amp -1 \\ \amp \amp 4y \amp {}+{} \amp z \amp {}={} \amp 2 \\ \end{alignedat} \end{equation*}
Eliminate \(y\) from the third equation by multiplying the second equation by -4 and adding it to the third. Notice that we now have a triangular system that can be solved using back substitution. (\(-4 R_2 + R_3 \to R_3\))
\begin{equation*} \begin{alignedat}{4} x \amp {}+{} \amp 2y \amp \amp \amp {}={} \amp 4 \\ \amp \amp y \amp {}+{} \amp z \amp {}={} \amp -1 \\ \amp \amp \amp {}-{} \amp 3z \amp {}={} \amp 6 \\ \end{alignedat} \end{equation*}
After scaling the third equation by \(-1/3\text{,}\) we have found the value for \(z\text{.}\) (\(\frac 13 R_3 \to R_3\))
\begin{equation*} \begin{alignedat}{4} x \amp {}+{} \amp 2y \amp \amp \amp {}={} \amp 4 \\ \amp \amp y \amp {}+{} \amp z \amp {}={} \amp -1 \\ \amp \amp \amp {} {} \amp z \amp {}={} \amp -2 \\ \end{alignedat} \end{equation*}
We eliminate \(z\) from the second equation by multiplying the third equation by -1 and adding to the second. (\(- R_3 + R_2 \to R_2\))
\begin{equation*} \begin{alignedat}{4} x \amp {}+{} \amp 2y \amp \amp \amp {}={} \amp 4 \\ \amp \amp y \amp {} {} \amp \amp {}={} \amp 1 \\ \amp \amp \amp {} {} \amp z \amp {}={} \amp -2 \\ \end{alignedat} \end{equation*}
Finally, multiply the second equation by -2 and add to the first to obtain (\(-2 R_2 + R_1 \to R_1\))
\begin{equation*} \begin{alignedat}{3} x \amp {}={} \amp 2 \\ y \amp {}={} \amp 1 \\ z \amp {}={} \amp -2 \\ \end{alignedat} \end{equation*}
Now that we have arrived at a decoupled system, we know that there is exactly one solution to our original system of equations, which is \((x,y,z) = (2,1,-2)\text{.}\)
One could find the same result by applying a different sequence of replacement and scaling operations. However, we chose this particular sequence guided by our desire to first transform the system into a triangular one. To do this, we eliminated the first variable \(x\) from all but one equation and then proceeded to the next variables working left to right. Once we had a triangular system, we used back substitution moving through the variables right to left.
We call this process Gaussian elimination and note that it is our primary tool for solving systems of linear equations.

Activity 2.2.2. Gaussian Elimination.

For each of the following linear systems, use Gaussian elimination to describe the solutions space. In particular, determine whether each linear system has exactly one solution, infinitely many solutions, or no solutions.
  1. \(\displaystyle \begin{alignedat}{4} x \amp {}+{} \amp y \amp {}+{} \amp 2z \amp {}={} \amp 1 \\ 2x \amp {}-{} \amp y \amp {}-{} \amp 2z \amp {}={} \amp 2 \\ -x \amp {}+{} \amp y \amp {}+{} \amp z \amp {}={} \amp 0 \\ \end{alignedat}\)
  2. \(\displaystyle \begin{alignedat}{4} -x \amp {}-{} \amp 2y \amp {}+{} \amp 2z \amp {}={} \amp -1 \\ 2x \amp {}+{} \amp 4y \amp {}-{} \amp z \amp {}={} \amp 5 \\ x \amp {}+{} \amp 2y \amp \amp \amp {}={} \amp 3 \\ \end{alignedat}\)
  3. \(\displaystyle \begin{alignedat}{4} -x \amp {}-{} \amp 2y \amp {}+{} \amp 2z \amp {}={} \amp -1 \\ 2x \amp {}+{} \amp 4y \amp {}-{} \amp z \amp {}={} \amp 5 \\ x \amp {}+{} \amp 2y \amp \amp \amp {}={} \amp 2 \\ \end{alignedat}\)
Answer.
  1. There is a single solution \((1,2,-1)\text{.}\)
  2. There are infinitely many solutions.
  3. There are no solutions.
Solution.
  1. Our aim is to apply a sequence of scaling, interchange, and replacement operations to first put the system into a triangular form. We begin by multiplying the first equation by \(-2\) and adding it to the second equation. Next, we add the first equation to the third. This leads us to:
    \begin{equation*} \begin{alignedat}{4} x \amp {}+{} \amp y \amp {}+{} \amp 2z \amp {}={} \amp 1 \\ \amp \amp -3y \amp {}-{} \amp 6z \amp {}={} \amp 0 \\ \amp \amp 2y \amp {}+{} \amp 3z \amp {}={} \amp 1 \\ \end{alignedat} \end{equation*}
    We will now apply a scaling operation to make the coefficient of \(y\) equal \(1\) in the second equation.
    \begin{equation*} \begin{alignedat}{4} x \amp {}+{} \amp y \amp {}+{} \amp 2z \amp {}={} \amp 1 \\ \amp \amp y \amp {}+{} \amp 2z \amp {}={} \amp 0 \\ \amp \amp 2y \amp {}+{} \amp 3z \amp {}={} \amp 1 \\ \end{alignedat} \end{equation*}
    Another replacement operation brings the system into a triangular form.
    \begin{equation*} \begin{alignedat}{4} x \amp {}+{} \amp y \amp {}+{} \amp 2z \amp {}={} \amp 1 \\ \amp \amp y \amp {}+{} \amp 2z \amp {}={} \amp 0 \\ \amp \amp \amp \amp -z \amp {}={} \amp 1 \\ \end{alignedat} \end{equation*}
    From here, we begin the process of back substitution seeking a decoupled system.
    \begin{equation*} \begin{alignedat}{4} x \amp {}+{} \amp y \amp \amp \amp {}={} \amp 3 \\ \amp \amp y \amp \amp \amp {}={} \amp 2 \\ \amp \amp \amp \amp z \amp {}={} \amp -1 \\ \end{alignedat} \end{equation*}
    Finally, we have the decoupled system
    \begin{equation*} \begin{alignedat}{4} x \amp \amp \amp \amp \amp {}={} \amp 1 \\ \amp \amp y \amp \amp \amp {}={} \amp 2 \\ \amp \amp \amp \amp z \amp {}={} \amp -1 \\ \end{alignedat} \end{equation*}
    which tells us that the solution space consists of the single solution \((1,2,-1)\text{.}\)
  2. Once again, we begin with a sequence of replacement and scaling operations that lead to the triangular system
    \begin{equation*} \begin{alignedat}{4} -x \amp {}-{} \amp 2y \amp {}+{} \amp 2z \amp {}={} \amp -1 \\ \amp \amp \amp \amp z \amp {}={} \amp 1 \\ \amp \amp \amp \amp 0 \amp {}={} \amp 0 \\ \end{alignedat} \end{equation*}
    Back substitution gives us the system
    \begin{equation*} \begin{alignedat}{4} x \amp {}+{} \amp 2y \amp \amp \amp {}={} \amp 3 \\ \amp \amp \amp \amp z \amp {}={} \amp 1 \\ \amp \amp \amp \amp 0 \amp {}={} \amp 0 \\ \end{alignedat} \end{equation*}
    The third equation does not impose a restriction on the solutions since it is satisfied for any \((x,y,z)\text{.}\) The second equation tells us that \(z\) must equal \(1\text{;}\) however, there are infinitely many solutions to the first equation that have \(z=1\text{.}\) Therefore, this system has infinitely many solutions.
  3. After applying two replacement and one scaling operation, we find
    \begin{equation*} \begin{alignedat}{4} -x \amp {}-{} \amp 2y \amp {}+{} \amp 2z \amp {}={} \amp -1 \\ \amp \amp \amp \amp z \amp {}={} \amp 1 \\ \amp \amp \amp \amp 2z \amp {}={} \amp 1 \\ \end{alignedat} \end{equation*}
    Another replacement operation leads to the system
    \begin{equation*} \begin{alignedat}{4} -x \amp {}-{} \amp 2y \amp {}+{} \amp 2z \amp {}={} \amp -1 \\ \amp \amp \amp \amp z \amp {}={} \amp 1 \\ \amp \amp \amp \amp 0 \amp {}={} \amp 1 \\ \end{alignedat} \end{equation*}
    Since the third equation has no solutions, the original system can have no solutions as well.

Subsection 2.2.2 Augmented matrices

After performing Gaussian elimination a few times, you probably noticed that you spent most of the time concentrating on the coefficients and simply recorded the variables as place holders. Based on this observation, we will introduce a shorthand description of linear systems.
When writing a linear system, we always write the variables in the same order in each equation. We then construct an augmented matrix by simply omitting the variables and recording the numerical data in a rectangular array. For instance, the system of equations below has the following augmented matrix
\begin{equation*} \begin{alignedat}{4} -x \amp {}-{} \amp 2y \amp {}+{} \amp 2z \amp {}={} \amp -1 \\ 2x \amp {}+{} \amp 4y \amp {}-{} \amp z \amp {}={} \amp 5 \\ x \amp {}+{} \amp 2y \amp \amp \amp {}={} \amp 3 \\ \end{alignedat} \end{equation*}
\begin{equation*} \left[ \begin{array}{rrr|r} -1 \amp -2 \amp 2 \amp -1 \\ 2 \amp 4 \amp -1 \amp 5 \\ 1 \amp 2 \amp 0 \amp 3 \\ \end{array} \right]. \end{equation*}
The vertical line reminds us where the equals signs appear in the equations. Entries in the matrix to the left of the vertical line correspond to coefficients of the equations. We sometimes choose to focus only on the coefficients of the system in which case we write the coefficient matrix as
\begin{equation*} \left[ \begin{array}{rrr} -1 \amp -2 \amp 2 \\ 2 \amp 4 \amp -1 \\ 1 \amp 2 \amp 0 \\ \end{array} \right]. \end{equation*}
The three operations we perform on systems of equations translate naturally into operations on matrices. For instance, the replacement operation that multiplies the first equation by 2 and adds it to the second may be performed by multiplying the first row of the augmented matrix by 2 and adding it to the second row:
\begin{equation*} \left[ \begin{array}{rrr|r} -1 \amp -2 \amp 2 \amp -1 \\ 2 \amp 4 \amp -1 \amp 5 \\ 1 \amp 2 \amp 0 \amp 3 \\ \end{array} \right] \sim \left[ \begin{array}{rrr|r} -1 \amp -2 \amp 2 \amp -1 \\ 0 \amp 0 \amp 3 \amp 3 \\ 1 \amp 2 \amp 0 \amp 3 \\ \end{array} \right]\text{.} \end{equation*}
The symbol \(\sim\) between the matrices indicates that the two matrices are related by a sequence of scaling, interchange, and replacement operations. Since these operations act on the rows of the matrices, we say that the matrices are row equivalent. Notice that the linear systems corresponding to two row equivalent augmented matrices have the same solution space.

Activity 2.2.3. Augmented matrices and solution spaces.

  1. Write the augmented matrix for the linear system
    \begin{equation*} \begin{alignedat}{4} x \amp {}+{} \amp 2y \amp {}-{} \amp z \amp {}={} \amp 1 \\ 3x \amp {}+{} \amp 2y \amp {}+{} \amp 2z \amp {}={} \amp 7 \\ -x \amp \amp \amp {}+{} \amp 4z \amp {}={} \amp -3 \\ \end{alignedat} \end{equation*}
    and perform Gaussian elimination to describe the solution space in as much detail as you can.
  2. Suppose that you have a linear system in the variables \(x\) and \(y\) whose augmented matrix is row equivalent to
    \begin{equation*} \left[ \begin{array}{rr|r} 1 \amp 0 \amp 3 \\ 0 \amp 1 \amp 0 \\ 0 \amp 0 \amp 0 \\ \end{array} \right]\text{.} \end{equation*}
    Write the linear system corresponding to this augmented matrix and describe its solution set in as much detail as you can.
  3. Suppose that you have a linear system in the variables \(x\) and \(y\) whose augmented matrix is row equivalent to
    \begin{equation*} \left[ \begin{array}{rr|r} 1 \amp 0 \amp 3 \\ 0 \amp 1 \amp 0 \\ 0 \amp 0 \amp 1 \\ \end{array} \right]\text{.} \end{equation*}
    Write the linear system corresponding to this augmented matrix and describe its solution set in as much detail as you can.
  4. Suppose that the augmented matrix of a linear system has the following shape where \(*\) could be any real number.
    \begin{equation*} \left[ \begin{array}{rrrrr|r} * \amp * \amp * \amp * \amp * \amp * \\ * \amp * \amp * \amp * \amp * \amp * \\ * \amp * \amp * \amp * \amp * \amp * \\ \end{array} \right]\text{.} \end{equation*}
    1. How many equations are there in this system and how many variables?
    2. Based on our earlier discussion in Section 2.1, do you think it’s possible that this system has exactly one solution, infinitely many solutions, or no solutions?
    3. Suppose that this augmented matrix is row equivalent to
      \begin{equation*} \left[ \begin{array}{rrrrr|r} 1 \amp 2 \amp 0 \amp 0 \amp 3 \amp 2 \\ 0 \amp 0 \amp 1 \amp 2 \amp -1 \amp -1 \\ 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \\ \end{array} \right]\text{.} \end{equation*}
      Make a choice for the names of the variables and write the corresponding linear system. Does the system have exactly one solution, infinitely many solutions, or no solutions?
Answer.
  1. There is a single solution \((3,-1,0)\text{.}\)
  2. There is a single solution \((3,0)\text{.}\)
  3. There are no solutions.
  4. This system has three equations in five variables, and there are infinitely many solutions.
Solution.
  1. The augmented matrix for this linear system is
    \begin{equation*} \left[\begin{array}{rrr|r} 1 \amp 2 \amp -1 \amp 1 \\ 3 \amp 2 \amp 2 \amp 7 \\ -1 \amp 0 \amp 4 \amp -3 \\ \end{array} \right] \sim \left[\begin{array}{rrr|r} 1 \amp 0 \amp 0 \amp 3 \\ 0 \amp 1 \amp 0 \amp -1 \\ 0 \amp 0 \amp 1 \amp 0 \end{array}\right] \end{equation*}
    This corresponds to the system of equations
    \begin{equation*} \begin{alignedat}{3} x \amp {}={} \amp 3 \\ y \amp {}={} \amp -1 \\ z \amp {}={} \amp 0 \\ \end{alignedat} \end{equation*}
    showing that there is a single solution \((x,y,z) = (3,-1,0)\text{.}\)
  2. The corresponding system of equations is
    \begin{equation*} \begin{alignedat}{3} x \amp {}={} \amp 3 \\ y \amp {}={} \amp 0 \\ 0 \amp {}={} \amp 0 \\ \end{alignedat} \end{equation*}
    The third equation is satisfied for any values of \(x\) and \(y\text{.}\) Therefore, we see that the only solution to the system is \((x,y) = (3,0)\text{.}\)
  3. Here, the corresponding system of equations is
    \begin{equation*} \begin{alignedat}{3} x \amp {}={} \amp 3 \\ y \amp {}={} \amp 0 \\ 0 \amp {}={} \amp 1 \\ \end{alignedat} \end{equation*}
    Since the third equation is not satisfied for any values of \(x\) and \(y\text{,}\) there are no solutions to the system.
  4. The system corresponding to this augmented matrix has three equations and five variables. Our first guess is there are infinitely many solutions. If we write out the equations corresponding to the augmented matrix, we find
    \begin{equation*} \begin{alignedat}{5} x_1 \amp {}+{} \amp 2x_2 \amp \amp \amp \amp {}+{} \amp 3x_5 \amp {}={} \amp 2 \\ \amp \amp \amp x_3 \amp {}+{} \amp 2x_4 \amp {}-{} \amp x_5 \amp {}={} \amp -1 \\ \end{alignedat} \end{equation*}
    since the third row of the augmented matrix does not restrict the solution space. From here, we see that there are infinitely many solutions: if we make any choice for the variables \(x_2\text{,}\) \(x_4\text{,}\) and \(x_5\text{,}\) we can find values for \(x_1\) and \(x_3\) that give a solution.

Subsection 2.2.3 Reduced row echelon form

There is a special class of matrices whose form makes it especially easy to describe the solution space of the corresponding linear system. As we describe the properties of this class of matrices, it may be helpful to consider an example, such as the following matrix. Once again, an asterisk (\(*\)) represents an element that can be any real number.
\begin{equation*} \left[ \begin{array}{rrrrrr} 1 \amp * \amp 0 \amp * \amp 0 \amp * \\ 0 \amp 0 \amp 1 \amp * \amp 0 \amp * \\ 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp * \\ 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \\ 0 \amp 0 \amp 0 \amp 0 \amp 0 \amp 0 \\ \end{array} \right]\text{.} \end{equation*}

Definition 2.2.5.

We say that a matrix is in reduced row echelon form (RREF) if the following properties are satisfied.
  • If the entries in a row are all zero, then the same is true of any row below it.
  • If we move across a row from left to right, the first nonzero entry we encounter is 1. We call this entry the leading entry in the row.
  • The leading entry in any row is to the right of the leading entries in all the rows above it.
  • A leading entry is the only nonzero entry in its column.
We call a matrix in reduced row echelon form a reduced row echelon matrix.
We have been intentionally vague about whether the matrix we are considering is an augmented matrix corresponding to a linear system or a coefficient matrix since we will consider both possibilities in the future.

Activity 2.2.4. Identifying reduced row echelon matrices.

Consider each of the following augmented matrices. Determine if the matrix is in reduced row echelon form. If it is not, perform a sequence of scaling, interchange, and replacement operations to obtain a row equivalent matrix that is in reduced row echelon form. Then use the reduced row echelon matrix to describe the solution space.
  1. \(\left[ \begin{array}{rrr|r} 2 \amp 0 \amp 4 \amp -8 \\ 0 \amp 1 \amp 3 \amp 2 \\ \end{array} \right] \text{.}\)
  2. \(\left[ \begin{array}{rrr|r} 1 \amp 0 \amp 0 \amp -1 \\ 0 \amp 1 \amp 0 \amp 3 \\ 0 \amp 0 \amp 1 \amp 1 \\ \end{array} \right] \text{.}\)
  3. \(\left[ \begin{array}{rrr|r} 1 \amp 0 \amp 4 \amp 2 \\ 0 \amp 1 \amp 3 \amp 2 \\ 0 \amp 0 \amp 0 \amp 1 \\ \end{array} \right] \text{.}\)
  4. \(\left[ \begin{array}{rrr|r} 0 \amp 1 \amp 3 \amp 2 \\ 0 \amp 0 \amp 0 \amp 0 \\ 1 \amp 0 \amp 4 \amp 2 \\ \end{array} \right] \text{.}\)
  5. \(\left[ \begin{array}{rrr|r} 1 \amp 2 \amp -1 \amp 2 \\ 0 \amp 1 \amp -2 \amp 0 \\ 0 \amp 0 \amp 1 \amp 1 \\ \end{array} \right] \text{.}\)
Answer.
  1. The row equivalent reduced row echelon form is
    \begin{equation*} \left[ \begin{array}{rrr|r} 1 \amp 0 \amp 2 \amp -4 \\ 0 \amp 1 \amp 3 \amp 2 \\ \end{array} \right]\text{,} \end{equation*}
    and there are infinitely many solutions.
  2. This matrix is in reduced row echelon form. There is a single solution \((-1,3,1)\text{.}\)
  3. This matrix is also in reduced row echelon form. However, this are no solutions since the third equation is \(0 = 1\text{.}\)
  4. The row equivalent reduced row echelon form is
    \begin{equation*} \left[ \begin{array}{rrr|r} 1 \amp 0 \amp 4 \amp 2 \\ 0 \amp 1 \amp 3 \amp 2 \\ 0 \amp 0 \amp 0 \amp 0 \\ \end{array} \right]\text{.} \end{equation*}
    There are infinitely many solutions.
  5. The row equivalent reduced row echelon form is
    \begin{equation*} \left[ \begin{array}{rrr|r} 1 \amp 0 \amp 0 \amp -1 \\ 0 \amp 1 \amp 0 \amp 2 \\ 0 \amp 0 \amp 1 \amp 1 \\ \end{array} \right]\text{.} \end{equation*}
    This system has the single solution \((-1,2,1)\text{.}\)
Solution.
  1. Because the leading entry in the first row is not a \(1\text{,}\) this is not in reduced row echelon form. If we scale the first row by \(1/2\text{,}\) however, we have a matrix in reduced row echelon form.
    \begin{equation*} \left[ \begin{array}{rrr|r} 2 \amp 0 \amp 4 \amp -8 \\ 0 \amp 1 \amp 3 \amp 2 \\ \end{array} \right] \sim \left[ \begin{array}{rrr|r} 1 \amp 0 \amp 2 \amp -4 \\ 0 \amp 1 \amp 3 \amp 2 \\ \end{array} \right]\text{.} \end{equation*}
    We may write the corresponding linear system as
    \begin{equation*} \begin{alignedat}{4} x_1 \amp \amp \amp {}+{} \amp 2x_3 \amp {}={} \amp -4 \\ \amp \amp x_2 \amp {}+{} \amp 3x_3 \amp {}={} \amp 2, \\ \end{alignedat} \end{equation*}
    which may be rewritten as
    \begin{equation*} \begin{alignedat}{2} x_1 \amp {}={} -8 - 4x_3 \\ x_2 \amp {}={} 2 - 3x_3. \\ \end{alignedat} \end{equation*}
    Since \(x_3\) may take on any value, this shows that there are infinitely many solutions.
  2. This matrix is in reduced row echelon form. There is a single solution \((-1,3,1)\text{.}\)
  3. This matrix is also in reduced row echelon form. However, this are no solutions since the third equation is \(0 = 1\text{.}\)
  4. This is not in reduced row echelon form because the row of zeroes should be at the bottom of the matrix. We also need another interchange so that the leading entry in the second row is to the right of the leading entry in the first row.
    \begin{equation*} \left[ \begin{array}{rrr|r} 0 \amp 1 \amp 3 \amp 2 \\ 0 \amp 0 \amp 0 \amp 0 \\ 1 \amp 0 \amp 4 \amp 2 \\ \end{array} \right] \sim \left[ \begin{array}{rrr|r} 1 \amp 0 \amp 4 \amp 2 \\ 0 \amp 1 \amp 3 \amp 2 \\ 0 \amp 0 \amp 0 \amp 0 \\ \end{array} \right]\text{.} \end{equation*}
    Once again, there are infinitely many solutions.
  5. This is not in reduced row echelon form because the leading entry in the second and third rows are not the only nonzero elements in their columns. We can use replacement operations to remedy this
    \begin{equation*} \left[ \begin{array}{rrr|r} 1 \amp 2 \amp -1 \amp 2 \\ 0 \amp 1 \amp -2 \amp 0 \\ 0 \amp 0 \amp 1 \amp 1 \\ \end{array} \right] \sim \left[ \begin{array}{rrr|r} 1 \amp 0 \amp 0 \amp -1 \\ 0 \amp 1 \amp 0 \amp 2 \\ 0 \amp 0 \amp 1 \amp 1 \\ \end{array} \right] \end{equation*}
    and see that the system has the single solution \((-1,2,1)\text{.}\)
The examples in the Activity 2.2.4 indicate that there is a sequence of row operations that transforms any matrix into one in reduced row echelon form. Moreover, the conditions that define reduced row echelon matrices guarantee that this matrix is unique.
Once we have this reduced row echelon matrix, we may describe the set of solutions to the corresponding linear system with relative ease.

Example 2.2.7. Describing the solution space from a reduced row echelon matrix.

  1. Consider the reduced row echelon matrix
    \begin{equation*} \left[ \begin{array}{rrr|r} 1 \amp 0 \amp 2 \amp -1 \\ 0 \amp 1 \amp 1 \amp 2 \\ \end{array} \right] \end{equation*}
    and its corresponding linear system as
    \begin{equation*} \begin{alignedat}{4} x \amp \amp \amp {}+{} \amp 2z \amp {}={} \amp -1 \\ \amp \amp y \amp {}+{} \amp z \amp {}={} \amp 2. \\ \end{alignedat} \end{equation*}
    Let’s rewrite the equations as
    \begin{equation*} \begin{alignedat}{2} x \amp {}={} \amp -1 -2z\\ y \amp {}={} \amp 2-z \\ \end{alignedat}\text{.} \end{equation*}
    From this description, it is clear that we obtain a solution for any value of the variable \(z\text{.}\) For instance, if \(z=2\text{,}\) then \(x = -5\) and \(y=0\) so that \((x,y,z) = (-5,0,2)\) is a solution. Similarly, if \(z=0\text{,}\) we see that \((x,y,z) = (-1,2,0)\) is also a solution.
    Because there is no restriction on the value of \(z\text{,}\) we call it a free variable, and note that the linear system has infinitely many solutions. The variables \(x\) and \(y\) are called basic variables as they are determined once we make a choice of the free variable.
    We will call this description of the solution space, in which the basic variables are written in terms of the free variables, a parametric description of the solution space.
  2. Consider the matrix
    \begin{equation*} \left[ \begin{array}{rrr|r} 1 \amp 0 \amp 0 \amp 4 \\ 0 \amp 1 \amp 0 \amp -3 \\ 0 \amp 0 \amp 1 \amp 1 \\ 0 \amp 0 \amp 0 \amp 0 \\ \end{array} \right]\text{.} \end{equation*}
    The last equation gives
    \begin{equation*} 0x +0y+0z = 0\text{,} \end{equation*}
    which is true for any \((x,y,z)\text{.}\) We may safely ignore this equation since it does not impose a restriction on \((x,y,z)\text{.}\) We then see that there is a unique solution \((x,y,z) = (4,-3,1)\text{.}\)
  3. Consider the matrix
    \begin{equation*} \left[ \begin{array}{rrr|r} 1 \amp 0 \amp 2 \amp 0 \\ 0 \amp 1 \amp -1 \amp 0 \\ 0 \amp 0 \amp 0 \amp 1 \\ \end{array} \right]\text{.} \end{equation*}
    Beginning with the last equation, we see that
    \begin{equation*} 0x +0y+0z = 0 = 1\text{,} \end{equation*}
    which is not true for any \((x,y,z)\text{.}\) There is no solution to this particular equation and therefore no solution to the system of equations.

Subsection 2.2.4 Solving matrix equations

Recall from Chapter 1 that any linear system of equations is equivalent to a matrix equation of the form \(A \xvec = \bvec\text{.}\) The augmented matrix for this system of equations is
\begin{equation*} \left[ A \mid \bvec \right]. \end{equation*}
So Gaussian elimination can be used to find solutions to this type of matrix equation.

Example 2.2.8.

Find all solutions to each of the following equations.
  1. \(\displaystyle \left[ \begin{array}{rrr} 1 \amp 2 \amp 3 \\ 3 \amp 1 \amp 2 \\ 2 \amp 0 \amp 3 \\ \end{array} \right] \threevec{x}{y}{z} = \threevec{2}{3}{-1}\)
  2. \(\displaystyle \left[ \begin{array}{rrr} 1 \amp 2 \amp 3 \\ 3 \amp 1 \amp 2 \\ 2 \amp 0 \amp 3 \\ 2 \amp -1 \amp 1 \\ \end{array} \right] \threevec{x}{y}{z} = \threevec{2}{3}{-1}{-1}\)
  3. \(\displaystyle \left[ \begin{array}{rrr} 1 \amp 2 \amp 3 \\ 3 \amp 1 \amp 2 \\ 2 \amp 0 \amp 3 \\ 2 \amp -1 \amp 1 \\ \end{array} \right] \threevec{x}{y}{z} = \threevec{2}{3}{1}\)
  4. \(\displaystyle \left[ \begin{array}{rrr} 1 \amp 2 \amp 3 \\ 3 \amp 1 \amp 2 \\ \end{array} \right] \threevec{x}{y}{z} = \twovec{2}{3}\)
Answer.
  1. \((x, y, z) = (1, 2, -1)\text{.}\)
  2. \((x, y, z) = (1, 2, -1)\text{.}\)
  3. No solutions.
  4. Infinitely many solutions: \((x, y) = ( \frac15 (4 - z), \frac15 (3 - 7z) )\text{.}\) Notice that when \(z = -1\text{,}\) we get \((x, y ,z) = (1, 2, -1)\) just as we saw above.

Subsection 2.2.5 Summary

We saw several important concepts in this chapter.
  • We can describe the solution space to a linear system by transforming it into a new linear system having the same solution space through a sequence of scaling, interchange, and replacement operations.
  • We can represent a linear system by an augmented matrix. Using scaling, interchange, and replacement operations, the augmented matrix is row equivalent to exactly one reduced row echelon matrix. The process of constructing this reduced row echelon matrix is called Gaussian elimination.
  • The reduced row echelon matrix allows us to easily describe the solution space of a linear system.

Exercises 2.2.6 Exercises

1.

For each of the linear systems below, write the associated augmented matrix and find the reduced row echelon matrix that is row equivalent to it. Identify the basic and free variables and then describe the solution space of the original linear system using a parametric description, if appropriate.
  1. \begin{equation*} \begin{alignedat}{3} 2x \amp {}+{} \amp y \amp {}={} \amp 0 \\ x \amp {}+{} \amp 2y \amp {}={} \amp 3 \\ -2x \amp {}+{} \amp 2y \amp {}={} \amp 6 \\ \end{alignedat} \end{equation*}
  2. \begin{equation*} \begin{alignedat}{5} -x_1 \amp {}+{} \amp 2x_2 \amp \amp \amp {}+{} \amp x_3 \amp {}={} \amp 2 \\ 3x_1 \amp \amp \amp \amp \amp {}+{} \amp 2x_3 \amp {}={} \amp -1 \\ -x_1 \amp {}-{} \amp x_2 \amp \amp \amp {}+{} \amp x_3 \amp {}={} \amp 2 \\ \end{alignedat} \end{equation*}
  3. \begin{equation*} \begin{alignedat}{5} x_1 \amp {}+{} \amp 2x_2 \amp {}-{} \amp 5x_3 \amp {}-{} \amp x_4 \amp {}={} \amp -3 \\ -2x_1 \amp {}-{} \amp 2x_2 \amp {}+{} \amp 6x_3 \amp {}-{} \amp 2x_4 \amp {}={} \amp 4 \\ x_1 \amp \amp \amp {}-{} \amp x_3 \amp {}+{} \amp 9x_4 \amp {}={} \amp -7 \\ \amp \amp -x_2 \amp {}+{} \amp 2x_3 \amp {}-{} \amp x_4 \amp {}={} \amp 4 \\ \end{alignedat} \end{equation*}

2.

Consider each matrix below and determine if it is in reduced row echelon form. If not, indicate the reason and apply a sequence of row operations to find its reduced row echelon matrix. For each matrix, indicate whether the corresponding linear system has infinitely many solutions, exactly one solution, or no solutions.
  1. \begin{equation*} \left[ \begin{array}{rrrr|r} 1 \amp 1 \amp 0 \amp 3 \amp 3 \\ 0 \amp 1 \amp 0 \amp -2 \amp 1 \\ 0 \amp 0 \amp 1 \amp 3 \amp 4 \\ \end{array} \right] \end{equation*}
  2. \begin{equation*} \left[ \begin{array}{rrrr|r} 1 \amp 0 \amp 0 \amp 0 \amp 0 \\ 0 \amp 2 \amp 0 \amp 0 \amp 0 \\ 0 \amp 0 \amp -3 \amp 0 \amp 0 \\ 0 \amp 0 \amp 0 \amp 1 \amp 0 \\ 0 \amp 0 \amp 0 \amp 0 \amp 1 \\ \end{array} \right] \end{equation*}
  3. \begin{equation*} \left[ \begin{array}{rrrr|r} 1 \amp 0 \amp 0 \amp 3 \amp 3 \\ 0 \amp 1 \amp 0 \amp -2 \amp 1 \\ 0 \amp 0 \amp 1 \amp 3 \amp 4 \\ 0 \amp 0 \amp 0 \amp 3 \amp 3 \\ \end{array} \right] \end{equation*}
  4. \begin{equation*} \left[ \begin{array}{rrrr|r} 0 \amp 0 \amp 1 \amp 0 \amp -1 \\ 0 \amp 1 \amp 0 \amp 0 \amp 3 \\ 1 \amp 1 \amp 1 \amp 1 \amp 2 \\ \end{array} \right] \end{equation*}

3.

Give an example of a reduced row echelon matrix that describes a linear system having the stated properties. If it is not possible to find such an example, explain why not.
  1. Write a reduced row echelon matrix for a linear system having five equations and three variables and having exactly one solution.
  2. Write a reduced row echelon matrix for a linear system having three equations and three variables and having no solution.
  3. Write a reduced row echelon matrix for a linear system having three equations and five variables and having infinitely many solutions.
  4. Write a reduced row echelon matrix for a linear system having three equations and four variables and having exactly one solution.
  5. Write a reduced row echelon matrix for a linear system having four equations and four variables and having exactly one solution.

4.

For any given matrix, Theorem 2.2.6 tells us that there is a reduced row echelon matrix that is row equivalent to it. This exercise demonstrates why this is the case. Each of the following matrices satisfies three of the four conditions required of a reduced row echelon matrix as prescribed by Definition 2.2.5. For each, indicate how a sequence of row operations can be applied to form a row equivalent reduced row echelon matrix.
  1. \begin{equation*} \begin{bmatrix} 1 \amp 0 \amp 2 \amp 3 \\ 0 \amp 0 \amp 0 \amp 0 \\ 0 \amp 1 \amp -2 \amp 1 \\ \end{bmatrix} \end{equation*}
  2. \begin{equation*} \begin{bmatrix} 1 \amp 0 \amp 0 \amp 2 \\ 0 \amp -2 \amp 0 \amp -4 \\ 0 \amp 0 \amp 1 \amp 1 \\ \end{bmatrix} \end{equation*}
  3. \begin{equation*} \begin{bmatrix} 0 \amp 1 \amp 0 \amp -2 \\ 0 \amp 0 \amp 1 \amp 4 \\ 1 \amp 0 \amp 0 \amp 3 \\ 0 \amp 0 \amp 0 \amp 0 \\ 0 \amp 0 \amp 0 \amp 0 \\ \end{bmatrix} \end{equation*}
  4. \begin{equation*} \begin{bmatrix} 1 \amp 0 \amp 2 \amp 3 \\ 0 \amp 1 \amp 3 \amp 0 \\ 0 \amp 0 \amp 1 \amp -1 \\ 0 \amp 0 \amp 0 \amp 0 \\ \end{bmatrix} \end{equation*}

5.

For each of the questions below, provide a justification for your response.
  1. What does the presence of a row whose entries are all zero in an augmented matrix tell us about the solution space of the linear system?
  2. How can you determine if a linear system has no solutions directly from its reduced row echelon matrix?
  3. How can you determine if a linear system has infinitely many solutions directly from its reduced row echelon matrix?
  4. What can you say the solution space of a linear system if there are more variables than equations and at least one solution exists?

6.

Determine whether the following statements are true or false and explain your reasoning.
  1. If every variable is basic, then the linear system has exactly one solution.
  2. If two augmented matrices are row equivalent to one another, then they describe two linear systems having the same solution spaces.
  3. The presence of a free variable indicates that there are no solutions to the linear system.
  4. If a linear system has exactly one solution, then it must have the same number of equations as variables.
  5. If a linear system has the same number of equations as variables, then it has exactly one solution.

7.

Determine whether the following statements are true or false and provide a justification for your response.
  1. Given two vectors \(\vvec\) and \(\wvec\text{,}\) the vector \(2\vvec\) is a linear combination of \(\vvec\) and \(\wvec\text{.}\)
  2. Suppose \(\vvec_1,\vvec_2,\ldots,\vvec_n\) is a collection of \(m\)-dimensional vectors and that the matrix \(\left[\begin{array}{rrrr} \vvec_1 \amp \vvec_2 \amp \ldots \amp \vvec_n \end{array}\right]\) has a pivot position in every row. If \(\bvec\) is any \(m\)-dimensional vector, then \(\bvec\) can be written as a linear combination of \(\vvec_1,\vvec_2,\ldots,\vvec_n\text{.}\)
  3. Suppose \(\vvec_1,\vvec_2,\ldots,\vvec_n\) is a collection of \(m\)-dimensional vectors and that the matrix \(\left[\begin{array}{rrrr} \vvec_1 \amp \vvec_2 \amp \ldots \amp \vvec_n \end{array}\right]\) has a pivot position in every row and every column. If \(\bvec\) is any \(m\)-dimensional vector, then \(\bvec\) can be written as a linear combination of \(\vvec_1,\vvec_2,\ldots,\vvec_n\) in exactly one way.
  4. It is possible to find two 3-dimensional vectors \(\vvec_1\) and \(\vvec_2\) such that every 3-dimensional vector can be written as a linear combination of \(\vvec_1\) and \(\vvec_2\text{.}\)

8.

Identify each statement as true or false and explain your reasoning.
  • A linear system with 4 equations in 6 unknowns can have exactly 7 solutions.
  • A linear system that has a free variable has an infinite number of solutions.
  • Every consistent linear system has a free variable.
  • If the RREF of for a consistent linear system has 2 zero rows, there will be an infinite number of solutions.
  • If the RREF of has no zero rows, the linear system \(A \xvec = \bvec\) is consistent.
<Prev^TopNext>