MAT1041 · Week 9 · - Rank of a Matrix and Systems of Linear Equations

Rank, row/column/null space and linear systems

You learn to find bases for the row space, column space and null space of a matrix, rank and nullity, the rank-nullity theorem, and to decide the consistency of a system with rank and write its solution in the form 'particular solution + homogeneous solution'.

row spacecolumn spacenull spaceranknullityrank-nullity theoremparticular solutiongeneral solutionconsistentpivot columnsinvertible matrix theorem

Three subspaces go with a matrix: the row space spanned by the rows, the column space spanned by the columns, and the null space made of the solutions of $A\mathbf{x} = \mathbf{0}$ . The relation among their dimensions (the rank-nullity theorem) is the most useful counting rule in linear algebra. And the good news: bases for all three come out of a single RREF computation. This week we also close the theory behind the “unique / infinite / none” decision of week 1.

Golden rules:

RREF first. All three subspaces are read off from it.
For the row space use the rows of the RREF, for the column space use the original columns.
Rank + nullity = number of columns.
Consistency: $\operatorname{rank}[A \mid \mathbf{b}] = \operatorname{rank}A$ .

The three subspaces

Let $A$ be $m \times n$ .

Subspace	Definition	Where it lives
Row space	the span of its rows	$\mathbb{R}^n$
Column space	the span of its columns = $\{A\mathbf{x}\}$	$\mathbb{R}^m$
Null space	$\{\mathbf{x} : A\mathbf{x} = \mathbf{0}\}$	$\mathbb{R}^n$

The column space is all the values $A\mathbf{x}$ can take, because $A\mathbf{x}$ is a combination of the columns (week 2). So $A\mathbf{x} = \mathbf{b}$ is consistent if and only if $\mathbf{b}$ is in the column space.

One RREF, three bases

Example. $A = \begin{bmatrix} 1 & 3 & 1 & 2 \\ 2 & 6 & 3 & 5 \\ 1 & 3 & 0 & 1 \end{bmatrix}$ .

$A \xrightarrow[R_3 \leftarrow R_3 - R_1]{R_2 \leftarrow R_2 - 2R_1} \begin{bmatrix} 1 & 3 & 1 & 2 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & -1 & -1 \end{bmatrix} \xrightarrow{R_3 \leftarrow R_3 + R_2} \begin{bmatrix} 1 & 3 & 1 & 2 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix} \xrightarrow{R_1 \leftarrow R_1 - R_2} \begin{bmatrix} 1 & 3 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix} = R$

The pivots are in columns 1 and 3.

Row space. Row operations replace rows by combinations of each other; the span stays the same. The nonzero rows of $R$ are independent (the pivots are in different places):

$\text{basis of row}(A)\text{: } \{(1, 3, 0, 1),\ (0, 0, 1, 1)\}.$

Column space. Row operations preserve the linear relations among the columns but change the columns themselves. In $R$ , column 2 = 3 × column 1 and column 4 = column 1 + column 3; the same relations hold in $A$ . The pivot columns are independent, and the rest are combinations of them:

$\text{basis of col}(A)\text{: } \{(1, 2, 1),\ (1, 3, 0)\} \quad (\text{columns 1 and 3 of } A).$

Null space. $R\mathbf{x} = \mathbf{0}$ : $x_1 + 3x_2 + x_4 = 0$ , $x_3 + x_4 = 0$ . With $x_2 = s$ , $x_4 = t$ free:

$\mathbf{x} = s(-3, 1, 0, 0) + t(-1, 0, -1, 1), \qquad \text{basis of null}(A)\text{: } \{(-3, 1, 0, 0),\ (-1, 0, -1, 1)\}.$

PITFALL · writing the RREF columns as the column space basis. The pivot columns of $R$ are $(1, 0, 0)$ and $(0, 1, 0)$ ; these are not even in the column space of $A$ (the column space of $A$ is the plane $3b_1 = b_2 + b_3$ ). For the column space, always use the original $A$ .

Rank and nullity

$\operatorname{rank}A = \dim\text{row}(A) = \dim\text{col}(A) = \text{number of pivots}, \qquad \operatorname{nullity}A = \dim\text{null}(A).$

