Derive: Lists of Numbers That Do Things

Let $E$ be the product of the row moves that carry $A$ to the cleared table $B=EA$. Every permitted move is reversible, as section 7.5 shows, so $E$ is invertible. For any coefficient list $x$, $$Ax=0\text{exactly when}EAx=Bx=0.$$ So $A$ and $B$ have the same linear relations among their columns. Two facts about $B$ now finish the proof. First, the pivot columns of $B$ are independent: if a combination of them is zero, take the lowest pivot and read the equation in its pivot row. That row contains no later pivot, so the coefficient of the lowest pivot is zero; then move upward, and every coefficient is zero in turn. Second, there are as many pivot columns as nonzero rows of $B$, and the nonzero rows are independent, so the pivot columns of $B$ span the column space of $B$. Hence the pivot columns of $B$ form a basis of that column space.

Now transfer the basis back to $A$. The pivot columns of $A$ are independent, because a vanishing combination of them would give the same vanishing combination of the pivot columns of $B$. To see that they span the column space of $A$, take any column $A_j$. Its image $B_j$ is a combination of the pivot columns of $B$; write $B_j={\sum }_i{c}_i{B}_{p_i}$. Then $$B\left(A_j-\sum _i{c}_i{A}_{p_i}\right)=B_j-\sum _i{c}_i{B}_{p_i}=0,$$ and the relation is shared with $A$, so $A_j={\sum }_i{c}_i{A}_{p_i}$. The pivot columns of $A$ therefore span every column of $A$. They form a basis, and the rank is their number. The kernel is the set of $x$ with $Bx=0$. In the cleared table each pivot variable is fixed once the non-pivot variables are chosen, and each non-pivot column contributes one free choice, so the kernel has dimension equal to the number of columns without a pivot. This is the ledger of section 7.6, read off from the elimination of section 7.5.

For the example, subtract twice the first row from the second and the first row from the third: $$\left(\begin{array}{cccc}1& 2& 3& 4\\ 0& 0& 1& 1\\ 0& 0& 2& 3\end{array}\right).$$ Now subtract twice the new second row from the new third row: $$\left(\begin{array}{cccc}1& 2& 3& 4\\ 0& 0& 1& 1\\ 0& 0& 0& 1\end{array}\right).$$ The pivots sit in columns $1$, $3$ and $4$, so those columns of the original table form a basis of the column space: $(1,2,1)$, $(3,7,5)$ and $(4,9,7)$. The rank is $3$. Column $2$ is the only column without a pivot, so the kernel has dimension $4-3=1$. Solve $Bx=0$ from the bottom up. The third row gives $x_4=0$. The second gives $x_3+x_4=0$, so $x_3=0$. The first gives $x_1+2x_2=0$, so $x_1=-2x_2$. The kernel is the line of multiples of $(-2,1,0,0)$, which is one basis vector, as the count predicted.

The rank counts independent rows, and a table with two rows has at most two of them, so $\mathrm{rank}A\le 2$. The ledger of section 7.6 gives $$\dim \ker A=3-\mathrm{rank}A\ge 3-2=1.$$ A kernel of dimension at least one contains a nonzero vector, so some nonzero input vanishes. This is an edge case of the ledger rather than a fact about the particular entries: every machine from three inputs to two outputs must lose at least one dimension, and no such machine can be one-to-one. If $Ax=b$ has one solution, it has a whole line of them, by the argument of section 7.4.

For the example, the second row is twice the first, so the rows are dependent and the rank is $1$. The kernel is the set of $(x,y,z)$ with $x+2y+3z=0$. Choose $y=1$ and $z=0$: then $x=-2$, giving $(-2,1,0)$. Choose $y=0$ and $z=1$: then $x=-3$, giving $(-3,0,1)$. Both vanish against both rows, and neither is a multiple of the other, so they are independent. The kernel has dimension $3-1=2$, and these two vectors are a basis. The image has dimension $1$, spanned by the common column direction $(1,2)$.

Suppose $x=x_p+k$ with $Ak=0$. Linearity gives $$Ax=A(x_p+k)=A{x}_p+Ak=b+0=b,$$ so every list of that form solves the system. Conversely, suppose $Ax=b$. Put $k=x-x_p$. Then $$Ak=Ax-A{x}_p=b-b=0,$$ so $k$ lies in the kernel and $x=x_p+k$. The two directions prove that the solution set is exactly the translate of the kernel by one particular solution. The system has a unique solution exactly when the kernel is the single zero list, which is the uniqueness test of section 7.4.

For the example, the rows read $x+y+z=6$ and $x+2y+3z=10$. Subtract the first equation from the second: $y+2z=4$, so $y=4-2z$. Substitute into the first: $x+(4-2z)+z=6$, so $x=2+z$. Put $z=0$ to obtain the particular solution $x_p=(2,4,0)$; check it: $2+4+0=6$ and $2+8+0=10$. For the kernel, set the right-hand side to zero. The same subtraction gives $y+2z=0$, so $y=-2z$, and then $x=-y-z=2z-z=z$. With $z=1$ the kernel vector is $(1,-2,1)$, and it is the only basis vector because the kernel has dimension $3-2=1$. The general solution is therefore $$\left(\begin{array}{c}x\\ y\\ z\end{array}\right)=\left(\begin{array}{c}2\\ 4\\ 0\end{array}\right)+t\left(\begin{array}{c}1\\ -2\\ 1\end{array}\right)=\left(\begin{array}{c}2+t\\ 4-2t\\ t\end{array}\right).$$ At $t=1$ this gives $(3,2,1)$, which satisfies $3+2+1=6$ and $3+4+3=10$. Every choice of $t$ gives another solution, and every solution arises from one choice of $t$.