2.4 Solution-set types

Gaussian elimination is not finished once the matrix looks simpler. The point of row reduction is that the reduced form lets you read the structure of the solution set. This note makes that reading process precise.

There are only three possible outcomes for a linear system:

1. exactly one solution,
2. infinitely many solutions,
3. no solution.

The classification is not based on guesswork. It follows from the position of the pivot columns in the reduced augmented matrix.

The consistency test

The first question is not whether the system has one solution or many. The first question is whether it has any solution at all.

Theorem

Consistency criterion from RREF

Let $A$ be the augmented matrix of an $m \times n$ linear system, and let $B$ be the RREF row-equivalent to $A$. Then the system is inconsistent if and only if the last column of $B$ is a pivot column.

Equivalently, the system is inconsistent if and only if $B$ contains a row of the form

$$\left[ \begin{array}{cccc|c} 0 & 0 & \cdots & 0 & d \end{array} \right] \qquad\text{with } d \neq 0.$$

Such a row represents the equation

$$0 = d,$$

which is impossible when $d \neq 0$. That is why contradiction rows settle the question immediately.

Dependent variables and free variables

When a consistent linear system is reduced to RREF, the pivot columns tell you which variables are determined by the others. Columns without pivots correspond to variables that may be chosen freely.

Definition

Dependent variables and free variables

Suppose the augmented matrix of a consistent linear system is row-equivalent to a matrix $B$ in RREF. If column $j$ of $B$ is a pivot column, then the variable $x_j$ is called a dependent variable or leading variable. A variable whose column is not a pivot column is called a free variable.

This language matters because it tells you how the final answer should be written. Free variables become parameters. Dependent variables are then solved in terms of those parameters.

Why only three cases can occur

Once the system is known to be consistent, the remaining issue is the number of free variables.

Theorem

Classification by the number of pivots

Suppose an $m \times n$ linear system is consistent, and suppose its augmented matrix is row-equivalent to an RREF matrix with $r$ pivot columns. Then $r \leq n$. Moreover:

1. if $r = n$, the system has a unique solution;
2. if $r \lt n$, the system has infinitely many solutions.

The reason is structural.

• If $r = n$, every variable column contains a pivot, so there are no free variables.
• If $r \lt n$, then $n - r \gt 0$, so at least one variable is free.
• Every choice of the free variables gives a solution, so consistency plus a free variable automatically creates infinitely many solutions.

Putting the consistency theorem and the pivot-count theorem together gives the standard trichotomy.

Theorem

Possible solution sets for a linear system

A linear system has exactly one of the following three solution-set types:

1. a unique solution;
2. infinitely many solutions;
3. no solution.

From a reduced matrix to every solution

The classification theorem contains two claims that deserve a proof. First, if no contradiction row occurs, there really is a solution. Second, varying a free variable produces different solutions, rather than different names for the same tuple. Both facts follow from the exact way RREF separates pivot columns from nonpivot columns.

Proof

The parameter map is exhaustive and injective

Let the coefficient matrix have $n$ columns, and write the reduced augmented matrix as $[R\mid d]$. Suppose there is no contradiction row. Let the pivot columns be $p_1,\ldots,p_r$ and the remaining coefficient columns be $f_1,\ldots,f_k$, where $k=n-r$. Each nonzero row has the form

$$x_{p_i}+\sum_{j=1}^{k}r_{i f_j}x_{f_j}=d_i.$$

The other pivot variables do not appear in this row: their columns contain zeros outside their own leading ones. Therefore we can choose arbitrary real parameters $t_1,\ldots,t_k$ and define

$$x_{f_j}=t_j,\qquad x_{p_i}=d_i-\sum_{j=1}^{k}r_{i f_j}t_j.$$

This construction gives a solution for every parameter choice. Each nonzero row is satisfied by its defining formula, and every remaining row is the identity $0=0$. Reversibility of reduction then makes it a solution of the original system as well. This proves the sufficiency part of the consistency criterion, which cannot be obtained just by noticing that a contradiction would be impossible.

The construction is exhaustive. If $x$ is any solution, read its free coordinates and set $t_j=x_{f_j}$. The pivot equations force every remaining coordinate to equal the displayed formula. Thus every solution comes from the construction; there are no additional tuples outside the parameterized set.

It is also injective. If two parameter lists differ, they differ in some entry $t_j$. Their solution tuples then differ in coordinate $f_j$, because that coordinate is exactly $t_j$. Hence distinct parameter choices always produce distinct solutions.

