Kernel of composition of linear transformations

Let $f : U \to V$ and $g : V \to W$ be linear transformations on the vector spaces $U$, $V$, and $W$. Supposedly,

$$\dim(\ker(g \circ f)) = \dim(\ker(f)) + \dim(\ker(g) \cap \operatorname{im}(f)).$$

How might I go about proving that?

(Attempt:) The $\dim(\ker(g)\cap\operatorname{im}(f))$ term suggests to me that I should define a vector space $V' = \ker(g) + \operatorname{im}(f)$ to invoke the theorem that

$$\dim(V') = \dim(\ker(g)) + \dim(\operatorname{im}(f)) - \dim(\ker(g) \cap \operatorname{im}(f)),$$

but I don't really see where to go from there.

-
First of all I would notice that $\ker(f)\cap \ker(g)\cap \operatorname{im}(f)=\emptyset$. Then I would also notice that $\ker(g\circ f)=(\ker(g)\cap \ker(f))\cup (\ker(g)\cap\operatorname{im}(f))$. Does this helps? –  uforoboa Sep 26 '12 at 9:09
@uforoboa: I don't think that $\ker(f)\cap\ker(g)\cap\operatorname{im}(f) = \emptyset$. For example, let $U=V=W=\mathbb{R}$, $f(x)=0$, and $g(x)=0$. Then $\ker(f)=\mathbb{R}$, $\ker(g)=\mathbb{R}$, and $\operatorname{im}(f)=\{0\}$, so $\ker(f)\cap\ker(g)\cap\operatorname{im}(f)=\{0\} \ne \emptyset$. –  Snowball Sep 26 '12 at 9:21
@Snowball.. you're right... I meant $\{0\}$ not $\emptyset$ of course –  uforoboa Sep 26 '12 at 9:28

HINT: Use two different expressions for $\text{dim}(U)$ in terms of the maps as well as an expression for $\text{dim}(\text{Im}(f))$ in terms of the map $g$.

HINT 2: You can view $g$ as acting on $\text{Im}(f)$ alone. What does that tell you about $\text{dim}(\text{Im}(f))$ ?

-
Sorry, that should have been $\text{dim}(\text{Im}(f))$. Corrected. –  Raskolnikov Sep 26 '12 at 9:24
$\dim(U) = \dim(\ker(f)) + \dim(\operatorname{im}(f)) = \dim(\ker(g \circ f) + \operatorname{im}(g \circ f))$, so that reduces the problem to showing that $\dim(\operatorname{im}(f)) = \dim(\operatorname{im}(g \circ f)) + \dim(\ker(g) \cap \operatorname{im}(f))$. I still don't quite see what sort of expression for $\dim(\operatorname{im}(f))$ I should be looking for, though. –  Snowball Sep 26 '12 at 9:47
OK, I'll add an extra hint. –  Raskolnikov Sep 26 '12 at 10:13
Thanks! Let $g' : \operatorname{im}(f) \to W$. Then $\dim(\operatorname{im}(f)) = \dim(\ker(g')) + \dim(\operatorname{im}(g'))$. $\ker(g') = \ker(g) \cap \operatorname{im}(f)$ and $\operatorname{im}(g') = \operatorname{im}(g \circ f)$, proving the identity. I probably would not have thought of hint 2 on my own. What led you to come up with it? –  Snowball Sep 26 '12 at 10:25
I just wrote down all the possible relations I could come up with and combined them. –  Raskolnikov Sep 26 '12 at 10:32

Here's one possible approach. If a vector is in $\ker f$, then it will certainly be in $\ker(g\circ f)$, but a vector $v$ could also "survive" $f$ (that is $f(v)\neq0$, so $v\notin\ker(f)$), but have $f(v)\in\ker g$ so that still $g(f(v))=0$. The term $\dim(\operatorname{im}(f)\cap\ker g)$ in a sense measures how much this second possibility adds to the dimension of $\ker(g\circ f)$, because in that case $f(v)\in\operatorname{im}(f)\cap\ker g$.

To make the idea precise, one may note that for the purpose of determining $g\circ f$, one may replace $g$ by its restriction to $\operatorname{im}(f)$ (since any vector to which $g$ gets applied in the setting of $g\circ f$ lies in $\operatorname{im}(f)$) $$g\circ f = g|_{\operatorname{im}(f)}\circ f$$ from which its follows that $$\operatorname{im}(g\circ f) = \operatorname{im}(g|_{\operatorname{im}(f)}).$$ Now you can apply the rank-nullity theorem successively to $g\circ f$, to $g|_{\operatorname{im}(f)}$, and to $f$ to obtain the required identity of dimensions: \begin{aligned} \dim\ker(g\circ f)&=\dim U-\operatorname{rk}(g|_{\operatorname{im}(f)})\\ &=\dim U-(\dim\operatorname{im}(f)-\dim\ker(g|_{\operatorname{im}(f)}))\\ &=\dim\ker(f)+\dim(\ker(g)\cap\operatorname{im}(f)) \end{aligned}

Another approach is to observe that the space $\ker(g)\cap\operatorname{im}(f)$ is precisely the image of $\ker(g\circ f)$ by $f$ (again the observations of the first paragraph apply; you can show both inclusions easily). Then apply the rank-nullity theorem to the restriction of $f$ to $\ker(g\circ f)$.

-
What if the nullity of f is non-zero, and you compose f with itself. The kernel cannot be of dimension 2 for given a certain number of compositions (and the matrix form of f) you get the zero matrix? –  Alec Teal Apr 22 at 17:06
@AlecTeal: Sorry, I don't understand at allwhat you are saying. Is there a relation with the current question? –  Marc van Leeuwen Apr 22 at 17:19
I think so. I have a 4x4 matrix with characteristic poly $(\lambda-1)^4$ I want to find the minimum polynomial, this has all the same roots with the property that $m(A)=0$, I've used a calculator to find $(A-1)^2=0$ (the zero matrix). By this conclusion this means the intersection of the kernel of f and image of f is non-empty (you use f and g, I am composing f with itself, and A is the matrix of f) –  Alec Teal Apr 22 at 17:22