Subsection CS Consistent 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.

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”?

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.

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.

Subsection FV Free 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.

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.

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.

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

Notice that to use this theorem we need only know that the system is consistent, together with the values of $m$ and $n$. 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$.
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$.
   2. $r<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$, 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.