That the row space and the column space have equal dimension is surprising (one lives in $\mathbb{R}^n$ , the other in $\mathbb{R}^m$ ), but both equal the number of pivots. Consequence: $\operatorname{rank}A^T = \operatorname{rank}A$ .

Rank-nullity theorem. If $A$ is $m \times n$ then

$\operatorname{rank}A + \operatorname{nullity}A = n.$

Every column is either a pivot column (counted in the rank) or a free variable column (counted in the nullity). In the example $2 + 2 = 4$ .

A table for quick questions ( $A$ is $m \times n$ ):

Information	Result
$\operatorname{rank}A \le \min(m, n)$	a 4×6 matrix has rank at most 4
$A\mathbf{x} = \mathbf{0}$ only trivial	nullity 0, rank $= n$
$\operatorname{rank}A = m$	a pivot in every row, consistent for every $\mathbf{b}$
$\operatorname{rank}A = n$	no free variable, a unique solution if consistent
$n > m$	nullity $\ge n - m > 0$ , the homogeneous system has a nontrivial solution

Rank and systems

For $A\mathbf{x} = \mathbf{b}$ :

Case	Result
$\operatorname{rank}[A \mid \mathbf{b}] > \operatorname{rank}A$	no solution
$\operatorname{rank}[A \mid \mathbf{b}] = \operatorname{rank}A = n$	unique solution
$\operatorname{rank}[A \mid \mathbf{b}] = \operatorname{rank}A < n$	infinitely many solutions, $n - \operatorname{rank}A$ parameters

This is the same as the decision table of week 1, just in the language of rank. A row $[0 \cdots 0 \mid c \neq 0]$ means adding an extra pivot to the augmented matrix.

In the example, for $\mathbf{b} = (b_1, b_2, b_3)$ the same operations leave $b_2 + b_3 - 3b_1$ on the right of the last row. For $\mathbf{b} = (3, 7, 2)$ , $7 + 2 - 9 = 0$ : consistent. For $\mathbf{b} = (1, 0, 0)$ , $-3 \neq 0$ : inconsistent, $\operatorname{rank}[A \mid \mathbf{b}] = 3$ .

General solution = particular solution + homogeneous solution

If $\mathbf{x}_p$ is any (particular) solution of $A\mathbf{x} = \mathbf{b}$ , then all solutions are

$\mathbf{x} = \mathbf{x}_p + \mathbf{x}_h, \qquad \mathbf{x}_h \in \text{null}(A).$

Why: the difference of two solutions satisfies $A(\mathbf{x} - \mathbf{x}_p) = \mathbf{b} - \mathbf{b} = \mathbf{0}$ , so it is in the null space.

In the example with $\mathbf{b} = (3, 7, 2)$ : the RREF of $[A \mid \mathbf{b}]$ gives $x_1 + 3x_2 + x_4 = 2$ , $x_3 + x_4 = 1$ . Take the free variables as 0: $\mathbf{x}_p = (2, 0, 1, 0)$ . Check: $A\mathbf{x}_p = (2 + 1, 4 + 3, 2 + 0) = (3, 7, 2)$ . The general solution:

$\mathbf{x} = (2, 0, 1, 0) + s(-3, 1, 0, 0) + t(-1, 0, -1, 1).$

Geometrically: the solution set is the null space shifted by $\mathbf{x}_p$ . It is not a subspace (it does not contain zero), but it is a parallel copy.

The invertible matrix theorem (current)

For $n \times n$ $A$ the following are equivalent:

$A$ is invertible. 2. $\det A \neq 0$ . 3. $A \sim I_n$ . 4. $A\mathbf{x} = \mathbf{0}$ has only the trivial solution. 5. $A\mathbf{x} = \mathbf{b}$ has a unique solution for every $\mathbf{b}$ . 6. $\operatorname{rank}A = n$ . 7. $\operatorname{nullity}A = 0$ . 8. The columns are independent. 9. The columns span $\mathbb{R}^n$ . 10. The rows are a basis of $\mathbb{R}^n$ .

On the exam, showing one item and writing another as the conclusion is a legitimate argument.

Common mistakes