If there are no free variables, the pivot equations determine one tuple. If there is at least one free variable, fix all the other parameters at zero and vary that one over the real numbers. Injectivity proves that the resulting solutions are infinitely numerous. The argument relies on working over the real numbers, as throughout this course. It is a statement about the number of solutions, not merely an observation that a parameter symbol appears in the answer.

The extreme case with no pivots is included. If the entire augmented matrix is zero, every tuple in $\mathbb R^n$ is a solution. All variables are free, and the parameter map is simply the identity map on the space of tuples. On the other hand, a zero coefficient matrix with even one nonzero constant is inconsistent. It is the augmented rows, not just the coefficients, that distinguish these cases.

Three reduced forms, three different readings

The reduced matrix already contains the whole story. The only question is whether you know what to look for.

Worked example

Read the matrix before solving

Consider the following three RREF augmented matrices.

First,

$$\left[ \begin{array}{cc|c} 1 & 0 & 3 \\ 0 & 1 & -2 \end{array} \right].$$

Both variable columns are pivot columns, so there are no free variables. The system has the unique solution

$$x_1 = 3,\qquad x_2 = -2.$$

Second,

$$\left[ \begin{array}{ccc|c} 1 & 2 & 0 & 5 \\ 0 & 0 & 0 & 0 \end{array} \right].$$

Column 1 is a pivot column, but columns 2 and 3 are not. So $x_2$ and $x_3$ are free variables. The equation is

$$x_1 + 2x_2 = 5,$$

which gives

$$x_1 = 5 - 2x_2.$$

Hence the solution set is

$$\{(5 - 2s, s, t) \mid s, t \in R\}.$$

Third,

$$\left[ \begin{array}{cc|c} 1 & 0 & 0 \\ 0 & 0 & 1 \end{array} \right].$$

The last row says $0 = 1$, so the system is inconsistent and has no solution.

The essential habit is this:

1. check for contradiction rows;
2. identify pivot columns;
3. count free variables;
4. write the dependent variables in terms of the free ones.

The sequence below organizes the three cases into a decision tree: check consistency first, then count the free variables. The larger parameterized example that follows uses the same order of decisions.

Compress the theorem into a decision tree: check the last column for inconsistency, then use pivot and free-variable counts to choose unique or infinite.

1. Read RREF

   Row operations preserve solution sets, so the RREF is safe to read. Separate the variable columns from the augmented column, then locate pivots and free columns.

2. Consistency first

   A row [0 0 ... 0 | d] with d nonzero represents 0=d. Equivalently, a pivot in the last column means the system has no solution.

3. Unique solution

   If the system is consistent and every variable column has a pivot, there are no free variables, so the RREF names exactly one solution vector.

4. Infinitely many

   If the system is consistent but some variable column has no pivot, that free variable becomes a real parameter, giving infinitely many solutions.

5. Three outcomes

   The trichotomy is complete: no solution, unique solution, or infinitely many solutions. A linear system cannot have exactly two solutions.

6. Practice the reading order

   Use the live classifier below to rehearse the same order: check for contradiction rows, count variable pivots, then classify the solution set.

The classification is structural: a contradiction row decides inconsistency, and once the system is consistent, the number of free variables decides whether the solution set is one point or an infinite family.

A larger parameterized example

When free variables appear, the answer should be written as a full set, not as a vague phrase such as "there are many solutions."

Worked example

Write the solution set explicitly

Suppose a system in variables $x_1, x_2, x_3, x_4, x_5$ has RREF

$$\left[ \begin{array}{ccccc|c} 1 & -1 & 0 & 0 & 3 & 6 \\ 0 & 0 & 1 & 0 & -2 & 1 \\ 0 & 0 & 0 & 1 & 4 & 9 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{array} \right].$$

Columns 1, 3, and 4 are pivot columns, so $x_1$, $x_3$, and $x_4$ are dependent variables. Columns 2 and 5 are non-pivot columns, so $x_2$ and $x_5$ are free.

Reading the rows gives

$$\begin{aligned} x_1 - x_2 + 3x_5 &= 6, \\ x_3 - 2x_5 &= 1, \\ x_4 + 4x_5 &= 9. \end{aligned}$$

Let

$$x_2 = s,\qquad x_5 = t.$$

Then

$$\begin{aligned} x_1 &= 6 + s - 3t, \\ x_3 &= 1 + 2t, \\ x_4 &= 9 - 4t. \end{aligned}$$

