Suppose UU and VV are finite-dimensional vector spaces and S∈L(V,W)S \in \mathcal L(V,W) and T∈L(U,V)T \in \mathcal L(U,V). Prove that

dim⁡null ST≤dim⁡null S+dim⁡null T\dim \text{null }ST \le \dim \text{null }S + \dim \text{null }T

It sufficies to show

dim⁡null ST=dim⁡null S∣range T+dim⁡null T\dim \text{null }ST = \dim \text{null }S|_{\text{range }T} + \dim \text{null T}

Since null S∣range T⊆null S\text{null }S|_{\text{range }T} \subseteq \text{null }S makes the inequality obvious

dim⁡null ST≤dim⁡null S+dim⁡null T\dim \text{null }ST \le \dim \text{null }S + \dim \text{null }T

In order to prove dim⁡null ST=dim⁡null S∣range T+dim⁡null T\dim \text{null }ST = \dim \text{null }S|_{\text{range }T} + \dim \text{null }T I'm going to construct u1,…,umu_1,\dots,u_m which is a basis for null ST\text{null }ST such that u1,…,uru_1,\dots,u_r is a basis for null T\text{null }T and Tur+1,…,TumTu_{r+1},\dots,Tu_m is a basis for null S∣range T\text{null }S|_{\text{range }T}.

Let u1,…,uru_1,\dots,u_r be a basis for null T\text{null }T then extend it to a basis u1,…,umu_1,\dots,u_m of null ST\text{null }ST. It suffices to show Tur+1,…,TumTu_{r+1},\dots,Tu_m is a basis for null S∣range T\text{null }S|_{\text{range }T}. It's independent because if

ar+1Tur+1+⋯+amTum=0a_{r+1}Tu_{r+1} + \dots + a_mTu_m = 0

Then (by linearity) ar+1ur+1+⋯+amum∈null Ta_{r+1}u_{r+1} + \dots + a_mu_m \in \text{null }T meaning we can write

b1u1+⋯+brur=ar+1ur+1+⋯+amumb_1u_1 + \dots + b_ru_r = a_{r+1}u_{r+1} + \dots + a_mu_m

Independence of u1,…,umu_1,\dots,u_m implies each bj=aj=0b_j = a_j = 0. Thus Tur+1,…,TumTu_{r+1},\dots,Tu_m is independent, now it suffices to show it spans null S∣range T\text{null }S|_{\text{range }T}.
Let v∈null S∣range Tv \in \text{null }S|_{\text{range }T}. since v∈range Tv \in \text{range }T there is some u∈Uu\in U such that v=Tuv = Tu, and since STu=0STu = 0 we can write

u=c1u1+⋯+cmumu = c_1u_1+\dots+c_mu_m

Apply TT to both sides and use the fact that Tuj=0Tu_j = 0 for 1≤j≤r1 \le j \le r

v=cr+1Tur+1+⋯+cmTumv = c_{r+1}Tu_{r+1} + \dots + c_mTu_m

Which shows that Tur+1,…,TumTu_{r+1},\dots,Tu_m spans null S∣range T\text{null }S|_{\text{range }T} completing the proof that it is a basis.

I don't like how long it took to prove null ST=null S∣range T+null T\text{null }ST = \text{null }S|_{\text{range }T} + \text{null }T. todo: look for a shorter proof by starting with a basis for null S∣range T\text{null }S|_{\text{range }T}

This was intuitively obvious but annoying to prove rigorously. My first solution (shown below) is ugly and I think wrong. I'll leave it here though since it's instructive

Old (bad) Solution

Let u1,…,uru_1,\dots,u_r be a basis for null T\text{null }T, since null T⊆null ST\text{null }T \subseteq \text{null }ST we can extend it to a basis u1,…,umu_1,\dots,u_m of null ST\text{null }ST. Let R=span(ur+1,…,um)R = \text{span}(u_{r+1},\dots,u_m). T∣RT|_R (TT restricted to RR) is injective since

null T∣R=null(T)∩R=span(u1,…,ur)∩span(ur+1,…,um)={0}\text{null }T|_R = \text{null($T$)} \cap R = \text{span}(u_1,\dots,u_r) \cap \text{span}(u_{r+1},\dots,u_m) = \{0\}

Therefor Tur+1,…,TumTu_{r+1},\dots,Tu_m are linearly independent in VV meaning we can extend it to a basis of VV

Tur+1,…,Tum,v1,…,vnTu_{r+1},\dots,Tu_m,v_1,\dots,v_n

which implies dim⁡null ST≤dim⁡null S+dim⁡null T\dim \text{null }ST \le \dim \text{null }S + \dim \text{null }T since we constructed a basis for null S\text{null }S and null T\text{null }T by extending a basis of null ST\text{null }ST.