3.5 Row Space, Column Space, Null Space, and Rank

We can now reduce any matrix and read off the solutions of any linear system. This section asks a coarser question: how much information does a matrix carry? Three subspaces come attached to every matrix $\mathbf{A}$ : the vectors $\mathbf{A}\mathbf{x}$ it can produce, the combinations of its rows, and the vectors it sends to zero. Their dimensions are governed by a single number, the rank, which is the number of pivots. With it we settle when a system is solvable and how many solutions it has, and we turn the questions of Chapter 1 about vectors in $F^m$ (independent? spanning? a basis of a sum or an intersection?) into a routine computation, which is the “systematic method” that Chapter 1 promised.

Throughout, $F$ is a field and $\mathbf{A} \in M_{m \times n}(F)$ has columns $\mathbf{a}_1, \dots, \mathbf{a}_n \in F^m$ .

3.5.1. Three subspaces of a matrix

Here is the matrix we will follow through the section: $\mathbf{A} = \begin{pmatrix} 1 & 2 & 0 & 0 & -1 \\ 2 & 4 & 1 & 0 & 0 \\ 1 & 2 & 1 & 1 & 2 \\ 0 & 0 & 1 & 1 & 3 \end{pmatrix} \in M_{4 \times 5}(\mathbb{R}).$ Three questions about it have come up in this chapter, and each answer is a set. For which $\mathbf{b} \in \mathbb{R}^4$ can we solve $\mathbf{A}\mathbf{x} = \mathbf{b}$ ? By Theorem 3.1.1, exactly for $\mathbf{b}$ in the span of the columns. Which $\mathbf{x} \in \mathbb{R}^5$ solve $\mathbf{A}\mathbf{x} = \mathbf{0}$ ? By Theorem 3.1.2, a subspace of $\mathbb{R}^5$ . And which new equations can we derive from the four by adding multiples of them? Their left-hand sides are exactly the combinations of the rows. These three sets recur so often that they get names.

The column space is everything $\mathbf{A}$ can produce, the null space is everything $\mathbf{A}$ kills, and the row space is every left-hand side we can build from the equations of $\mathbf{A}\mathbf{x} = \mathbf{b}$ .

Definition 3.5.1 (Column space)

The column space of $\mathbf{A} \in M_{m \times n}(F)$ is the span of its columns, $\operatorname{col}(\mathbf{A}) \mathrel{:=} \operatorname{span}(\mathbf{a}_1, \dots, \mathbf{a}_n) = \{ \mathbf{A}\mathbf{x} : \mathbf{x} \in F^n \} \subseteq F^m .$

Definition 3.5.2 (Row space)

The row space of $\mathbf{A} \in M_{m \times n}(F)$ is the span of its rows, $\operatorname{row}(\mathbf{A}) \mathrel{:=} \operatorname{span}(\text{row } 1, \dots, \text{row } m) \subseteq M_{1 \times n}(F) .$

Definition 3.5.3 (Null space)

The null space of $\mathbf{A} \in M_{m \times n}(F)$ is the solution set of the homogeneous system, $\operatorname{nul}(\mathbf{A}) \mathrel{:=} \{ \mathbf{x} \in F^n : \mathbf{A}\mathbf{x} = \mathbf{0} \} \subseteq F^n .$

In words: $\operatorname{col}(\mathbf{A})$ lives among the outputs, in $F^m$ (one entry per row); $\operatorname{nul}(\mathbf{A})$ lives among the inputs, in $F^n$ (one entry per column); and $\operatorname{row}(\mathbf{A})$ consists of row vectors of length $n$ . The two descriptions of $\operatorname{col}(\mathbf{A})$ agree by Theorem 0.9.3: $\mathbf{A}\mathbf{x} = x_1\mathbf{a}_1 + \dots + x_n\mathbf{a}_n$ , and as $\mathbf{x}$ runs over $F^n$ these are all the combinations of the columns.

Well-definedness. All three are subspaces. $\operatorname{col}(\mathbf{A})$ and $\operatorname{row}(\mathbf{A})$ are spans, hence subspaces by Theorem 1.3.1, of $F^m$ and of $M_{1 \times n}(F)$ respectively. $\operatorname{nul}(\mathbf{A})$ is a subspace of $F^n$ by Theorem 3.1.2. The row vectors $M_{1 \times n}(F)$ form an $n$ -dimensional space, with the standard basis $\mathbf{e}_1^{\top}, \dots, \mathbf{e}_n^{\top}$ (Example (Dimensions of the Running Examples)). Transposing turns row vectors into columns and respects sums and scalar multiples (Theorem 0.9.5), so it sends a combination of rows to the same combination of their transposes, and only the zero row transposes to $\mathbf{0}$ . The transposes of the rows of $\mathbf{A}$ are the columns of $\mathbf{A}^{\top}$ . Hence transposing sends $\operatorname{row}(\mathbf{A})$ onto $\operatorname{col}(\mathbf{A}^{\top})$ , a list of rows is independent exactly when the list of their transposes is, and transposing a basis of $\operatorname{row}(\mathbf{A})$ gives a basis of $\operatorname{col}(\mathbf{A}^{\top})$ . Therefore $\dim \operatorname{row}(\mathbf{A}) = \dim \operatorname{col}(\mathbf{A}^{\top}). \tag{$\ast$}$

Examples.

The identity. $\operatorname{col}(\mathbf{I}_n) = F^n$ , since the columns $\mathbf{e}_1, \dots, \mathbf{e}_n$ span; $\operatorname{row}(\mathbf{I}_n) = M_{1 \times n}(F)$ ; and $\operatorname{nul}(\mathbf{I}_n) = \{\mathbf{0}\}$ , since $\mathbf{I}_n\mathbf{x} = \mathbf{x}$ .
The zero matrix is the degenerate case. For $\mathbf{O} = \mathbf{O}_{m \times n}$ , $\operatorname{col}(\mathbf{O}) = \operatorname{span}(\mathbf{0}, \dots, \mathbf{0}) = \{\mathbf{0}\}$ , $\operatorname{row}(\mathbf{O}) = \{\mathbf{0}\}$ , and $\operatorname{nul}(\mathbf{O}) = F^n$ , since every $\mathbf{x}$ is killed. It carries no information, and its column space is as small as possible while its null space is as large as possible. We will see that this trade-off is exact.
A single row. For $\mathbf{A} = \begin{pmatrix} 1 & 1 & -1 \end{pmatrix} \in M_{1 \times 3}(\mathbb{R})$ , the columns are the scalars $1, 1, -1 \in \mathbb{R}^1$ , so $\operatorname{col}(\mathbf{A}) = \mathbb{R}^1$ , $\operatorname{row}(\mathbf{A}) = \operatorname{span}\bigl(\begin{pmatrix} 1 & 1 & -1 \end{pmatrix}\bigr)$ is a line of row vectors, and $\operatorname{nul}(\mathbf{A})$ is the plane $x + y - z = 0$ in $\mathbb{R}^3$ .

Nonexample by minimal change. Replace $\mathbf{0}$ by a nonzero right-hand side: the solution set $\{ \mathbf{x} \in F^n : \mathbf{A}\mathbf{x} = \mathbf{b} \}$ with $\mathbf{b} \neq \mathbf{0}$ . It is described by the same equations, and it is still of the form $\mathbf{p} + \operatorname{nul}(\mathbf{A})$ when nonempty (Theorem 3.1.3). But it does not contain $\mathbf{0}$ , since $\mathbf{A}\mathbf{0} = \mathbf{0} \neq \mathbf{b}$ , so it fails the first condition of Theorem 1.2.1.

Warning. The three spaces live in different places. For $\mathbf{A} \in M_{4 \times 5}(\mathbb{R})$ above, $\operatorname{col}(\mathbf{A}) \subseteq \mathbb{R}^4$ but $\operatorname{nul}(\mathbf{A}) \subseteq \mathbb{R}^5$ , so a statement such as “ $\operatorname{nul}(\mathbf{A}) \subseteq \operatorname{col}(\mathbf{A})$ ” does not even make sense. Keep track by size: $\mathbf{A}\mathbf{x}$ needs $\mathbf{x}$ with $n$ entries and returns a vector with $m$ entries.

3.5.2. Rank and nullity

The column space measures how much $\mathbf{A}$ can reach, and the null space how much it collapses. We measure each by its dimension. Both are subspaces of finite-dimensional spaces, so both have a dimension by Theorem 1.6.7.

The rank counts the independent directions that $\mathbf{A}$ can produce.

Definition 3.5.4 (Rank of a matrix)

The rank of $\mathbf{A} \in M_{m \times n}(F)$ is $\operatorname{rank} \mathbf{A} \mathrel{:=} \dim \operatorname{col}(\mathbf{A})$ .

Definition 3.5.5 (Nullity of a matrix)

The nullity of $\mathbf{A} \in M_{m \times n}(F)$ is $\operatorname{nullity} \mathbf{A} \mathrel{:=} \dim \operatorname{nul}(\mathbf{A})$ .

From the examples above: $\operatorname{rank} \mathbf{I}_n = n$ and $\operatorname{nullity} \mathbf{I}_n = 0$ ; $\operatorname{rank} \mathbf{O}_{m \times n} = 0$ and $\operatorname{nullity} \mathbf{O}_{m \times n} = n$ ; and $\operatorname{rank} \begin{pmatrix} 1 & 1 & -1 \end{pmatrix} = 1$ , with nullity $2$ . In each case rank plus nullity equals the number of columns. Two simple bounds hold at once: $\operatorname{rank} \mathbf{A} \le m$ , because $\operatorname{col}(\mathbf{A}) \subseteq F^m$ , and $\operatorname{rank} \mathbf{A} \le n$ , because $\operatorname{col}(\mathbf{A})$ is spanned by $n$ vectors (Theorem 1.6.3). Why define rank through columns and not rows? We could have, and one of the main theorems of this section says the answer would be the same.

3.5.3. What row operations preserve

To compute these spaces we will row reduce. So we first ask what a row operation does to each of them. Recall from Theorem 3.4.8 that $\mathbf{A}$ is row equivalent to $\mathbf{B}$ exactly when $\mathbf{B} = \mathbf{E}\mathbf{A}$ with $\mathbf{E} \in M_m(F)$ invertible; since row equivalence is symmetric (Theorem 3.2.2 (b)), we may simply say that $\mathbf{A}$ and $\mathbf{B}$ are row equivalent.

Theorem 3.5.1 (Row operations and the three spaces)

Let $\mathbf{A}, \mathbf{B} \in M_{m \times n}(F)$ be row equivalent. Then:

(a) $\operatorname{row}(\mathbf{B}) = \operatorname{row}(\mathbf{A})$ ;
(b) $\operatorname{nul}(\mathbf{B}) = \operatorname{nul}(\mathbf{A})$ . Equivalently, writing $\mathbf{b}_1, \dots, \mathbf{b}_n$ for the columns of $\mathbf{B}$ : for all $c_1, \dots, c_n \in F$ , the columns of $\mathbf{A}$ satisfy $c_1\mathbf{a}_1 + \dots + c_n\mathbf{a}_n = \mathbf{0}$ if and only if the columns of $\mathbf{B}$ satisfy $c_1\mathbf{b}_1 + \dots + c_n\mathbf{b}_n = \mathbf{0}$ ;
(c) but $\operatorname{col}(\mathbf{B})$ and $\operatorname{col}(\mathbf{A})$ need not be equal.

