3 Matrices 3.10 RREF existence and uniqueness 3.12 Invertibility and RREF

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}<c_{2}<\cdots<c_{r}$ , 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<d_{k}$ , 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.