Proof of Theorem RCLS

(⇐) The first half of the proof begins with the assumption that column $n+1$ of $B$ is a pivot column. Then the leading 1 of row $r$ is located in column $n+1$ of $B$ and so row $r$ of $B$ begins with $n$ consecutive zeros, finishing with the leading 1. This is a representation of the equation $0=1$, which is false. Since this equation is false for any collection of values we might choose for the variables, there are no solutions for the system of equations, and the system is inconsistent.

(⇒) For the second half of the proof, we wish to show that if we assume the system is inconsistent, then column $n+1$ of $B$ is a pivot column. But instead of proving this directly, we will form the logically equivalent statement that is the contrapositive, and prove that instead (see Proof Technique CP). Turning the implication around, and negating each portion, we arrive at the logically equivalent statement: if column $n+1$ of $B$ is not a pivot column, then the system of equations is consistent.

If column $n+1$ of $B$ is not a pivot column, the leading 1 for row $r$ is located somewhere in columns 1 through $n$. Then every preceding row's leading 1 is also located in columns 1 through $n$. In other words, since the last leading 1 is not in the last column, no leading 1 for any row is in the last column, due to the echelon layout of the leading 1's (Definition RREF). We will now construct a solution to the system by setting each dependent variable to the entry of the final column in the row with the corresponding leading 1, and setting each free variable to zero. That sentence is pretty vague, so let us be more precise. Using our notation for the sets $D$ and $F$ from the reduced row-echelon form (Definition RREF): \begin{align*} x_{d_i}&=\matrixentry{B}{i,n+1},\quad 1\leq i\leq r & x_{f_i}&=0,\quad 1\leq i\leq n-r \end{align*}

These values for the variables make the equations represented by the first $r$ rows of $B$ all true (convince yourself of this). Rows numbered greater than $r$ (if any) are all zero rows, hence represent the equation $0=0$ and are also all true. We have now identified one solution to the system represented by $B$, and hence a solution to the system represented by $A$ (Theorem REMES). So we can say the system is consistent (Definition CS).