Notes - Linear Algebra I MT22, Rank and nullity inequalities
Flashcards
Quickly prove that if $S : V \to W$ and $T: U \to V$, then
\[\text{rank}(ST) \le \min(\text{rank}(S), \text{rank}(T))\]
To see $\text{rank}(ST) \le \text{rank}(S)$, we show $\text{Im}(ST) \subseteq \text{Im}(S)$. Suppose $x \in \text{Im}(ST)$, then $\exists y$ s.t. $ST(y) = x$, which implies $S(z) = x$ for some z.
To see $\text{rank}(ST) \le \text{rank(T)}$, consider the restriction of $S$ to $\text{Im}(T)$, i.e.
\[S' : \text{Im}(T) \to W\]By the rank nullity theorem,
\[\begin{aligned} &\dim \text{Im}(T) = \text{rank}(S') + \text{null}(S') \\\\ \implies &\text{rank}(T) = \text{rank}(S') + \text{null}(S') \\\\ \implies &\text{rank}(S') \le \text{rank}(T) \\\\ \implies &\text{rank}(ST) \le \text{rank}(T) \end{aligned}\]Quickly prove that if $S : V \to W$ and $T : U \to V$, then
\[\text{null}(ST) \le \text{null}(S) + \text{null}(T)\]
Consider a basis of $\ker T = \{u _ 1, \ldots, u _ n\}$ and extend to a basis $\ker ST = \{u _ 1, \ldots, u _ n, v _ 1, \ldots, v _ m\}$. Therefore $\text{null}(T) = n$ and $\text{null(ST)} = n + m$.
Then note $\{T(v _ 1), \ldots, T(v _ m)\}$ must be a subset of a basis of $\ker S$, hence $\text{null}(S) \le m$. Adding all the inequalities together,
\[\text{null}(S) + \text{null}(T) \le m + n = \text{null}(ST)\]