Let $$A$$ be a matrix defined over a field that is in reduced row-echelon form (RREF). Then the solutions of $$Ax = b$$ can be read off the augmented matrix $$[A~b]$$ immediately. What follows is a look at all the possible scenarios.

### Some terminology

Suppose that the augmented matrix is $$\begin{bmatrix} 1 & 2 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 3 \end{bmatrix}$$, which is in RREF. Columns $$1, 3,$$ and $$4$$ contain the leading ones. These columns are called pivot columns. The variables that correspond to these columns are called pivot variables. The remaining variables are called free variables.

### Existence of solutions

Suppose that the augmented matrix is $$\begin{bmatrix} 1 & 2 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{bmatrix}$$. Notice that the third row has $$0$$'s in the columns corresonding to the variables but a nonzero in the right-most column, the column that corresponds to the right-hand side values. This means that there is no solution because the equation that the third row represents is “$$0 = 1$$”. In general, if an augmented matrix in RREF has a row that contains all $$0$$'s except the right-most entry, then the system has no solution.

If the augmented matrix does not have such a row, then there is at least one solution that can easily be obtained by setting each of the pivot variables to the corresponding right-hand side value and setting the free variables to $$0$$. For example, if the augmented matrix is $$\begin{bmatrix} 1 & 2 & 0 & 0 & 5 \\ 0 & 0 & 1 & 0 & 4 \\ 0 & 0 & 0 & 1 & 3 \end{bmatrix}$$, a solution is given by setting the pivot variables $$x_1 = 5$$, $$x_3 = 4$$, $$x_4=3$$ and the free variable $$x_2 = 0$$.

In the case when the augmented matrix in RREF tells us that there is a solution, we can often say more about the solution set as we will see next.

### The case of multiple solutions

Suppose that the augmented matrix does not have a row that contains all $$0$$'s except the right-most entry. If there is a free variable, then there will be infinitely many solutions unless the system is defined over a finite field. Consider the augmented matrix given by $$\begin{bmatrix} 1 & 2 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 3 \end{bmatrix}$$. The second column is not a pivot column. We can set the variable corresponding to this column to any value and still obtain a solution for the system. In particular, setting $$x_2=s$$, we obtain a solution with $$x_1 = -2s$$, $$x_3 = 0$$, $$x_4 = 3$$. In other words, for every value of $$s$$, $$x = \begin{bmatrix} -2s \\ s \\0 \\ 3\end{bmatrix}$$ is a solution. For example, setting $$s = 0$$ gives the solution $$x = \begin{bmatrix} 0 \\ 0 \\0 \\ 3\end{bmatrix}$$ and setting $$s = -1$$ gives the solution $$x = \begin{bmatrix} 2 \\ -1 \\0 \\ 3\end{bmatrix}$$.

(To see how one obtain the solution above, one can write out the system in full: \begin{eqnarray} x_1 + 2x_2 = 0 \\ x_3 = 0 \\ x_4 = 3\end{eqnarray} Setting $$x_2 = s$$ gives \begin{eqnarray} x_1 + 2s = 0 \\ x_3 = 0 \\ x_4 = 3\end{eqnarray} Now, solving for $$x_1$$ gives the solution as shown above.)

### The case of a unique solution

If the augmented matrix does not tell us there is no solution and if there is no free variable (i.e. every column other than the right-most column is a pivot column), then the system has a unique solution. For example, if $$A = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ 0 & 0\end{bmatrix}$$ and $$b = \begin{bmatrix} 2 \\ 3 \\ 0 \end{bmatrix}$$, then there is a unique solution to the system $$A x = b$$.

## Exercises

Each the following matrices defined over the rational numbers is an augmented matrix for some system of linear equations. Determine if the system has no solution, a unique solution, or infinitely many solutions.

1. $$\begin{bmatrix} 1 & -1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1\end{bmatrix}$$

2. $$\begin{bmatrix} 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \end{bmatrix}$$

3. $$\begin{bmatrix} 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 2 & 3 & 2 \end{bmatrix}$$