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.