# 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 impossible, 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:

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

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

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

The variables whose column has no leading entry are called free parameters.

## 3.11.1 Fundamental solutions

Recall that homogeneous system of linear equations is one whose matrix form is $A\mathbf{x}=\mathbf{0}$. This section is about a set of solutions to such a system called the fundamental solutions. These are the ones you get by putting the system into RREF and then choosing one free parameter to be 1 and the rest to be 0.

Let $R\mathbf{x}=\mathbf{0}$ be a homogeneous linear system where the $m\times n$ matrix $R$ is in RREF. Suppose that there are leading entries in rows 1 up to $r$ of $R$, where $r\leqslant m$ and $r\leqslant n$. Let the leading entry in row $i$ occur in column $c_{i}$, so $c_{1}, and note that because of part 3 of the RREF definition Definition 3.9.2, column $c_{i}$ of $R$ has a 1 in position $i$ and zeroes elsewhere. Let the columns of $R$ with no leading entry be $d_{1}<\cdots, so that $k+r=n$.

Here is an example. Suppose that

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

In this case $m=3,n=5$, and $r=2$ as only rows 1 and 2 contain leading entries. The leading entries are in columns 2 and 4, so $c_{1}=2,c_{2}=4$. Columns 1, 3, and 5 don’t contain leading entries, so $k=3$ and $d_{1}=1,d_{2}=3,d_{3}=5$. If the variables in this linear system are $x,y,z,u,v$ then $x$, $z$, and $v$ are free parameters as their columns have no leading entry.

There are therefore three fundamental solutions, obtained by setting one free variable to 1 and the rest to 0 (and then working out the values of the other variables $y$ and $u$ by substituting into the equations).

By substituting into the equations $R\mathbf{x}=\mathbf{0}$, which are

 $\displaystyle y+2z+3v$ $\displaystyle=0$ $\displaystyle u+4v$ $\displaystyle=0,$

you can check that the fundamental solution corresponding to $x=1,z=v=0$ is

 $\begin{pmatrix}1&0&0&0&0\end{pmatrix}^{T},$

the fundamental solution in which $z=1,x=v=0$

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

and the fundamental solution corresponding to $v=1,x=z=0$ is

 $\begin{pmatrix}0&-3&0&-4&1\end{pmatrix}^{T}$

It’s possible to write down a general expression for the fundamental solutions of a system $R\mathbf{x}=\mathbf{0}$: with the notation above, for each $1\leqslant j\leqslant k$ the $j$th fundamental solution $\mathbf{s}_{j}$ to $R\mathbf{x}=\mathbf{0}$ is

 $\mathbf{s}_{j}=\mathbf{e}_{d_{j}}-\sum_{i=1}^{r}r_{i,d_{j}}\mathbf{e}_{c_{i}}$

where $R=(r_{ij})$ and $\mathbf{e}_{j}$ denotes, as usual, the $j$th standard basis vector. We won’t use this expression in MATH0005 so I won’t prove it here.

The reason we are interested in fundamental solutions is that they have an important property: any solution to $R\mathbf{x}=\mathbf{0}$ can be written uniquely as a linear combination of the fundamental solutions. This property is expressed by saying that the fundamental solutions form a basis of the space of solutions of $R\mathbf{x}=\mathbf{0}$: we will look at bases for the solution space the final chapter of MATH0005.

###### Corollary 3.11.1.

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

In terms of systems of linear equations, this says that homogeneous linear system with more variables than equations 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 per row. It must therefore contain a column with no leading entry, and so there is a fundamental solution which is not the zero vector as one of its entries is 1. ∎

The number $r$ of leading entries in the RREF form of a $m\times n$ matrix $A$ is called the rank of $A$, and the number $k$ of columns with no leading entry is its nullity. The fact that $r+k=n$ is called the rank-nullity theorem, which we will return to in a more general context in the final chapter of MATH0005 on linear algebra.