Rank-nullity theorem
Rank-nullity theorem
The nullity (dimension of the nullspace) and the rank (dimension of the range) of an matrix add up to the column dimension of , . |
Proof: Let be the dimension of the nullspace (). Let be a matrix such that its columns form an orthonormal basis of . In particular, we have . Using the QR decomposition of the matrix , we obtain a matrix such that the matrix is orthogonal. Now define the matrix .
We proceed to show that the columns of form a basis for the range of . To do this, we first prove that the columns of span the range of . Then we will show that these columns are independent. This will show that the dimension of the range (that is, the rank) is indeed equal to .
Since is an orthonormal matrix, for any , there exist two vectors such that
If , then
This proves that the columns of span the range of :
Now let us show that the columns of are independent. Assume a vector satisfies and let us show . We have , which implies that is in the nullspace of . Hence, there exists another vector such that . This is contradicted by the fact that is an orthogonal matrix: pre-multiplying the last equation by , and exploiting the fact that
we obtain