# Proving a linear system $A\bf{x} = \bf{b}$ is consistent iff the rank of ($A\;|\;\bf{b}$) equals the rank of $A$

Prove that a linear system $A\bf{x} = \bf{b}$ is consistent if and only if the rank of ($A\;|\;\bf{b}$) equals the rank of A.

I can see that it's impossible for the rank of ($A\;|\;\bf{b}$) to be less than the rank of $A$, and if the rank of ($A\;|\;\bf{b}$) is greater than the rank of $A$, then in echelon form we'll have something like:

$$(A\;|\;\bf{b}) = \left[\begin{array}{rrrr|r}1 & 2 & 3 & 4 & 5 \\ 0 & 1 & 2 & 3 & 7 \\ 0 & 0 & 0 & 1 & 3 \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0\end{array}\right]$$

which is clearly inconsistent, but I don't know how to express it. I think I need to say that $\bf{b}$ is not in the column space of A.

-
But that's just what you're proving -- one definition of the rank is "the dimension of the column space". So if the dimension of the column space of $[A\mid\mathbf b]$ is larger than the dimension of the column space of $A$ itself, it must be because $\mathbf b$ is outside the smaller space -- otherwise adding it in would not increase the dimension. – Henning Makholm Apr 15 '12 at 14:15
Ah, okay! I see now. I knew I was missing something dumb. Thank you! – Matt Gregory Apr 15 '12 at 14:20
To follow up on Henning's nice answer, you can reason through this problem without any use of row reduction (Gaussian elimination). The key is to remember the interpretation that $Ax = b$ has a solution if and only if $b$ is in the column space of $A$. – Michael Joyce Apr 15 '12 at 14:20
The rank of a matrix is the number of nonzero rows in an echelon form. An echelon form of $[A|b]$ also gives an echelon form of $A$. So if the rank of $[A|b]$ exceeds the rank of $A$, then there is a row of $[A|b]$ with zeroes in all entries except for the last entry. – David Mitra Apr 15 '12 at 14:22
Thanks you guys! But why don't you put your answers in the answer part? I don't know why people put answers in the comments. – Matt Gregory Apr 15 '12 at 14:40

I'll assume the definition of the rank of a matrix as the dimension of the space spanned by its columns, which space is the image of the linear map $\mathbb x\mapsto A\,\mathbb x$ that is represented by $A$. Clearly the rank of $(A~b)$ cannot be less than that of $A$. Now obviously $A\,\mathbf x=\mathbf b$ has a solution if and only if $\mathbb b$ is in the image of the linear map represented by $A$, and this means that adding $\mathbb b$ as an additional column to $A$ does not increase the rank, so it stays equal. Conversely, if $A\,\mathbf x=\mathbf b$ does not have a solution then $\mathbb b$ is not in the mentioned image, so adding $\mathbf b$ strictly increases the span of the columns of the matrix, and therefore the rank (by $1$).

-
Thanks! That's a very intuitive way of looking at it. – Matt Gregory Jul 18 '12 at 14:31

I would first show, or appeal to, the following:

$\ \ 1)$ The rank of a matrix is the number of nonzero rows in an echelon form of the matrix.

$\ \ 2)$ An echelon form of $[A\,|\,\bf b]$ also gives an echelon form of A.

So the rank of $[A\,|\,\bf b]$ as at least the rank of $A$ and if the rank of $[A\,|\,\bf b]$ exceeds the rank of $A$, then there is a row of $[A\,|\,\bf b]$ with zeroes in all entries except for the last entry (that is you have an echelon form as in your post).

-
It seems like there ought to be a more rigorous way to say that "there is a row of an augmented matrix with zeroes in all entries except for the last entry, therefore it's inconsistent", but I guess if people regard that as being okay, I should accept it. – Matt Gregory Apr 15 '12 at 14:50
@MattGregory Phrased differently: If $C$ has exactly $n$ non-zero rows and $[C|D]$ has $n+1$ nonzero rows, then one of the non-zero rows of $[C|D]$ must correspond to a zero row of $C$. – David Mitra Apr 15 '12 at 15:21