Is nullity$(A)\leq$ nullity$(AB)$? I understand this proof of a related fact: Show that $nullity(B)\leq nullity(AB)$ but I'm not sure if it translates to this due to matrix dimensions. If $A$ and $B$ are square, we can say:
Let $x$ be an element of the null space of $A$. Then $(AB)x=(Ax)B=(0)B=0$ so $x$ is an element of the null space of $AB$, implying that $NS(A)\subseteq NS(AB)$, and hence the desired result. But since the matrices aren't necessarily square, can we adapt this proof using the left null space? ie...
Let $x^T$ be an element of the left null space of $A$. Then $x^T(AB)=(x^TA)B=(0)B=0$, so $x^T$ is an element of the left null space of $AB$, and hence nullity$(A)\leq$ nullity$(AB)$.
I'm not sure if this works because I'm not entirely clear on the relation between the left null space and the null space.
 A: $A$ has smaller left-nullity than $AB$ but not smaller (right)-nullity. For example, if
$$ A = \begin{pmatrix} 1 & 1 \end{pmatrix}, B = \begin{pmatrix} 1 \\ 1 \end{pmatrix}, $$
then $\operatorname{nullity}(A) = 1$ but $\operatorname{nullity}(AB) = 0$.
You can see what the rank-nullity theorem says: if the dimension of $A$ is $m \times n$ and $B$ is $n \times p$ then
$$\operatorname{rank}(A) + \operatorname{nullity}(A) = n,$$
$$\operatorname{rank}(B) + \operatorname{nullity}(B) = p,$$
$$\operatorname{rank}(AB) + \operatorname{nullity}(AB) = p.$$
So we are able to relate the nullity of $B$ to that of $AB$ because they are both related to $p$ but the nullity of $A$ is only related to $n$. If $\operatorname{nullity}(A) > p$ then $\operatorname{nullity}(A) > \operatorname{nullity}(AB)$ since $\operatorname{nullity}(AB) \le p$.
If $A$ and $B$ are square matrices then the inequality is always true: $\operatorname{nullity}(A) \le \operatorname{nullity}(AB)$. One way to see this is to observe that the rank decreases: $\operatorname{rank}(AB) \le \operatorname{rank}(A)$.
A: For square matrices, assuming you already know $\operatorname{nullity}(B) \le \operatorname{nullity}(AB)$, you can prove $\operatorname{nullity}(A) \le \operatorname{nullity}(AB)$ by taking the transpose.
The nullity of the transposed matrix is equal to the nullity of the original one so:
$$\operatorname{nullity}(A) = \operatorname{nullity}\left(A^T\right) \le \operatorname{nullity}\left(B^TA^T\right) = \operatorname{nullity}\left((AB)^T\right) = \operatorname{nullity}\left(AB\right)$$