Proof.

(a) Write $\mathbf{B} = \mathbf{E}\mathbf{A}$ with $\mathbf{E}$ invertible, by Theorem 3.4.8. By Theorem 0.9.2, row $i$ of $\mathbf{E}\mathbf{A}$ is $(\text{row } i \text{ of } \mathbf{E})\mathbf{A}$ , which by Theorem 0.9.3 (rows version) is a combination of the rows of $\mathbf{A}$ . So every row of $\mathbf{B}$ lies in $\operatorname{row}(\mathbf{A})$ , and $\operatorname{row}(\mathbf{B}) \subseteq \operatorname{row}(\mathbf{A})$ by Proposition 1.3.4 (1). Since $\mathbf{A} = \mathbf{E}^{-1}\mathbf{B}$ with $\mathbf{E}^{-1}$ invertible, the same argument gives $\operatorname{row}(\mathbf{A}) \subseteq \operatorname{row}(\mathbf{B})$ .
(b) The equality $\operatorname{nul}(\mathbf{B}) = \operatorname{nul}(\mathbf{A})$ is Lemma 3.3.1. By Theorem 0.9.3, $c_1\mathbf{a}_1 + \dots + c_n\mathbf{a}_n = \mathbf{A}\mathbf{c}$ and $c_1\mathbf{b}_1 + \dots + c_n\mathbf{b}_n = \mathbf{B}\mathbf{c}$ with $\mathbf{c} = (c_1, \dots, c_n)$ , so the second statement is the first one written out (this is Lemma 3.3.2).
(c) Let $\mathbf{A} = \begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix} \in M_2(\mathbb{R})$ and $\mathbf{B} = \begin{pmatrix} 1 & 1 \\ 0 & 0 \end{pmatrix}$ , obtained by $R_2 \to R_2 - R_1$ . Then $\operatorname{col}(\mathbf{A}) = \operatorname{span}((1, 1))$ and $\operatorname{col}(\mathbf{B}) = \operatorname{span}((1, 0))$ . These lines differ, since $(1, 0)$ is not a multiple of $(1, 1)$ .

So row reduction keeps the row space and the relations among the columns, but it moves the columns themselves.

Warning. Do not read $\operatorname{col}(\mathbf{A})$ off the reduced form. In (c) above, the RREF of $\mathbf{A}$ is $\mathbf{B}$ , whose column space is the $x$ -axis, while $\operatorname{col}(\mathbf{A})$ is the line $y = x$ . What survives row reduction is the pattern of dependence: in both matrices column 2 equals column 1. So we use the RREF to decide which columns to take, and then take those columns from $\mathbf{A}$ .

3.5.4. Bases from the reduced form

Fix the notation for the rest of the section. Let $\mathbf{R} = (r_{kj})$ be the reduced row echelon form of $\mathbf{A}$ (Theorem 3.2.3, Theorem 3.3.4), with columns $\mathbf{r}_1, \dots, \mathbf{r}_n \in F^m$ . Let $\mathbf{R}$ have $r$ nonzero rows, and let the pivot of row $k$ lie in column $j_k$ , so that $j_1 < j_2 < \dots < j_r$ . These are the pivot columns of $\mathbf{A}$ , well defined by Corollary 3.3.5. The remaining columns are the free columns. We use three facts from Definition 3.2.4:

rows $r + 1, \dots, m$ of $\mathbf{R}$ are zero;
column $j_k$ of $\mathbf{R}$ is $\mathbf{e}_k$ (the pivot is $1$ and the only nonzero entry of its column);
in row $k$ , every entry to the left of the pivot is $0$ .

From the last two, if column $j$ of $\mathbf{R}$ has exactly $t$ pivot columns to its left, then every entry of $\mathbf{r}_j$ in rows $t + 1, \dots, m$ is zero, except the pivot entry of row $t + 1$ when $j = j_{t+1}$ . Indeed, for $k \ge t + 1$ , row $k$ is either zero or has its pivot in column $j_k \ge j$ , and entries to the left of a pivot vanish. In the running example, $\mathbf{R} = \begin{pmatrix} 1 & 2 & 0 & 0 & -1 \\ 0 & 0 & 1 & 0 & 2 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{pmatrix},$ with $r = 3$ , pivot columns $1, 3, 4$ and free columns $2, 5$ (the reduction is carried out in Example (Bases for the running example) below).

The column space comes first. In $\mathbf{R}$ the answer is visible: the pivot columns are $\mathbf{e}_1, \dots, \mathbf{e}_r$ , and every column has zeros below row $r$ . Row reduction does not preserve columns, but by Theorem 3.5.1 (b) it preserves every linear relation among them, and “is a basis” and “equals this combination” are statements about relations.

Theorem 3.5.2 (Pivot columns form a basis of the column space)

Let $\mathbf{A} \in M_{m \times n}(F)$ have pivot columns $j_1 < \dots < j_r$ , and let $\mathbf{R} = (r_{kj})$ be its RREF. Then:

(a) the pivot columns of $\mathbf{A}$ , $(\mathbf{a}_{j_1}, \dots, \mathbf{a}_{j_r})$ , form a basis of $\operatorname{col}(\mathbf{A})$ ;
(b) if column $j$ is free and $t$ pivot columns lie to its left, then $\mathbf{a}_j = r_{1j}\mathbf{a}_{j_1} + \dots + r_{tj}\mathbf{a}_{j_t}$ ;
(c) the pivot columns of $\mathbf{A}$ are exactly the vectors kept when $(\mathbf{a}_1, \dots, \mathbf{a}_n)$ is sifted as in Theorem 1.5.4.

Idea. Both claims are statements about linear relations among columns, so by Theorem 3.5.1 (b) it suffices to prove them for $\mathbf{R}$ , where they can be seen by inspection. The pivot columns of $\mathbf{R}$ are $\mathbf{e}_1, \dots, \mathbf{e}_r$ , which are independent. A free column of $\mathbf{R}$ is $\sum_k r_{kj}\mathbf{e}_k$ , a combination of the pivot columns to its left with its own entries as coefficients. So we transfer two relations back to $\mathbf{A}$ : “ $\sum c_k \mathbf{a}_{j_k} = \mathbf{0}$ forces $c_1 = \dots = c_r = 0$ ” and “ $\mathbf{a}_j - \sum_k r_{kj}\mathbf{a}_{j_k} = \mathbf{0}$ ”. Part (c) is a rereading of Corollary 3.3.5.

Proof. Throughout, we use Theorem 3.5.1 (b) in the form: for scalars $c_1, \dots, c_n$ , $c_1\mathbf{a}_1 + \dots + c_n\mathbf{a}_n = \mathbf{0} \iff c_1\mathbf{r}_1 + \dots + c_n\mathbf{r}_n = \mathbf{0} . \tag{$\dagger$}$

(b) Let column $j$ be free, with $t$ pivot columns $j_1, \dots, j_t$ to its left. By the fact in bold before the theorem, the entries of $\mathbf{r}_j$ in rows $t + 1, \dots, m$ are zero, so $\mathbf{r}_j = r_{1j}\mathbf{e}_1 + \dots + r_{tj}\mathbf{e}_t = r_{1j}\mathbf{r}_{j_1} + \dots + r_{tj}\mathbf{r}_{j_t}$ , since $\mathbf{r}_{j_k} = \mathbf{e}_k$ . This is a linear relation among the columns of $\mathbf{R}$ with coefficient $1$ on $\mathbf{r}_j$ , $-r_{kj}$ on $\mathbf{r}_{j_k}$ , and $0$ elsewhere. By $(\dagger)$ , the columns of $\mathbf{A}$ satisfy the same relation, which is (b).
(c) Spanning. Each pivot column $\mathbf{a}_{j_k}$ lies in $\operatorname{span}(\mathbf{a}_{j_1}, \dots, \mathbf{a}_{j_r})$ , and each free column does by (b). Hence $\operatorname{col}(\mathbf{A}) = \operatorname{span}(\mathbf{a}_1, \dots, \mathbf{a}_n) \subseteq \operatorname{span}(\mathbf{a}_{j_1}, \dots, \mathbf{a}_{j_r})$ by Proposition 1.3.4 (1). The reverse inclusion holds by Proposition 1.3.4 (2), since the pivot columns are among the columns.

Independence. Let $c_1\mathbf{a}_{j_1} + \dots + c_r\mathbf{a}_{j_r} = \mathbf{0}$ . This is a relation among all the columns of $\mathbf{A}$ with coefficient $0$ on the free columns. By $(\dagger)$ , $c_1\mathbf{r}_{j_1} + \dots + c_r\mathbf{r}_{j_r} = c_1\mathbf{e}_1 + \dots + c_r\mathbf{e}_r = \mathbf{0}$ . The $k$ -th entry of the left side is $c_k$ , so $c_1 = \dots = c_r = 0$ . Hence the pivot columns of $\mathbf{A}$ are linearly independent, and with spanning they form a basis of $\operatorname{col}(\mathbf{A})$ by Definition 1.5.1.

(c) By Corollary 3.3.5 (a), column $j$ is a pivot column if and only if $\mathbf{a}_j \notin \operatorname{span}(\mathbf{a}_1, \dots, \mathbf{a}_{j-1})$ . Sifting keeps $\mathbf{a}_j$ exactly when $\mathbf{a}_j$ is not in the span of the vectors kept before it, and by Theorem 1.5.4 (applied to $(\mathbf{a}_1, \dots, \mathbf{a}_{j-1})$ ) that span is $\operatorname{span}(\mathbf{a}_1, \dots, \mathbf{a}_{j-1})$ . Hence the kept vectors are exactly the pivot columns. This proves the theorem.

This is sifting (Theorem 1.5.4) done by elimination. In Chapter 1, each step “is $\mathbf{v}_j$ in the span of the vectors kept so far?” was a separate small system. One row reduction answers all of them at once, and part (b) even gives the coefficients.

The row space and the null space are read off $\mathbf{R}$ directly.

Theorem 3.5.3 (Basis of the row space)

The nonzero rows of the RREF $\mathbf{R}$ of $\mathbf{A}$ form a basis of $\operatorname{row}(\mathbf{A})$ .

Proof. By Theorem 3.5.1 (a), $\operatorname{row}(\mathbf{A}) = \operatorname{row}(\mathbf{R})$ . The zero rows of $\mathbf{R}$ contribute nothing to a combination, so the $r$ nonzero rows span $\operatorname{row}(\mathbf{R})$ . For independence, let $c_1(\text{row } 1) + \dots + c_r(\text{row } r) = \mathbf{0}$ . Look at the entry in column $j_k$ : since column $j_k$ of $\mathbf{R}$ is $\mathbf{e}_k$ , only row $k$ has a nonzero entry there, equal to $1$ . So that entry of the combination is $c_k$ , and $c_k = 0$ for each $k$ . Hence the nonzero rows are a basis of $\operatorname{row}(\mathbf{A})$ .

For the null space, each free variable gets one basis vector: set that free variable to $1$ , the other free variables to $0$ , and solve for the pivot variables.

