# Thread: Need help with a basic proof.

1. ## Need help with a basic proof.

I need to prove: "A system of equations Ax = b is consistent if and only if the rank of A equals the rank of [A|b]. I believe this is true, but I'm not sure of a theorem that supports my claim.

Any ideas?

I need to prove: "A system of equations Ax = b is consistent if and only if the rank of A equals the rank of [A|b]. I believe this is true, but I'm not sure of a theorem that supports my claim.

Any ideas?
For this, let's use rank = column rank = number of nonzero columns in RREF.

Then, it is clear that the rank of [A|b] cannot be smaller than the rank of A; any set of linearly independent columns in A remains so in A. So either they have the same rank, or the rank of [A|b] increases by 1.

Now, suppose rank(A) = r, and rank([A|b]) = r+1. Then the matrix [A|b] has r+1 nonzero columns in RREF. Note that, if we reduce [A|b] to RREF, and then ignore the last column, what remains is the (unique) RREF for A. (Simply check that all of the conditions for RREF hold if we delete columns from the end of the matrix.) Thus, among these colums, we have exactly r of them nonzero (since rank(A)=1). We conclude that the last column must be nonzero in RREF, to make the rank work out to r+1.

Suppose the first "1" in the last column, then, appears in row k. Since we are in RREF, there may be no nonzero entries to the left of this entry. Translating this back into equations, this corresponds to an equation of the form 0=1. So the system is inconsistent.

This proves (==>) (by contrapositive, I suppose). For (<==), if the ranks are equal, then adding the column b does not give us another linearly independent column. Again note that, for the matrix [A|b], putting [A|b] in RREF gives the RREF for A in the columns not corresponding to b. Consider now the coluimns of the "A" part; we must have r linearly independent ones. But then the "b" column may not have a "1" in any position where there is not already a nonzero entry in that row, for otherwise, this column would be linearly independent from the rest, and the rank of [A|b] would be r+1.

It follows that, reducing the system, we get no equations of the form 0=1. So the system is consistent.