Skip to main content
Logo image

Understanding Linear Algebra

David Austin

Section 1.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 1.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 1.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:
    x=2y=−1.
  2. Give a description of the solution space to the linear system:
    −x+2y−z=−33y+z=−12z=4.
  3. Give a description of the solution space to the linear system:
    x+3y=−12x+y=3.
  4. Describe the solution space to the linear equation 0x=0.
  5. Describe the solution space to the linear equation 0x=5.
🔗
These examples lead to a few observations that motivate a general approach to finding solutions of linear systems.
🔗

Observation 1.2.1.

First, finding the solution space to some systems is simple. For example, because each equation in the following system
🔗
x=−4y=2.
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). We call such a system decoupled.
🔗
🔗
🔗

Observation 1.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
🔗
x+2y−2z=−4−y+z=33z=3.
Multiplying both sides of the last equation by 1/3 gives us
🔗
x+2y−2z=−4−y+z=3z=1.
Any solution to this linear system must then have z=1.
🔗
🔗
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:
🔗
x+2y=−2−y=2.
The second equation, after multiplying both sides by −1, tells us that y=−2. We can then substitute this value into the first equation to determine that x=2.
🔗
🔗
In this way, we arrive at a decoupled system, which shows that there is exactly one solution, namely (x,y,z)=(2,−2,1).
🔗
Our original system,
🔗
x+2y−2z=−4−y+z=33z=3,
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 1.2.3.

We can use substitution in a more general way to solve linear systems. For example, a natural approach to the system
🔗
x+2y=12x+3y=3.
is to use the first equation to express x in terms of y:
🔗
x=1−2y
and then substitute this into the second equation and simplify:
🔗
2x+3y=32(1−2y)+3y=32−4y+3y=3−y=1y=−1
From here, we can substitute y=−1 into the first equation to arrive at the solution (x,y)=(3,−1).
🔗
🔗
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
🔗
−2(equation 1)+equation 2
to obtain
−2(x+2y=1)+2x+3y=3
🔗
which gives us
🔗
−2x−4y=−2+2x+3y=3−y=1.
🔗
🔗
🔗
In this way, the system
🔗
x+2y=12x+3y=3
is transformed into the new triangular system
🔗
x+2y=1−y=1.
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. 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
We can multiply one equation by a nonzero number. For instance,
🔗
2x−4y=6
has the same set of solutions as
🔗
12(2x−4y=6)
or
🔗
x−2y=3.
🔗
Interchange
Interchanging equations will not change the set of solutions. For instance,
🔗
2x+4y=1x−3y=0
has the same set of solutions as
🔗
x−3y=02x+4y=1.
🔗
Replacement
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 1.2.4.

Let’s illustrate the use of these operations to find the solution space to the system of equations:
🔗
x+2y=42x+y−3z=11−3x−2y+z=−10
🔗
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.
🔗
x+2y=4−3y−3z=3−3x−2y+z=−10
🔗
🔗
Another replacement operation eliminates x from the third equation. We multiply the first equation by 3 and add to the third.
🔗
x+2y=4−3y−3z=34y+z=2
🔗
🔗
Scale the second equation by multiplying it by −1/3.
🔗
x+2y=4y+z=−14y+z=2
🔗
🔗
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.
🔗
x+2y=4y+z=−1−3z=6
🔗
🔗
After scaling the third equation by −1/3, we have found the value for z.
🔗
x+2y=4y+z=−1z=−2
🔗
🔗
We eliminate z from the second equation by multiplying the third equation by -1 and adding to the second.
🔗
x+2y=4y=1z=−2
🔗
🔗
Finally, multiply the second equation by -2 and add to the first to obtain:
🔗
x=2y=1z=−2.
🔗
🔗
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).
🔗
🔗
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 1.2.2. Gaussian Elimination.

For each of the following linear systems, use Gaussian elimination to describe the solutions to the following systems of linear equations. In particular, determine whether each linear system has exactly one solution, infinitely many solutions, or no solutions.
🔗
  1. x+y+2z=12x−y−2z=2−x+y+z=0
  2. −x−2y+2z=−12x+4y−z=5x+2y=3
  3. −x−2y+2z=−12x+4y−z=5x+2y=2
🔗
🔗
🔗

Subsection 1.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 forgetting about the variables and recording the numerical data in a rectangular array. For instance, the system of equations below has the following augmented matrix
−x−2y+2z=−12x+4y−z=5x+2y=3
🔗
[−1−22−124−151203].
🔗
🔗
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
🔗
[−1−2224−1120].
🔗
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:
[−1−22−124−151203]∼[−1−22−100331203].
🔗
🔗
The symbol ∼ 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 1.2.3. Augmented matrices and solution spaces.

  1. Write the augmented matrix for the linear system
    x+2y−z=13x+2y+2z=7−x+4z=−3
    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
    [103010000].
    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
    [103010001].
    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.
    [∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗].
    1. How many equations are there in this system and how many variables?
    2. Based on our earlier discussion in Section 1.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
      [1200320012−1−1000000].
      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?
🔗
🔗
🔗

Subsection 1.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.
🔗
[1∗0∗0∗001∗0∗00001∗000000000000].
🔗

Definition 1.2.5.

We say that a matrix is in reduced row echelon form 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 1.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. [204−80132].
  2. [100−101030011].
  3. [104201320001].
  4. [013200001042].
  5. [12−1201−200011].
🔗
🔗
The examples in the previous activity 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 1.2.7. Describing the solution space from a reduced row echelon matrix.

  1. Consider the reduced row echelon matrix
    [102−10112]
    and its corresponding linear system as
    x+2z=−1y+z=2.
    Let’s rewrite the equations as
    x=−1−2zy=2−z.
    From this description, it is clear that we obtain a solution for any value of the variable z. For instance, if z=2, then x=−5 and y=0 so that (x,y,z)=(−5,0,2) is a solution. Similarly, if z=0, we see that (x,y,z)=(−1,2,0) is also a solution.
    Because there is no restriction on the value of z, 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
    [1004010−300110000].
    The last equation gives
    0x+0y+0z=0,
    which is true for any (x,y,z). We may safely ignore this equation since it does not impose a restriction on (x,y,z). We then see that there is a unique solution (x,y,z)=(4,−3,1).
  3. Consider the matrix
    [102001−100001].
    Beginning with the last equation, we see that
    0x+0y+0z=0=1,
    which is not true for any (x,y,z). There is no solution to this particular equation and therefore no solution to the system of equations.
🔗
🔗
🔗

Subsection 1.2.4 Summary

We saw several important concepts in this section.
🔗
  • 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 1.2.5 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. 2x+y=0x+2y=3−2x+2y=6
  2. −x1+2x2+x3=23x1+2x3=−1−x1−x2+x3=2
  3. x1+2x2−5x3−x4=−3−2x1−2x2+6x3−2x4=4x1−x3+9x4=−7−x2+2x3−x4=4
🔗
🔗

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. [11033010−2100134]
  2. [100000200000−3000001000001]
  3. [10033010−210013400033]
  4. [0010−10100311112]
🔗
🔗

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 1.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 1.2.5. For each, indicate how a sequence of row operations can be applied to form a row equivalent reduced row echelon matrix.
🔗
  1. [1023000001−21]
  2. [10020−20−40011]
  3. [010−20014100300000000]
  4. [10230130001−10000]
🔗
🔗

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 about 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.
🔗
🔗
You have attempted 1 of 1 activities on this page.
🔗
PrevTopNext