Wrong	Right
Using the number of rows in rank-nullity	$n$ = the number of columns
Writing the RREF columns as the column space	The original pivot columns
Blindly writing the original rows as the row space	They may be dependent; the nonzero rows of the RREF are safe
Thinking the rank is the number of nonzero entries	The number of pivots
If $\det = 0$ then rank $= 0$	Rank $< n$ ; it can be 1 or 2
Forgetting the particular solution in the general solution	$\mathbf{x}_p + \mathbf{x}_h$
Looking for the null space in $\mathbb{R}^m$	In $\mathbb{R}^n$ (where $\mathbf{x}$ lives)

Test yourself

Exam-style questions. Solve them on paper first, then reveal the answer.

Question 1easy

Find the rank of $\begin{bmatrix} 1 & 2 \\ 2 & 4 \end{bmatrix}$ .

Show answer

$R_2 \leftarrow R_2 - 2R_1$ gives a zero row. One pivot: rank 1.
By columns: column 2 = 2 × column 1, the number of independent columns is 1.

Question 2easy

$A$ is a $5 \times 7$ matrix with rank 3. What is the nullity of $A$ ?

Show answer

Rank-nullity: $\operatorname{rank}A + \operatorname{nullity}A = n$ = the number of columns $= 7$ . $\operatorname{nullity} = 7 - 3 = 4$ . The number of rows (5) does not appear in this formula.

Question 3medium

Find the rank of $A = \begin{bmatrix} 1 & -1 & 2 & 0 \\ 2 & -2 & 5 & 1 \\ -1 & 1 & 1 & 3 \end{bmatrix}$ .

Show answer

$R_2 \leftarrow R_2 - 2R_1$ : $(0, 0, 1, 1)$ . $R_3 \leftarrow R_3 + R_1$ : $(0, 0, 3, 3)$ . $R_3 \leftarrow R_3 - 3R_2$ : a zero row.
Two pivots (columns 1 and 3): rank 2.

Question 4medium

For the matrix $A$ of the previous question, find a basis for the row space of $A$ .

Show answer

\{(1, -1, 0, -2),\ (0, 0, 1, 1)\}

Row operations do not change the row space. The nonzero rows of the RREF form a basis.
With $R_1 \leftarrow R_1 - 2R_2$ the RREF is: $(1, -1, 0, -2)$ and $(0, 0, 1, 1)$ .
(The REF rows $(1, -1, 2, 0)$ , $(0, 0, 1, 1)$ are also a correct answer.)

Question 5medium

For the same $A$ , find a basis for the column space of $A$ .

Show answer

\{(1, 2, -1),\ (2, 5, 1)\}

The pivots are in columns 1 and 3. A basis of the column space: the original 1st and 3rd columns of $A$ .
Writing the columns of the RREF is wrong: row operations change the column space.

Question 6medium

For the same $A$ , find a basis for the null space and the nullity.

Show answer

Basis

\{(1, 1, 0, 0), (2, 0, -1, 1)\}

, nullity

2

RREF: $x_1 - x_2 - 2x_4 = 0$ , $x_3 + x_4 = 0$ . $x_2 = s$ , $x_4 = t$ are free. $\mathbf{x} = (s + 2t, s, -t, t) = s(1, 1, 0, 0) + t(2, 0, -1, 1)$ .
Check: $2 + 2 = 4$ the number of columns (rank + nullity).

Question 7medium

For the same $A$ , is $\mathbf{b} = (1, 3, 4)$ in the column space of $A$ ?

Show answer

The same operations on $[A \mid \mathbf{b}]$ : $R_2 - 2R_1$ : $(0, 0, 1, 1 \mid 1)$ ; $R_3 + R_1$ : $(0, 0, 3, 3 \mid 5)$ ; $R_3 - 3R_2$ : $(0, 0, 0, 0 \mid 2)$ .
Inconsistent, that is, $\operatorname{rank}[A \mid \mathbf{b}] = 3 > \operatorname{rank}A = 2$ . $\mathbf{b}$ is not in the column space.
(If $\mathbf{b} = (1, 3, 2)$ the last row would have been $0 = 0$ .)

Question 8hard

