Results 1 to 5 of 5

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

  1. #1
    Member
    Joined
    Jan 2009
    Posts
    153

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

    $\displaystyle
    A\in R^{s\times n}~,~B\in R^{n\times s}
    $

    Proof:
    $\displaystyle
    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
    $\displaystyle
    A\in R^{s\times n}~,~B\in R^{n\times t}
    $

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

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

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

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

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

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

    but $\displaystyle rank(f)=\dim im(f) \leq \dim \ker T_1=nul(T_1)$ and $\displaystyle 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:

    $\displaystyle 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; Sep 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

    $\displaystyle 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

    $\displaystyle 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 $\displaystyle 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: Dec 9th 2011, 12:10 AM
  2. Replies: 3
    Last Post: Aug 20th 2010, 05:32 AM
  3. Rank(T) = Rank(L_A) proof?
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: Jul 17th 2010, 08:22 PM
  4. Row rank and column rank
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: Apr 13th 2010, 07:40 AM
  5. Short proof that rows-rank=column-rank?
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: Jun 26th 2009, 10:02 AM

Search tags for this page

Search Tags


/mathhelpforum @mathhelpforum