Therefore the solution set is

$$\{(6 + s - 3t,\ s,\ 1 + 2t,\ 9 - 4t,\ t) \mid s, t \in R\}.$$

Two free variables produce a two-parameter family of solutions.

Parameter choices must survive direct verification

Worked example

Three nonadjacent free variables in six coordinates

Consider the following RREF for a system in six variables:

$$\left[\begin{array}{rrrrrr|r} 1&4&0&0&2&1&4\\ 0&0&1&0&1&-3&2\\ 0&0&0&1&2&-6&1\\ 0&0&0&0&0&0&0 \end{array}\right].$$

The pivot indices are $1,3,4$, so the free indices are $2,5,6$. Set $x_2=s$, $x_5=t$, and $x_6=u$. Reading each nonzero row yields

$$x=(4-4s-2t-u,\ s,\ 2-t+3u,\ 1-2t+6u,\ t,\ u), \qquad s,t,u\in\mathbb R.$$

For a direct check, the first row becomes $(4-4s-2t-u)+4s+2t+u=4$. The second becomes $(2-t+3u)+t-3u=2$, and the third becomes $(1-2t+6u)+2t-6u=1$. All parameter terms cancel as required. Conversely, every solution supplies its own values of $s,t,u$ through coordinates two, five, and six, after which the remaining coordinates are forced.

This is stronger than listing a few numerical solutions. Setting all parameters to zero gives $(4,0,2,1,0,0)$, but that tuple is only one member of the family. The full formula records both which choices are independent and how they change the remaining coordinates. Keeping coordinates in the original variable order is essential; grouping the three free coordinates together at the end would describe a different tuple unless the reordering were explicitly announced.

The five-coordinate example earlier has the same logical structure, even though it uses only two parameters. A useful self-check is to recover those parameters from the completed tuple: its second coordinate is exactly the first parameter and its fifth coordinate is exactly the second. This makes both the completeness claim and the absence of duplicate parameter descriptions transparent.

A useful corollary when there are more variables than equations

One common classroom situation is a consistent system with fewer equations than variables.

Theorem

More variables than equations

Suppose a consistent linear system has $m$ equations in $n$ variables, and suppose $n \gt m$. Then the system has infinitely many solutions.

Why? In RREF there can be at most $m$ nonzero rows, so there can be at most $m$ pivot columns. If $n \gt m$, then at least one of the $n$ variable columns must be non-pivot. Hence there is at least one free variable, and consistency then forces infinitely many solutions.

This corollary does not say that every underdetermined system is consistent. It says that once such a system is consistent, uniqueness is impossible.

Why counting equations is not enough

Counterexample mode

Equal numbers of equations and variables do not imply uniqueness

Consider three systems, each consisting of two equations in two unknowns:

$$\begin{aligned} \text{I: }&x+y=2,\quad x-y=0;\\ \text{II: }&x+y=2,\quad 2x+2y=4;\\ \text{III: }&x+y=2,\quad 2x+2y=5. \end{aligned}$$

System I has the unique solution $(1,1)$. Subtracting twice the first equation from the second in system II gives $0=0$, so it has the family $(2-t,t)$. The same operation in system III gives $0=1$, so it has no solution. The displayed equation count and variable count agree in every case, yet all three outcomes occur.

The failed hypothesis is that every displayed equation provides a new, compatible restriction. A repeated equation adds no restriction, while an incompatible equation removes every candidate. Pivots count independent restrictions after the equations have been combined; merely counting rows does not do that work. The repaired criterion is precise: a real linear system has a unique solution if and only if it is consistent and every variable column is a pivot column.

Adding redundant equations can also produce more equations than variables without preventing uniqueness. The system $x=1$, $y=2$, $x+y=3$ has three equations and two unknowns, but still has exactly one solution. Replacing the third equation by $x+y=4$ makes the system inconsistent. Therefore an overdetermined system may be consistent or inconsistent; the inequality between the two counts alone settles neither question.

Likewise, having fewer equations than variables guarantees infinitely many solutions only after consistency is known. In three variables, the two equations $x+y+z=0$ and $2x+2y+2z=1$ contradict one another. Their augmented reduction contains a nonzero constant after all coefficient entries in that row have vanished. Counting unused variable columns cannot repair this contradiction.

A parameter in the equations is not a free variable

Worked example

Classify an entire family before dividing

Let $a,b$ be given real numbers and consider

$$x+y=1,\qquad 2x+ay=b.$$

