Skip to main content

Linear Algebra Gathering and Sharpening Tools

Ryan Higginbottom

Section 1.3 Solving Linear Systems With Matrices

In the previous section, we learned how to write the augmented matrix of a linear system and Algorithm 1.2.13 provided a process to reduce any matrix to RREF. In this section, we will learn how to use the RREF of a matrix to solve the corresponding linear system. We will also prove some important results related to these solutions.
🔗
We first introduce some terminology. These terms relate what we saw in Definition 1.2.12 back to the corresponding linear systems.
🔗

Definition 1.3.1.

Suppose that \(A\) is the coefficient matrix corresponding to a system of linear equations and that \(A\) is in REF. Then a variable corresponding to a pivot column in \(A\) is called a basic variable (or pivot variable), and a variable corresponding to a non-pivot column in \(A\) is called a free variable.
🔗
🔗

Note 1.3.2.

Note that in this definition \(A\) is the coefficient matrix (not the augmented matrix) of the linear system. We are using the coefficient matrix because we are making a definition concerning variables, and the rightmost column in the augmented matrix does not correspond to a variable in the linear system.
🔗
🔗
The augmented matrix of an \(m\times n\) linear system is of size \(m\times (n+1)\text{.}\) This puts some limitations on the different reduced row-echelon forms that we could see in this context. In the following two examples, we will consider specific reduced row-echelon forms and what they say about the linear systems to which they correspond.
🔗

Example 1.3.3.

Consider the following as the augmented matrix corresponding to a system of linear equations:
\begin{equation*} A = \left[\begin{array}{@{}ccc|c@{}} 1 \amp 0 \amp 3 \amp 0 \\ 0 \amp 1 \amp 2 \amp 0 \\ 0 \amp 0 \amp 0 \amp 1 \end{array}\right]\text{.} \end{equation*}
This is a \(3\times 4\) matrix, so the original linear system has three equations and three variables. Hopefully the reader can see that this matrix is indeed in RREF. (Consult Definition 1.2.9 for a refresher.)
🔗
We will now write the equations which correspond to each row of the matrix, and we will pay special attention to the final row:
\begin{align*} x_1 + 0x_2+3x_3 \amp =0\\ 0x_1+x_2 + 2x_3 \amp =0\\ 0x_1+0x_2+0x_3 \amp =1\text{.} \end{align*}
Usually we omit terms in linear equations when the coefficient is \(0\text{,}\) but we are including those terms here to make a point. When the coefficient of a variable is \(0\text{,}\) the entire linear term disappears since no value of the variable could make the product with the coefficient anything other than \(0\text{.}\) This means that each of these equations can be written in a more simple form. In particular, the third equation can be written as \(0=1\text{.}\)
🔗
This may feel rather elementary, but there are no possible variable values to make \(0=1\) a true statement. It is false all of the time. Since we are searching for values of the variables which satisfy all the equations simultaneously, and since one of the equations has no solution, the linear system has no solution. This is an inconsistent linear system.
🔗
We proved in Theorem 1.2.7 that row-equivalent matrices correspond to equivalent linear systems. Therefore, we can say that the original linear system for this example is inconsistent.
🔗
🔗
What we saw in Example 1.3.3 we will be able to generalize (see Theorem 1.3.5) in our effort to categorize inconsistent linear systems. Before we do that, let’s look at an augmented matrix which has a different RREF.
🔗

Example 1.3.4.

