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

1. ## 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)$

2. 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).$

3. I make a mistake

It should be

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

4. 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.

5. The key is constructing a transformation.

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

,

,

,

,

,

,

,

,

,

# rank a b ranka rankb

Click on a term to search for related topics.