Here $x,y$ are the unknowns; $a,b$ describe which system is being asked about. The legal operation $R_2\leftarrow R_2-2R_1$ gives

$$\left[\begin{array}{cc|c}1&1&1\\0&a-2&b-2\end{array}\right].$$

If $a\ne2$, the second row determines $y=(b-2)/(a-2)$ and the first determines $x=1-y$. Thus the solution is unique. If $a=2$ and $b\ne2$, the second row is the contradiction $0=b-2$, so there is no solution. If $a=2$ and $b=2$, the second row is zero and the solutions are $(1-t,t)$ for arbitrary real $t$.

These cases exhaust all possible pairs $(a,b)$. Dividing by $a-2$ before separating the case $a=2$ would discard precisely the systems where the answer can change from unique to infinite or empty. The parameter $t$ in the final solution family plays a different role: it varies solutions of one fixed system, while $a,b$ choose the system itself.

A second proof that two solutions force infinitely many

There is an algebraic check on the trichotomy that does not require a new row reduction. Suppose $u$ and $v$ are distinct solutions of the same system $Ax=b$. For every real number $t$, define $w(t)=u+t(v-u)$. Matrix multiplication gives

$$Aw(t)=Au+t(Av-Au)=b+t(b-b)=b.$$

Thus every point on this line is a solution. These solutions are distinct as $t$ varies: if $w(s)=w(t)$, then $(s-t)(v-u)=0$. Some coordinate of $v-u$ is nonzero, so that coordinate forces $s=t$. A real linear system with two distinct solutions consequently cannot stop at two, three, or any other finite number greater than one.

This proof complements the parameter-map proof. The parameter map constructs all solutions and counts their independent choices. The line argument starts from two known solutions and proves that infinitely many must exist, without claiming that this one line contains every solution. For a system with several free variables, its full solution set may be larger than the particular line joining two selected solutions.

Compare the three cases interactively

The classifier below is useful because it makes the reading process explicit: you check contradiction rows, look for pivots, and then decide how many free variables remain.

Common mistakes

Common mistake

A free variable is not an unfinished calculation

A free variable is a genuine feature of the system. It means the solution set is parameterized. The algebra is complete, even though the answer is a family of vectors rather than one point.

Common mistake

A zero row is not the same as a contradiction row

The row

$$\left[ \begin{array}{cccc|c} 0 & 0 & 0 & 0 & 0 \end{array} \right]$$

adds no new condition and is perfectly compatible with consistency. By contrast,

$$\left[ \begin{array}{cccc|c} 0 & 0 & 0 & 0 & 1 \end{array} \right]$$

is a contradiction and destroys consistency.

Quick checks

Checkpoint

What does the row $\left[\begin{array}{ccc|c}0 & 0 & 0 & 1\end{array}\right]$ tell you about the system?

Interpret the row as an equation.

Solution · Answer

It represents the equation $0 = 1$, so the system is inconsistent and has no solution.

Checkpoint

If a consistent system in four variables has three pivot columns, how many free variables does it have?

Count the non-pivot variable columns.

Solution · Answer

It has $4 - 3 = 1$ free variable, so the system has infinitely many solutions.

Exercises

Checkpoint

Classify the solution set of the system whose RREF is $\left[\begin{array}{ccc|c}1 & 0 & 2 & 4 \\ 0 & 1 & -3 & -1 \\ 0 & 0 & 0 & 0\end{array}\right]$, and write the solution set explicitly.

Start by naming the free variable, then solve for the pivot variables.

Solution · Guided solution

Columns 1 and 2 are pivot columns, while column 3 is not. So $x_3$ is free. Let

$$x_3 = t.$$

Then the rows give

$$x_1 + 2t = 4, \qquad x_2 - 3t = -1.$$

Hence

$$x_1 = 4 - 2t, \qquad x_2 = -1 + 3t.$$

So the solution set is

$$\{(4 - 2t,\ -1 + 3t,\ t) \mid t \in R\}.$$

Checkpoint

Why can a consistent system never have exactly two solutions?

Answer from the free-variable theorem, not from a picture.

Solution · Guided solution

If a consistent system has no free variables, it has one unique solution. If it has at least one free variable, then the free variable can take infinitely many real values, so the system has infinitely many solutions. There is no structural way to obtain exactly two solutions.

Related notes

Read 2.3 Gaussian elimination and RREF for the mechanics of row reduction, and 2.2 Augmented matrices and row operations for the meaning of augmented matrices and elementary row operations.