Solving Ax = b: Row Reduced Form R

The goal: completely solve Ax = b

This is the lecture where we completely solve linear equations. Given $A\mathbf{x} = \mathbf{b}$, three things can happen: no solution, exactly one, or a whole family of them. Elimination has to identify which case we’re in — and when solutions exist, find them all.

Strang reuses the matrix from the null space lecture:

$$A = \begin{bmatrix} 1 & 2 & 2 & 2 \\ 2 & 4 & 6 & 8 \\ 3 & 6 & 8 & 10 \end{bmatrix}$$

The main point last time is still the main point: row three is the sum of rows one and two. So before doing anything, you can predict what elimination will discover about the right-hand side. If the left-hand sides of equations one and two add up to the left-hand side of equation three, then the right-hand sides must too: we’ll need $b_1 + b_2 = b_3$. Take $b_1 = 1$, $b_2 = 5$ — then the only acceptable $b_3$ is $6$. If some combination of the left-hand sides gives all zeros, the same combination of the right-hand sides must give zero.

To watch elimination discover this, handle the right-hand side the honest way: do the same thing to it that you do to the rows of $A$. Tack $\mathbf{b}$ on as an extra column — the augmented matrix $\begin{bmatrix} A & \mathbf{b} \end{bmatrix}$. (In Matlab, that’s all you’d type.) Eliminate:

$$\left[\begin{array}{cccc|c} 1 & 2 & 2 & 2 & b_1 \\ 2 & 4 & 6 & 8 & b_2 \\ 3 & 6 & 8 & 10 & b_3 \end{array}\right] \longrightarrow \left[\begin{array}{cccc|c} 1 & 2 & 2 & 2 & b_1 \\ 0 & 0 & 2 & 4 & b_2 - 2b_1 \\ 0 & 0 & 0 & 0 & b_3 - b_2 - b_1 \end{array}\right]$$

The last row says $0 = b_3 - b_2 - b_1$. That’s the condition for solvability — exactly what we expected.

When is Ax = b solvable?

The equivalence of those two statements isn’t immediate — but somehow they must agree, Strang notes, because each is equivalent to the solvability of the system.

For our example, take the good right-hand side $\mathbf{b} = (1, 5, 6)$. Elimination turns it into $1$, then $5 - 2(1) = 3$, then $6 - 5 - 1 = 0$. The last equation reads $0 = 0$ — fine. We’re left with two genuine equations in four unknowns, so we expect not just one solution but a whole bunch.

Step one: a particular solution

Question zero — does a solution exist? — is answered. Now construct the solutions. This is the algorithm you’ll follow on the quiz and the final.

Step one: find one particular solution $\mathbf{x}_p$. Since there are lots of solutions, you could find a particular one your own way, but here’s the natural way:

Here the pivots sit in columns 1 and 3, so $x_2$ and $x_4$ are free — they live in the columns without pivots. Set $x_2 = x_4 = 0$. The free columns drop out and the eliminated system collapses to

$$\begin{aligned} x_1 + 2x_3 &= 1 \\ 2x_3 &= 3 \end{aligned}$$

We’re back in the normal case where back substitution does it: $x_3 = \tfrac{3}{2}$, then $x_1 = 1 - 2x_3 = -2$. So

$$\mathbf{x}_p = \begin{bmatrix} -2 \\ 0 \\ \tfrac{3}{2} \\ 0 \end{bmatrix}$$

On the quiz, please: plug it back into the original system and check. All those row operations were supposed to preserve the solutions, and they do.

The complete solution: x = xp + xn

One solution isn’t all of them. The point is that you can add on anything from the null space:

$$\mathbf{x}_{\text{complete}} = \mathbf{x}_p + \mathbf{x}_n$$

Why does this pattern work — the pattern that shows up all through mathematics, everywhere there are linear equations? One line:

$$A(\mathbf{x}_p + \mathbf{x}_n) = A\mathbf{x}_p + A\mathbf{x}_n = \mathbf{b} + \mathbf{0} = \mathbf{b}$$

Anything in the null space has right-hand side zero, so adding it keeps the right-hand side correct. For our example, the null space was computed last time: two free variables, so two special solutions — one per free variable, with a $1$ in that free slot and $0$ in the other, pivot variables filled in from the equations $x_1 + 2x_2 + 2x_3 + 2x_4 = 0$ and $2x_3 + 4x_4 = 0$. The complete solution is

$$\mathbf{x} = \begin{bmatrix} -2 \\ 0 \\ \tfrac{3}{2} \\ 0 \end{bmatrix} + c_1 \begin{bmatrix} -2 \\ 1 \\ 0 \\ 0 \end{bmatrix} + c_2 \begin{bmatrix} 2 \\ 0 \\ -2 \\ 1 \end{bmatrix}$$