Consider the following matrix as the augmented matrix of a linear system:
\begin{equation*} A = \left[\begin{array}{@{}ccc|c@{}} 1 \amp 0 \amp -3 \amp 5 \\ 0 \amp 1 \amp 2 \amp 7 \\ 0 \amp 0 \amp 0 \amp 0 \\ \end{array}\right]\text{.} \end{equation*}
(Again, the reader should verify that this matrix is in reduced row-echelon form.)
🔗
The final row of this matrix corresponds to the equation \(0=0\text{.}\) Since this equation is true all the time, for all values of the involved variables, we won’t consider it any longer as it places no further restrictions on the solutions.
🔗
The first two rows of \(A\) correspond to the following two linear equations:
\begin{align*} x_1 - 3x_3 \amp =5\\ x_2 + 2x_3 \amp =7\text{.} \end{align*}
🔗
From Definition 1.3.1, we see that in this system \(x_1\) and \(x_2\) are basic variables and \(x_3\) is a free variable. What does that mean for the solutions of this system? We call \(x_3\) “free” because any element of \(\rr\) that we put into \(x_3\) will produce a solution for this system. The variable \(x_3\) is “free” to take on any value, and then the values of the basic variables \(x_1\) and \(x_2\) are determined by that value and the linear equations.
🔗
For example, in this system of equations, if \(x_3=2\text{,}\) then \(x_1=11\) and \(x_2=3\text{,}\) giving \((11,3,2)\) as a solution to the linear system. If \(x_3=-1\text{,}\) then \(x_1=2\) and \(x_2=9\text{,}\) giving \((2,9,-1)\) as a solution to the system. Since \(x_3\) can take on any value in \(\rr\text{,}\) and since we have a solution to the system for each value of \(x_3\text{,}\) this means we have a solution to the system for each element of \(\rr\text{.}\) We conclude that there are an infinite number of solutions to this system.
🔗
The solutions to this linear system can be written in a number of ways. We will prefer the following form:
\begin{equation*} \left\{ \begin{array}{l} x_1 = 5 + 3x_3 \\ x_2 = 7-2x_3 \\ x_3 \text{ is free.} \end{array} \right. \end{equation*}
This is called a parametric description of the solution set. Sometimes solutions like this are written with the letter \(t\) or \(s\) in place of \(x_3\) to better match the usage of the word “parameter” elsewhere. We will follow the convention of using the free variables as parameters in our solutions.
🔗
🔗
In Example 1.3.4, we saw that having a free variable corresponded to having an infinite number of solutions. But we need to be careful about our conclusions, because there was also a free variable (\(x_3\)) in Example 1.3.3, and in that case there were no solutions to the system. A free variable only indicates an infinite number of solutions when the system is consistent.
🔗
The two previous examples, combined with Example 1.2.5, give us a sense of what solutions to linear systems can look like given certain characteristics of the associated augmented matrices. We can now state in theorem form what we observed to be true in these examples.
🔗

Proof.

We note that the pivot columns do not change when a matrix goes from row-echelon form to reduced row-echelon form (see Algorithm 1.2.13), so we are not losing any generality with our assumption that \(A\) is in RREF.
🔗
This theorem is a biconditional statement, and we will prove one implication directly. We assume there is no pivot in the final column of \(A\text{.}\) Then when we consider the linear equations which correspond to the rows of \(A\text{,}\) we see that each of the basic variables can be written in terms of the free variables, if any free variables exist. If no free variables exist, then all basic variables have an assigned value and the system is consistent. In the case that there is at least one free variable, we can pick an element of \(\rr\)—let’s say, \(0\)—to assign to each of the free variables. This produces a solution to the linear system, and our system is consistent.
🔗
We will prove the contrapositive of the other implication. If there is a pivot in the final column of \(A\text{,}\) then the corresponding linear equation reduces to \(0=1\text{.}\) This means that there is no solution to the linear system, so the system is inconsistent.
🔗
🔗
Given that two major questions about the solutions to linear systems involve consistency and uniqueness, the next natural theorem to consider is related to this second concept.
🔗

Proof.

As with the proof of Theorem 1.3.5, we are not losing any generality by assuming that \(A\) is in RREF.
🔗
We first suppose that there is a pivot in each of the first \(n\) columns of \(A\text{;}\) this implies that \(m \ge n\text{.}\) We also recall that the linear system is assumed to be consistent, meaning that the first \(n\) rows of \(A\) have the following form:
\begin{equation*} \left[\begin{array}{@{}cccc|c@{}} 1 \amp 0 \amp \cdots \amp 0 \amp b_1 \\ 0 \amp 1 \amp \cdots \amp 0 \amp b_2 \\ \vdots \amp \vdots \amp \ddots \amp \vdots \amp \vdots \\ 0 \amp 0 \amp \cdots \amp 1 \amp b_n \end{array}\right]\text{.} \end{equation*}
(The matrix \(A\) may have rows of all zeros below the \(n\) rows here, but that will not affect our discussion.)
🔗
If the matrix \(A\) has the form we have just detailed, then the original linear system is equivalent to one with equations of the form \(x_1=b_1\text{,}\) \(x_2=b_2\text{,}\) \(\ldots\text{,}\) \(x_n=b_n\text{.}\) That is, the system has a unique solution.
🔗
We will prove the contrapositive of the other implication. We suppose that there is at least one free variable (call it \(x_j\)) in the linear system. We recall (see Example 1.3.4) that when the matrix for a consistent system is in RREF, all solutions can be written by expressing basic variables in terms of any existing free variables. Therefore, this system has a solution in which all free variables are set equal to \(0\text{.}\) Further, this system has a solution in which all free variables except \(x_j\) are set equal to \(0\) and \(x_j=1\text{.}\) This may not change the value of any of the basic variables, and there may not be any free variables aside from \(x_j\text{,}\) but these two solutions we have just described are not the same since \(x_j\) has a different value in each one. Therefore, this system has more than one solution, meaning that the system does not have a unique solution.
🔗
🔗

Proof.

Suppose \(A\) is the augmented matrix corresponding to an \(m\times n\) linear system with \(m < n\text{.}\) The RREF of \(A\) can have at most \(m\) pivots, so by Theorem 1.3.6 the system cannot have a unique solution.
🔗
🔗
The two previous theorems provide the last step to an algorithm for solving any linear system.
🔗
The earlier examples in this section can be completed using this algorithm. We will include an additional example so the reader can practice using the algorithm once more.
🔗

Example 1.3.9.

Consider the following linear system:
\begin{align*} -7x - 4y + 7z \amp = -3\\ -2x + 2y - 4z \amp = 2\\ 5x + 4y + z \amp = 5\text{.} \end{align*}
Does this system have a solution? If the system has a solution, write down the solution.
🔗
Solution.
We follow Algorithm 1.3.8 and form the augmented matrix \(A\) for this system. When we row reduce this matrix, we find
\begin{equation*} A = \left[\begin{array}{@{}ccc|c@{}} -7 \amp -4 \amp 7 \amp -3 \\ -2 \amp 2 \amp -4 \amp 2 \\ 5 \amp 4 \amp 1 \amp 5 \end{array}\right] \sim \left[\begin{array}{@{}ccc|c@{}} 1 \amp 0 \amp 0 \amp -1/9 \\ 0 \amp 1 \amp 0 \amp 4/3 \\ 0 \amp 0 \amp 1 \amp 2/9 \end{array}\right]\text{.} \end{equation*}
We will refer to the RREF of \(A\) as \(B\text{.}\) Since \(B\) has no pivot in the rightmost column, our linear system is consistent. Secondly, since \(B\) has a pivot in each of the first three columns, the solution to our linear system is unique. We record this solution as \(x = -1/9\text{,}\) \(y = 4/3\text{,}\) and \(z = 2/9\text{.}\)
🔗
🔗
🔗
The rest of this section will be devoted to proving Theorem 1.3.13, which states that the RREF of a matrix is unique. (There are actually a couple of places so far in this section where we have been a bit sloppy and referred to the RREF of a matrix, but in each of these cases the uniqueness of the RREF was not essential to the argument.)
🔗
We will begin with a lemma. (Our approach to proving Theorem 1.3.13 has been heavily influenced by Kuttler’s treatment
 2 
math.libretexts.org/Bookshelves/Linear_Algebra/A_First_Course_in_Linear_Algebra_(Kuttler)/
.)
🔗

Proof.

The first sentence in this lemma has essentially been proved in the discussion within Example 1.3.4. We will prove the second statement directly. We consider \(A\) as the augmented matrix of a consistent \(m\times n\) linear system. Suppose \(A\) is row equivalent to \(B\text{,}\) where \(B\) is in RREF. We recall that part of the definition of RREF (Definition 1.2.9) is that pivots are the leftmost non-zero number in their row.
🔗
We consider the linear equation corresponding to row \(d\) of \(B\text{;}\) this equation will begin with a basic variable \(x_i\) and will possibly involve other variables \(x_j\text{,}\) with \(j > i\text{,}\) before the equals sign. However, all of these other variables \(x_j\) will be free variables, because any other basic variable \(x_k\text{,}\) with \(k > i\text{,}\) will correspond to a column in which that pivot is the only non-zero number. In other words, all entries \(b_{dk}\) along row \(d\) in \(B\) which correspond to pivot columns \(k\text{,}\) for \(k > i\text{,}\) will be zero.
🔗
🔗
The basic idea for the proof of Theorem 1.3.13 is to prove the result for homogeneous linear systems first and then to obtain the proof for general linear systems as an extension. We turn to our first result about homogeneous linear systems. (For a refresher on homogeneous systems, see Definition 1.1.5.)
🔗

Proof.

We will prove this directly. Suppose that \(x_i\) is a basic variable of a homogeneous linear system and that in a solution of this system, \(x_j=0\) for all free variables \(x_j\) with \(j > i\text{.}\) From Lemma 1.3.10 we know that in the description of the solution to this system, \(x_j\) will be written as a linear function of the free variables with larger indices. But the nature of a homogeneous linear system demands that such a linear function will involve only free variables and no constants (the constants are all \(0\)). Therefore, if \(x_j=0\) for all free variables \(x_j\) with \(j > i\text{,}\) we must have \(x_i=0\) as well.
🔗
🔗
We will now prove the uniqueness result for augmented matrices of homogeneous systems. (We should note here, perhaps, that while we introduced the notions of REF and RREF for augmented matrices, the row reduction algorithm can be applied to any matrix at all.)
🔗

Proof.

We proceed by contradiction and assume that \(B \neq C\text{.}\) Since \(B\) and \(C\) are row equivalent and both are in RREF, they must have the same pivot positions. (The reader is asked to prove this in Exercise 1.3.15.) Since \(B \neq C\text{,}\) these matrices must differ in some row, call it row \(k\text{.}\) Since \(B\) and \(C\) have the same pivot positions, we assume there is a pivot in column \(i\) of row \(k\) in both matrices. There must be some position \(j\text{,}\) with \(j > i\text{,}\) such that \(b_{kj} \neq c_{kj}\text{.}\) The variable \(x_j\) must not be a basic variable in the linear system, because if so, we would have \(b_{kj} = c_{kj} = 0\text{.}\) So \(x_j\) is a free variable.
🔗
Homogeneous linear systems are always consistent. (The reader is asked to prove this in Exercise 1.3.10.) There must exist a solution to the linear system where \(x_j=1\) and all other free variables take on the value of \(0\text{.}\) In this solution, using the linear equations that correspond to the rows in \(B\text{,}\) we solve and obtain \(x_i=-b_{kj}\text{.}\) Using the linear equations that correspond to the rows in \(C\text{,}\) we find \(x_i=-c_{kj}\text{.}\) Since a solution is completely determined by the values of the free variables, this implies that \(b_{kj} = c_{kj}\text{,}\) which is a contradiction.
🔗
🔗
With this proposition in hand, we can state and prove our first large result.
🔗

Proof.

We first form the matrix \(A'\) by augmenting the matrix \(A\) with an additional column on the right consisting of all zeros. We similarly form the matrices \(B'\) and \(C'\) from \(B\) and \(C\text{.}\) We note that \(B'\) and \(C'\) are also in RREF and they are obtained from \(A'\) using the same row operations that reduced \(A\) to \(B\) and \(C\text{.}\)
🔗
We can consider \(A'\text{,}\) \(B'\text{,}\) and \(C'\) as augmented matrices corresponding to \(m\times n\) homogeneous linear systems. By Proposition 1.3.12, since \(A'\) is row equivalent to both \(B'\) and \(C'\text{,}\) where both \(B'\) and \(C'\) are in RREF, we must have \(B'=C'\text{.}\) By the construction of \(B'\) and \(C'\text{,}\) this implies \(B=C\text{.}\)
🔗
🔗

Reading Questions Reading Questions

1.

Consider the following linear system:
\begin{align*} 4x_1 + 7x_2 + 17x_3 \amp = 23\\ -3x_1 - 5x_2 - 12x_3 \amp = -17\text{.} \end{align*}
Determine which of the variables are basic variables and which are free variables. Explain your answer.
🔗
🔗

2.

Consider the following linear system:
\begin{align*} x_1 - 2x_2 + 2x_3 \amp = -1\\ -x_1 + 2x_2 - x_3 \amp = -1\\ 3x_1 - 6x_2 + 7x_3 \amp = -5\text{.} \end{align*}
Write a parametric description of the solution set of this system. (Follow Example 1.3.4.)
🔗
🔗
🔗

Exercises Exercises

1.

In each of the following, suppose the augmented matrix for a linear system has been reduced to the following RREF. Write down the solution(s) to the system (if they exist).
  1. \(\displaystyle \left[\begin{array}{@{}ccc|c@{}} 1 \amp 0 \amp 0 \amp -4 \\ 0 \amp 1 \amp 0 \amp 5 \\ 0 \amp 0 \amp 1 \amp 0 \end{array}\right]\)
    🔗
    🔗
  2. \(\displaystyle \left[\begin{array}{@{}ccc|c@{}} 1 \amp -2 \amp 0 \amp 2 \\ 0 \amp 0 \amp 1 \amp -3 \\ 0 \amp 0 \amp 0 \amp 0 \end{array}\right]\)
    🔗
    🔗
  3. \(\displaystyle \left[\begin{array}{@{}ccc|c@{}} 1 \amp 0 \amp -3 \amp 0 \\ 0 \amp 1 \amp 5 \amp 0 \\ 0 \amp 0 \amp 0 \amp 1 \end{array}\right]\)
    🔗
    🔗
  4. \(\displaystyle \left[\begin{array}{@{}ccccc|c@{}} 1 \amp 0 \amp 2 \amp -4 \amp 0 \amp 7 \\ 0 \amp 1 \amp 9 \amp -1 \amp 0 \amp -4 \\ 0 \amp 0 \amp 0 \amp 0 \amp 1 \amp 4 \end{array}\right]\)
    🔗
    🔗
🔗
Answer.
  1. The only solution is \((-4,5,0)\text{.}\)
    🔗
    🔗
  2. The solutions can be written parametrically as
    \begin{equation*} \begin{cases} x_1 = 2x_2 + 2 \\ x_2 \text{ is free} \\ x_3 = -3. \end{cases} \end{equation*}
    🔗
    🔗
  3. There are no solutions.
    🔗
    🔗
  4. The solutions can be written parametrically as
    \begin{equation*} \begin{cases} x_1 = -2x_3 + 4x_4 + 7 \\ x_2 = -9x_3 + x_4 - 4 \\ x_3 \text{ is free} \\ x_4 \text{ is free} \\ x_5 = 4. \end{cases} \end{equation*}
    🔗
    🔗
🔗
🔗
🔗

2.

Solve the following linear system.
\begin{align*} 2x - 3y + 5z \amp = 0\\ -x + 2y -3z \amp = 0\\ x + 4y - 4z \amp = 0 \end{align*}
🔗
🔗

3.

Solve the following linear systems.
  1. \begin{align*} x - 2y + 3z \amp = 4\\ 5x - 6y + 7z \amp = 5 \end{align*}
    🔗
    🔗
  2. \begin{align*} x - 2y + 2z - w \amp = 1\\ 3x - 7y - z + 5w \amp =2 \end{align*}
    🔗
    🔗
  3. \begin{align*} 2x-y+z \amp = 3\\ -x+3y+2z \amp = 1\\ 3x+y+4z \amp = 7 \end{align*}
    🔗
    🔗
  4. \begin{align*} 4x - 2y \amp = -4\\ 2x+5y+6z \amp = 2\\ 3x-y + \tfrac{1}{2}z \amp = 0 \end{align*}
    🔗
    🔗
🔗
🔗

4.

Determine the values of \(a\) for which the following linear system has no solutions, exactly one solution, or infinitely many solutions. Explain your answers.
\begin{align*} x + 2y + 2z \amp = -4\\ 2x - 2y + 4z \amp = 7\\ x + 2y - (a^2-5)z \amp = a+1 \end{align*}
🔗
🔗

5.

Under what conditions is the following linear system consistent? Your answer should be an equation or equations that must be satisfied by the \(b_i\text{.}\) Explain your answer.
\begin{align*} x + 2y \amp = b_1\\ -2x -5y + 3z \amp = b_2\\ x + 4y - 6z \amp = b_3 \end{align*}
🔗
Answer.
This system is consistent if and only if \(3b_1 + 2b_2 + b_3 = 0\text{.}\)
🔗
🔗
🔗

6.

Solve the following system for \(x\text{,}\) \(y\text{,}\) and \(z\text{.}\) (Hint: define new variables to produce a linear system.) Explain your solution.
\begin{align*} -\frac{1}{x} + \frac{2}{y} - \frac{4}{z} \amp = 2\\ -\frac{2}{x} + \frac{2}{y} - \frac{4}{z} \amp = 6\\ -\frac{3}{x} + \frac{4}{y} + \frac{4}{z} \amp = -4 \end{align*}
🔗
🔗

7.

Answer the question posed in Exercise 1.1.1 by solving the linear system that was created in that exercise.
🔗
🔗

8.

Answer the question posed in Exercise 1.1.2 by solving the linear system that was created in that exercise.
🔗
Answer.
The function is \(f(x) = \tfrac{1}{2}x^2 - 3x + \tfrac{5}{2}\text{.}\)
🔗
🔗
🔗

9.

Suppose that the graph of the function \(f(x) = ax^3+bx^2+cx+d\) passes through the points \((-1,2)\text{,}\) \((-2,-9)\text{,}\) \((1,4)\text{,}\) and \((2,15)\text{.}\) Determine the values of \(a\text{,}\) \(b\text{,}\) \(c\text{,}\) and \(d\text{.}\)
🔗
Answer.
The values are \(a= \frac{5}{3}\text{,}\) \(b=0\text{,}\) \(c=-\frac{2}{3}\text{,}\) and \(d=3\text{.}\)
🔗
🔗
🔗

Writing Exercises

10.
Prove that every homogeneous linear system is consistent.
🔗
Hint.
It is easy to find at least one solution to every homogeneous system. Why?
🔗
🔗
🔗
11.
  1. Prove that if \(ad-bc \neq 0\text{,}\) then the reduced row-echelon form of \(\begin{bmatrix} a \amp b \\ c \amp d \end{bmatrix}\) is \(\begin{bmatrix} 1 \amp 0 \\ 0 \amp 1 \end{bmatrix}\text{.}\)
    🔗
    🔗
  2. Use part (a) to prove that if \(ad-bc \neq 0\text{,}\) then the linear system
    \begin{align*} ax + by \amp = p\\ cx + dy \amp = q \end{align*}
    has exactly one solution.
    🔗
    🔗
🔗
🔗
12.
Using only results from this section, explain why every linear system over \(\rr\) has either no solutions, exactly one solution, or an infinite number of solutions.
🔗
🔗
13.
Suppose that a \(3\times 4\) coefficient matrix for a linear system has three pivot columns. Is the system consistent? Explain.
🔗
Answer.
Yes, this system is consistent. (Why?)
🔗
🔗
🔗
14.
What would one have to know about the pivot columns in an augmented matrix in order to conclude that the linear system has exactly one solution? Explain.
🔗
🔗
15.
Suppose that matrices \(A\) and \(B\) are row equivalent and both matrices are in REF. Prove that \(A\) and \(B\) have the same pivot positions.
🔗
🔗
🔗
🔗
🔗
PrevTopNext