15
$\begingroup$

I was looking for an answer for this problem in terms of matrices, but I really don't know how to prove this result. The proposition says that:

Let $A\in M_{m\times k}(\mathbb{C})$, $B\in M_{k\times p}(\mathbb{C})$ and $C\in M_{p\times n}(\mathbb{C})$, then $\textrm{rank}(AB)+\textrm{rank}(BC)\leq \textrm{rank}(B)+\textrm{rank}(ABC)$

$\endgroup$
2

2 Answers 2

16
$\begingroup$

Notation:

  • $\rho(\cdot)$ stands for rank,
  • $\ker(\cdot)$ for null space (aka kernel),
  • $\text{im}(\cdot)$ for column space (aka image).

All we need is the following well known identity (see this answer for a proof): $$\rho(AB)=\rho(B)−\dim(\text{im}(B) \cap \ker(A)) \tag{1}$$ and the following observation: $$\text{im}(BC) \cap \ker(A) \subseteq \text{im}(B)\cap \ker(A)\tag{2}$$ which holds since $\text{im}(BC)\subseteq \text{im}(B)$.

Now we want to write $\rho(ABC)$ in such a way that $\text{im}(BC)\cap \ker(A)$ pops up, so we could make use of $(2)$. Analogously to $(1)$:

$$\rho(ABC)=\rho(BC)−\dim(\text{im}(BC) \cap \ker(A)) \tag{3}.$$

From $(1)$ and $(3)$:

$$\rho(AB)+ \rho(BC) = \rho(B) + \rho(ABC) + \underbrace{\dim(\text{im}(BC) \cap \ker(A))−\dim(\text{im}(B) \cap \ker(A))}_{\leq 0 \text{ due to } (2)}$$ which implies the desired inequality.

$\endgroup$
1
  • $\begingroup$ i just wanna start studying linear algebra , do you recommend a self-study text book? i wanna learn everything for example it was awesome when you used (1) to solve the problem. $\endgroup$
    – Arsh Gh
    Sep 20, 2016 at 4:53
6
$\begingroup$

If you know the Sylvester inequality then it's a two lines proof.

Sylvester Inequality:

Consider $A_{m\times r}$ and $B_{r\times n}$. Then $$r(AB)\geq r(A)+r(B)-r \tag{1}$$ where $r(\cdot)$ is the rank.

Let $B=U_{k\times r} V_{r\times p}$ be a full-rank factorization of $B$.

Then by $(1)$,

\begin{align} r(ABC)&\geq r(AU)+r(VC)-r\\ &=r(AB)+r(BC)-r(B). \end{align}


For a proof of Sylvester inequality refer the following:

enter image description here

$\endgroup$
1
  • $\begingroup$ Please provide a link or name the book from where the screenshot of Sylvester Theorem has been taken. $\endgroup$
    – S.S
    May 17, 2020 at 12:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.