For which values of $k$ does $A = \begin{bmatrix} 1 & 2 & 3 \\ 2 & k & 6 \\ 1 & 1 & k \end{bmatrix}$ have rank 2?

Show answer

k = 3

k = 4

$\det A = 1(k^2 - 6) - 2(2k - 6) + 3(2 - k) = k^2 - 7k + 12 = (k - 3)(k - 4)$ .
If $\det \neq 0$ the rank is 3. When $k = 3$ or $4$ , $\det = 0$ , rank $< 3$ . Rows 1 and 3, $(1, 2, 3)$ and $(1, 1, k)$ , are not proportional for any $k$ , so rank $\ge 2$ .
Conclusion: the rank is exactly 2.

Question 9hard

Write the general solution of $x_1 + x_2 + 2x_3 = 3$ , $2x_1 + 3x_2 + 5x_3 = 8$ in the form $\mathbf{x} = \mathbf{x}_p + \mathbf{x}_h$ .

Show answer

\mathbf{x} = (1, 2, 0) + t(-1, -1, 1)

$R_2 \leftarrow R_2 - 2R_1$ : $(0, 1, 1 \mid 2)$ . $R_1 \leftarrow R_1 - R_2$ : $(1, 0, 1 \mid 1)$ . $x_3 = t$ : $x_1 = 1 - t$ , $x_2 = 2 - t$ . The particular solution ( $t = 0$ ) is $(1, 2, 0)$ ; the homogeneous part $t(-1, -1, 1)$ is the null space of $A$ .

Question 10easy

True or false: A $4 \times 6$ matrix can have rank 5.

Show answer

False

Rank = number of pivots; there is at most one pivot per row, and there are 4 rows. $\operatorname{rank}A \le \min(m, n) = 4$ .

Question 11hard

$A$ is $6 \times 4$ and $A\mathbf{x} = \mathbf{0}$ has only the trivial solution. Find $\operatorname{rank}A$ . Is $A\mathbf{x} = \mathbf{b}$ consistent for every $\mathbf{b} \in \mathbb{R}^6$ ?

Show answer

\operatorname{rank}A = 4

; no

Only the trivial solution $\Rightarrow$ nullity 0 $\Rightarrow$ rank $= 4 - 0 = 4$ .
The column space is a 4-dimensional subspace of $\mathbb{R}^6$ , not all of $\mathbb{R}^6$ . For some $\mathbf{b}$ it is inconsistent.
But when it is consistent the solution is unique (no free variable).

Question 12medium

If $A$ is $3 \times 5$ with $\operatorname{rank}A = 3$ , what are $\operatorname{rank}A^T$ and the dimension of the null space of $A^T$ ?

Show answer

3

and

0

$\operatorname{rank}A^T = \operatorname{rank}A = 3$ (the row space and the column space have equal dimension). $A^T$ is $5 \times 3$ : nullity $= 3 - 3 = 0$ .

Verification: The RREF, rank, pivot columns and null space bases were computed exactly in node with BigInt fractions; the consistency conditions were checked by trying exact solutions with many b vectors, the particular solutions by the product A·x = b, and the parametric rank question at many values of k (verify/MAT1041/09.mjs).

Review card

Row space row(A) ⊆ Rⁿ: the nonzero ROWS of the RREF are a basis (row operations do not change it). Column space col(A) ⊆ Rᵐ: the ORIGINAL form of the PIVOT COLUMNS is a basis. Null space null(A) ⊆ Rⁿ: solve Ax = 0, separate by the free variables. rank A = number of pivots = dim row = dim col. rank A^T = rank A. nullity A = dim null(A) = number of free variables. RANK-NULLITY: rank A + nullity A = n (number of COLUMNS). rank ≤ min(m, n). Ax = b is consistent ⇔ b ∈ col(A) ⇔ rank[A|b] = rank A. If consistent: x = x_p + x_h (a particular solution + any vector from the null space). rank = n → unique solution; rank < n → infinitely many. rank = m (a pivot in every row) → consistent for every b. Square A invertible ⇔ rank = n ⇔ nullity = 0 ⇔ det ≠ 0 ⇔ rows/columns are a basis.