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

For a linear map $T:V\to W$, its image of a linear map and kernel of a linear map areTheir dimensions define the rank of a linear map and nullity:The image of a linear map measures which output vectors can occur, while the kernel of a linear map measures which input vectors are sent to zero.

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.

By diagonalizability, $V$ has an eigenbasis $e_1,\dots ,e_m$ with $T{e}_j={\lambda }_j{e}_j$. Arrange the basis so that ${\lambda }_1=\cdots ={\lambda }_r=0$ and the remaining eigenvalues are nonzero. If there are no zero or no nonzero eigenvalues, the corresponding linear span below is simply the zero vector subspace.

For $v={\sum }_j{a}_j{e}_j$, the equation $Tv=0$ holds precisely when $a_j=0$ for every $j>r$. ThusEvery output is in $\mathrm{span}\{e_{r+1},\dots ,e_m\}$, and conversely $e_j=T({\lambda }_j^{-1}{e}_j)$ for each $j>r$. ThereforeThese two disjoint parts of a basis span $V$ and their linear spans intersect only at zero. This is exactly the direct sum of vector spaces assertion

Take the linear mapIts kernel of a linear map consists of all $(x,0)$, and its image of a linear map is the same line:Their set intersection is nonzero and their sum is only one-dimensional. In particular, $(0,1)$ cannot be written as a sum of one vector from each of these vector subspaces. The nonzero set intersection also prevents an internal direct sum of vector spaces. ThusThe matrix is a nonzero nilpotent matrix; its failure of diagonalizability explains why the preceding result does not apply.