Skip to main content
\(\newcommand{\orderof}[1]{\sim #1} \newcommand{\Z}{\mathbb{Z}} \newcommand{\reals}{\mathbb{R}} \newcommand{\real}[1]{\mathbb{R}^{#1}} \newcommand{\complexes}{\mathbb{C}} \newcommand{\complex}[1]{\mathbb{C}^{#1}} \newcommand{\conjugate}[1]{\overline{#1}} \newcommand{\modulus}[1]{\left\lvert#1\right\rvert} \newcommand{\zerovector}{\vect{0}} \newcommand{\zeromatrix}{\mathcal{O}} \newcommand{\innerproduct}[2]{\left\langle#1,\,#2\right\rangle} \newcommand{\norm}[1]{\left\lVert#1\right\rVert} \newcommand{\dimension}[1]{\dim\left(#1\right)} \newcommand{\nullity}[1]{n\left(#1\right)} \newcommand{\rank}[1]{r\left(#1\right)} \newcommand{\ds}{\oplus} \newcommand{\detname}[1]{\det\left(#1\right)} \newcommand{\detbars}[1]{\left\lvert#1\right\rvert} \newcommand{\trace}[1]{t\left(#1\right)} \newcommand{\sr}[1]{#1^{1/2}} \newcommand{\spn}[1]{\left\langle#1\right\rangle} \newcommand{\nsp}[1]{\mathcal{N}\!\left(#1\right)} \newcommand{\csp}[1]{\mathcal{C}\!\left(#1\right)} \newcommand{\rsp}[1]{\mathcal{R}\!\left(#1\right)} \newcommand{\lns}[1]{\mathcal{L}\!\left(#1\right)} \newcommand{\per}[1]{#1^\perp} \newcommand{\augmented}[2]{\left\lbrack\left.#1\,\right\rvert\,#2\right\rbrack} \newcommand{\linearsystem}[2]{\mathcal{LS}\!\left(#1,\,#2\right)} \newcommand{\homosystem}[1]{\linearsystem{#1}{\zerovector}} \newcommand{\rowopswap}[2]{R_{#1}\leftrightarrow R_{#2}} \newcommand{\rowopmult}[2]{#1R_{#2}} \newcommand{\rowopadd}[3]{#1R_{#2}+R_{#3}} \newcommand{\leading}[1]{\boxed{#1}} \newcommand{\rref}{\xrightarrow{\text{RREF}}} \newcommand{\elemswap}[2]{E_{#1,#2}} \newcommand{\elemmult}[2]{E_{#2}\left(#1\right)} \newcommand{\elemadd}[3]{E_{#2,#3}\left(#1\right)} \newcommand{\scalarlist}[2]{{#1}_{1},\,{#1}_{2},\,{#1}_{3},\,\ldots,\,{#1}_{#2}} \newcommand{\vect}[1]{\mathbf{#1}} \newcommand{\colvector}[1]{\begin{bmatrix}#1\end{bmatrix}} \newcommand{\vectorcomponents}[2]{\colvector{#1_{1}\\#1_{2}\\#1_{3}\\\vdots\\#1_{#2}}} \newcommand{\vectorlist}[2]{\vect{#1}_{1},\,\vect{#1}_{2},\,\vect{#1}_{3},\,\ldots,\,\vect{#1}_{#2}} \newcommand{\vectorentry}[2]{\left\lbrack#1\right\rbrack_{#2}} \newcommand{\matrixentry}[2]{\left\lbrack#1\right\rbrack_{#2}} \newcommand{\lincombo}[3]{#1_{1}\vect{#2}_{1}+#1_{2}\vect{#2}_{2}+#1_{3}\vect{#2}_{3}+\cdots +#1_{#3}\vect{#2}_{#3}} \newcommand{\matrixcolumns}[2]{\left\lbrack\vect{#1}_{1}|\vect{#1}_{2}|\vect{#1}_{3}|\ldots|\vect{#1}_{#2}\right\rbrack} \newcommand{\transpose}[1]{#1^{t}} \newcommand{\inverse}[1]{#1^{-1}} \newcommand{\submatrix}[3]{#1\left(#2|#3\right)} \newcommand{\adj}[1]{\transpose{\left(\conjugate{#1}\right)}} \newcommand{\adjoint}[1]{#1^\ast} \newcommand{\set}[1]{\left\{#1\right\}} \newcommand{\setparts}[2]{\left\lbrace#1\,\middle|\,#2\right\rbrace} \newcommand{\card}[1]{\left\lvert#1\right\rvert} \newcommand{\setcomplement}[1]{\overline{#1}} \newcommand{\charpoly}[2]{p_{#1}\left(#2\right)} \newcommand{\eigenspace}[2]{\mathcal{E}_{#1}\left(#2\right)} \newcommand{\eigensystem}[3]{\lambda&=#2&\eigenspace{#1}{#2}&=\spn{\set{#3}}} \newcommand{\geneigenspace}[2]{\mathcal{G}_{#1}\left(#2\right)} \newcommand{\algmult}[2]{\alpha_{#1}\left(#2\right)} \newcommand{\geomult}[2]{\gamma_{#1}\left(#2\right)} \newcommand{\indx}[2]{\iota_{#1}\left(#2\right)} \newcommand{\ltdefn}[3]{#1\colon #2\rightarrow#3} \newcommand{\lteval}[2]{#1\left(#2\right)} \newcommand{\ltinverse}[1]{#1^{-1}} \newcommand{\restrict}[2]{{#1}|_{#2}} \newcommand{\preimage}[2]{#1^{-1}\left(#2\right)} \newcommand{\rng}[1]{\mathcal{R}\!\left(#1\right)} \newcommand{\krn}[1]{\mathcal{K}\!\left(#1\right)} \newcommand{\compose}[2]{{#1}\circ{#2}} \newcommand{\vslt}[2]{\mathcal{LT}\left(#1,\,#2\right)} \newcommand{\isomorphic}{\cong} \newcommand{\similar}[2]{\inverse{#2}#1#2} \newcommand{\vectrepname}[1]{\rho_{#1}} \newcommand{\vectrep}[2]{\lteval{\vectrepname{#1}}{#2}} \newcommand{\vectrepinvname}[1]{\ltinverse{\vectrepname{#1}}} \newcommand{\vectrepinv}[2]{\lteval{\ltinverse{\vectrepname{#1}}}{#2}} \newcommand{\matrixrep}[3]{M^{#1}_{#2,#3}} \newcommand{\matrixrepcolumns}[4]{\left\lbrack \left.\vectrep{#2}{\lteval{#1}{\vect{#3}_{1}}}\right|\left.\vectrep{#2}{\lteval{#1}{\vect{#3}_{2}}}\right|\left.\vectrep{#2}{\lteval{#1}{\vect{#3}_{3}}}\right|\ldots\left|\vectrep{#2}{\lteval{#1}{\vect{#3}_{#4}}}\right.\right\rbrack} \newcommand{\cbm}[2]{C_{#1,#2}} \newcommand{\jordan}[2]{J_{#1}\left(#2\right)} \newcommand{\hadamard}[2]{#1\circ #2} \newcommand{\hadamardidentity}[1]{J_{#1}} \newcommand{\hadamardinverse}[1]{\widehat{#1}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

SectionTSSTypes of Solution Sets

We will now be more careful about analyzing the reduced row-echelon form derived from the augmented matrix of a system of linear equations. In particular, we will see how to systematically handle the situation when we have infinitely many solutions to a system, and we will prove that every system of linear equations has either zero, one or infinitely many solutions. With these tools, we will be able to routinely solve any linear system.

SubsectionCSConsistent Systems

The computer scientist Donald Knuth said, “Science is what we understand well enough to explain to a computer. Art is everything else.” In this section we will remove solving systems of equations from the realm of art, and into the realm of science. We begin with a definition.

DefinitionCSConsistent System

A system of linear equations is consistent if it has at least one solution. Otherwise, the system is called inconsistent.

We will want to first recognize when a system is inconsistent or consistent, and in the case of consistent systems we will be able to further refine the types of solutions possible. We will do this by analyzing the reduced row-echelon form of a matrix, using the value of \(r\text{,}\) and the sets of column indices, \(D\) and \(F\text{,}\) first defined back in Definition RREF.

Use of the notation for the elements of \(D\) and \(F\) can be a bit confusing, since we have subscripted variables that are in turn equal to integers used to index the matrix. However, many questions about matrices and systems of equations can be answered once we know \(r\text{,}\) \(D\) and \(F\text{.}\) The choice of the letters \(D\) and \(F\) refer to our upcoming definition of dependent and free variables (Definition IDV). An example will help us begin to get comfortable with this aspect of reduced row-echelon form.

The number \(r\) is the single most important piece of information we can get from the reduced row-echelon form of a matrix. It is defined as the number of nonzero rows, but since each nonzero row has a leading 1, it is also the number of leading 1's present. For each leading 1, we have a pivot column, so \(r\) is also the number of pivot columns. Repeating ourselves, \(r\) is the number of nonzero rows, the number of leading 1's and the number of pivot columns. Across different situations, each of these interpretations of the meaning of \(r\) will be useful, though it may be most helpful to think in terms of pivot columns.

Before proving some theorems about the possibilities for solution sets to systems of equations, let us analyze one particular system with an infinite solution set very carefully as an example. We will use this technique frequently, and shortly we will refine it slightly.

Archetypes I and J are both fairly large for doing computations by hand (though not impossibly large). Their properties are very similar, so we will frequently analyze the situation in Archetype I, and leave you the joy of analyzing Archetype J yourself. So work through Archetype I with the text, by hand and/or with a computer, and then tackle Archetype J yourself (and check your results with those listed). Notice too that the archetypes describing systems of equations each lists the values of \(r\text{,}\) \(D\) and \(F\text{.}\) Here we go…

Using the reduced row-echelon form of the augmented matrix of a system of equations to determine the nature of the solution set of the system is a very key idea. So let us look at one more example like the last one. But first a definition, and then the example. We mix our metaphors a bit when we call variables free versus dependent. Maybe we should call dependent variables “enslaved”?

DefinitionIDVIndependent and Dependent Variables

Suppose \(A\) is the augmented matrix of a consistent system of linear equations and \(B\) is a row-equivalent matrix in reduced row-echelon form. Suppose \(j\) is the index of a pivot column of \(B\text{.}\) Then the variable \(x_j\) is dependent. A variable that is not dependent is called independent or free.

If you studied this definition carefully, you might wonder what to do if the system has \(n\) variables and column \(n+1\) is a pivot column? We will see shortly, by Theorem RCLS, that this never happens for a consistent system.

Sets are an important part of algebra, and we have seen a few already. Being comfortable with sets is important for understanding and writing proofs. If you have not already, pay a visit now to Section SET.

We can now use the values of \(m\text{,}\) \(n\text{,}\) \(r\text{,}\) and the independent and dependent variables to categorize the solution sets for linear systems through a sequence of theorems.

Through the following sequence of proofs, you will want to consult three proof techniques. See Proof Technique E, Proof Technique N, Proof Technique CP.

First we have an important theorem that explores the distinction between consistent and inconsistent linear systems.

Proof

The beauty of this theorem being an equivalence is that we can unequivocally test to see if a system is consistent or inconsistent by looking at just a single entry of the reduced row-echelon form matrix. We could program a computer to do it!

SageRCLSRecognizing Consistency of a Linear System
Click to open

Notice that for a consistent system the row-reduced augmented matrix has \(n+1\in F\text{,}\) so the largest element of \(F\) does not refer to a variable. Also, for an inconsistent system, \(n+1\in D\text{,}\) and it then does not make much sense to discuss whether or not variables are free or dependent since there is no solution. Take a look back at Definition IDV and see why we did not need to consider the possibility of referencing \(x_{n+1}\) as a dependent variable.

With the characterization of Theorem RCLS, we can explore the relationships between \(r\) and \(n\) for a consistent system. We can distinguish between the case of a unique solution and infinitely many solutions, and furthermore, we recognize that these are the only two possibilities.

Proof

SubsectionFVFree Variables

The next theorem simply states a conclusion from the final paragraph of the previous proof, allowing us to state explicitly the number of free variables for a consistent system.

Proof

We have accomplished a lot so far, but our main goal has been the following theorem, which is now very simple to prove. The proof is so simple that we ought to call it a corollary, but the result is important enough that it deserves to be called a theorem. (See Proof Technique LC.) Notice that this theorem was presaged first by Example TTS and further foreshadowed by other examples.

Proof

Here is a diagram that consolidates several of our theorems from this section, and which is of practical use when you analyze systems of equations. Note this presumes we have the reduced row-echelon form of the augmented matrix of the system to analyze.

<<SVG image is unavailable, or your browser cannot render it>>

Figure1.55Decision Tree for Solving Linear Systems

We have one more theorem to round out our set of tools for determining solution sets to systems of linear equations.

Proof

Notice that to use this theorem we need only know that the system is consistent, together with the values of \(m\) and \(n\text{.}\) We do not necessarily have to compute a row-equivalent reduced row-echelon form matrix, even though we discussed such a matrix in the proof. This is the substance of the following example.

These theorems give us the procedures and implications that allow us to completely solve any system of linear equations. The main computational tool is using row operations to convert an augmented matrix into reduced row-echelon form. Here is a broad outline of how we would instruct a computer to solve a system of linear equations.

  1. Represent a system of linear equations in \(n\) variables by an augmented matrix (an array is the appropriate data structure in most computer languages).
  2. Convert the matrix to a row-equivalent matrix in reduced row-echelon form using the procedure from the proof of Theorem REMEF. Identify the location of the pivot columns, and their number \(r\text{.}\)
  3. If column \(n+1\) is a pivot column, output the statement that the system is inconsistent and halt.
  4. If column \(n+1\) is not a pivot column, there are two possibilities:

    1. \(r=n\) and the solution is unique. It can be read off directly from the entries in rows 1 through \(n\) of column \(n+1\text{.}\)
    2. \(r\lt n\) and there are infinitely many solutions. If only a single solution is needed, set all the free variables to zero and read off the dependent variable values from column \(n+1\text{,}\) as in the second half of the proof of Theorem RCLS. If the entire solution set is required, figure out some nice compact way to describe it, since your finite computer is not big enough to hold all the solutions (we will have such a way soon).

The above makes it all sound a bit simpler than it really is. In practice, row operations employ division (usually to get a leading entry of a row to convert to a leading 1) and that will introduce round-off errors. Entries that should be zero sometimes end up being very, very small nonzero entries, or small entries lead to overflow errors when used as divisors. A variety of strategies can be employed to minimize these sorts of errors, and this is one of the main topics in the important subject known as numerical linear algebra.

In this section we have gained a foolproof procedure for solving any system of linear equations, no matter how many equations or variables. We also have a handful of theorems that allow us to determine partial information about a solution set without actually constructing the whole set itself. Donald Knuth would be proud.

SubsectionReading Questions

1

How can we easily recognize when a system of linear equations is inconsistent or not?

2

Suppose we have converted the augmented matrix of a system of equations into reduced row-echelon form. How do we then identify the dependent and independent (free) variables?

3

What are the possible solution sets for a system of linear equations?

SubsectionExercises

C10

In the spirit of Example ISSI, describe the infinite solution set for Archetype J.

For Exercises C21–C28, find the solution set of the system of linear equations. Give the values of \(n\) and \(r\text{,}\) and interpret your answers in light of the theorems of this section.

C21

\begin{align*} x_1 + 4x_2 + 3x_3 - x_4 &= 5\\ x_1 - x_2 + x_3 + 2x_4 &= 6\\ 4x_1 + x_2 + 6x_3 + 5x_4 &= 9 \end{align*}

Solution
C22

\begin{align*} x_1 - 2x_2 + x_3 - x_4 &= 3\\ 2x_1 - 4x_2 + x_3 + x_4 &= 2\\ x_1 - 2x_2 - 2x_3 + 3x_4 &= 1 \end{align*}

Solution
C23

\begin{align*} x_1 - 2x_2 + x_3 - x_4 &= 3\\ x_1 + x_2 + x_3 - x_4 &= 1\\ x_1 \quad + x_3 - x_4 &= 2 \end{align*}

Solution
C24

\begin{align*} x_1 - 2x_2 + x_3 - x_4 &= 2\\ x_1 + x_2 + x_3 - x_4 &= 2\\ x_1 \quad + x_3 - x_4 &= 2 \end{align*}

Solution
C25

\begin{align*} x_1 + 2x_2 + 3x_3 &= 1\\ 2x_1 - x_2 + x_3 &= 2\\ 3x_1 + x_2 + x_3 &= 4\\ \quad x_2 + 2x_3 &= 6 \end{align*}

Solution
C26

\begin{align*} x_1 + 2x_2 + 3x_3 &= 1\\ 2x_1 - x_2 + x_3 &= 2\\ 3x_1 + x_2 + x_3 &= 4\\ \quad 5x_2 + 2x_3 &= 1 \end{align*}

Solution
C27

\begin{align*} x_1 + 2x_2 + 3x_3 &= 0\\ 2x_1 - x_2 + x_3 &= 2\\ x_1 - 8x_2 - 7x_3 &= 1\\ \quad x_2 + x_3 &= 0 \end{align*}

Solution
C28

\begin{align*} x_1 + 2x_2 + 3x_3 &= 1\\ 2x_1 - x_2 + x_3 &= 2\\ x_1 - 8x_2 - 7x_3 &= 1\\ \quad x_2 + x_3 &= 0 \end{align*}

Solution
M45

The details for Archetype J include several sample solutions. Verify that one of these solutions is correct (any one, but just one). Based only on this evidence, and especially without doing any row operations, explain how you know this system of linear equations has infinitely many solutions.

Solution
M46

Consider Archetype J, and specifically the row-reduced version of the augmented matrix of the system of equations, denoted as \(B\) here, and the values of \(r\text{,}\) \(D\) and \(F\) immediately following. Determine the values of the entries \begin{align*} \matrixentry{B}{1,d_1}& & \matrixentry{B}{3,d_3}& & \matrixentry{B}{1,d_3}& & \matrixentry{B}{3,d_1}& & \matrixentry{B}{d_1,1}& & \matrixentry{B}{d_3,3}& & \matrixentry{B}{d_1,3}& & \matrixentry{B}{d_3,1}& & \matrixentry{B}{1,f_1}& & \matrixentry{B}{3,f_1}& \end{align*} (See Exercise TSS.M70 for a generalization.)

For Exercises M51–M57 say as much as possible about each system's solution set. Be sure to make it clear which theorems you are using to reach your conclusions.

M51

A consistent system of 8 equations in 6 variables.

Solution
M52

A consistent system of 6 equations in 8 variables.

Solution
M53

A system of 5 equations in 9 variables.

Solution
M54

A system with 12 equations in 35 variables.

Solution
M56

A system with 6 equations in 12 variables.

Solution
M57

A system with 8 equations and 6 variables. The reduced row-echelon form of the augmented matrix of the system has 7 pivot columns.

Solution
M60

Without doing any computations, and without examining any solutions, say as much as possible about the form of the solution set for each archetype that is a system of equations.

Archetype A, Archetype B, Archetype C, Archetype D, Archetype E, Archetype F, Archetype G, Archetype H, Archetype I, Archetype J

M70

Suppose that \(B\) is a matrix in reduced row-echelon form that is equivalent to the augmented matrix of a system of equations with \(m\) equations in \(n\) variables. Let \(r\text{,}\) \(D\) and \(F\) be as defined in Definition RREF. What can you conclude, in general, about the following entries? \begin{align*} \matrixentry{B}{1,d_1}& & \matrixentry{B}{3,d_3}& & \matrixentry{B}{1,d_3}& & \matrixentry{B}{3,d_1}& & \matrixentry{B}{d_1,1}& & \matrixentry{B}{d_3,3}& & \matrixentry{B}{d_1,3}& & \matrixentry{B}{d_3,1}& & \matrixentry{B}{1,f_1}& & \matrixentry{B}{3,f_1}& \end{align*} If you cannot conclude anything about an entry, then say so. (See Exercise TSS.M46.)

T10

An inconsistent system may have \(r\gt n\text{.}\) If we try (incorrectly!) to apply Theorem FVCS to such a system, how many free variables would we discover?

Solution
T11

Suppose \(A\) is the augmented matrix of a system of linear equations in \(n\) variables. and that \(B\) is a row-equivalent matrix in reduced row-echelon form with \(r\) pivot columns. If \(r=n+1\text{,}\) prove that the system of equations is inconsistent.

Solution
T20

Suppose that \(B\) is a matrix in reduced row-echelon form that is equivalent to the augmented matrix of a system of equations with \(m\) equations in \(n\) variables. Let \(r\text{,}\) \(D\) and \(F\) be as defined in Definition RREF. Prove that \(d_k\geq k\) for all \(1\leq k\leq r\text{.}\) Then suppose that \(r\geq 2\) and \(1\leq k\lt\ell\leq r\) and determine what can you conclude, in general, about the following entries. \begin{align*} \matrixentry{B}{k,d_k}& & \matrixentry{B}{k,d_\ell}& & \matrixentry{B}{\ell,d_k}& & \matrixentry{B}{d_k,k}& & \matrixentry{B}{d_k,\ell}& & \matrixentry{B}{d_\ell,k}& & \matrixentry{B}{d_k,f_\ell}& & \matrixentry{B}{d_\ell,f_k}& \end{align*} If you cannot conclude anything about an entry, then say so. (See Exercise TSS.M46 and Exercise TSS.M70.)

T40

Suppose that the coefficient matrix of a consistent system of linear equations has two columns that are identical. Prove that the system has infinitely many solutions.

Solution
T41

Consider the system of linear equations \(\linearsystem{A}{\vect{b}}\text{,}\) and suppose that every element of the vector of constants \(\vect{b}\) is a common multiple of the corresponding element of a certain column of \(A\text{.}\) More precisely, there is a complex number \(\alpha\text{,}\) and a column index \(j\text{,}\) such that \(\vectorentry{\vect{b}}{i}=\alpha\matrixentry{A}{ij}\) for all \(i\text{.}\) Prove that the system is consistent.

Solution