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.
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$, and the sets of column indices, $D$ and $F$, 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$, $D$ and $F$. 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$, $D$ and $F$. 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”?
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$. 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$, $n$, $r$, 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.
Suppose $A$ is the augmented matrix of a system of linear equations with $n$ variables. Suppose also that $B$ is a row-equivalent matrix in reduced row-echelon form with $r$ nonzero rows. Then the system of equations is inconsistent if and only if column $n+1$ of $B$ is a pivot column.
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!
Notice that for a consistent system the row-reduced augmented matrix has $n+1\in F$, so the largest element of $F$ does not refer to a variable. Also, for an inconsistent system, $n+1\in D$, 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.
Suppose $A$ is the augmented matrix of a consistent system of linear equations with $n$ variables. Suppose also that $B$ is a row-equivalent matrix in reduced row-echelon form with $r$ pivot columns. Then $r\leq n$. If $r=n$, then the system has a unique solution, and if $r<n$, then the system has infinitely many solutions.