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 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. ∎