with any constants $c_1, c_2$. Is there a free constant multiplying $\mathbf{x}_p$? No way — $\mathbf{x}_p$ solves $A\mathbf{x}_p = \mathbf{b}$, and you’re not allowed to multiply that by three. But $\mathbf{x}_n$ you can scale and combine freely, because the right side stays zero. One particular guy, plus a whole subspace.

That’s the picture and that’s the algorithm: eliminate, check $0 = 0$ on the zero rows, find the particular solution, find the special solutions, add.

Thinking bigger: full column rank and full row rank

Now the bigger picture. Let $A$ be $m$ by $n$ with rank $r$ — and our current definition of rank is the number of pivots. Since $m$ rows can hold at most $m$ pivots, and a column can’t have more than one pivot, always

$$r \le m \qquad \text{and} \qquad r \le n$$

The special interest is full rank, when $r$ is as big as it can be — and there are two separate ways that can happen.

Full column rank: $r = n$. Every column has a pivot, so no free variables at all. The null space contains only the zero vector — there are no free variables to give other values to. So the complete solution is just $\mathbf{x} = \mathbf{x}_p$, if a solution exists: there are either zero or one solutions. In many real applications the columns are independent (Strang’s later word) and this is exactly the situation.

Full row rank: $r = m$. Every row has a pivot, so elimination produces no zero rows — there are no requirements on $\mathbf{b}$ at all. A solution exists for every right-hand side. And how many variables are free? Of the $n$ variables, $r = m$ are used up as pivot variables, leaving $n - m$ free variables.

The best example is just the transpose of the last one:

$$A = \begin{bmatrix} 1 & 2 & 6 & 5 \\ 3 & 1 & 1 & 1 \end{bmatrix}$$

Rank 2 again — two pivots, in columns 1 and 2. The reduced form is $R = \begin{bmatrix} I & F \end{bmatrix}$: the pivot columns become the identity, no zero rows, and the “stuff” $F$ over on the right is what enters the special solutions and the null space.

The whole picture: four cases

Finally the corner case, the most important of all: $r = m = n$. The matrix is square and full rank — no need to say full column or full row rank, because the counts agree. That’s exactly the invertible matrices, the square nice chapter-two case. Example: $A = \begin{bmatrix} 1 & 2 \\ 3 & 1 \end{bmatrix}$. Its reduced row echelon form is $R = I$ — the good matrices come out trivially in $R$. Null space: the zero vector only. Conditions on $\mathbf{b}$: none at all. One solution, always.

The full summary, which Strang says summarizes the whole lecture:

Case	Reduced form $R$	Solutions to $A\mathbf{x} = \mathbf{b}$
$r = m = n$	$I$	exactly $1$
$r = n$, $r$ less than $m$	$\begin{bmatrix} I \\ 0 \end{bmatrix}$	$0$ or $1$
$r = m$, $r$ less than $n$	$\begin{bmatrix} I & F \end{bmatrix}$	infinitely many ($1$ or $\infty$, and the null space is never trivial)
$r$ less than $m$, $r$ less than $n$	$\begin{bmatrix} I & F \\ 0 & 0 \end{bmatrix}$	$0$ or $\infty$

(One caution from the board: in the wide cases the $F$ columns can be mixed into the $I$ — the pivot columns aren’t necessarily the first ones.)

Problems

Work these before revealing the solutions — the algorithm from the lecture carries you through each one.

Problem 8.1 Solvability condition on b

Use elimination on the augmented matrix to find the condition on $b_1, b_2, b_3$ for

$$\begin{bmatrix} 1 & 3 & 1 \\ 2 & 6 & 4 \\ 3 & 9 & 5 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} b_1 \\ b_2 \\ b_3 \end{bmatrix}$$

to be solvable. Explain the condition using a combination of the rows of $A$.

Show solution

Eliminate on $\begin{bmatrix} A & \mathbf{b} \end{bmatrix}$. Row 2 minus $2 \times$ row 1, and row 3 minus $3 \times$ row 1:

$$\left[\begin{array}{ccc|c} 1 & 3 & 1 & b_1 \\ 0 & 0 & 2 & b_2 - 2b_1 \\ 0 & 0 & 2 & b_3 - 3b_1 \end{array}\right]$$

Row 3 minus row 2:

$$\left[\begin{array}{ccc|c} 1 & 3 & 1 & b_1 \\ 0 & 0 & 2 & b_2 - 2b_1 \\ 0 & 0 & 0 & b_3 - b_2 - b_1 \end{array}\right]$$

The zero row demands $b_3 - b_2 - b_1 = 0$, i.e. $b_3 = b_1 + b_2$.

Row explanation: row 1 plus row 2 equals row 3 in $A$ (check: $1+2=3$, $3+6=9$, $1+4=5$), so that combination of rows gives the zero row after subtraction — and the same combination of the entries of $\mathbf{b}$ must give the zero number.

