Linear Algebra › Section D · Vector spaces › Topic D.6

Rank and the rank-nullity theorem

The rows and the columns of a matrix span different spaces, yet those spaces always have the same dimension, the rank. The rank-nullity theorem then balances the directions a matrix keeps against the directions it sends to zero.

Three spaces from one matrix

An m x n matrix \(A\) carries three natural subspaces. Two are familiar: \(\operatorname{Nul} A\) in \(\mathbb{R}^n\) and \(\operatorname{Col} A\) in \(\mathbb{R}^m\). The third comes from the rows. Each row has n entries, so the rows can be viewed as vectors in \(\mathbb{R}^n\), and their span is the row space, \(\operatorname{Row} A\). Since the rows of \(A\) are the columns of \(A^T\), \(\operatorname{Row} A = \operatorname{Col} A^T\). This topic shows how to find a basis for each space from a single row reduction, and how their dimensions are tied together.

The row space and its basis

Row operations do not change the row space. Each new row is a combination of the old rows, so the row space cannot grow; and each operation can be undone, so it cannot shrink. Hence row-equivalent matrices have the same row space. If \(B\) is an echelon form of \(A\), the non-zero rows of \(B\) form a basis for \(\operatorname{Row} A\) as well as for \(\operatorname{Row} B\): they span it, and they are independent because each starts with a pivot in a column where the rows below it have zeros. Note the contrast with the column space, where you must return to the original columns of \(A\).

Worked example: bases for all three spaces

Let

A = \begin{bmatrix} 1 & -1 & 2 & 3 \\ 2 & -2 & 5 & 4 \\ -1 & 1 & -1 & -5 \\ 3 & -3 & 7 & 7 \end{bmatrix}

1. Row reduce: the reduced echelon form has rows (1, -1, 0, 7), (0, 0, 1, -2) and two zero rows. Pivots sit in columns 1 and 3. 2. Row space: a basis is \(\{(1, -1, 0, 7), (0, 0, 1, -2)\}\), the non-zero rows of the echelon form. 3. Column space: a basis is columns 1 and 3 of \(A\) itself, \(\{(1, 2, -1, 3), (2, 5, -1, 7)\}\). 4. Null space: \(x_2\) and \(x_4\) are free, with \(x_1 = x_2 - 7x_4\) and \(x_3 = 2x_4\), giving the basis \(\{(1, 1, 0, 0), (-7, 0, 2, 1)\}\). Each space has dimension 2.

Rank: row rank equals column rank

The rank of \(A\) is the dimension of its column space: \(\operatorname{rank} A = \dim \operatorname{Col} A\). The example shows something that is always true. The number of pivots counts the pivot columns, which gives \(\dim \operatorname{Col} A\), and it also counts the non-zero rows of an echelon form, which gives \(\dim \operatorname{Row} A\). So

\dim \operatorname{Row} A = \dim \operatorname{Col} A = \operatorname{rank} A

and therefore \(\operatorname{rank} A^T = \operatorname{rank} A\). This is a surprising fact: in a 5 x 100 matrix the 5 rows live in \(\mathbb{R}^{100}\) and the 100 columns in \(\mathbb{R}^5\), yet their spans always have the same dimension. In general, \(\operatorname{rank} A \le \min(m, n)\).

The rank-nullity theorem

The dimension of \(\operatorname{Nul} A\) is called the nullity of \(A\). For any m x n matrix,

\operatorname{rank} A + \dim \operatorname{Nul} A = n

the number of columns. The proof is a count. Each column of \(A\) is either a pivot column or a column of a free variable, never both. The pivot columns number \(\operatorname{rank} A\), and the free variables number \(\dim \operatorname{Nul} A\). In terms of the transformation \(\mathbf{x} \mapsto A\mathbf{x}\), the n dimensions of the input space split into those that survive into the range and those sent to zero. The example checks: \(2 + 2 = 4\).

Worked example: using the theorem

