What Rank and Nullity Count
A matrix with \(n\) columns acts on vectors with \(n\) entries: multiplication by \(\mathbf{A}\in\mathbb{R}^{m\times n}\) defines a linear map from \(\mathbb{R}^n\) to \(\mathbb{R}^m\). Some input directions may be sent to \(\mathbf{0}\); these directions form the null space. Other input directions contribute to the range of possible outputs, which is the column space. The rank-nullity theorem says that these two counts account for all \(n\) input dimensions.
For a matrix \(\mathbf{A}\in\mathbb{R}^{m\times n}\), its null space is \(\operatorname{Nul}\mathbf{A}=\{\mathbf{x}\in\mathbb{R}^n:\mathbf{A}\mathbf{x}=\mathbf{0}\}\), and its column space is \(\operatorname{Col}\mathbf{A}=\{\mathbf{A}\mathbf{x}:\mathbf{x}\in\mathbb{R}^n\}\). The latter is the span of the columns of \(\mathbf{A}\). Both are subspaces. Their dimensions are called the nullity and rank, respectively.
These quantities count dimensions, not vectors. A null space may contain infinitely many vectors, but its nullity is the number of vectors in any basis for that space. Likewise, rank is the number of vectors in a basis for the column space. The theorem concerns the column count \(n\), regardless of whether the matrix is square.
Extending a Basis
The proof will start with a basis of the null space and extend it to a basis of the whole domain. The added vectors will be the input directions that remain after the null directions have been accounted for.
Proof. Let \(\mathbf{u}_1,\dots,\mathbf{u}_k\) be linearly independent. Examine the standard basis vectors \(\mathbf{e}_1,\dots,\mathbf{e}_n\) one at a time. Append \(\mathbf{e}_i\) to the current list if it is not in the span of that list; if it is in the span, do not append it. Appending a vector outside the current span preserves independence: a dependence relation with a nonzero coefficient on the new vector would express it as a combination of the old vectors. Thus the resulting list remains linearly independent. At the end, every \(\mathbf{e}_i\) is in the span of the resulting list, so that list spans \(\mathbb{R}^n\), since every vector in \(\mathbb{R}^n\) is a combination of the standard basis vectors. It is therefore a basis. A subspace of \(\mathbb{R}^n\) has a basis: one can select a maximal independent list from a finite spanning list for the subspace, or apply basis extraction in finite dimensions. Applying the extension just proved to that basis gives the particular conclusion. \(\square\)
The Matrix Rank-Nullity Theorem
Proof. Write \(N=\operatorname{Nul}\mathbf{A}\), and let \(\mathbf{u}_1,\dots,\mathbf{u}_k\) be a basis of \(N\), where \(k=\operatorname{nullity}\mathbf{A}\). By the basis extension lemma, extend this list to a basis of \(\mathbb{R}^n\): \(\mathbf{u}_1,\dots,\mathbf{u}_k,\mathbf{w}_1,\dots,\mathbf{w}_r\). There are \(n\) vectors in this basis, so \(k+r=n\).
We show that \(\mathbf{A}\mathbf{w}_1,\dots,\mathbf{A}\mathbf{w}_r\) form a basis of \(\operatorname{Col}\mathbf{A}\). First, they span it. For any \(\mathbf{y}\in\operatorname{Col}\mathbf{A}\), there is an \(\mathbf{x}\in\mathbb{R}^n\) such that \(\mathbf{y}=\mathbf{A}\mathbf{x}\). Expand \(\mathbf{x}\) in the extended basis: \(\mathbf{x}=\sum_{i=1}^{k}a_i\mathbf{u}_i+\sum_{j=1}^{r}b_j\mathbf{w}_j\). Each \(\mathbf{u}_i\) is in the null space, so \(\mathbf{A}\mathbf{u}_i=\mathbf{0}\). By linearity, \(\mathbf{y}=\mathbf{A}\mathbf{x}=\sum_{j=1}^{r}b_j\mathbf{A}\mathbf{w}_j\). Thus these images span the column space.
Next, they are independent. Suppose \(\sum_{j=1}^{r}c_j\mathbf{A}\mathbf{w}_j=\mathbf{0}\). Linearity gives \(\mathbf{A}(\sum_{j=1}^{r}c_j\mathbf{w}_j)=\mathbf{0}\), so \(\sum_{j=1}^{r}c_j\mathbf{w}_j\in N\). Since the \(\mathbf{u}_i\) form a basis of \(N\), there are scalars \(d_i\) such that \(\sum_{j=1}^{r}c_j\mathbf{w}_j=\sum_{i=1}^{k}d_i\mathbf{u}_i\). Moving all terms to one side gives a linear relation among the full basis \(\mathbf{u}_1,\dots,\mathbf{u}_k,\mathbf{w}_1,\dots,\mathbf{w}_r\). Its independence forces every \(c_j=0\). Therefore the images are independent and form a basis of the column space. Hence \(\operatorname{rank}\mathbf{A}=r\), and \(\operatorname{rank}\mathbf{A}+\operatorname{nullity}\mathbf{A}=r+k=n\). \(\square\)
The argument also explains the equality. A basis of the null space accounts for the input directions that map to zero. The remaining basis vectors map to independent vectors that span all possible outputs. The proof does not require \(\mathbf{A}\) to be square, nor does it require a determinant.
Worked Examples
Worked Example: A Matrix with One Null Direction
For \(\mathbf{A}=\begin{bmatrix}1&2&0\\0&1&1\end{bmatrix}\), find a basis of the null space, extend it to a basis of \(\mathbb{R}^3\), and verify rank-nullity.
Solving \(\mathbf{A}\mathbf{x}=\mathbf{0}\) by row reduction gives
Thus \(x_1=2x_3\) and \(x_2=-x_3\). Setting \(x_3=t\) gives \(\mathbf{x}=t(2,-1,1)^{\top}\), so \(\operatorname{Nul}\mathbf{A}\) has basis \(\mathbf{u}=(2,-1,1)^{\top}\) and nullity \(1\). Direct multiplication checks the claim: \(\mathbf{A}\mathbf{u}=(2-2,\,-1+1)^{\top}=(0,0)^{\top}\).
Append \(\mathbf{e}_1,\mathbf{e}_2\) to \(\mathbf{u}\). This is a basis of \(\mathbb{R}^3\): an arbitrary \((x,y,z)^{\top}\) has the expression \(z\mathbf{u}+(x-2z)\mathbf{e}_1+(y+z)\mathbf{e}_2=(x,y,z)^{\top}\), and the coefficients are determined by its coordinates. The added vectors map to \(\mathbf{A}\mathbf{e}_1=(1,0)^{\top}\) and \(\mathbf{A}\mathbf{e}_2=(2,1)^{\top}\). These are independent, since \(a(1,0)^{\top}+b(2,1)^{\top}=(0,0)^{\top}\) forces \(b=0\) from the second coordinate and \(a=0\) from the first. They span the column space, as these are the first two columns and the third column \((0,1)^{\top}\) equals \(-\mathbf{A}\mathbf{e}_1+\mathbf{A}\mathbf{e}_2\). Therefore rank is \(2\), nullity is \(1\), and \(3=2+1\).
Check: the null vector maps to zero, and the two independent images span every column, confirming both counts.
Worked Example: A Rectangular Matrix with Two Null Directions
Let \(\mathbf{A}=\begin{bmatrix}1&0&1&2\\0&1&1&-1\\1&1&2&1\end{bmatrix}\). Find its rank and nullity using a basis extension.
Subtract \(R_1\) from \(R_3\), then subtract \(R_2\) from the new \(R_3\):
The equations are \(x_1+x_3+2x_4=0\) and \(x_2+x_3-x_4=0\). Set \(x_3=s\) and \(x_4=t\). Then \(\mathbf{x}=s(-1,-1,1,0)^{\top}+t(-2,1,0,1)^{\top}\). The two displayed vectors form a null-space basis: every solution has this form, and setting the third and fourth coordinates to zero in a combination forces both coefficients to be zero. Direct checks give \(\mathbf{A}(-1,-1,1,0)^{\top}=(0,0,0)^{\top}\) and \(\mathbf{A}(-2,1,0,1)^{\top}=(0,0,0)^{\top}\). Thus nullity is \(2\).
Append \(\mathbf{e}_1,\mathbf{e}_2\) to these two null vectors. Every \((x_1,x_2,x_3,x_4)^{\top}\) can be written as \(x_3(-1,-1,1,0)^{\top}+x_4(-2,1,0,1)^{\top}+(x_1+x_3+2x_4)\mathbf{e}_1+(x_2+x_3-x_4)\mathbf{e}_2\). Thus the list spans \(\mathbb{R}^4\); its coefficients are also uniquely determined by the four coordinates, so it is a basis. The added vectors map to the first two columns, \((1,0,1)^{\top}\) and \((0,1,1)^{\top}\). They are independent because their first and second coordinates force both coefficients in any zero combination to vanish. The other columns are their combinations: \((1,1,2)^{\top}=(1,0,1)^{\top}+(0,1,1)^{\top}\) and \((2,-1,1)^{\top}=2(1,0,1)^{\top}-(0,1,1)^{\top}\). Hence rank is \(2\), and \(4=2+2\).
Check: the two proposed null vectors multiply to zero, and the two independent image vectors produce all four columns.
Worked Example: A Matrix with a Two-Dimensional Null Space
For \(\mathbf{B}=\begin{bmatrix}1&2&3\\2&4&6\\-1&-2&-3\end{bmatrix}\), determine the nullity and rank.
Apply \(R_2\to R_2-2R_1\) and \(R_3\to R_3+R_1\):
The only equation is \(x_1+2x_2+3x_3=0\). Taking \(x_2=s\) and \(x_3=t\) gives \(\mathbf{x}=s(-2,1,0)^{\top}+t(-3,0,1)^{\top}\). These vectors are independent because their second and third coordinates in a zero combination are respectively \(s\) and \(t\). Multiplication verifies each is in the null space: \(\mathbf{B}(-2,1,0)^{\top}=\mathbf{0}\) and \(\mathbf{B}(-3,0,1)^{\top}=\mathbf{0}\).
Append \(\mathbf{e}_1\). Every \((x,y,z)^{\top}\) equals \(y(-2,1,0)^{\top}+z(-3,0,1)^{\top}+(x+2y+3z)\mathbf{e}_1\); therefore the list is a basis of \(\mathbb{R}^3\). The added vector maps to \(\mathbf{B}\mathbf{e}_1=(1,2,-1)^{\top}\ne\mathbf{0}\), which spans the column space because the other columns are \(2\mathbf{B}\mathbf{e}_1\) and \(3\mathbf{B}\mathbf{e}_1\). Thus nullity is \(2\), rank is \(1\), and \(3=2+1\).
Common Pitfall: Using the Number of Rows
A frequent error is to replace the number of columns by the number of rows. For the \(2\times3\) matrix in the first example, a wrong calculation might say “rank \(2\), nullity \(1\), and there are \(2\) rows, so the theorem would require \(2=2+1\).” That is not the rank-nullity equation: the domain is \(\mathbb{R}^3\), because the matrix takes three-entry inputs. The correct count is \(3=2+1\). The number of rows describes the size of the output vectors, not the dimension of the domain.
Another useful check is that rank and nullity are nonnegative integers and add to \(n\). If a computation gives a null-space basis with \(k\) vectors and a column-space basis with \(r\) vectors, then \(k+r\) must equal the number of columns. This check can reveal an omitted free variable or a missed pivot, though the theorem does not replace verifying the actual bases.
Check Your Understanding
For each question, identify the domain dimension before applying rank-nullity.
- A matrix has \(5\) columns and nullity \(2\). What is its rank?
- Explain why the images of the added basis vectors in the proof span the column space.
- For \(\begin{bmatrix}1&0&1\\0&1&1\end{bmatrix}\), find the nullity and rank, and verify their sum.
- Why does a relation \(\sum_j c_j\mathbf{A}\mathbf{w}_j=\mathbf{0}\) imply that every \(c_j\) is zero when the \(\mathbf{w}_j\) complete a null-space basis to a domain basis?
- A \(3\times5\) matrix has rank \(3\). What is its nullity?
