Solving Ax = 0: Pivot Variables, Special Solutions

From definition to algorithm

Lectures five and six defined the null space and the column space — what’s in those spaces. Now Strang wants to actually describe them: how do you compute all the vectors in the null space? “This is turning the idea, the definition, into an algorithm.” The algorithm for solving $A\mathbf{x} = \mathbf{0}$.

The running example is deliberately rectangular — this whole chapter is about rectangular matrices:

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

Before any computing, Strang eyeballs it. Column two is a multiple of column one — same direction, not independent. And row one plus row two gives row three, so the third row isn’t independent either. “All that should come out of elimination.” The algorithm is elimination — but extended to the rectangular case, where we keep going even when a zero shows up in a pivot position.

One thing to hold onto throughout: elimination does not change the null space. Subtracting a multiple of one equation from another is a legitimate operation on the equations — the solutions of the system don’t move. (The column space does change, as we’ll see — you have to pay attention to what elimination leaves unchanged.) And since the right-hand side is all zeros, it stays all zeros; there’s no point writing it down.

Elimination on a rectangular matrix: the echelon form U

The first pivot is the $1$ in the corner, and you know what to do with it. Subtract $2$ times row one from row two, and $3$ times row one from row three:

$$\begin{bmatrix} 1 & 2 & 2 & 2 \\ 2 & 4 & 6 & 8 \\ 3 & 6 & 8 & 10 \end{bmatrix} \;\longrightarrow\; \begin{bmatrix} \boxed{1} & 2 & 2 & 2 \\ 0 & 0 & 2 & 4 \\ 0 & 0 & 2 & 4 \end{bmatrix}$$

On to the second column. The pivot position holds a zero — that’s signaling a difficulty. Look below, hoping for a nonzero to row-exchange with: zero there too. What that’s really telling us is that column two is a combination of the earlier columns — it’s dependent. But we don’t stop to think; in that column there’s nothing to do, so we go on to the next column. There sits a perfectly good pivot, the $2$. The multiplier is one: subtract row two from row three, and out comes a row of zeros.

$$U = \begin{bmatrix} \boxed{1} & 2 & 2 & 2 \\ 0 & 0 & \boxed{2} & 4 \\ 0 & 0 & 0 & 0 \end{bmatrix}$$

Strang can’t quite call $U$ upper triangular — it’s in echelon form. “The word echelon means, like, staircase form”: the nonzeros come down in a staircase. That row of zeros at the bottom is elimination discovering what we saw by eye: row three was a combination of rows one and two, and elimination knocked it out.

Pivot variables, free variables, special solutions

Now solve $U\mathbf{x} = \mathbf{0}$ — same null space as $A\mathbf{x} = \mathbf{0}$. There are solutions: three equations (really two, as it turned out), four unknowns — solutions were guaranteed.

Here’s the critical step. Separate the columns into two kinds. Columns one and three hold the pivots: they are the pivot columns, and $x_1, x_3$ are the pivot variables. Columns two and four are the free columns, and $x_2, x_4$ are the free variables. Why “free”? Because we may assign any numbers to $x_2$ and $x_4$, freely — and then the equations determine $x_1$ and $x_3$ by back substitution. In equations, $U\mathbf{x} = \mathbf{0}$ says

$$\begin{aligned} x_1 + 2x_2 + 2x_3 + 2x_4 &= 0 \\ 2x_3 + 4x_4 &= 0 \end{aligned}$$

First choice: set $x_2 = 1$, $x_4 = 0$ — a free choice, but a convenient one. Back up from the last equation: $x_4 = 0$ forces $x_3 = 0$; then the first equation gives $x_1 = -2$. One solution found:

$$\mathbf{x} = \begin{bmatrix} -2 \\ 1 \\ 0 \\ 0 \end{bmatrix}$$

Check what it says about the columns: minus two of column one plus one of column two is the zero column — of course, since column two is twice column one. And once we have one solution, we have a line of them: any multiple $c\,(-2, 1, 0, 0)$ is in the null space too — an infinitely long line in four-dimensional space.

