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

• Sep 9th 2010, 07:24 AM
math2009
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)$
• Sep 9th 2010, 12:55 PM
NonCommAlg
Quote:

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

It should be

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

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

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