Rank-Nullity Theorem Applications

Welcome back! In our previous lesson, we developed a robust algorithm, Gaussian elimination, for solving systems of linear equations. We saw that the structure of the solution depended on the number of pivots (leading variables) and free variables. A unique solution existed when there were no free variables, while infinite solutions arose when free variables were present.

Today, we will formalize these concepts. The number of pivots is directly related to a matrix's rank, and the number of free variables is related to its nullity. Our goal is to compute the rank and nullity of a matrix and apply the rank-nullity theorem, a fundamental result that elegantly connects these two quantities to the dimensions of the matrix itself. This theorem provides a deep insight into the structure of linear transformations.

1. Defining Rank and Nullity

Let's begin by formally defining our key terms. The rank and nullity of a matrix are dimensions of two of its "fundamental subspaces": the column space and the null space.

To summarize the definitions for an $m\times n$ matrix $A$:

• Column Space, $C(A)$: The span of the columns of $A$. This is a subspace of ${\mathbb{R}}^m$.
• Rank, $\text{rank}(A)$: The dimension of the column space of $A$. So, $\text{rank}(A)=\dim (C(A))$.
• Null Space, $N(A)$: The set of all solutions to the homogeneous equation $A\mathbf{x}=0$. This is a subspace of ${\mathbb{R}}^n$.
• Nullity, $\text{nullity}(A)$: The dimension of the null space of $A$. So, $\text{nullity}(A)=\dim (N(A))$.

The video below offers another perspective on these definitions, framing them in the context of a linear map.

2. Computing Rank and Nullity

While the definitions are based on the dimensions of subspaces, the most practical way to compute rank and nullity is through the process we already know: Gaussian elimination.

• To find the rank: Reduce the matrix $A$ to its row-echelon form. The number of pivots (or, equivalently, the number of non-zero rows) is the rank of $A$. This works because elementary row operations do not change the dimension of the row space, and the non-zero rows of an echelon matrix form a basis for that space. A crucial theorem states that the dimension of the row space and the column space are always equal.

• To find the nullity: Find the general solution to $A\mathbf{x}=0$. The number of free variables in this solution is the nullity of $A$. Each free variable corresponds to a basis vector for the null space.

Let's see this in action.

3. The Rank-Nullity Theorem

In the example you just studied, you might have noticed a relationship: for the $4\times 6$ matrix $A$, $\text{rank}(A)=2$ and $\text{nullity}(A)=4$. Note that $2+4=6$, which is the number of columns. This is no coincidence; it is the essence of the Rank-Nullity Theorem.

Theorem (Rank-Nullity): If $A$ is an $m\times n$ matrix, then

$$\text{rank}(A)+\text{nullity}(A)=n$$

An Intuitive Proof

From our work with Gaussian elimination, we can construct a straightforward proof. For a system $A\mathbf{x}=0$ with $n$ variables (i.e., $A$ has $n$ columns):

1. The number of pivots in the row-echelon form of $A$ gives the number of leading variables. By definition, this is the rank of $A$.
2. The number of non-pivot columns gives the number of free variables. This is the number of parameters in the general solution to $A\mathbf{x}=0$, which by definition is the nullity of $A$.
3. The total number of variables is the sum of the leading and free variables. Therefore, (number of leading variables) + (number of free variables) = n, which directly implies rank(A) + nullity(A) = n.

A Formal Proof

While the argument above is correct and intuitive, a more rigorous proof relies on constructing bases for the null space and column space. Given your interest in formal derivations, the following proof is highly valuable. It builds a basis for the entire domain ${\mathbb{R}}^n$ starting from a basis for the null space.

Test your understanding!

A $7\times 10$ matrix $A$ defines a linear transformation from ${\mathbb{R}}^{10}$ to ${\mathbb{R}}^7$. If the dimension of the null space of $A$ is 3, what is the dimension of its column space?

Show answer

Here, $n=10$ (the number of columns, dimension of the domain). We are given that $\text{nullity}(A)=\dim (N(A))=3$.
Using the Rank-Nullity Theorem:

$$\text{rank}(A)+\text{nullity}(A)=n$$ $$\text{rank}(A)+3=10$$ $$\text{rank}(A)=7$$

The dimension of the column space, which is the rank, is 7. This also implies that the transformation is surjective (onto), as its image spans all of ${\mathbb{R}}^7$.

4. The Full Picture: The Four Fundamental Subspaces

The rank and nullity are dimensions of two of the four fundamental subspaces associated with any matrix. Understanding all four provides a complete geometric picture of how a linear transformation acts. For an $m\times n$ matrix $A$ with rank $r$:

1. Column Space $C(A)$: A subspace of ${\mathbb{R}}^m$ with dimension $r$.
2. Null Space $N(A)$: A subspace of ${\mathbb{R}}^n$ with dimension $n-r$.
3. Row Space $C(A^T)$: A subspace of ${\mathbb{R}}^n$ with dimension $r$.
4. Left Null Space $N(A^T)$: A subspace of ${\mathbb{R}}^m$ with dimension $m-r$.

The Rank-Nullity theorem, rank(A) + nullity(A) = n, describes the dimensional trade-off within the domain ${\mathbb{R}}^n$. A corresponding theorem applies to the transpose, giving rank(A^T) + nullity(A^T) = m. Since $\text{rank}(A)=\text{rank}(A^T)=r$, this becomes r + (m-r) = m, describing the trade-off within the codomain ${\mathbb{R}}^m$.

The following lecture excerpt from Prof. Gilbert Strang, who popularized this framework, masterfully explains these relationships.

This famous diagram provides a powerful visual summary of everything we've discussed.

Conclusion

In this lesson, we attached formal meaning to the pivot and free variable counts from Gaussian elimination.

Key Takeaways:

• The rank of a matrix $A$ is the dimension of its column space (and row space). It is computed as the number of pivots in its row-echelon form.
• The nullity of a matrix $A$ is the dimension of its null space. It is computed as the number of free variables in the solution to $A\mathbf{x}=0$.
• The Rank-Nullity Theorem states that for any $m\times n$ matrix $A$, $\text{rank}(A)+\text{nullity}(A)=n$. This represents a fundamental conservation law: every dimension of the input space ${\mathbb{R}}^n$ is either "crushed" into the null space or mapped to a dimension in the column space.

In our next lesson, we will move on to another central concept in linear algebra: the determinant of a square matrix. We will see that the determinant provides a single-number summary of many of the matrix's properties, including a powerful test for invertibility, which itself is directly connected to the rank. An $n\times n$ matrix is invertible if and only if its rank is $n$, a fact we are now equipped to understand means its nullity must be 0.