Problem 8.2 Complete solution xp + xn

Find the complete solution of

$$\begin{bmatrix} 1 & 2 & 3 \\ 2 & 4 & 8 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} 1 \\ 4 \end{bmatrix}$$

following the algorithm: particular solution first, then the null space.

Show solution

Eliminate: row 2 minus $2 \times$ row 1 gives

$$\left[\begin{array}{ccc|c} 1 & 2 & 3 & 1 \\ 0 & 0 & 2 & 2 \end{array}\right]$$

Pivots in columns 1 and 3; the free variable is $x_2$.

Particular solution: set $x_2 = 0$. Then $2x_3 = 2$ gives $x_3 = 1$, and $x_1 = 1 - 3x_3 = -2$. So $\mathbf{x}_p = (-2, 0, 1)$.

Null space: set $x_2 = 1$ and solve $A\mathbf{x} = \mathbf{0}$: the second equation gives $2x_3 = 0$, so $x_3 = 0$, and $x_1 = -2x_2 - 3x_3 = -2$. Special solution $(-2, 1, 0)$.

Complete solution:

$$\mathbf{x} = \begin{bmatrix} -2 \\ 0 \\ 1 \end{bmatrix} + c \begin{bmatrix} -2 \\ 1 \\ 0 \end{bmatrix} \quad \text{for any } c.$$

Geometrically, a line in $\mathbb{R}^3$ through $(-2, 0, 1)$ — parallel to the null space, but not through the origin. Check $\mathbf{x}_p$ in the original system: $-2 + 0 + 3 = 1$ and $-4 + 0 + 8 = 4$.

Problem 8.3 Full column rank, r = n

The tall thin matrix

$$A = \begin{bmatrix} 1 & 2 \\ 1 & 3 \\ 2 & 1 \end{bmatrix}$$

has rank 2 (full column rank). (a) What is its null space? (b) Find the condition on $b_1, b_2, b_3$ for $A\mathbf{x} = \mathbf{b}$ to be solvable. (c) Solve completely when $\mathbf{b} = (3, 4, 3)$.

Show solution

(a) Two columns, two pivots: no free variables, so $N(A)$ is the zero vector only.

(b) Eliminate on the augmented matrix. Row 2 minus row 1, and row 3 minus $2 \times$ row 1:

$$\left[\begin{array}{cc|c} 1 & 2 & b_1 \\ 0 & 1 & b_2 - b_1 \\ 0 & -3 & b_3 - 2b_1 \end{array}\right]$$

Row 3 plus $3 \times$ row 2:

$$\left[\begin{array}{cc|c} 1 & 2 & b_1 \\ 0 & 1 & b_2 - b_1 \\ 0 & 0 & b_3 + 3b_2 - 5b_1 \end{array}\right]$$

Condition: $b_3 + 3b_2 - 5b_1 = 0$. Most right-hand sides fail it — three equations, two unknowns.

(c) $\mathbf{b} = (3, 4, 3)$: check $3 + 12 - 15 = 0$, so it’s solvable. Back-substitute: $x_2 = 4 - 3 = 1$, then $x_1 = 3 - 2x_2 = 1$. Since the null space is trivial, $\mathbf{x} = (1, 1)$ is the only solution — indeed $\mathbf{b}$ is exactly the sum of the two columns. Zero or one solutions in this case, and here it’s one.

Problem 8.4 Counting solutions by rank

For each matrix shape and rank below, say how many solutions $A\mathbf{x} = \mathbf{b}$ can have (for the various choices of $\mathbf{b}$), and describe the reduced form $R$:

(a) $A$ is $3 \times 3$ with $r = 3$. (b) $A$ is $2 \times 4$ with $r = 2$. (c) $A$ is $5 \times 3$ with $r = 3$. (d) $A$ is $4 \times 4$ with $r = 2$.

Show solution

(a) $r = m = n$: invertible, $R = I$. Exactly one solution for every $\mathbf{b}$.

(b) $r = m = 2$ less than $n = 4$: full row rank, $R = \begin{bmatrix} I & F \end{bmatrix}$ (with $F$ possibly mixed into $I$ if the pivot columns aren’t first). No zero rows, so solvable for every $\mathbf{b}$, with $n - m = 2$ free variables: infinitely many solutions, always.

(c) $r = n = 3$ less than $m = 5$: full column rank, $R = \begin{bmatrix} I \\ 0 \end{bmatrix}$ with two zero rows. Null space is trivial, but $\mathbf{b}$ must satisfy two conditions: zero or one solutions.

(d) $r = 2$ less than both $m = 4$ and $n = 4$: $R = \begin{bmatrix} I & F \\ 0 & 0 \end{bmatrix}$. Two conditions on $\mathbf{b}$ and two free variables: zero solutions or infinitely many.