# 3.11 Solving RREF systems

Suppose we start with a linear system with matrix form $A\mathbf{x}=\mathbf{b}$ then put the augmented matrix $(A\mid\mathbf{b})$ into RREF. Suppose the resulting matrix in RREF is $(A^{\prime}\mid\mathbf{b}^{\prime})$. The whole point of RREF was that the solutions of $A\mathbf{x}=\mathbf{b}$ are the same as those of $A^{\prime}\mathbf{x}=\mathbf{b}^{\prime}$ but it should be “easy” to find the solutions of $A^{\prime}\mathbf{x}=\mathbf{b}^{\prime}$. How do we actually find those solutions?

###### Example 3.11.1.

Here is an augmented matrix in RREF

 $\begin{pmatrix}1&0&2&0&0\\ 0&1&4&0&0\\ 0&0&0&1&0\\ 0&0&0&0&1\end{pmatrix}$

If the variables are called $x,y,z,w$ then the corresponding equations are

 $\displaystyle x+2z$ $\displaystyle=0$ $\displaystyle y+4z$ $\displaystyle=0$ $\displaystyle w$ $\displaystyle=0$ $\displaystyle 0$ $\displaystyle=1$

The last equation is false, so there are no solutions to this linear system.

###### Example 3.11.2.

Here is the same augmented matrix with a different final column.

 $\begin{pmatrix}1&0&2&0&2\\ 0&1&4&0&3\\ 0&0&0&1&4\\ 0&0&0&0&0\end{pmatrix}$

In this case, if the variables are $x,y,z,w$, the equations are

 $\displaystyle x+2z$ $\displaystyle=2$ $\displaystyle y+4z$ $\displaystyle=3$ $\displaystyle w$ $\displaystyle=4$ $\displaystyle 0$ $\displaystyle=0$

The solutions are $x=2-2z,y=3-4z,w=4$. The last $0=0$ equation doesn’t tell us anything so it can be ignored. We can write the solutions in vector form as

 $\displaystyle\begin{pmatrix}x\\ y\\ z\\ w\end{pmatrix}$ $\displaystyle=\begin{pmatrix}2-2z\\ 3-4z\\ z\\ 4\end{pmatrix}$ $\displaystyle=\begin{pmatrix}2\\ 3\\ 0\\ 4\end{pmatrix}+z\begin{pmatrix}-2\\ -4\\ 1\\ 0\end{pmatrix}$

In general, for an augmented matrix in row reduced echelon form:

• If the last column of the augmented matrix has a leading entry (like in the first example above), there are no solutions. Otherwise,

• variables corresponding to a column with no leading entry (like $z$ in the second example) can be chosen freely, and

• the other variables are uniquely determined in terms of these free variables.

Variables whose column has no leading entry are called free variables and variables whose column does contain a leading entry are called pivot variables.

It’s easy to see why the first bullet point is true: in that case the row with a leading entry in its final column would correspond to an equation saying

 $0=1$

which has no solutions, so the system is inconsistent. Let’s prove the second part of the claim.

###### Theorem 3.11.1.

Suppose $R\mathbf{x}=\mathbf{b}$ is a system of linear equations whose augmented matrix is in RREF and does not have a leading entry in the final column. Let $R$ be $m\times n$, let $x_{j_{1}},\ldots,x_{j_{k}}$ be the free variables, and let $x_{i_{1}},\ldots,x_{i_{l}}$ be the pivot variables. Then for any list of numbers $a_{1},\ldots,a_{k}$ there is exactly one solution to $R\mathbf{x}=\mathbf{b}$ in which $x_{j_{p}}=a_{p}$ for all $1\leqslant p\leqslant k$.

The point of this theorem is to make precise the idea that in a RREF linear system, the values of the free variables can be chosen arbitrarily, and these choices completely determine the values of the other (pivot) variables.

###### Proof.

The $l$ nonzero equations corresponding to the first $l$ rows of the augmented matrix take the form

 $x_{i_{q}}+\sum_{p=1}^{k}r_{q,j_{p}}x_{j_{p}}=b_{q}$ (3.12)

for $1\leqslant q\leqslant l$. (The coefficient of $x_{i_{q}}$ is 1 because leading entries in a RREF matrix are 1, and no pivot variables except $x_{i_{q}}$ appear in the $q$th equation with nonzero coefficient because pivot variables correspond to columns with a leading entry, and by the definition of RREF every other entry in those columns must be zero).

Now let $a_{1},\ldots,a_{k}$ be any numbers. If $x_{j_{p}}=a_{p}$ for $1\leqslant p\leqslant k$ then the equations (3.12) force

 $x_{i_{q}}=b_{q}-\sum_{p=1}^{k}r_{q,j_{p}}a_{p}.$

All values of the free and pivot variables are determined, so there is exactly one such solution. ∎

###### Example 3.11.3.

Consider the system of linear equations

 $\displaystyle 2x_{1}+x_{2}+x_{3}-2x_{4}$ $\displaystyle=3$ $\displaystyle x_{1}+x_{3}-2x+4$ $\displaystyle=2$ $\displaystyle x_{1}+2x_{3}-4x_{4}$ $\displaystyle=1$ $\displaystyle 3x_{1}+x_{2}+3x_{3}-6x_{4}$ $\displaystyle=4.$

By doing row operations to the corresponding augmented matrix, you can reach the RREF matrix

 $\begin{pmatrix}1&0&0&0&3\\ 0&1&0&0&-2\\ 0&0&1&-2&-1\\ 0&0&0&0&0\end{pmatrix}$

with corresponding system of linear equations

 $\displaystyle x_{1}$ $\displaystyle=3$ $\displaystyle x_{2}$ $\displaystyle=-2$ $\displaystyle x_{3}-2x_{4}$ $\displaystyle=-1.$

There is one free variable, $x_{4}$, which can take any value. The general solution is

 $\begin{pmatrix}x_{1}\\ x_{2}\\ x_{3}\\ x_{4}\end{pmatrix}=\begin{pmatrix}3\\ -2\\ 2x_{4}-1\\ x_{4}\end{pmatrix}.$

We can now show that homogeneous linear systems with more variables than equations have nonzero solutions (that is, solutions other than the zero vector $\mathbf{0}$).

###### Proposition 3.11.2.

If $A$ is $m\times n$ and $n>m$ then the matrix equation $A\mathbf{x}=\mathbf{0}$ has a nonzero solution.

###### Proof.

When we do row operations to $A$ to get a RREF matrix, that RREF matrix has at most one leading entry in each of its $m$ rows. Since there are more columns than rows, there must be a column with no leading entry. The corresponding variable is a free variable, so there is a solution in which it is nonzero. ∎