Let be some matrix, we want to prove that every matrix is row equivalent to exactly one reduced echelon matrix.
Let us assume that a matrix is row equivalent to more than one reduced echelon matrix. Specifically, suppose there exist two reduced echelon matrices and such that both are row equivalent to .
Since both and are row equivalent to , there exist sequences of row operations that transform into and into .
Since row operations preserve the pivot positions, the pivot positions in must be the same as those in . Similarly, the pivot positions in must also match those in .
Since both and are in reduced echelon form and have the same pivot positions, they must be identical. This contradicts our assumption that and are distinct reduced echelon matrices. Therefore, the assumption that a matrix can be row equivalent to more than one reduced echelon matrix is false. It follows that every matrix is row equivalent to exactly one reduced echelon matrix.
For this proof, since it is an "if and only if," we need to prove both the forward phase (denoted as ) and the backward phase (denoted as ) of the theorem.
Lets first do the forward phase of the proof: A linear system is consistent if the rightmost column of the augmented matrix is not a pivot column.
Lets assume that a linear system is consistent if the rightmost column of the augmented matrix is a pivot column. Now, let be the augmented matrix for this system, and let be in reduced echelon form. We can denote the columns of as , where is the augmented column. Recall that all values above and below a pivot position are zeroed out, and since we have a pivot position in our augmented column, we have a row in the form , where is the pivot position.
Looking at this system as an equation, we get , where is non-zero (by the definition of pivot position). Since is non-zero, we have , which is an inconsistent system since cannot equal a non-zero number. This is a contradiction to our original assumption that a linear system is consistent if the rightmost column of the augmented matrix is a pivot column.
Now, lets do the backward phase: If the rightmost column of the augmented matrix is not a pivot column, then the linear system is consistent.
Assume that if the rightmost column of the augmented matrix is not a pivot column, then the linear system is inconsistent. In reduced echelon form, this implies that there will never be a row in the form with , because we originally stated that the rightmost column of the augmented matrix is not a pivot column. Since no contradictions arise from this, the system must be consistent. Therefore, if the rightmost column is not a pivot column, then the system is consistent.