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$

Clearly we can choose any value for $z$ and this will uniquely determine the values of the other three variables through the equations $x=2-2z,y=3-4z,w=4$ . The general solution is

\begin{pmatrix}x\\ y\\ z\\ w\end{pmatrix}=\begin{pmatrix}2-2z\\ 3-4z\\ z\\ 4\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. ∎

To give the general solution of a system of linear equations means to identify the free variables by putting the system into RREF and then give an expression for the pivot variables in terms of the free variables. Here is another example of finding a general solution of a system of linear equations.

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