Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
4  
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
1  
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
2  
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
add comment

2 Answers

up vote 1 down vote accepted

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$).

share|improve this answer
    
Thanks! That's a very intuitive way of looking at it. –  Matt Gregory Jul 18 '12 at 14:31
add comment

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).

share|improve this answer
    
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
1  
@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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.