Theorem 3.5.4 (Basis of the null space)

Let $\mathbf{A} \in M_{m \times n}(F)$ have RREF $\mathbf{R} = (r_{kj})$ with pivot columns $j_1 < \dots < j_r$ . For each free column $f$ , define $\mathbf{s}_f \in F^n$ by $\begin{aligned} (\mathbf{s}_f)_f &= 1, \\ (\mathbf{s}_f)_{f'} &= 0 \text{ for every other free } f', \\ (\mathbf{s}_f)_{j_k} &= -r_{kf} \text{ for } k = 1, \dots, r . \end{aligned}$ Then the vectors $\mathbf{s}_f$ , one for each free column $f$ , form a basis of $\operatorname{nul}(\mathbf{A})$ . In particular $\operatorname{nullity} \mathbf{A} = n - r$ , the number of free columns.

Proof. By Theorem 3.5.1 (b), $\operatorname{nul}(\mathbf{A}) = \operatorname{nul}(\mathbf{R})$ . For $k \le r$ , row $k$ of $\mathbf{R}$ has entry $1$ in column $j_k$ , entry $0$ in every other pivot column (since column $j_{k'}$ is $\mathbf{e}_{k'}$ ), and entries $r_{kf}$ in the free columns. Rows $k > r$ are zero. Hence $\mathbf{R}\mathbf{x} = \mathbf{0}$ is equivalent to the $r$ equations $x_{j_k} = -\sum_{f \text{ free}} r_{kf}\, x_f \qquad (k = 1, \dots, r). \tag{$\ddagger$}$ Spanning. Let $\mathbf{x} \in \operatorname{nul}(\mathbf{A})$ , and put $\mathbf{y} = \sum_{f \text{ free}} x_f \mathbf{s}_f$ . For a free column $f$ , the $f$ -th entry of $\mathbf{y}$ is $x_f$ , since $\mathbf{s}_f$ has a $1$ there and the other $\mathbf{s}_{f'}$ have $0$ . For a pivot column, the $j_k$ -th entry of $\mathbf{y}$ is $\sum_f x_f(-r_{kf})$ , which equals $x_{j_k}$ by $(\ddagger)$ . So $\mathbf{x} = \mathbf{y}$ lies in the span of the $\mathbf{s}_f$ . Each $\mathbf{s}_f$ itself satisfies $(\ddagger)$ , so it lies in $\operatorname{nul}(\mathbf{A})$ .

Independence. If $\sum_f c_f\mathbf{s}_f = \mathbf{0}$ , then the $f$ -th entry of the left side is $c_f$ , so every $c_f = 0$ .

Hence the $\mathbf{s}_f$ form a basis of $\operatorname{nul}(\mathbf{A})$ , and there are $n - r$ of them.

Example (Bases for the running example)

Find bases of $\operatorname{col}(\mathbf{A})$ , $\operatorname{row}(\mathbf{A})$ , and $\operatorname{nul}(\mathbf{A})$ , and the rank and nullity, for $\mathbf{A} = \begin{pmatrix} 1 & 2 & 0 & 0 & -1 \\ 2 & 4 & 1 & 0 & 0 \\ 1 & 2 & 1 & 1 & 2 \\ 0 & 0 & 1 & 1 & 3 \end{pmatrix} \in M_{4 \times 5}(\mathbb{R}).$

Solution. Row reduce: $\begin{aligned} \mathbf{A} \xrightarrow[R_3 \to R_3 - R_1]{R_2 \to R_2 - 2R_1} \begin{pmatrix} 1 & 2 & 0 & 0 & -1 \\ 0 & 0 & 1 & 0 & 2 \\ 0 & 0 & 1 & 1 & 3 \\ 0 & 0 & 1 & 1 & 3 \end{pmatrix} &\xrightarrow[R_4 \to R_4 - R_2]{R_3 \to R_3 - R_2} \begin{pmatrix} 1 & 2 & 0 & 0 & -1 \\ 0 & 0 & 1 & 0 & 2 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 \end{pmatrix} \\ &\xrightarrow{R_4 \to R_4 - R_3} \mathbf{R} = \begin{pmatrix} 1 & 2 & 0 & 0 & -1 \\ 0 & 0 & 1 & 0 & 2 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{pmatrix}. \end{aligned}$ The pivot columns are $1, 3, 4$ , and the free columns are $2, 5$ .

Column space. By Theorem 3.5.2 (a), the pivot columns of $\mathbf{A}$ , $\mathbf{a}_1 = (1, 2, 1, 0), \qquad \mathbf{a}_3 = (0, 1, 1, 1), \qquad \mathbf{a}_4 = (0, 0, 1, 1),$ form a basis of $\operatorname{col}(\mathbf{A})$ , so $\operatorname{rank} \mathbf{A} = 3$ . By part (b), the free columns are $\mathbf{a}_2 = 2\mathbf{a}_1$ (from column 2 of $\mathbf{R}$ ) and $\mathbf{a}_5 = -\mathbf{a}_1 + 2\mathbf{a}_3 + \mathbf{a}_4$ (from column 5). Check: $-(1, 2, 1, 0) + 2(0, 1, 1, 1) + (0, 0, 1, 1) = (-1, 0, 2, 3) = \mathbf{a}_5$ . Note that $\operatorname{col}(\mathbf{A}) \neq \operatorname{col}(\mathbf{R})$ : every column of $\mathbf{R}$ has last entry $0$ , but $\mathbf{a}_3$ does not.

Row space. By Theorem 3.5.3, a basis is $\begin{pmatrix} 1 & 2 & 0 & 0 & -1 \end{pmatrix}, \quad \begin{pmatrix} 0 & 0 & 1 & 0 & 2 \end{pmatrix}, \quad \begin{pmatrix} 0 & 0 & 0 & 1 & 1 \end{pmatrix},$ so $\dim \operatorname{row}(\mathbf{A}) = 3$ .

Null space. The equations $(\ddagger)$ read $x_1 = -2x_2 + x_5$ , $x_3 = -2x_5$ , $x_4 = -x_5$ . By Theorem 3.5.4, a basis is $\mathbf{s}_2 = (-2, 1, 0, 0, 0), \qquad \mathbf{s}_5 = (1, 0, -2, -1, 1),$ so $\operatorname{nullity} \mathbf{A} = 2$ . Check: $\mathbf{A}\mathbf{s}_2 = -2\mathbf{a}_1 + \mathbf{a}_2 = \mathbf{0}$ and $\mathbf{A}\mathbf{s}_5 = \mathbf{a}_1 - 2\mathbf{a}_3 - \mathbf{a}_4 + \mathbf{a}_5 = \mathbf{0}$ , which are the two relations found above.

So $\operatorname{rank} \mathbf{A} = \dim \operatorname{row}(\mathbf{A}) = 3$ and $\operatorname{rank} \mathbf{A} + \operatorname{nullity} \mathbf{A} = 5$ , the number of columns.

Quick check. Without computing anything, what is the largest possible rank of a $3 \times 5$ matrix, and the smallest possible nullity?

Solution. $\operatorname{rank} \mathbf{A} = \dim \operatorname{col}(\mathbf{A}) \le 3$ , since $\operatorname{col}(\mathbf{A}) \subseteq F^3$ . By Theorem 3.5.4, the nullity is the number of free columns, $5 - r$ , where $r \le 3$ is the number of pivots (one per nonzero row). So the nullity is at least $2$ . For example $\begin{pmatrix} \mathbf{I}_3 & 0_{3 \times 2} \end{pmatrix}$ attains rank $3$ and nullity $2$ .

3.5.5. Row rank equals column rank

The example came out with $\dim \operatorname{row}(\mathbf{A}) = \dim \operatorname{col}(\mathbf{A})$ . This is not luck, and it is surprising: the row space and the column space live in different spaces, and the rows and columns of a $4 \times 5$ matrix have nothing obvious in common. Counting pivots explains it.

Theorem 3.5.5 (Row rank equals column rank)

Let $\mathbf{A} \in M_{m \times n}(F)$ , and let $r$ be the number of pivots of its RREF. Then $\dim \operatorname{row}(\mathbf{A}) = \dim \operatorname{col}(\mathbf{A}) = r .$ Consequently $\operatorname{rank} \mathbf{A} = \operatorname{rank} \mathbf{A}^{\top}$ .

Proof. By Theorem 3.5.2 (a), $\operatorname{col}(\mathbf{A})$ has a basis consisting of the $r$ pivot columns, so $\dim \operatorname{col}(\mathbf{A}) = r$ . By Theorem 3.5.3, $\operatorname{row}(\mathbf{A})$ has a basis consisting of the nonzero rows of the RREF. Each nonzero row contains exactly one pivot and each pivot lies in a nonzero row, so there are $r$ of them, and $\dim \operatorname{row}(\mathbf{A}) = r$ . Finally, by $(\ast)$ at the start of this section, $\operatorname{rank} \mathbf{A}^{\top} = \dim \operatorname{col}(\mathbf{A}^{\top}) = \dim \operatorname{row}(\mathbf{A}) = r = \operatorname{rank} \mathbf{A}$ .

The theorem makes the rank independent of which echelon form we compute. Gaussian elimination without the final clearing-up phase produces an echelon form that is not reduced, and different sequences of operations produce different echelon forms. They all give the same count.

Corollary 3.5.6 (Rank from any echelon form)

Let $\mathbf{A} \in M_{m \times n}(F)$ , and let $\mathbf{G}$ be a matrix in row echelon form that is row equivalent to $\mathbf{A}$ . Then the number of nonzero rows of $\mathbf{G}$ is $\operatorname{rank} \mathbf{A}$ , and the columns of $\mathbf{G}$ containing its pivots are exactly the pivot columns of $\mathbf{A}$ .

Proof. By Corollary 3.3.5 (b), the pivot columns of $\mathbf{G}$ are the pivot columns of $\mathbf{A}$ . Each nonzero row of $\mathbf{G}$ has exactly one pivot, in a different column (Definition 3.2.3), so the number of nonzero rows of $\mathbf{G}$ equals the number of pivot columns of $\mathbf{A}$ , which is $\operatorname{rank} \mathbf{A}$ by Theorem 3.5.5.

Warning. Rank is a property of $\mathbf{A}$ , not of a computation, but it must be counted from a row echelon form. The number of nonzero rows of $\mathbf{A}$ itself is not the rank: $\begin{pmatrix} 1 & 2 \\ 2 & 4 \end{pmatrix}$ has two nonzero rows and rank $1$ . Count nonzero rows only after reaching an echelon form. And the rank depends on the field when the entries are read in different fields: $\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$ has rank $2$ over $\mathbb{R}$ , but over $\mathbb{F}_2$ , where $-1 = 1$ , both rows are $\begin{pmatrix} 1 & 1 \end{pmatrix}$ and the rank is $1$ .

3.5.6. Rank–nullity and the Rouché–Capelli theorem

The trade-off between the zero matrix and the identity was exact, and now we can say why.

Theorem 3.5.7 (Rank–Nullity for Matrices)

For every $\mathbf{A} \in M_{m \times n}(F)$ , $\operatorname{rank} \mathbf{A} + \operatorname{nullity} \mathbf{A} = n,$ the number of columns of $\mathbf{A}$ .

Proof. Let $r$ be the number of pivot columns of $\mathbf{A}$ . By Theorem 3.5.5, $\operatorname{rank} \mathbf{A} = r$ . By Theorem 3.5.4, $\operatorname{nullity} \mathbf{A} = n - r$ . Adding gives $n$ .

Each column of $\mathbf{A}$ is either a pivot column, contributing a direction to $\operatorname{col}(\mathbf{A})$ , or a free column, contributing a direction to $\operatorname{nul}(\mathbf{A})$ . Nothing is lost and nothing is counted twice. This is the same equation as the Rank–Nullity Theorem of Chapter 2, which proved it for linear maps by counting basis vectors, with no matrices at all.

Now the question this chapter started with. When does $\mathbf{A}\mathbf{x} = \mathbf{b}$ have a solution, and how many solutions are there? The first answer was $\mathbf{b} \in \operatorname{col}(\mathbf{A})$ (Theorem 3.1.1); here is a version that is a pure count.

Theorem 3.5.8 (Rouché–Capelli Theorem)

Let $\mathbf{A} \in M_{m \times n}(F)$ , $\mathbf{b} \in F^m$ , and let $[\mathbf{A} \mid \mathbf{b}] \in M_{m \times (n+1)}(F)$ be the augmented matrix.

(a) The system $\mathbf{A}\mathbf{x} = \mathbf{b}$ is consistent if and only if $\operatorname{rank} \mathbf{A} = \operatorname{rank}\,[\mathbf{A} \mid \mathbf{b}]$ .
(b) Suppose it is consistent, let $\mathbf{p}$ be one solution, let $r = \operatorname{rank} \mathbf{A}$ , and let $\mathbf{s}_1, \dots, \mathbf{s}_{n-r}$ be a basis of $\operatorname{nul}(\mathbf{A})$ . Then every solution can be written as $\mathbf{x} = \mathbf{p} + t_1\mathbf{s}_1 + \dots + t_{n-r}\mathbf{s}_{n-r}$ for exactly one choice of $(t_1, \dots, t_{n-r}) \in F^{n-r}$ . In words: the solutions form an $(n - r)$ -parameter family.
(c) If moreover $F$ is a finite field with $q$ elements (for instance $\mathbb{F}_p$ , with $q = p$ ), a consistent system has exactly $q^{\,n - \operatorname{rank} \mathbf{A}}$ solutions.

Idea. For (a), adding the column $\mathbf{b}$ can only enlarge the column space, and the dimension goes up exactly when $\mathbf{b}$ is new, that is, when $\mathbf{b} \notin \operatorname{col}(\mathbf{A})$ . For (b), the structure theorem says solutions are $\mathbf{p}$ plus null vectors, and null vectors have unique coordinates in a basis. For (c), unique coordinates mean the solutions are in bijection with $F^{n-r}$ , which has $q^{n-r}$ elements.

Proof.

(a) By Definition 3.5.1, $\operatorname{col}([\mathbf{A} \mid \mathbf{b}]) = \operatorname{span}(\mathbf{a}_1, \dots, \mathbf{a}_n, \mathbf{b})$ , which contains $\operatorname{col}(\mathbf{A})$ by Proposition 1.3.4 (2).
$(\Rightarrow)$ Suppose the system is consistent. By Theorem 3.1.1, $\mathbf{b} \in \operatorname{span}(\mathbf{a}_1, \dots, \mathbf{a}_n)$ , so by Theorem 1.3.5 $\operatorname{col}([\mathbf{A} \mid \mathbf{b}]) = \operatorname{col}(\mathbf{A})$ , and the ranks are equal.

$(\Leftarrow)$ Suppose $\operatorname{rank} \mathbf{A} = \operatorname{rank}\,[\mathbf{A} \mid \mathbf{b}]$ . Then $\operatorname{col}(\mathbf{A})$ is a subspace of $\operatorname{col}([\mathbf{A} \mid \mathbf{b}])$ of the same dimension, so $\operatorname{col}(\mathbf{A}) = \operatorname{col}([\mathbf{A} \mid \mathbf{b}])$ by Theorem 1.6.8. In particular $\mathbf{b} \in \operatorname{col}(\mathbf{A})$ , and the system is consistent by Theorem 3.1.1.
(b) By Theorem 3.5.7, $\operatorname{nullity} \mathbf{A} = n - r$ , so a basis $\mathbf{s}_1, \dots, \mathbf{s}_{n-r}$ of $\operatorname{nul}(\mathbf{A})$ exists (Theorem 3.5.4). By Theorem 3.1.3, $\mathbf{x}$ is a solution if and only if $\mathbf{x} - \mathbf{p} \in \operatorname{nul}(\mathbf{A})$ . By Theorem 1.5.1, applied in the vector space $\operatorname{nul}(\mathbf{A})$ with this basis, each $\mathbf{x} - \mathbf{p} \in \operatorname{nul}(\mathbf{A})$ equals $t_1\mathbf{s}_1 + \dots + t_{n-r}\mathbf{s}_{n-r}$ for exactly one $(t_1, \dots, t_{n-r})$ . Conversely every such expression is in $\operatorname{nul}(\mathbf{A})$ , so $\mathbf{p}$ plus it is a solution. This proves (b).
(c) By (b), the rule $(t_1, \dots, t_{n-r}) \mapsto \mathbf{p} + t_1\mathbf{s}_1 + \dots + t_{n-r}\mathbf{s}_{n-r}$ is a bijection from $F^{n-r}$ onto the solution set: every solution is hit, and by exactly one tuple. A tuple in $F^{n-r}$ is a choice of $n - r$ entries, each one of $q$ elements, so $F^{n-r}$ has $q^{n-r}$ elements. (When $r = n$ there is exactly one tuple, the empty one, and the basis of $\operatorname{nul}(\mathbf{A})$ is empty, so $\mathbf{p}$ is the only solution and $q^0 = 1$ .) Hence the solution set has $q^{n-r}$ elements.

Over an infinite field such as $\mathbb{Q}$ , $\mathbb{R}$ or $\mathbb{C}$ , part (b) gives the familiar trichotomy: no solution, exactly one solution (when $\operatorname{rank} \mathbf{A} = n$ ), or infinitely many (when $\operatorname{rank} \mathbf{A} < n$ , since distinct values of $t_1$ give distinct solutions). Over a finite field “infinitely many” is replaced by an exact power of $q$ . For example, over $\mathbb{F}_2$ a system can never have exactly $3$ or $6$ solutions.

Example (Counting solutions over

\mathbb{F}_3

)

Over $\mathbb{F}_3$ , consider $\mathbf{A} = \begin{pmatrix} 1 & 1 & 0 & 2 \\ 1 & 2 & 1 & 0 \\ 2 & 0 & 1 & 2 \end{pmatrix}, \qquad \mathbf{b} = \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix}, \qquad \mathbf{b}' = \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix}.$ Decide whether $\mathbf{A}\mathbf{x} = \mathbf{b}$ and $\mathbf{A}\mathbf{x} = \mathbf{b}'$ are consistent, and count their solutions.

Solution. We reduce both augmented matrices at once, carrying two right-hand columns; arithmetic is modulo $3$ , so $-1 = 2$ and $-2 = 1$ . $\begin{aligned} \left[\begin{array}{cccc|c|c} 1 & 1 & 0 & 2 & 1 & 1 \\ 1 & 2 & 1 & 0 & 0 & 0 \\ 2 & 0 & 1 & 2 & 1 & 0 \end{array}\right] &\xrightarrow[R_3 \to R_3 - 2R_1]{R_2 \to R_2 - R_1} \left[\begin{array}{cccc|c|c} 1 & 1 & 0 & 2 & 1 & 1 \\ 0 & 1 & 1 & 1 & 2 & 2 \\ 0 & 1 & 1 & 1 & 2 & 1 \end{array}\right] \\ &\xrightarrow[R_1 \to R_1 - R_2]{R_3 \to R_3 - R_2} \left[\begin{array}{cccc|c|c} 1 & 0 & 2 & 1 & 2 & 2 \\ 0 & 1 & 1 & 1 & 2 & 2 \\ 0 & 0 & 0 & 0 & 0 & 2 \end{array}\right]. \end{aligned}$ Row operations act on each column separately, so deleting either right-hand column gives a reduction of the corresponding augmented matrix. For instance, in row 2, $(1, 2, 1, 0) - (1, 1, 0, 2) = (0, 1, 1, -2) = (0, 1, 1, 1)$ , and in row 3, $(2, 0, 1, 2) - 2(1, 1, 0, 2) = (0, -2, 1, -2) = (0, 1, 1, 1)$ .

The left block is an echelon form of $\mathbf{A}$ with two nonzero rows, so $\operatorname{rank} \mathbf{A} = 2$ by Corollary 3.5.6. With $\mathbf{b}$ , the augmented matrix $[\mathbf{A} \mid \mathbf{b}]$ has the same two nonzero rows (the last is zero), so $\operatorname{rank}\,[\mathbf{A} \mid \mathbf{b}] = 2 = \operatorname{rank} \mathbf{A}$ , and by Theorem 3.5.8 (a) the system is consistent. By part (c) it has exactly $3^{4 - 2} = 9$ solutions. Explicitly, the reduced system is $x_1 = 2 - 2x_3 - x_4 = 2 + x_3 + 2x_4$ and $x_2 = 2 - x_3 - x_4 = 2 + 2x_3 + 2x_4$ , with $x_3, x_4 \in \mathbb{F}_3$ free: nine choices.

With $\mathbf{b}'$ , the last row $(0, 0, 0, 0 \mid 2)$ is a nonzero row with its pivot in the last column, so $[\mathbf{A} \mid \mathbf{b}']$ has three nonzero rows in echelon form and $\operatorname{rank}\,[\mathbf{A} \mid \mathbf{b}'] = 3 \neq 2$ . By Theorem 3.5.8 (a), $\mathbf{A}\mathbf{x} = \mathbf{b}'$ has no solution. Indeed, row 3 of $\mathbf{A}$ is the sum of rows 1 and 2, so any solution would need $b'_3 = b'_1 + b'_2 = 1$ , but $b'_3 = 0$ .

3.5.7. Rank of a product

Multiplying matrices cannot create information: every column of $\mathbf{A}\mathbf{B}$ is a combination of the columns of $\mathbf{A}$ , and every row is a combination of the rows of $\mathbf{B}$ . The rank records this.

Theorem 3.5.9 (Rank of a product)

Let $\mathbf{A} \in M_{m \times n}(F)$ and $\mathbf{B} \in M_{n \times p}(F)$ . Then $\operatorname{rank}(\mathbf{A}\mathbf{B}) \le \min(\operatorname{rank} \mathbf{A}, \operatorname{rank} \mathbf{B}).$ Moreover, if $\mathbf{P} \in M_m(F)$ and $\mathbf{Q} \in M_n(F)$ are invertible, then $\operatorname{rank}(\mathbf{P}\mathbf{A}) = \operatorname{rank} \mathbf{A} = \operatorname{rank}(\mathbf{A}\mathbf{Q})$ .

Proof. Let $\mathbf{b}_1, \dots, \mathbf{b}_p \in F^n$ be the columns of $\mathbf{B}$ . By Theorem 0.9.2, the columns of $\mathbf{A}\mathbf{B}$ are $\mathbf{A}\mathbf{b}_1, \dots, \mathbf{A}\mathbf{b}_p$ , which lie in $\operatorname{col}(\mathbf{A})$ by Definition 3.5.1. By Proposition 1.3.4 (1), $\operatorname{col}(\mathbf{A}\mathbf{B}) \subseteq \operatorname{col}(\mathbf{A})$ , so $\operatorname{rank}(\mathbf{A}\mathbf{B}) \le \operatorname{rank} \mathbf{A}$ by Theorem 1.6.7. Similarly, row $i$ of $\mathbf{A}\mathbf{B}$ is $(\text{row } i \text{ of } \mathbf{A})\mathbf{B}$ , a combination of the rows of $\mathbf{B}$ by Theorem 0.9.3 (rows version), so $\operatorname{row}(\mathbf{A}\mathbf{B}) \subseteq \operatorname{row}(\mathbf{B})$ . By Theorem 3.5.5, $\operatorname{rank}(\mathbf{A}\mathbf{B}) = \dim \operatorname{row}(\mathbf{A}\mathbf{B}) \le \dim \operatorname{row}(\mathbf{B}) = \operatorname{rank} \mathbf{B}$ .

For the second statement, apply the inequality twice: $\operatorname{rank} \mathbf{A} = \operatorname{rank}(\mathbf{P}^{-1}(\mathbf{P}\mathbf{A})) \le \operatorname{rank}(\mathbf{P}\mathbf{A}) \le \operatorname{rank} \mathbf{A}$ , so equality holds throughout. The same sandwich with $\mathbf{A} = (\mathbf{A}\mathbf{Q})\mathbf{Q}^{-1}$ gives $\operatorname{rank}(\mathbf{A}\mathbf{Q}) = \operatorname{rank} \mathbf{A}$ .

The equality case recovers something we already knew in a new form: row operations (left multiplication by an invertible $\mathbf{P}$ ) do not change the rank. The inequality is often strict. For $\mathbf{A} = \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}$ , both factors of $\mathbf{A} \cdot \mathbf{A}$ have rank $1$ , but $\mathbf{A}^2 = \mathbf{O}$ has rank $0$ .

