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

Question

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

Answer 1

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

Answer 2

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.