# $n - \mathrm{rank}\,\ A \ge \mathrm{rank}\,\ A - \mathrm{rank}\,\ A^2$

$A$ is a square ($n \times n$) matrix.

Prove that $n - \mathrm{rank}\,\ A \ge \mathrm{rank}\,\ A - \mathrm{rank}\,\ A^2$

Attempt

Let $f: x \to Ax$ where $x \in V$ and $g: v \to Av$ where $v \in \Im(f)$. Then

$$n - \mathrm{rank}\,\ A =$$ $$\dim \ker (f) = \dim\{x \in V: Ax = 0\} \ge \dim\{x \in \Im (f): Ax = 0\} = \dim \ker(g)$$$$= \mathrm{rank}\,\ A - \mathrm{rank}\,\ A^2$$ because $\Im(A) \subseteq V$.

• Please explain what is $\mathcal{J}$? And how did you introduce $V$? Are $f$ and $g$ non-redundant? – Zhanxiong Jun 14 '18 at 19:11
• $\Im$ is the image of a function (that's what Tex makes out of the symbol) $f: V \to W$, $V$ is a vector space of dimension $n$ I introduced $f$ and $g$ only for notation purposes – Ignacio Jun 14 '18 at 19:28
• Your attempt makes perfect sense (which gives an geometric proof for the Sylvester's inequality). Maybe the only thing you need to elaborate more is the last equality. – Zhanxiong Jun 14 '18 at 19:52

## 2 Answers

It is a so-called Sylvester's inequality, and It has a more general form $$n + rk(AB) \ge rk(A) + rk(B)$$ The proof of this fact is: $$n + rk(AB) = rk \begin{pmatrix}I_n & 0 \\ 0 & AB\end{pmatrix} \\ \begin{pmatrix}I_n & 0 \\ 0 & AB\end{pmatrix} \sim \begin{pmatrix}I_n & 0 \\ A & AB\end{pmatrix} \sim \begin{pmatrix}I_n & -B \\ A & 0\end{pmatrix} \sim \begin{pmatrix}B & I_n \\ 0 & A\end{pmatrix} \\ rk \begin{pmatrix}B & I_n \\ 0 & A\end{pmatrix} \ge rkA + rkB$$ So, we have that $$n + rk(AB) \ge rkA + rkB$$

From your attempt, I am assuming you are interested in a proof which uses the property of subspaces. Here is one proof, which may fill in the blanks in your attempt. Also, for more generality, let me prove the Sylvester's inequality directly: $$\text{rank}(A) + \text{rank}(B) - n \leq \text{rank}(AB), \tag{*}$$ where $A \in F^{m \times n}, B \in F^{n \times p}$ and $F$ is some given number field, say $\mathbb{R}$ or $\mathbb{C}$.

To begin with, define \begin{align} & V_A = \{x \in F^n: Ax = 0\}, \\ & V_B = \{y \in F^p: By = 0\}, \\ & V_{AB} = \{z \in F^p: ABz = 0\}. \end{align} It is well-known that, as the null spaces of corresponding transformations, \begin{align} & \dim(V_A) = n - \text{rank}(A), \\ & \dim(V_B) = p - \text{rank}(B), \\ & \dim(V_{AB}) = p - \text{rank}(AB). \end{align} Now define $$V_0 = \{x \in F^n: x = By, y \in V_{AB}\}.$$ It can be seen $V_0$ is a subspace of $F^n$ and $V_0 \subseteq V_A$. If we can further show $$\dim(V_0) = \dim(V_{AB}) - \dim(V_B), \tag{1}$$ then \begin{align} \dim(V_A) = n - \text{rank}(A) & \geq \dim(V_0) = (p - \text{rank}(AB)) - (p - \text{rank}(B)) \\ & = \text{rank}(B) - \text{rank}(AB), \end{align} i.e., $(*)$ holds.

To show $(1)$, let $\dim(V_B) = s, \dim(V_{AB}) = t$. Since $V_B \subseteq V_{AB}$, we can expand the basis $\{y_1, \ldots, y_s\}$ of $V_B$ to $\{y_1, \ldots, y_s, y_{s + 1}, \ldots, y_t\}$, the basis of $V_{AB}$. Clearly, $By_{s + 1}, \ldots, By_t \in V_0$. Suppose $$\lambda_{s + 1}By_{s + 1} + \cdots + \lambda_t By_t = B(\lambda_{s + 1} y_{s + 1} + \cdots + \lambda_t y_t) = 0,$$ where $\lambda_{s + 1}, \ldots, \lambda_t \in F$, then $\lambda_{s + 1} y_{s + 1} + \cdots + \lambda_t y_t \in V_B$, which implies that there exist $\lambda_1, \ldots, \lambda_s \in F$, such that $$\lambda_{s + 1} y_{s + 1} + \cdots + \lambda_t y_t = \lambda_1 y_1 + \cdots + \lambda_s y_s,$$ which further implies $\lambda_1 = \cdots = \lambda_t = 0$, because $\{y_1, \ldots, y_t\}$ is a basis of $V_{AB}$. In summary, $$\lambda_{s + 1} = \cdots = \lambda_t = 0. \tag{2}$$

Next, assume $x \in V_0$, then there exists $y \in V_{AB}$ such that $x = By$. For $y \in V_{AB}$ and $\{y_1, \ldots, y_t\}$ is a basis of $V_{AB}$, there exist $\alpha_1, \ldots, \alpha_t \in F$ such that $$y = \alpha_1 y_1 + \cdots + \alpha_s y_s + \alpha_{s + 1}y_{s + 1} + \cdots + \alpha_t y_t,$$ consequently, $$x = By = \alpha_1 By_1 + \cdots + \alpha_s By_s + \alpha_{s + 1} By_{s + 1} + \cdots + \alpha_t By_t = \alpha_{s + 1} By_{s + 1} + \cdots + \alpha_t By_t. \tag{3}$$ The last equality holds because $y_1, \ldots, y_s \in V_B$, hence $By_1 = \cdots = By_s = 0$.

$(2)$ and $(3)$ together show that $\{By_{s + 1}, \ldots, By_t\}$ is a basis of $V_{AB}$, therefore $$\dim(V_0) = t - s = \dim(V_{AB}) - \dim(V_B),$$ $(1)$ holds, and this completes the proof.