The Rank-Nullity Theorem for Linear Transformations and Matrices

What’s the rank-nullity theorem?

Let $T:V→W$ be a linear transformation from a finite-dimensional vector space $V$ to an arbitrary space $W$. Then $rank(T)+nullity(T)=dim(V)$

Proof of the rank-nullity theorem?

Let $\dim(V)=n$.

• Choose a basis $\{v_1,\ldots,v_k\}$ for $\ker(T)$, so $\operatorname{nullity}(T)=k$. Since this set is linearly independent, extend it to a basis $B=\{v_1,\ldots,v_{k},v_{k+1},\ldots,v_{n}\}$ of $V$.

Claim that $B_2=\{T(v_{k+1}),\ldots,T(v_{n})\}$ is a basis for $\operatorname{Im}(T)$.

• It spans because any $w\in\operatorname{Im}(T)$ can be written as $w=T(v)$, and when $v$ is written using the full basis of $V$, the terms $T(v_1),\ldots,T(v_k)$ disappear because $v_1,\ldots,v_k\in\ker(T)$.

• It is linearly independent because if $c_{k+1}T(v_{k+1})+\cdots+c_nT(v_n)=0$, then $c_{k+1}v_{k+1}+\cdots+c_nv_n\in\ker(T)$, so it can be written using $v_1,\ldots,v_k$.

We can write $c_{k+1}v_{k+1}+\cdots+c_nv_n=c_1v_1+\cdots+c_kv_k$ for some $c_1,\ldots,c_k\in K$. Rearranging gives $-c_1v_1-\cdots-c_kv_k+c_{k+1}v_{k+1}+\cdots+c_nv_n=0$ so all coefficients are zero since $\mathcal{B}$ is linearly independent. Therefore $\mathcal{B}_2$ is a basis for $\operatorname{Im}(T)$ and has $n-k$ vectors. Hence $\operatorname{rank}(T)=n-k$ and $\operatorname{nullity}(T)=k$, so $\operatorname{rank}(T)+\operatorname{nullity}(T)=n=\dim(V)$.

What is a row and column space of a matrix?

Let $A \in M_{mn}(K)$.

The Row Space of $A$ is the subspace of $K^n$ spanned by the rows of $A$, denoted by $Row(A)$ .

The column space of $A$ is the subspace of $K^m$ spanned by the columns of A, denoted by $Col(A)$

Proof that if $A,B\in M_{mn}(K)$ are row equivalent, then $Row(B)=Row(A)$ and if they’re column equivalent, then $Col(B)=Col(A)$.

The matrix $A$ can be transformed into $B$ by applying a sequence of elementary row operations. Therefore the rows of $B$ are linear combinations of the rows of $A$ and so $Row(B)\subseteq Row(A)$. Reversing the row operations we can transform $B$ into $A$ so we get $Row(A) \subseteq Row(B)$.

$\implies Row(A)=Row(B)$.

Applying same argument with elementary column operations gives the second part.

Why do the non-zero rows of $\operatorname{RREF}(A)$ form a basis for $\operatorname{Row}(A)$?

Let $R=\operatorname{RREF}(A)$. Since row equivalent matrices have the same row space, $\operatorname{Row}(A)=\operatorname{Row}(R)$.

The non-zero rows of $R$ span $\operatorname{Row}(R)$ because zero rows add nothing to the span. They are also linearly independent because each non-zero row has a leading $1$ in a pivot column where all other rows have $0$. Therefore the non-zero rows of $R$ form a basis for $\operatorname{Row}(A)$, and $\dim(\operatorname{Row}(A))$ equals the number of non-zero rows in $R$.

What is the null space of a matrix $A$?

$Null(A)$ is the subset of $K^n$ consisting of solutions of the linear system $Av=0$, i.e

$$Null(A)=\{v\in K^n|Av=0\}$$

NOTE:

• The dimension of $Null(A)$ is called the nullity of A, $Nullity(A)$

  • $Null(A)=Ker(T_A)$ where $T_A$ is the linear transformation $T_A(v)=Av$

How is the column space of a matrix connected to the image of its matrix transformation?

For $A\in M_{m,n}(K)$, define $T_A:K^n\to K^m$ by $T_A(v)=Av$. Then $\operatorname{Col}(A)=\operatorname{Im}(T_A)$.

This is because multiplying $A$ by a vector gives a linear combination of the columns of $A$, so every output lies in $\operatorname{Col}(A)$. Conversely, each column of $A$ is an output of $T_A$ since $Ae_i$ equals the $i$-th column of $A$.

What is $Rank(A)$ where $A$ is a matrix?

The dimension of the column space of $A$. $Rank(A)=Rank(T_A)$

What is the Rank-Nullity Theorem for matrices?

If $A$ is an $m\times n$ matrix, then $Rank(A)+Nullity(A)=n$.

Proof:

Let $A\in M_{m,n}(K)$ and define $T_A:K^n\to K^m$ by $T_A(v)=Av$.

The image of $T_A$ is the column space of $A$, so $\operatorname{rank}(T_A)=\operatorname{rank}(A)$.

By definition we have $\operatorname{nullity}(T_A)=\operatorname{nullity}(A)$.

By rank-nullity for linear transformations, $\operatorname{rank}(T_A)+\operatorname{nullity}(T_A)=\dim(K^n)=n$. Therefore $\operatorname{rank}(A)+\operatorname{nullity}(A)=n$.

Why do the row space and column space of a matrix have the same dimension?

Let $R=\operatorname{RREF}(A)$, and suppose $R$ has $r$ non-zero rows.

The non-zero rows of $R$ form a basis for $\operatorname{Row}(A)$, so $\dim(\operatorname{Row}(A))=r$.

Also, row reduction does not change the solution set of $Av=0$, so $A$ and $R$ have the same nullity.

By rank-nullity, $\operatorname{rank}(A)+\operatorname{nullity}(A)=n$ and $\operatorname{rank}(R)+\operatorname{nullity}(R)=n$.

Since the nullities are equal, $\operatorname{rank}(A)=\operatorname{rank}(R)$. In RREF, $\operatorname{rank}(R)=r$, the number of non-zero rows.

Therefore $\dim(\operatorname{Col}(A))=\operatorname{rank}(A)=r=\dim(\operatorname{Row}(A))$.

NOTE: It is not true in general that $col(A)=Row(A)$, they just have the same dimension.