3.5.8. A toolkit for questions from Chapter 1

In Chapter 1 we asked, again and again, whether some vectors in $F^m$ are independent, whether they span, how to extend them to a basis, and what the sum and intersection of two subspaces are. Each was answered by solving a small system by hand. Everything now reduces to one move: put the vectors as columns of a matrix, row reduce, and read off pivots.

Theorem 3.5.10 (Independence and spanning by rank)

Let $\mathbf{v}_1, \dots, \mathbf{v}_k \in F^m$ , and let $\mathbf{A} = \begin{pmatrix} \mathbf{v}_1 & \cdots & \mathbf{v}_k \end{pmatrix} \in M_{m \times k}(F)$ . Then:

(a) $(\mathbf{v}_1, \dots, \mathbf{v}_k)$ is linearly independent if and only if $\operatorname{rank} \mathbf{A} = k$ , that is, every column is a pivot column;
(b) $(\mathbf{v}_1, \dots, \mathbf{v}_k)$ spans $F^m$ if and only if $\operatorname{rank} \mathbf{A} = m$ , that is, every row of the RREF has a pivot;
(c) $(\mathbf{v}_1, \dots, \mathbf{v}_k)$ is a basis of $F^m$ if and only if $k = m = \operatorname{rank} \mathbf{A}$ .

