2
Aug 18

## Rank of a matrix and the rank-nullity theorem

If you find proofs shorter than mine, shoot me an email.

### Rank and its properties

Definition 1. The dimension of the image $\text{Img}(A)$ is called a rank of the matrix $A$ and denoted $\text{rank}(A)$.

Exercise 1. For any matrix $A$

(1) $\text{rank}(A)=\text{rank}(A^{T}).$

Proof. Suppose $A$ is of size $n\times k$. We know that

(2) $R^k=N(A)\oplus\text{Img}(A^T).$

By (2) any $x\in R^k$ can be represented as

(3) $x=y+z,$ with $y\in N(A),$ $z\in\text{Img}(A^T)$ and $y\perp z.$

From (3) $Ax=Ay+Az=Az.$ By Definition 1, $\text{Img}(A^T)$ is spanned by some linearly independent vectors $z^{(1)},...,z^{(m)}$ with $m=\dim\text{Img}(A^T).$ Hence $z=\sum_{i=1}^ma_iz^{(i)}$ with some $a_i$ depending on $z$ and $Ax=\sum_{i=1}^ma_iAz^{(i)}.$ This shows that $\text{Img}(A)$ is spanned by $Az^{(1)},...,Az^{(m)}.$ If we prove linear independence of these vectors, (1) will follow.

Suppose $\sum_{i=1}^mb_iAz^{(i)}=0$ with some $b_{i}.$ Then $A\left(\sum_{i=1}^mb_iz^{(i)}\right)=0.$ This tells us that $\sum_{i=1}^mb_iz^{(i)}\in N(A).$ Since the vector $\sum_{i=1}^mb_iz^{(i)}$ also belongs to $\text{Img}(A^T),$ by Exercise 3 it is zero. By linear independence, $\sum_{i=1}^mb_iz^{(i)}=0$ is possible only when $b_1=...=b_m=0.$ This proves the linear independence of $Az^{(1)},...,Az^{(m)}$ and the statement.

Exercise 2 (rank-nullity theorem) If $A$ is $n\times k,$ then $\dim N(A)+\dim \text{Img}(A)=k.$

Proof. Exercise 4 and equation (2) imply $k=\dim N(A)+\dim\text{Img}(A^T).$ But we know from Exercise 1 that $\dim\text{Img}(A^T)=\dim\text{Img}(A).$

Exercise 3. Let $A$ be of size $n\times k.$ Then $\text{rank}(A)\leq\min\{n,k\}.$

Proof. From Exercise 2 we see that $\text{rank}(A)=\dim\text{Img}(A)\leq k.$ Applying this inequality to $A^T$ we get $\text{rank}(A)=\text{rank}(A^T)=\dim\text{Img}(A^T)\leq n.$