Is that the whole null space? No — there are two free variables, and we’ve only made one choice. Second choice: $x_2 = 0$, $x_4 = 1$. This solution is guaranteed to be new — no multiple of the first one can put a $1$ in the fourth slot. Back substitution: $2x_3 + 4 = 0$ gives $x_3 = -2$; then $x_1 - 4 + 2 = 0$ gives $x_1 = 2$:

$$\mathbf{x} = \begin{bmatrix} 2 \\ 0 \\ -2 \\ 1 \end{bmatrix}$$

The whole null space: n − r special solutions

Now we can describe the complete null space — all solutions of $A\mathbf{x} = \mathbf{0}$. Take all combinations of the special solutions. Don’t forget the crucial plus sign:

$$\mathbf{x} = c \begin{bmatrix} -2 \\ 1 \\ 0 \\ 0 \end{bmatrix} + d \begin{bmatrix} 2 \\ 0 \\ -2 \\ 1 \end{bmatrix}$$

That’s a complete algorithm. Do elimination, pressing onward when a column offers nothing. Count the pivots — that’s $r$. Give the $n - r$ free variables their zero–one values, back-substitute for the pivot variables, and take all combinations.

Going further: the reduced row echelon form R

Strang could stop at $U$, but he wants to clean the matrix up “as good as it can be.” Two more moves. First, eliminate upwards — get zeros above the pivots as well as below. Subtracting row two of $U$ from row one turns the $2$ above the second pivot into a $0$ (and produces a $-2$ in the last column). Second, divide each row by its pivot so the pivots equal $1$ — dividing an equation by $2$ changes no solutions. The result is $R$, the reduced row echelon form:

$$R = \begin{bmatrix} 1 & 2 & 0 & -2 \\ 0 & 0 & 1 & 2 \\ 0 & 0 & 0 & 0 \end{bmatrix}$$

Matlab produces it in one command: rref(A). And $R$ carries all the information as clearly as it can be carried. Pivot rows one and two, pivot columns one and three — and sitting in those pivot rows and columns is the $2 \times 2$ identity matrix. In the free columns sits the free part $F$: the entries $2, 0$ in column two and $-2, 2$ in column four. Zero rows below, recording that the original third row was a combination of the others.

Here’s why, in block form. Pretend the pivot columns come first (a typical reduced form):

$$R = \begin{bmatrix} I & F \\ 0 & 0 \end{bmatrix} \qquad \begin{array}{l} I:\ r \times r,\ \text{the pivot columns} \\ F:\ \text{the } n - r \text{ free columns} \end{array}$$

Do all the special solutions at once by building a null space matrix $N$ whose columns are the special solutions, so that $RN = 0$ (that’s the teaching-code command null(A)). The equation $R\mathbf{x} = \mathbf{0}$ says: (pivot variables) $+\, F \cdot$ (free variables) $= \mathbf{0}$, so the pivot variables equal $-F$ times the free variables. Put the identity in the free-variable part, and $-F$ appears in the pivot part:

$$N = \begin{bmatrix} -F \\ I \end{bmatrix}$$

Back substitution, when the system has been reduced this far, is totally simple.

The same algorithm on the transpose

To practice, Strang runs the whole thing again on $A^T$ — “just for the heck of it.” Before calculating, predict: this matrix has three columns, and the third column is the sum of the first two, so we expect two pivot columns and one free column. Elimination had better discover that.

Problems

Run the lecture’s algorithm yourself — elimination, rank, free variables, special solutions — before opening the solutions.

Problem 7.1 The full algorithm

Find all solutions of $A\mathbf{x} = \mathbf{0}$ for

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

Give the rank, identify the pivot and free variables, and write the null space as all combinations of special solutions.

Show solution

Subtract $2$ times row one from row two:

$$\begin{bmatrix} 1 & 3 & 1 & 2 \\ 0 & 0 & 2 & 4 \\ 0 & 0 & 2 & 4 \end{bmatrix}$$

Column two has a zero pivot position with zeros below — move on. Column three has pivot $2$; subtract row two from row three:

$$U = \begin{bmatrix} 1 & 3 & 1 & 2 \\ 0 & 0 & 2 & 4 \\ 0 & 0 & 0 & 0 \end{bmatrix}$$

Two pivots, so $r = 2$. Pivot variables $x_1, x_3$; free variables $x_2, x_4$; there will be $4 - 2 = 2$ special solutions.