Proof.

(a) By Theorem 0.9.3, $c_1\mathbf{v}_1 + \dots + c_k\mathbf{v}_k = \mathbf{A}\mathbf{c}$ with $\mathbf{c} = (c_1, \dots, c_k)$ , so the list is independent if and only if $\operatorname{nul}(\mathbf{A}) = \{\mathbf{0}\}$ , that is, $\operatorname{nullity} \mathbf{A} = 0$ . By Theorem 3.5.7 this means $\operatorname{rank} \mathbf{A} = k$ .
(b) The list spans $F^m$ if and only if $\operatorname{col}(\mathbf{A}) = F^m$ . Since $\operatorname{col}(\mathbf{A}) \subseteq F^m$ and $\dim F^m = m$ , this holds if and only if $\operatorname{rank} \mathbf{A} = m$ , by Theorem 1.6.8 for one direction and because equal spaces have equal dimension for the other. The number of pivots is $\operatorname{rank} \mathbf{A}$ by Theorem 3.5.5, and the RREF has $m$ rows, each with at most one pivot.
(c) Combine (a) and (b) with Definition 1.5.1.

Example (Testing independence)

Decide whether $\mathbf{v}_1 = (1, 2, 0, 1)$ , $\mathbf{v}_2 = (2, 4, 1, 1)$ , $\mathbf{v}_3 = (0, 0, 1, -1)$ are linearly independent in $\mathbb{R}^4$ . If not, find a linear relation.

Solution. Row reduce the matrix with these columns: $\begin{aligned} \begin{pmatrix} 1 & 2 & 0 \\ 2 & 4 & 0 \\ 0 & 1 & 1 \\ 1 & 1 & -1 \end{pmatrix} &\xrightarrow[R_4 \to R_4 - R_1]{R_2 \to R_2 - 2R_1} \begin{pmatrix} 1 & 2 & 0 \\ 0 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & -1 & -1 \end{pmatrix} \\ &\xrightarrow{R_2 \leftrightarrow R_3} \begin{pmatrix} 1 & 2 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \\ 0 & -1 & -1 \end{pmatrix} \\ &\xrightarrow[R_1 \to R_1 - 2R_2]{R_4 \to R_4 + R_2} \begin{pmatrix} 1 & 0 & -2 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix}. \end{aligned}$ Only columns 1 and 2 are pivot columns, so the rank is $2 < 3$ , and the vectors are dependent by Theorem 3.5.10 (a). Column 3 of the RREF gives the relation, by Theorem 3.5.2 (b): $\mathbf{v}_3 = -2\mathbf{v}_1 + \mathbf{v}_2$ . Check: $-2(1, 2, 0, 1) + (2, 4, 1, 1) = (0, 0, 1, -1)$ . Moreover $(\mathbf{v}_1, \mathbf{v}_2)$ is a basis of $\operatorname{span}(\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3)$ by Theorem 3.5.2 (a).

To extend an independent list to a basis of $F^m$ , append the standard basis and keep the pivot columns. The appended vectors guarantee that the columns span $F^m$ . The original vectors all survive, because by Theorem 3.5.2 (c) a column is discarded only if it lies in the span of the columns before it, and an independent list has no such vector (Lemma 1.5.3).

Example (Extending to a basis by elimination)

Extend the independent list $(\mathbf{v}_1, \mathbf{v}_2) = ((1, 2, 0, 1), (2, 4, 1, 1))$ from Example (Testing independence) to a basis of $\mathbb{R}^4$ .

Solution. Form $\mathbf{M} = \begin{pmatrix} \mathbf{v}_1 & \mathbf{v}_2 & \mathbf{e}_1 & \mathbf{e}_2 & \mathbf{e}_3 & \mathbf{e}_4 \end{pmatrix}$ and row reduce: $\begin{aligned} \begin{pmatrix} 1 & 2 & 1 & 0 & 0 & 0 \\ 2 & 4 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 1 \end{pmatrix} &\xrightarrow[R_4 \to R_4 - R_1]{R_2 \to R_2 - 2R_1} \begin{pmatrix} 1 & 2 & 1 & 0 & 0 & 0 \\ 0 & 0 & -2 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & -1 & -1 & 0 & 0 & 1 \end{pmatrix} \\ &\xrightarrow[\text{then } R_4 \to R_4 + R_2]{R_2 \leftrightarrow R_3} \begin{pmatrix} 1 & 2 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & -2 & 1 & 0 & 0 \\ 0 & 0 & -1 & 0 & 1 & 1 \end{pmatrix} \end{aligned}$ $\xrightarrow[\text{then } R_3 \to -R_3]{R_3 \leftrightarrow R_4} \begin{pmatrix} 1 & 2 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & -1 & -1 \\ 0 & 0 & -2 & 1 & 0 & 0 \end{pmatrix} \xrightarrow{R_4 \to R_4 + 2R_3} \begin{pmatrix} 1 & 2 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & -1 & -1 \\ 0 & 0 & 0 & 1 & -2 & -2 \end{pmatrix}.$ This is an echelon form with pivots in columns $1, 2, 3, 4$ . By Corollary 3.5.6 these are the pivot columns of $\mathbf{M}$ , so by Theorem 3.5.2 (a) the corresponding columns of $\mathbf{M}$ form a basis of $\operatorname{col}(\mathbf{M}) = \mathbb{R}^4$ : $(\mathbf{v}_1, \mathbf{v}_2, \mathbf{e}_1, \mathbf{e}_2).$ (Clearing above the pivots gives the RREF, whose column 5 says $\mathbf{e}_3 = -\mathbf{v}_1 + \mathbf{v}_2 - \mathbf{e}_1 - 2\mathbf{e}_2$ ; check: $-(1, 2, 0, 1) + (2, 4, 1, 1) - (1, 0, 0, 0) - 2(0, 1, 0, 0) = (0, 0, 1, 0)$ .)

For sums and intersections, one reduction does both jobs.

Proposition 3.5.11 (Sum and intersection by elimination)

Let $U, W \subseteq F^m$ be subspaces with bases $(\mathbf{u}_1, \dots, \mathbf{u}_k)$ and $(\mathbf{w}_1, \dots, \mathbf{w}_l)$ , and let $\mathbf{M} = \begin{pmatrix} \mathbf{u}_1 & \cdots & \mathbf{u}_k & \mathbf{w}_1 & \cdots & \mathbf{w}_l \end{pmatrix} \in M_{m \times (k+l)}(F)$ . Then:

(a) the pivot columns of $\mathbf{M}$ form a basis of $U + W$ ;
(b) for $\mathbf{x} = (x_1, \dots, x_{k+l}) \in F^{k+l}$ write $\mathbf{u}_{\mathbf{x}} \mathrel{:=} x_1\mathbf{u}_1 + \dots + x_k\mathbf{u}_k$ , the combination of the $\mathbf{u}$ ’s with the first $k$ entries of $\mathbf{x}$ as coefficients. If $(\mathbf{n}_1, \dots, \mathbf{n}_d)$ is a basis of $\operatorname{nul}(\mathbf{M})$ , then $(\mathbf{u}_{\mathbf{n}_1}, \dots, \mathbf{u}_{\mathbf{n}_d})$ is a basis of $U \cap W$ .

In particular $\dim(U + W) = \operatorname{rank} \mathbf{M}$ and $\dim(U \cap W) = \operatorname{nullity} \mathbf{M}$ .

Proof.

