07 - Rank-Nullity Theorem

Rank-Nullity Theorem

Let $V,W$ be vector spaces with $V$ finite-dimensional
Let $T:V\to W$ be linear

Then

$$\dim V=\mathrm{rank}(T)+\mathrm{nullity}(T)$$

Proof (Main)

Let $v_1,\cdots ,v_n$ be a basis for $\ker T$, where $n=\mathrm{nullity}(T)$
Extend this to a basis $v_1,\cdots ,v_n,v_1^{\prime },\cdots ,v_r^{\prime }$ so that $\dim V=n+r$
We claim that $B=\{T{v}_1^{\prime },\cdots ,T{v}_r^{\prime }\}$ is a basis for $\mathrm{Im}T$

1. $B$ spans $\mathrm{Im}T$
   By Properties of Rank and Kernel (3), $T(v_1),\cdots ,T(v_n),T(v_1^{\prime }),\cdots ,T(v_r^{\prime })$ spans $\mathrm{Im}T$
   But $v_1,\cdots ,v_n\in \ker T$, meaning $T(v_1)=\cdots =T(v_n)=0_W$
   so in fact $T{v}_1^{\prime },\cdots ,T{v}_r^{\prime }$ span $\mathrm{Im}T$
2. $B$ is linearly independent
   Take ${\alpha }_1,\cdots ,{\alpha }_r\in \mathbf{F}$ such that

$${\alpha }_{1}T(v_1^{\prime })+\cdots +{\alpha }_{r}T(v_r^{\prime })=0_W$$

As $T$ is linear then we can rewrite this to

$$T({\alpha }_1{v}_1^{\prime }+\cdots +{\alpha }_r{v}_r^{\prime })=0_W$$

So by definition then

$${\alpha }_1{v}_1^{\prime }+\cdots +\alpha v_r^{\prime }\in \ker T$$

As $v_1,\cdots ,v_n$ is a basis for $\ker T$, there are ${\beta }_1,\cdots ,{\beta }_n\in \mathbf{F}$ such that

$${\alpha }_1{v}_1^{\prime }+\cdots +{\alpha }_r{v}_r^{\prime }={\beta }_1{v}_1+\cdots +{\beta }_n{v}_n$$

As $v_1,\cdots ,v_n,v_1^{\prime },\cdots ,v_r^{\prime }$ is a basis then it is linearly independent hence

$${\alpha }_1=\cdots ={\alpha }_r={\beta }_1=\cdots ={\beta }_n=0$$

Hence $T{v}_1^{\prime },\cdots ,T{v}_r^{\prime }$ is linearly independent

So $B$ is a basis

So $\mathrm{rank}(T)=r$ and so $\dim (V)=n+r=\mathrm{nullity}(T)+\mathrm{rank}(T)$

Proof (Using Matrices)

Let $A$ be a $m\times n$ matrix and consider it’s reduced form $\mathrm{RRE}(A)$
There are as many leading $1s$ as there are non-zero rows, that is the row rank of $A$
The kernel of $A$ can be parameterised by assigning parameters to every column without a leading 1
Hence

$$\begin{array}{rl}\text{row rank of }A& =\text{number of leading }1s\\ \text{nullity of }A& =\text{number of leaing columns without leading }1s\end{array}$$

Therefore

$$\begin{array}{rl}n& =\dim {\mathbb{R}}_{col}^n\\ & =(\text{number of leading }1s)+(\text{number of columns without leading }1s)\\ & =(\text{row rank of }A)+(\text{nullity of}A)\end{array}$$