Past exam of the year 1 of the computer science course of the University of Oxford / 2003 / Calculus, probability, linear algebra, discrete mathematics, logic and proof, and models of computation / 3 / a / ii / Solution

The rank-nullity theorem states that a linear map $T:V\to W$ with finite-dimensional $V$ satisfiesChoose a basis $k_1,\dots ,k_r$ of $\ker T$ and use basis extension to obtain a basis $k_1,\dots ,k_r,u_1,\dots ,u_s$ of $V$. We prove that $T{u}_1,\dots ,T{u}_s$ is a basis of $\mathrm{im}T$.

Every $v\in V$ is a linear combination of the extended basis. Applying $T$ kills the $k_i$ terms, so $Tv$ is a linear combination of $T{u}_1,\dots ,T{u}_s$. This proves the linear span assertion. For linear independence, if ${\sum }_j{b}_{j}T{u}_j=0$, then ${\sum }_j{b}_j{u}_j$ belongs to the kernel of a linear map. Hence ${\sum }_j{b}_j{u}_j={\sum }_i{a}_i{k}_i$ for some scalars $a_i$. The linear independence of the extended basis forces every $a_i$ and $b_j$ to vanish. Consequently $\mathrm{rank}T=s$ and $\mathrm{nullity}T=r$, while $\dim V=r+s$, proving the theorem.