(a) By Proposition 1.7.2, $U + W = \operatorname{span}(\mathbf{u}_1, \dots, \mathbf{u}_k, \mathbf{w}_1, \dots, \mathbf{w}_l) = \operatorname{col}(\mathbf{M})$ , and Theorem 3.5.2 (a) applies.
(b) By Theorem 0.9.3, $\mathbf{x} \in \operatorname{nul}(\mathbf{M})$ means $x_1\mathbf{u}_1 + \dots + x_k\mathbf{u}_k = -(x_{k+1}\mathbf{w}_1 + \dots + x_{k+l}\mathbf{w}_l)$ , so $\mathbf{u}_{\mathbf{x}}$ lies in $U$ and in $W$ . Also $\mathbf{u}_{\mathbf{x} + \mathbf{y}} = \mathbf{u}_{\mathbf{x}} + \mathbf{u}_{\mathbf{y}}$ and $\mathbf{u}_{c\mathbf{x}} = c\,\mathbf{u}_{\mathbf{x}}$ , by the vector space axioms in $F^m$ .

Spanning. Let $\mathbf{v} \in U \cap W$ . Since the $\mathbf{u}$ ’s span $U$ and the $\mathbf{w}$ ’s span $W$ , $\mathbf{v} = a_1\mathbf{u}_1 + \dots + a_k\mathbf{u}_k = b_1\mathbf{w}_1 + \dots + b_l\mathbf{w}_l$ . Then $\mathbf{x} = (a_1, \dots, a_k, -b_1, \dots, -b_l) \in \operatorname{nul}(\mathbf{M})$ and $\mathbf{u}_{\mathbf{x}} = \mathbf{v}$ . Writing $\mathbf{x} = \sum_i t_i\mathbf{n}_i$ gives $\mathbf{v} = \sum_i t_i\mathbf{u}_{\mathbf{n}_i}$ .

Independence. Let $\sum_i t_i\mathbf{u}_{\mathbf{n}_i} = \mathbf{0}$ , and put $\mathbf{x} = \sum_i t_i\mathbf{n}_i \in \operatorname{nul}(\mathbf{M})$ . Then $\mathbf{u}_{\mathbf{x}} = x_1\mathbf{u}_1 + \dots + x_k\mathbf{u}_k = \mathbf{0}$ , so $x_1 = \dots = x_k = 0$ because the $\mathbf{u}$ ’s are independent. Since $\mathbf{M}\mathbf{x} = \mathbf{0}$ , also $x_{k+1}\mathbf{w}_1 + \dots + x_{k+l}\mathbf{w}_l = \mathbf{0}$ , so the remaining entries vanish because the $\mathbf{w}$ ’s are independent. Hence $\mathbf{x} = \mathbf{0}$ , and $t_1 = \dots = t_d = 0$ because the $\mathbf{n}_i$ are independent.

The dimension statements follow by counting the two bases, using Theorem 3.5.5 for $\operatorname{rank} \mathbf{M}$ .

Adding the two counts and using Theorem 3.5.7 gives $\dim(U + W) + \dim(U \cap W) = \operatorname{rank} \mathbf{M} + \operatorname{nullity} \mathbf{M} = k + l = \dim U + \dim W$ . This is the Dimension Formula for Sums (Theorem 1.7.3) again, now with a second, computational proof for subspaces of $F^m$ . (Some texts use the matrix with columns $\mathbf{u}_1, \dots, \mathbf{u}_k, -\mathbf{w}_1, \dots, -\mathbf{w}_l$ instead of $\mathbf{M}$ , so that a null vector gives equal combinations $\sum a_i\mathbf{u}_i = \sum b_j\mathbf{w}_j$ with no sign change. The two null spaces differ only by the signs of the last $l$ entries.)

Example (A basis of a sum)

Let $U = \operatorname{span}(\mathbf{u}_1, \mathbf{u}_2)$ and $W = \operatorname{span}(\mathbf{w}_1, \mathbf{w}_2)$ in $\mathbb{R}^4$ , where $\mathbf{u}_1 = (1, 0, 1, 2), \quad \mathbf{u}_2 = (0, 1, 1, 1), \quad \mathbf{w}_1 = (1, 1, 0, 1), \quad \mathbf{w}_2 = (1, 3, 0, 1).$ Find a basis and the dimension of $U + W$ .

Solution. Each pair is independent, since neither vector is a multiple of the other (compare the first two entries), so $\dim U = \dim W = 2$ . Row reduce $\mathbf{M} = \begin{pmatrix} \mathbf{u}_1 & \mathbf{u}_2 & \mathbf{w}_1 & \mathbf{w}_2 \end{pmatrix}$ : $\begin{pmatrix} 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 3 \\ 1 & 1 & 0 & 0 \\ 2 & 1 & 1 & 1 \end{pmatrix} \xrightarrow[R_4 \to R_4 - 2R_1]{R_3 \to R_3 - R_1} \begin{pmatrix} 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 3 \\ 0 & 1 & -1 & -1 \\ 0 & 1 & -1 & -1 \end{pmatrix} \xrightarrow[R_4 \to R_4 - R_2]{R_3 \to R_3 - R_2} \begin{pmatrix} 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 3 \\ 0 & 0 & -2 & -4 \\ 0 & 0 & -2 & -4 \end{pmatrix}$ $\xrightarrow[\text{then } R_3 \to -\frac12 R_3]{R_4 \to R_4 - R_3} \begin{pmatrix} 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 3 \\ 0 & 0 & 1 & 2 \\ 0 & 0 & 0 & 0 \end{pmatrix} \xrightarrow[R_2 \to R_2 - R_3]{R_1 \to R_1 - R_3} \mathbf{R} = \begin{pmatrix} 1 & 0 & 0 & -1 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 2 \\ 0 & 0 & 0 & 0 \end{pmatrix}.$ The pivot columns are $1, 2, 3$ . By Proposition 3.5.11 (a), $(\mathbf{u}_1, \mathbf{u}_2, \mathbf{w}_1)$ is a basis of $U + W$ , and $\dim(U + W) = 3$ . Column 4 of $\mathbf{R}$ says $\mathbf{w}_2 = -\mathbf{u}_1 + \mathbf{u}_2 + 2\mathbf{w}_1$ ; check: $-(1, 0, 1, 2) + (0, 1, 1, 1) + 2(1, 1, 0, 1) = (1, 3, 0, 1)$ .

Example (A basis of an intersection)

For $U$ and $W$ as in Example (A basis of a sum), find a basis of $U \cap W$ , and check the Dimension Formula for Sums.

Solution. We reuse the RREF $\mathbf{R}$ of $\mathbf{M}$ . Its only free column is column 4, so by Theorem 3.5.4 $\operatorname{nul}(\mathbf{M})$ has the basis $\mathbf{n} = (1, -1, -2, 1)$ (set $x_4 = 1$ ; then $x_1 = 1$ , $x_2 = -1$ , $x_3 = -2$ ). The relation $\mathbf{M}\mathbf{n} = \mathbf{0}$ reads $\mathbf{u}_1 - \mathbf{u}_2 - 2\mathbf{w}_1 + \mathbf{w}_2 = \mathbf{0}$ , that is, $\mathbf{u}_1 - \mathbf{u}_2 = 2\mathbf{w}_1 - \mathbf{w}_2 .$ By Proposition 3.5.11 (b), $\mathbf{u}_{\mathbf{n}} = \mathbf{u}_1 - \mathbf{u}_2 = (1, -1, 0, 1)$ is a basis of $U \cap W$ . Check that it lies in $W$ : $2(1, 1, 0, 1) - (1, 3, 0, 1) = (1, -1, 0, 1)$ . So $\dim(U \cap W) = 1$ , and $\dim U + \dim W - \dim(U \cap W) = 2 + 2 - 1 = 3 = \dim(U + W),$ in agreement with Theorem 1.7.3.

3.5.9. Exercises

A. Check your understanding

Exercise (A1)

(a) Define $\operatorname{col}(\mathbf{A})$ , $\operatorname{row}(\mathbf{A})$ , $\operatorname{nul}(\mathbf{A})$ , and $\operatorname{rank} \mathbf{A}$ for $\mathbf{A} \in M_{m \times n}(F)$ , and say which space each subspace lives in.
(b) State the Rank–Nullity Theorem for matrices and the Rouché–Capelli Theorem.
(c) True or false: if $\mathbf{R}$ is the RREF of $\mathbf{A}$ , then $\operatorname{col}(\mathbf{R}) = \operatorname{col}(\mathbf{A})$ . Justify your answer.
(d) True or false: there is a $4 \times 6$ real matrix with nullity $1$ . Justify your answer.
(e) True or false: for every $\mathbf{A} \in M_{m \times n}(F)$ , $\operatorname{rank} \mathbf{A} = \operatorname{rank} \mathbf{A}^{\top}$ . Justify your answer.
(f) Describe how to find a basis of $U \cap W$ for subspaces $U, W \subseteq F^m$ given by bases.

Solution.

(a) $\operatorname{col}(\mathbf{A})$ is the span of the columns, a subspace of $F^m$ ; $\operatorname{row}(\mathbf{A})$ is the span of the rows, a subspace of $M_{1 \times n}(F)$ ; $\operatorname{nul}(\mathbf{A}) = \{ \mathbf{x} \in F^n : \mathbf{A}\mathbf{x} = \mathbf{0} \}$ , a subspace of $F^n$ ; and $\operatorname{rank} \mathbf{A} = \dim \operatorname{col}(\mathbf{A})$ (Definition 3.5.1, Definition 3.5.2, Definition 3.5.3, Definition 3.5.4).
(b) For $\mathbf{A} \in M_{m \times n}(F)$ , $\operatorname{rank} \mathbf{A} + \operatorname{nullity} \mathbf{A} = n$ (Theorem 3.5.7). For $\mathbf{b} \in F^m$ , $\mathbf{A}\mathbf{x} = \mathbf{b}$ is consistent if and only if $\operatorname{rank} \mathbf{A} = \operatorname{rank}\,[\mathbf{A} \mid \mathbf{b}]$ ; then the solutions are $\mathbf{p} + \operatorname{nul}(\mathbf{A})$ , an $(n - \operatorname{rank} \mathbf{A})$ -parameter family, with exactly $q^{\,n - \operatorname{rank} \mathbf{A}}$ solutions over a field with $q$ elements (Theorem 3.5.8).
(c) False. For $\mathbf{A} = \begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}$ , $\mathbf{R} = \begin{pmatrix} 1 & 1 \\ 0 & 0 \end{pmatrix}$ , and $(1, 1) \in \operatorname{col}(\mathbf{A})$ but $(1, 1) \notin \operatorname{col}(\mathbf{R}) = \operatorname{span}((1, 0))$ . Row operations preserve the row space and the column relations, not the column space (Theorem 3.5.1).
(d) False. Its rank is at most $4$ , since the column space lies in $\mathbb{R}^4$ , so by Theorem 3.5.7 its nullity is $6 - \operatorname{rank} \mathbf{A} \ge 2$ .
(e) True. This is Theorem 3.5.5.
(f) Put the basis vectors of $U$ and then of $W$ as the columns of $\mathbf{M}$ , find a basis of $\operatorname{nul}(\mathbf{M})$ from the RREF, and for each basis vector $\mathbf{n}$ take the combination of the $\mathbf{u}$ ’s with the first $k$ entries of $\mathbf{n}$ as coefficients (Proposition 3.5.11).

B. Practice

Exercise (B1: The three subspaces of a

3 \times 5

matrix)

Let $\mathbf{A} = \begin{pmatrix} 1 & -1 & 2 & 0 & 3 \\ 2 & -2 & 5 & 1 & 4 \\ -1 & 1 & -1 & 1 & -5 \end{pmatrix} \in M_{3 \times 5}(\mathbb{R}).$ Find bases of $\operatorname{col}(\mathbf{A})$ , $\operatorname{row}(\mathbf{A})$ and $\operatorname{nul}(\mathbf{A})$ . Hence verify $\operatorname{rank} \mathbf{A} + \operatorname{nullity} \mathbf{A} = 5$ .

Solution. Row reduce: $\mathbf{A} \xrightarrow[R_3 \to R_3 + R_1]{R_2 \to R_2 - 2R_1} \begin{pmatrix} 1 & -1 & 2 & 0 & 3 \\ 0 & 0 & 1 & 1 & -2 \\ 0 & 0 & 1 & 1 & -2 \end{pmatrix} \xrightarrow[R_1 \to R_1 - 2R_2]{R_3 \to R_3 - R_2} \mathbf{R} = \begin{pmatrix} 1 & -1 & 0 & -2 & 7 \\ 0 & 0 & 1 & 1 & -2 \\ 0 & 0 & 0 & 0 & 0 \end{pmatrix}.$ The pivot columns are $1$ and $3$ ; the free columns are $2, 4, 5$ .

By Theorem 3.5.2, the pivot columns of $\mathbf{A}$ , $(1, 2, -1)$ and $(2, 5, -1)$ , form a basis of $\operatorname{col}(\mathbf{A})$ . By Theorem 3.5.3, $\begin{pmatrix} 1 & -1 & 0 & -2 & 7 \end{pmatrix}$ and $\begin{pmatrix} 0 & 0 & 1 & 1 & -2 \end{pmatrix}$ form a basis of $\operatorname{row}(\mathbf{A})$ . The reduced equations are $x_1 = x_2 + 2x_4 - 7x_5$ and $x_3 = -x_4 + 2x_5$ , so by Theorem 3.5.4 a basis of $\operatorname{nul}(\mathbf{A})$ is $\mathbf{s}_2 = (1, 1, 0, 0, 0), \qquad \mathbf{s}_4 = (2, 0, -1, 1, 0), \qquad \mathbf{s}_5 = (-7, 0, 2, 0, 1).$ For example $\mathbf{A}\mathbf{s}_4 = 2\mathbf{a}_1 - \mathbf{a}_3 + \mathbf{a}_4 = (2, 4, -2) - (2, 5, -1) + (0, 1, 1) = \mathbf{0}$ . Hence $\operatorname{rank} \mathbf{A} = 2$ and $\operatorname{nullity} \mathbf{A} = 3$ , and $2 + 3 = 5$ , as Theorem 3.5.7 requires.

Exercise (B2: Independence and extension in

\mathbb{R}^4

)

Let $\mathbf{v}_1 = (1, 0, 2, 1)$ , $\mathbf{v}_2 = (2, 1, 3, 1)$ , $\mathbf{v}_3 = (0, 1, -1, -1)$ in $\mathbb{R}^4$ .

(a) Determine whether $(\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3)$ is linearly independent. Justify your answer.
(b) Find a basis of $\operatorname{span}(\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3)$ , and extend it to a basis of $\mathbb{R}^4$ using standard basis vectors.

Solution.

(a) Row reduce the matrix with columns $\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3$ : $\begin{pmatrix} 1 & 2 & 0 \\ 0 & 1 & 1 \\ 2 & 3 & -1 \\ 1 & 1 & -1 \end{pmatrix} \xrightarrow[R_4 \to R_4 - R_1]{R_3 \to R_3 - 2R_1} \begin{pmatrix} 1 & 2 & 0 \\ 0 & 1 & 1 \\ 0 & -1 & -1 \\ 0 & -1 & -1 \end{pmatrix} \xrightarrow[R_4 \to R_4 + R_2,\ R_1 \to R_1 - 2R_2]{R_3 \to R_3 + R_2} \begin{pmatrix} 1 & 0 & -2 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{pmatrix}.$ The rank is $2 < 3$ , so the list is dependent by Theorem 3.5.10 (a). Column 3 gives $\mathbf{v}_3 = -2\mathbf{v}_1 + \mathbf{v}_2$ (Theorem 3.5.2 (b)); check: $(-2, 0, -4, -2) + (2, 1, 3, 1) = (0, 1, -1, -1)$ .
(b) By Theorem 3.5.2 (a), $(\mathbf{v}_1, \mathbf{v}_2)$ is a basis of $\operatorname{span}(\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3)$ . To extend it, row reduce $\begin{pmatrix} \mathbf{v}_1 & \mathbf{v}_2 & \mathbf{e}_1 & \mathbf{e}_2 & \mathbf{e}_3 & \mathbf{e}_4 \end{pmatrix}$ : $\begin{aligned} \begin{pmatrix} 1 & 2 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 2 & 3 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 0 & 1 \end{pmatrix} &\xrightarrow[R_4 \to R_4 - R_1]{R_3 \to R_3 - 2R_1} \begin{pmatrix} 1 & 2 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & -1 & -2 & 0 & 1 & 0 \\ 0 & -1 & -1 & 0 & 0 & 1 \end{pmatrix} \\ &\xrightarrow[R_4 \to R_4 + R_2]{R_3 \to R_3 + R_2} \begin{pmatrix} 1 & 2 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & -2 & 1 & 1 & 0 \\ 0 & 0 & -1 & 1 & 0 & 1 \end{pmatrix} \end{aligned}$ $\xrightarrow[\text{then } R_3 \to -R_3]{R_3 \leftrightarrow R_4} \begin{pmatrix} 1 & 2 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & -1 & 0 & -1 \\ 0 & 0 & -2 & 1 & 1 & 0 \end{pmatrix} \xrightarrow{R_4 \to R_4 + 2R_3} \begin{pmatrix} 1 & 2 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & -1 & 0 & -1 \\ 0 & 0 & 0 & -1 & 1 & -2 \end{pmatrix}.$ This echelon form has pivots in columns $1, 2, 3, 4$ , which are the pivot columns by Corollary 3.5.6. By Theorem 3.5.2 (a) the corresponding columns form a basis of the column space, which is $\mathbb{R}^4$ since it contains $\mathbf{e}_1, \dots, \mathbf{e}_4$ . Hence $(\mathbf{v}_1, \mathbf{v}_2, \mathbf{e}_1, \mathbf{e}_2)$ is a basis of $\mathbb{R}^4$ extending $(\mathbf{v}_1, \mathbf{v}_2)$ .

Exercise (B3: Sum and intersection in

\mathbb{R}^5

)

Let $U = \operatorname{span}(\mathbf{u}_1, \mathbf{u}_2, \mathbf{u}_3)$ and $W = \operatorname{span}(\mathbf{w}_1, \mathbf{w}_2)$ in $\mathbb{R}^5$ , where $\begin{aligned} &\mathbf{u}_1 = (1, 1, 0, 0, 1), \quad \mathbf{u}_2 = (0, 1, 1, 0, 0), \quad \mathbf{u}_3 = (1, 0, 0, 1, 0), \\ &\mathbf{w}_1 = (1, 2, 2, 1, 2), \quad \mathbf{w}_2 = (0, 0, 1, 1, 1). \end{aligned}$ Find $\dim U$ , $\dim W$ , a basis of $U + W$ , and a basis of $U \cap W$ . Hence verify Theorem 1.7.3.

Solution. Row reduce $\mathbf{M} = \begin{pmatrix} \mathbf{u}_1 & \mathbf{u}_2 & \mathbf{u}_3 & \mathbf{w}_1 & \mathbf{w}_2 \end{pmatrix}$ : $\begin{aligned} \begin{pmatrix} 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 2 & 0 \\ 0 & 1 & 0 & 2 & 1 \\ 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 2 & 1 \end{pmatrix} &\xrightarrow[R_5 \to R_5 - R_1]{R_2 \to R_2 - R_1} \begin{pmatrix} 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & -1 & 1 & 0 \\ 0 & 1 & 0 & 2 & 1 \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & -1 & 1 & 1 \end{pmatrix} \\ &\xrightarrow{R_3 \to R_3 - R_2} \begin{pmatrix} 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & -1 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & -1 & 1 & 1 \end{pmatrix} \end{aligned}$ $\xrightarrow[R_5 \to R_5 + R_3]{R_4 \to R_4 - R_3} \begin{pmatrix} 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & -1 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 2 & 2 \end{pmatrix} \xrightarrow[\text{then } R_4 \to \frac12 R_4]{R_4 \leftrightarrow R_5} \begin{pmatrix} 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & -1 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{pmatrix}.$ Clearing above the pivots ( $R_3 \to R_3 - R_4$ , $R_2 \to R_2 - R_4$ , $R_1 \to R_1 - R_4$ , then $R_2 \to R_2 + R_3$ , $R_1 \to R_1 - R_3$ ) gives $\mathbf{R} = \begin{pmatrix} 1 & 0 & 0 & 0 & -1 \\ 0 & 1 & 0 & 0 & -1 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{pmatrix}.$ The pivot columns are $1, 2, 3, 4$ , so $(\mathbf{u}_1, \mathbf{u}_2, \mathbf{u}_3, \mathbf{w}_1)$ is independent by Theorem 3.5.2 (a), and so are its sub-lists $(\mathbf{u}_1, \mathbf{u}_2, \mathbf{u}_3)$ and $(\mathbf{w}_1)$ ; also $\mathbf{w}_2$ is not a multiple of $\mathbf{w}_1$ (compare first entries). Hence $\dim U = 3$ and $\dim W = 2$ , with the given spanning lists as bases. By Proposition 3.5.11 (a), $(\mathbf{u}_1, \mathbf{u}_2, \mathbf{u}_3, \mathbf{w}_1)$ is a basis of $U + W$ , so $\dim(U + W) = 4$ .

The only free column is column 5. Setting $x_5 = 1$ gives $\mathbf{n} = (1, 1, 0, -1, 1)$ , a basis of $\operatorname{nul}(\mathbf{M})$ by Theorem 3.5.4. So $\mathbf{u}_1 + \mathbf{u}_2 - \mathbf{w}_1 + \mathbf{w}_2 = \mathbf{0}$ , and by Proposition 3.5.11 (b), $\mathbf{u}_1 + \mathbf{u}_2 = (1, 2, 1, 0, 1)$ is a basis of $U \cap W$ . Check: $\mathbf{w}_1 - \mathbf{w}_2 = (1, 2, 1, 0, 1)$ . Hence $\dim(U \cap W) = 1$ , and $\dim U + \dim W - \dim(U \cap W) = 3 + 2 - 1 = 4 = \dim(U + W).$

C. Going deeper

Exercise (C1: Rank of a sum)

Let $\mathbf{A}, \mathbf{B} \in M_{m \times n}(F)$ . Prove that $\operatorname{rank}(\mathbf{A} + \mathbf{B}) \le \operatorname{rank} \mathbf{A} + \operatorname{rank} \mathbf{B}$ . Give an example where the inequality is strict.

Solution. The $j$ -th column of $\mathbf{A} + \mathbf{B}$ is $\mathbf{a}_j + \mathbf{b}_j$ , which lies in $\operatorname{col}(\mathbf{A}) + \operatorname{col}(\mathbf{B})$ (Definition 1.7.1). This sum is a subspace (Theorem 1.7.1), so by Theorem 1.3.1, $\operatorname{col}(\mathbf{A} + \mathbf{B}) \subseteq \operatorname{col}(\mathbf{A}) + \operatorname{col}(\mathbf{B})$ . By Theorem 1.6.7 and Theorem 1.7.3, $\begin{aligned} \operatorname{rank}(\mathbf{A} + \mathbf{B}) &\le \dim(\operatorname{col}(\mathbf{A}) + \operatorname{col}(\mathbf{B})) \\ &= \operatorname{rank} \mathbf{A} + \operatorname{rank} \mathbf{B} - \dim(\operatorname{col}(\mathbf{A}) \cap \operatorname{col}(\mathbf{B})) \\ &\le \operatorname{rank} \mathbf{A} + \operatorname{rank} \mathbf{B} . \end{aligned}$ For strictness, take $\mathbf{A} = \mathbf{I}_2$ and $\mathbf{B} = -\mathbf{I}_2$ over $\mathbb{R}$ : $\operatorname{rank}(\mathbf{A} + \mathbf{B}) = \operatorname{rank} \mathbf{O} = 0 < 2 + 2$ .

Exercise (C2: Matrices of rank one)

Let $\mathbf{A} \in M_{m \times n}(F)$ . Prove that $\operatorname{rank} \mathbf{A} = 1$ if and only if $\mathbf{A} = \mathbf{x}\mathbf{y}^{\top}$ for some nonzero $\mathbf{x} \in F^m$ and $\mathbf{y} \in F^n$ .

Solution. $(\Leftarrow)$ Suppose $\mathbf{A} = \mathbf{x}\mathbf{y}^{\top}$ with $\mathbf{x}, \mathbf{y} \neq \mathbf{0}$ , and write $\mathbf{y} = (y_1, \dots, y_n)$ . By Theorem 0.9.2, the $j$ -th column of $\mathbf{x}\mathbf{y}^{\top}$ is $\mathbf{x}$ times the $j$ -th column of $\mathbf{y}^{\top}$ , the $1 \times 1$ matrix $(y_j)$ ; that is, $y_j\mathbf{x}$ . So every column lies in $\operatorname{span}(\mathbf{x})$ , and $\operatorname{col}(\mathbf{A}) \subseteq \operatorname{span}(\mathbf{x})$ . Since $\mathbf{y} \neq \mathbf{0}$ , some $y_j \neq 0$ , and then $y_j\mathbf{x} \neq \mathbf{0}$ because $\mathbf{x} \neq \mathbf{0}$ (Theorem 1.1.9). The list $(\mathbf{x})$ is independent, since $a\mathbf{x} = \mathbf{0}$ forces $a = 0$ (Theorem 1.1.9), so $\operatorname{span}(\mathbf{x})$ has dimension $1$ , and $\operatorname{rank} \mathbf{A} \le 1$ by Theorem 1.6.7. On the other hand $\operatorname{rank} \mathbf{A} \neq 0$ : a space of dimension $0$ has the empty list as a basis, so it equals $\operatorname{span}() = \{\mathbf{0}\}$ , but $\operatorname{col}(\mathbf{A})$ contains the nonzero vector $y_j\mathbf{x}$ . Hence $\operatorname{rank} \mathbf{A} = 1$ .

$(\Rightarrow)$ Suppose $\operatorname{rank} \mathbf{A} = 1$ , and let $(\mathbf{x})$ be a basis of $\operatorname{col}(\mathbf{A})$ ; then $\mathbf{x} \neq \mathbf{0}$ . Each column $\mathbf{a}_j \in \operatorname{col}(\mathbf{A})$ equals $y_j\mathbf{x}$ for some $y_j \in F$ . Put $\mathbf{y} = (y_1, \dots, y_n)$ . By the computation in $(\Leftarrow)$ , the $j$ -th column of $\mathbf{x}\mathbf{y}^{\top}$ is $y_j\mathbf{x} = \mathbf{a}_j$ , so $\mathbf{A} = \mathbf{x}\mathbf{y}^{\top}$ . If $\mathbf{y} = \mathbf{0}$ , then $\mathbf{A} = \mathbf{O}$ would have rank $0$ , so $\mathbf{y} \neq \mathbf{0}$ . This proves the claim.

Exercise (C3: The matrix

i + j

)

For $n \ge 1$ , let $\mathbf{A}_n \in M_n(\mathbb{R})$ have entries $a_{ij} = i + j$ . Prove that $\operatorname{rank} \mathbf{A}_1 = 1$ and $\operatorname{rank} \mathbf{A}_n = 2$ for every $n \ge 2$ . Hence find $\operatorname{nullity} \mathbf{A}_n$ .

Hint: write each row as a combination of two fixed row vectors.

Solution. For $n = 1$ , $\mathbf{A}_1 = (2) \neq \mathbf{O}$ , so $\operatorname{rank} \mathbf{A}_1 = 1$ . Let $n \ge 2$ , and put $\mathbf{1} = \begin{pmatrix} 1 & 1 & \cdots & 1 \end{pmatrix}$ and $\mathbf{d} = \begin{pmatrix} 1 & 2 & \cdots & n \end{pmatrix}$ in $M_{1 \times n}(\mathbb{R})$ . Row $i$ of $\mathbf{A}_n$ is $\begin{pmatrix} i + 1 & \cdots & i + n \end{pmatrix} = i\mathbf{1} + \mathbf{d}$ . So $\operatorname{row}(\mathbf{A}_n) \subseteq \operatorname{span}(\mathbf{1}, \mathbf{d})$ , and $\dim \operatorname{row}(\mathbf{A}_n) \le 2$ by Theorem 1.6.3.

Rows 1 and 2 are $\begin{pmatrix} 2 & 3 & \cdots \end{pmatrix}$ and $\begin{pmatrix} 3 & 4 & \cdots \end{pmatrix}$ . If $c_1(\text{row } 1) + c_2(\text{row } 2) = \mathbf{0}$ , the first two entries give $2c_1 + 3c_2 = 0$ and $3c_1 + 4c_2 = 0$ . Subtracting the first from the second gives $c_1 + c_2 = 0$ , so $c_1 = -c_2$ , and then $-2c_2 + 3c_2 = c_2 = 0$ , so $c_1 = 0$ . Hence $\operatorname{row}(\mathbf{A}_n)$ contains two independent vectors, and $\dim \operatorname{row}(\mathbf{A}_n) \ge 2$ by Theorem 1.6.3.

So $\dim \operatorname{row}(\mathbf{A}_n) = 2$ , and $\operatorname{rank} \mathbf{A}_n = 2$ by Theorem 3.5.5. By Theorem 3.5.7, $\operatorname{nullity} \mathbf{A}_n = n - 2$ for $n \ge 2$ , and $\operatorname{nullity} \mathbf{A}_1 = 0$ .

Exercise (C4: Counting right-hand sides over a finite field)

Let $F$ be a finite field with $q$ elements, and let $\mathbf{A} \in M_{m \times n}(F)$ have rank $r$ .

(a) Prove that exactly $q^{r}$ vectors $\mathbf{b} \in F^m$ make $\mathbf{A}\mathbf{x} = \mathbf{b}$ consistent.
(b) By counting the pairs $(\mathbf{x}, \mathbf{b}) \in F^n \times F^m$ with $\mathbf{A}\mathbf{x} = \mathbf{b}$ in two ways, and using Theorem 3.1.3 but not Theorem 3.5.7, prove that $\operatorname{nul}(\mathbf{A})$ has exactly $q^{\,n - r}$ elements. Deduce $\operatorname{nullity} \mathbf{A} = n - r$ : a counting proof of Rank–Nullity over a finite field.
(c) Over $\mathbb{F}_2$ , let $\mathbf{A} = \begin{pmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \end{pmatrix}$ . How many $\mathbf{b} \in \mathbb{F}_2^3$ give a consistent system, and how many solutions does each such system have?

Solution.

(a) By Theorem 3.1.1, $\mathbf{A}\mathbf{x} = \mathbf{b}$ is consistent exactly when $\mathbf{b} \in \operatorname{col}(\mathbf{A})$ . Let $(\mathbf{c}_1, \dots, \mathbf{c}_r)$ be a basis of $\operatorname{col}(\mathbf{A})$ . By Theorem 1.5.1, $(t_1, \dots, t_r) \mapsto t_1\mathbf{c}_1 + \dots + t_r\mathbf{c}_r$ is a bijection $F^r \to \operatorname{col}(\mathbf{A})$ : every vector of $\operatorname{col}(\mathbf{A})$ is hit by exactly one tuple. Since $F^r$ has $q^r$ elements, so does $\operatorname{col}(\mathbf{A})$ .
(b) Let $N = \lvert \operatorname{nul}(\mathbf{A}) \rvert$ . Each $\mathbf{x} \in F^n$ determines exactly one $\mathbf{b} = \mathbf{A}\mathbf{x}$ , so there are $q^n$ pairs. Now group the pairs by $\mathbf{b}$ . If $\mathbf{b} \notin \operatorname{col}(\mathbf{A})$ , there are none, by Theorem 3.1.1. If $\mathbf{b} \in \operatorname{col}(\mathbf{A})$ , pick one solution $\mathbf{p}$ ; by Theorem 3.1.3 the solutions are $\mathbf{p} + \operatorname{nul}(\mathbf{A})$ , and $\mathbf{h} \mapsto \mathbf{p} + \mathbf{h}$ is a bijection from $\operatorname{nul}(\mathbf{A})$ onto this set (it is surjective by definition, and $\mathbf{p} + \mathbf{h} = \mathbf{p} + \mathbf{h}'$ gives $\mathbf{h} = \mathbf{h}'$ ). So each of the $q^r$ vectors $\mathbf{b}$ of (a) accounts for exactly $N$ pairs, and there are $q^r N$ pairs in total. Hence $q^r N = q^n$ , and $N = q^{\,n-r}$ .

Let $d = \operatorname{nullity} \mathbf{A}$ . The argument of (a), applied to a basis of $\operatorname{nul}(\mathbf{A})$ of length $d$ , gives $N = q^{d}$ . So $q^{d} = q^{\,n-r}$ . Since $q \ge 2$ , distinct exponents give distinct powers of $q$ , so $d = n - r$ . This is Theorem 3.5.7, proved here by counting alone.
(c) Over $\mathbb{F}_2$ , $R_3 \to R_3 + R_1$ gives row 3 equal to $(0, 1, 1)$ , and then $R_3 \to R_3 + R_2$ makes it zero. So an echelon form is $\begin{pmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \end{pmatrix}$ , and $\operatorname{rank} \mathbf{A} = 2$ by Corollary 3.5.6. By (a), exactly $2^2 = 4$ of the $8$ vectors $\mathbf{b}$ give a consistent system, and by Theorem 3.5.8 (c) each has $2^{3-2} = 2$ solutions. (The consistent $\mathbf{b}$ are those with $b_1 + b_2 + b_3 = 0$ . The rows of $\mathbf{A}$ add up to zero, so every consistent $\mathbf{b}$ satisfies this equation; exactly $4$ vectors of $\mathbb{F}_2^3$ satisfy it, and $4$ are consistent, so the two sets coincide.)