1. A 7 x 10 matrix has a 3-dimensional null space. Its rank is \(10 - 3 = 7\), so \(\operatorname{Col} A\) is a 7-dimensional subspace of \(\mathbb{R}^7\), which is all of \(\mathbb{R}^7\). Every system \(A\mathbf{x} = \mathbf{b}\) is consistent. 2. A 5 x 5 matrix has a null space that is a line. Its rank is \(5 - 1 = 4\), less than 5, so it is not invertible. 3. Can a 4 x 9 matrix have a 2-dimensional null space? Its rank would be \(9 - 2 = 7\), but rank cannot exceed the 4 rows, so no. Every 4 x 9 matrix has nullity at least \(9 - 4 = 5\).

Full rank

An m x n matrix has full column rank when \(\operatorname{rank} A = n\): the columns are independent, the null space is \(\{\mathbf{0}\}\), and \(A\mathbf{x} = \mathbf{b}\) has at most one solution. It has full row rank when \(\operatorname{rank} A = m\): the columns span \(\mathbb{R}^m\), and \(A\mathbf{x} = \mathbf{b}\) has at least one solution for every \(\mathbf{b}\). A matrix whose rank is less than \(\min(m, n)\) is called rank-deficient. A tall matrix (more rows than columns) can have full column rank but never full row rank; a wide one can have full row rank but never full column rank.

Rank and the invertible matrix theorem

For an n x n matrix, rank gives several new entries for the list in "The invertible matrix theorem". Each of the following is equivalent to \(A\) being invertible: the columns of \(A\) form a basis of \(\mathbb{R}^n\); \(\operatorname{Col} A = \mathbb{R}^n\); \(\operatorname{rank} A = n\); \(\dim \operatorname{Nul} A = 0\); and \(\operatorname{Nul} A = \{\mathbf{0}\}\). By the rank-nullity theorem, \(\operatorname{rank} A = n\) and \(\dim \operatorname{Nul} A = 0\) say the same thing. So for square matrices, rank joins pivots and determinants as a test for invertibility.

Rank in practice

Rank measures how much genuine information a matrix holds. A table of measurements with low rank depends on only a few underlying factors, and recommendation systems model the table of users and products as approximately low rank. In control engineering, a rank test decides whether a system can be steered to any state, a property called controllability. With real data, rounding makes matrices almost never exactly rank-deficient, and tiny pivots may be noise. Numerical software therefore estimates rank by counting singular values above a tolerance, using the method of "The singular value decomposition".

Common mistakes to avoid

Using the rows of \(A\) itself as a basis for \(\operatorname{Row} A\) fails when they are dependent; use the non-zero rows of an echelon form. Using echelon-form columns as a basis for \(\operatorname{Col} A\) is the opposite error. In the rank-nullity theorem, n is the number of columns, not rows: a 5 x 8 matrix of rank 5 has nullity 3, not 0. Row space vectors live in \(\mathbb{R}^n\) and column space vectors in \(\mathbb{R}^m\), even though the two spaces have the same dimension. They are usually different spaces.

Key takeaways

Row operations preserve the row space, so the non-zero rows of an echelon form are a basis for \(\operatorname{Row} A\); the pivot columns of \(A\) are a basis for \(\operatorname{Col} A\). The rank is \(\dim \operatorname{Col} A = \dim \operatorname{Row} A\), the number of pivots, so \(\operatorname{rank} A^T = \operatorname{rank} A \le \min(m, n)\). The rank-nullity theorem says \(\operatorname{rank} A + \dim \operatorname{Nul} A = n\). For an n x n matrix, rank n is equivalent to invertibility. Numerical rank counts singular values above a tolerance.

Flashcards

Flashcard

Row A

Span of the rows of A, a subspace of ℝⁿ

Equals Col Aᵀ.

Test your understanding

Question 1 of 5

A 6 x 8 matrix has rank 5. What is the dimension of its null space?

Question 2 of 5

An echelon form of A has non-zero rows (1, -1, 0, 7) and (0, 0, 1, -2), with pivots in columns 1 and 3. Which set is guaranteed to be a basis for Row A, whatever A is?

Question 3 of 5

A is a 4 x 7 matrix of rank 4. Which statement is true?

Question 4 of 5

Can a 5 x 9 matrix have a null space of dimension 3?

Question 5 of 5

For a square n x n matrix A, which condition is equivalent to A being invertible?

← Previous topicNext topic →