Set $x_2 = 1, x_4 = 0$: the second equation $2x_3 + 4x_4 = 0$ gives $x_3 = 0$; the first, $x_1 + 3x_2 + x_3 + 2x_4 = 0$, gives $x_1 = -3$. Special solution $(-3, 1, 0, 0)$.

Set $x_2 = 0, x_4 = 1$: $2x_3 + 4 = 0$ gives $x_3 = -2$; then $x_1 - 2 + 2 = 0$ gives $x_1 = 0$. Special solution $(0, 0, -2, 1)$.

The null space is

$$\mathbf{x} = c \begin{bmatrix} -3 \\ 1 \\ 0 \\ 0 \end{bmatrix} + d \begin{bmatrix} 0 \\ 0 \\ -2 \\ 1 \end{bmatrix}$$

Problem 7.2 Reading solutions off R

Continue Problem 7.1: reduce $U$ to the reduced row echelon form $R$, identify the identity part $I$ and the free part $F$, and confirm that the special solutions are the columns of $N$ with $-F$ in the pivot variables and $I$ in the free variables.

Show solution

Eliminate upward — subtract $\tfrac{1}{2}$ of row two from row one to clear the $1$ above the second pivot — then divide row two by $2$:

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

The identity sits in the pivot rows and pivot columns (columns one and three). The free columns (two and four) hold

$$F = \begin{bmatrix} 3 & 0 \\ 0 & 2 \end{bmatrix}$$

Then $-F$ placed in the pivot slots $x_1, x_3$ and the identity in the free slots $x_2, x_4$ gives exactly the special solutions $(-3, 1, 0, 0)$ and $(0, 0, -2, 1)$ found by back substitution: the entries $3, 0$ and $0, 2$ reappear with their signs switched. $RN = 0$ checks.

Problem 7.3 Counting with the rank

(a) A matrix $A$ is $5 \times 7$ with rank $4$. How many free variables and how many special solutions does $A\mathbf{x} = \mathbf{0}$ have? (b) For which relationship between $r$ and $n$ does the null space contain only the zero vector? (c) $B$ is $7 \times 5$ with rank $4$ — how many special solutions now? Why does the rank not change in passing from a matrix to its transpose here?

Show solution

(a) Free variables: $n - r = 7 - 4 = 3$, so there are $3$ special solutions, one per free variable.

(b) The null space is only $\mathbf{x} = \mathbf{0}$ exactly when there are no free variables: $n - r = 0$, i.e. $r = n$ — a pivot in every column.

(c) Now $n = 5$, so $n - r = 5 - 4 = 1$: one special solution. The rank is the same $4$ because, as the lecture notes, the number of pivot columns of $A$ and $A^T$ is the same — but the number of special solutions changes, since it depends on $n$, the number of columns.

Problem 7.4 Predict, then verify

The third column of

$$A = \begin{bmatrix} 1 & 2 & 3 \\ 2 & 5 & 7 \\ 3 & 9 & 12 \end{bmatrix}$$

is the sum of the first two. Before computing: what rank do you expect, and how many special solutions? Then run elimination and find the whole null space.

Show solution

Prediction: columns one and two are independent, column three depends on them — so two pivot columns, rank $2$, and $3 - 2 = 1$ special solution.

Elimination: subtract $2$ times row one from row two, and $3$ times row one from row three:

$$\begin{bmatrix} 1 & 2 & 3 \\ 0 & 1 & 1 \\ 0 & 3 & 3 \end{bmatrix} \;\longrightarrow\; U = \begin{bmatrix} 1 & 2 & 3 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \end{bmatrix}$$

(subtracting $3$ times row two from row three). Rank $2$ as predicted; $x_3$ is free.

Special solution: set $x_3 = 1$. Then $x_2 + x_3 = 0$ gives $x_2 = -1$, and $x_1 + 2(-1) + 3(1) = 0$ gives $x_1 = -1$. Check: $-\mathbf{c}_1 - \mathbf{c}_2 + \mathbf{c}_3 = \mathbf{0}$, which is exactly the dependence we spotted. The null space is the line

$$\mathbf{x} = c \begin{bmatrix} -1 \\ -1 \\ 1 \end{bmatrix}$$