Results 1 to 5 of 5

Math Help - Proof: rank(AB)+n >= rank(A)+rank(B)

  1. #1
    Member
    Joined
    Jan 2009
    Posts
    153

    Proof: rank(AB)+n >= rank(A)+rank(B)

    <br />
A\in R^{s\times n}~,~B\in R^{n\times s}<br />

    Proof:
    <br />
rank(AB)+n \geqslant rank(A)+rank(B)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by math2009 View Post
    <br />
A\in R^{s\times n}~,~B\in R^{n\times t}<br />

    Proof:
    <br />
rank(AB)+n \geqslant rank(A)+rank(B)
    this is a nice problem! i think by that R you mean the field of real numbers \mathbb{R}. well, you really don't need your ground field to be \mathbb{R}. so i'll assume that F is any field and A and B are

    s \times n and n \times t matrices respectively, with entries in F. let T_1,T_2 be the linear transformations corresponding to A and B respectively, i.e. T_1: F^n \to F^s and T_2: F^t \to F^n

    are defined by T_1(x)=Ax for all x \in F^n and T_2(x)=Bx for all x \in F^t.

    claim. nul(T_1T_2) \leq nul(T_1) + nul(T_2), where nul means "dimension of the kernel".

    proof. define f: \ker (T_1T_2) \to \ker T_1 by f(x)=T_2(x) for all x \in \ker(T_1T_2). note that f is well-defined because if x \in \ker(T_1T_2), then T_1T_2(x)=0 and thus

    f(x)=T_2(x) \in \ker T_1. it's obvious that f is linear and \ker f = \ker T_2. therefore, by the rank-nulity theorem, we have rank(f)+nul(f)=\dim \ker(T_1T_2)=nul(T_1T_2).

    but rank(f)=\dim im(f) \leq \dim \ker T_1=nul(T_1) and nul(f)=\dim \ker(f)=\dim \ker T_2 =nul(T_2). \Box

    now solving your problem is easy: applying the above claim and the rank-nulity theorem we have:

    rank(T_1T_2)+n=t-nul(T_1T_2)+n \geq n-nul(T_1)+ t-nul(T_2)=rank(T_1) + rank(T_2).
    Last edited by NonCommAlg; September 9th 2010 at 03:52 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jan 2009
    Posts
    153
    I make a mistake

    It should be

     A\in R^{s\times n}~,~B\in R^{n\times t}
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by math2009 View Post
    I make a mistake

    It should be

     A\in R^{s\times n}~,~B\in R^{n\times t}
    well, it really doesn't matter. the proof still works. see my edited proof.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Jan 2009
    Posts
    153
    The key is constructing a transformation.

    It's different with normal T:\mathbb{R}^{m}\rightarrow \mathbb{R}^{n}
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Row Rank = Column Rank?
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: December 9th 2011, 12:10 AM
  2. Replies: 3
    Last Post: August 20th 2010, 05:32 AM
  3. Rank(T) = Rank(L_A) proof?
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: July 17th 2010, 08:22 PM
  4. Row rank and column rank
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: April 13th 2010, 07:40 AM
  5. Short proof that rows-rank=column-rank?
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: June 26th 2009, 10:02 AM

Search Tags


/mathhelpforum @mathhelpforum