1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Please explain what is $\mathcal{J}$? And how did you introduce $V$? Are $f$ and $g$ non-redundant? $\endgroup$
    – Zhanxiong
    Commented Jun 14, 2018 at 19:11
  • $\begingroup$ $\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 $\endgroup$
    – Ignacio
    Commented Jun 14, 2018 at 19:28
  • 1
    $\begingroup$ 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. $\endgroup$
    – Zhanxiong
    Commented Jun 14, 2018 at 19:52

2 Answers 2

6
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .