Results 1 to 2 of 2

Math Help - Need help with a basic proof.

  1. #1
    Newbie
    Joined
    Oct 2010
    Posts
    17

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Nov 2010
    Posts
    193
    Quote Originally Posted by addieandjack View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Basic proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 25th 2010, 09:26 PM
  2. Please look at this basic proof.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 26th 2010, 06:39 PM
  3. Basic proof.
    Posted in the Algebra Forum
    Replies: 4
    Last Post: November 23rd 2009, 12:27 AM
  4. Basic proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 17th 2009, 12:14 PM
  5. Basic proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: June 30th 2007, 08:11 AM

Search Tags


/mathhelpforum @mathhelpforum