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

• Sep 9th 2010, 07:24 AM
math2009
Proof: rank(AB)+n >= rank(A)+rank(B)
$
A\in R^{s\times n}~,~B\in R^{n\times s}
$

Proof:
$
rank(AB)+n \geqslant rank(A)+rank(B)$
• Sep 9th 2010, 12:55 PM
NonCommAlg
Quote:

Originally Posted by math2009
$
A\in R^{s\times n}~,~B\in R^{n\times t}
$

Proof:
$
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).$
• Sep 9th 2010, 03:03 PM
math2009
I make a mistake

It should be

$A\in R^{s\times n}~,~B\in R^{n\times t}$
• Sep 9th 2010, 03:56 PM
NonCommAlg
Quote:

Originally Posted by math2009
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.
• Sep 9th 2010, 05:28 PM
math2009
The key is constructing a transformation.

It's different with normal $T:\mathbb{R}^{m}\rightarrow \mathbb{R}^{n}$