Rank-Nullity Theorem
The rank-nullity theorem states that the rank and the nullity (the dimension of the kernel) sum to the number of columns in a given matrix. If there is a matrix \(M\) with \(x\) rows and \(y\) columns over a field, then \[\text{rank}(M) + \text{nullity}(M) = y.\] This can be generalized further to linear maps: if \(T: V \rightarrow W\) is a linear map, then \[\text{dim}\big(\text{im}(T)\big) + \text{dim}\big(\text{ker}(T)\big) = \text{dim}(V).\]
The rank-nullity theorem is further generalized by consideration of the fundamental subspaces and the fundamental theorem of linear algebra.
The rank-nullity theorem is useful in calculating either one by calculating the other instead, which is useful as it is often much easier to find the rank than the nullity (or vice versa).
Examples
Consider the matrix
\[A = \begin{pmatrix}3&1\\-6&-2\end{pmatrix}.\]
Here, the rank is 1, since the basis \(\left\{\begin{pmatrix}3\\-6\end{pmatrix},\begin{pmatrix}1\\-2\end{pmatrix}\right\}\) can be reduced to \(\left\{\begin{pmatrix}1\\-2\end{pmatrix}\right\}\). The kernel of \(A\) is vectors such that \(Av = 0\), which is a vector space spanned by \(\left\{\begin{pmatrix}1\\-3\end{pmatrix}\right\}\) and has dimension 1. Hence the rank and nullity are both 1, and sum to 2, the number of columns in \(A\).
This can be applied to nonsquare matrices as well. For instance, in the matrix
\[A = \begin{pmatrix}2&5&-3\\1&4&2\end{pmatrix},\]
the rank is 2, spanned by the first two columns of \(A\), and the kernel is a vector space spanned by \(\left\{\begin{pmatrix}22\\-7\\3\end{pmatrix}\right\}\) that thus has dimension 1. As expected, the sum of the rank and nullity is thus 3, the number of columns in \(A\).
Proofs
There are a number of proofs of the rank-nullity theorem available. The simplest uses reduction to the Gauss-Jordan form of a matrix, since it is much easier to analyze. Thus the proof strategy is straightforward: show that the rank-nullity theorem can be reduced to the case of a Gauss-Jordan matrix by analyzing the effect of row operations on the rank and nullity, and then show that the rank-nullity theorem is true for Gauss-Jordan matrices.
The rank of a matrix \(A\) is equivalent to the rank of the Gauss-Jordan form of \(A.\) The kernel of \(A\) is equivalent to the nullspace of the Gauss-Jordan form of \(A\).
The first part of this theorem is clear as the rank is invariant under row operations, and the Gauss-Jordan form \(B\) of \(A\) is obtained through row operations. Analyzing the kernel proceeds in a similar method: suppose \(x \in \text{Null}(A)\), so that \(Ax = 0\) by definition. The Gauss-Jordan form of \(A\) is obtained through row operations, so it can be written as \(MA,\) where \(M\) is some invertible matrix. Then \(Bx = MAx = M0=0\), so \(x \in \text{Null}(B)\). Similarly, if \(x \in \text{Null}(B)\), then \(Ax = M^{-1}Bx = M^{-1}0 = 0\), so \(\text{Null}(A) = \text{Null}(B),\) as desired.
The rank of a matrix in Gauss-Jordan form is the number of leading variables. The nullity of a matrix in Gauss-Jordan form is the number of free variables.
By definition, the Gauss-Jordan form of a matrix consists of a matrix whose nonzero rows have a leading 1. These cannot vanish under row operations, so all the nonzero rows are linearly independent. Hence the rank is equal to the number of leading 1s, which is equivalent to the number of leading variables.Now suppose there are \(m\) leading variables and \(n\) free variables. Then the vectors
\[v_1 = \begin{pmatrix}0\\0\\\vdots\\1\\0\\\vdots\\0\end{pmatrix}, v_2 = \begin{pmatrix}0\\0\\\vdots\\0\\1\\\vdots\\0\end{pmatrix}, \ldots, v_n = \begin{pmatrix}0\\0\\\vdots\\0\\0\\\vdots\\1\end{pmatrix}\]
form a basis for the nullspace of the Gauss-Jordan form of the matrix. These vectors are clearly linearly independent, and hence the nullity is \(n\)--the number of free variables.
The rank-nullity theorem is an immediate consequence of these two results. The rank of a matrix \(A\) and the nullspace of a matrix \(A\) are equivalent to the rank and nullspace of the Gauss-Jordan form of \(A\), so it is sufficient to prove the rank-nullity theorem for matrices already in Gauss-Jordan form. But the number of columns in a Gauss-Jordan form matrix is exactly the sum of the number of leading variables (which was shown above to be the rank) and the number of free variables (which was shown above to be the nullity), as each variable must be either leading or free. This completes the proof. \(_\square\)