5.6 Hyperplanes and Linear Systems Revisited

Chapter 3 met subspaces of $F^n$ in two disguises. A parametric description lists spanning vectors, as in $\operatorname{col}(\mathbf{A})$ . An implicit description lists equations, as in $\operatorname{nul}(\mathbf{A})$ . We moved from equations to spanning vectors by elimination, but we never asked whether the reverse is always possible, or how many equations it takes. Duality answers both questions at once: the equations of a subspace $U$ are the elements of $U^{0}$ . This section turns that sentence into an algorithm, proves once more that row rank and nullity add up to $n$ , and ends the chapter with a dictionary between a space and its dual.

5.6.1. Row vectors are functionals

Recall from Theorem 5.1.1 how functionals on $F^n$ look. For $\mathbf{a} = (a_1, \dots, a_n) \in F^n$ , put $\varphi_{\mathbf{a}} \colon F^n \to F, \qquad \varphi_{\mathbf{a}}(\mathbf{x}) = \mathbf{a}^{\top}\mathbf{x} = a_1x_1 + \dots + a_nx_n .$ By that theorem, every $\varphi \in (F^n)^{*}$ is $\varphi_{\mathbf{a}}$ for exactly one $\mathbf{a}$ , namely $a_j = \varphi(\mathbf{e}_j)$ , and $\mathbf{a} \mapsto \varphi_{\mathbf{a}}$ is an isomorphism $F^n \to (F^n)^{*}$ .

The functional $\varphi_{\mathbf{a}}$ is “multiply by the row vector $\mathbf{a}^{\top}$ ”. So the identification is really between functionals and row vectors, and that is what makes a system of equations a dual object. Write the rows of $\mathbf{A} \in M_{m \times n}(F)$ as $\mathbf{a}_1^{\top}, \dots, \mathbf{a}_m^{\top}$ with $\mathbf{a}_i \in F^n$ . The $i$ -th entry of $\mathbf{A}\mathbf{x}$ is $\mathbf{a}_i^{\top}\mathbf{x} = \varphi_{\mathbf{a}_i}(\mathbf{x})$ , so the homogeneous system $\mathbf{A}\mathbf{x} = \mathbf{0}$ says exactly that $\varphi_{\mathbf{a}_1}(\mathbf{x}) = \dots = \varphi_{\mathbf{a}_m}(\mathbf{x}) = 0$ . Hence $\operatorname{nul}(\mathbf{A}) = \operatorname{ker}\varphi_{\mathbf{a}_1} \cap \dots \cap \operatorname{ker}\varphi_{\mathbf{a}_m} .$ Each non-zero row contributes a hyperplane (Theorem 5.5.3), and the null space is their intersection. An equation is a functional, and a system is a list of functionals.

The identification uses the standard basis of $F^n$ , and nothing else. Under it, the coordinate functionals $\mathbf{x} \mapsto x_i$ , which form the dual basis of $(\mathbf{e}_1, \dots, \mathbf{e}_n)$ , correspond to $\mathbf{e}_1, \dots, \mathbf{e}_n$ , that is, to the rows $\mathbf{e}_1^{\top}, \dots, \mathbf{e}_n^{\top}$ .

5.6.2. Every subspace is a solution set

To describe $U$ by equations, we need equations that hold on $U$ , that is, functionals in $U^{0}$ , and enough of them that they hold only on $U$ . The first requirement is the definition of $U^{0}$ . The second follows from the separation of points, applied in the quotient.

Lemma 5.6.1 (A subspace is cut out by its annihilator)

Let $V$ be a finite-dimensional vector space and $U$ a subspace. For $\mathbf{v} \in V$ , $\mathbf{v} \in U \quad \iff \quad \varphi(\mathbf{v}) = 0 \text{ for every } \varphi \in U^{0} .$ If $(\varphi_1, \dots, \varphi_k)$ is a basis of $U^{0}$ , then $U = \operatorname{ker}\varphi_1 \cap \dots \cap \operatorname{ker}\varphi_k$ .

Proof. $(\Rightarrow)$ This is Definition 5.2.1.

$(\Leftarrow)$ Suppose $\mathbf{v} \notin U$ . Then $\mathbf{v} + U$ is a non-zero vector of $V/U$ by Lemma 4.4.3 (b), and $V/U$ is finite-dimensional (Theorem 4.4.5). By Theorem 5.1.5 there is $\psi \in (V/U)^{*}$ with $\psi(\mathbf{v} + U) \ne 0$ . By Theorem 5.5.2, $\varphi = \psi \circ \pi$ lies in $U^{0}$ , and $\varphi(\mathbf{v}) = \psi(\mathbf{v} + U) \ne 0$ . This proves the contrapositive.

For the last statement, $U \subseteq \operatorname{ker}\varphi_i$ for each $i$ since $\varphi_i \in U^{0}$ . Conversely, if $\varphi_i(\mathbf{v}) = 0$ for all $i$ , then every $\varphi = \sum_i c_i\varphi_i \in U^{0}$ has $\varphi(\mathbf{v}) = 0$ , so $\mathbf{v} \in U$ by $(\Leftarrow)$ .

The lemma is Corollary 5.3.4 in disguise. That corollary says $U^{00} = U$ under $V \cong V^{**}$ ; the lemma unpacks it into a statement about vectors. In $F^n$ , with rows in place of functionals, it becomes the main theorem of this section.

Theorem 5.6.2 (Every Subspace Is a Solution Set)

Let $U$ be a subspace of $F^n$ with $\dim U = k$ .

(a) There is a matrix $\mathbf{A} \in M_{(n-k) \times n}(F)$ with $U = \operatorname{nul}(\mathbf{A})$ . One may take as rows of $\mathbf{A}$ the vectors $\mathbf{a}_1^{\top}, \dots, \mathbf{a}_{n-k}^{\top}$ for any $\mathbf{a}_i \in F^n$ such that $(\varphi_{\mathbf{a}_1}, \dots, \varphi_{\mathbf{a}_{n-k}})$ is a basis of $U^{0}$ .
(b) If $\mathbf{B} \in M_{m \times n}(F)$ and $\operatorname{nul}(\mathbf{B}) = U$ , then $m \ge n - k$ .

So $U$ is the solution set of a homogeneous system of exactly $n - k = \operatorname{codim} U$ equations, and of no system with fewer. (When $k = n$ , that is $U = F^n$ , this is the empty system, with no equations.)

Proof.

(a) By Theorem 5.2.2, $\dim U^{0} = n - k$ . Choose a basis of $U^{0}$ ; by the identification above it is $(\varphi_{\mathbf{a}_1}, \dots, \varphi_{\mathbf{a}_{n-k}})$ for some $\mathbf{a}_i \in F^n$ . Let $\mathbf{A}$ have rows $\mathbf{a}_1^{\top}, \dots, \mathbf{a}_{n-k}^{\top}$ . Then $\operatorname{nul}(\mathbf{A}) = \operatorname{ker}\varphi_{\mathbf{a}_1} \cap \dots \cap \operatorname{ker}\varphi_{\mathbf{a}_{n-k}} = U,$ where the second equality is Lemma 5.6.1.
(b) By Theorem 3.5.7, $\operatorname{rank} \mathbf{B} = n - \operatorname{nullity} \mathbf{B} = n - k$ . By Theorem 3.5.5, $\operatorname{rank} \mathbf{B} = \dim \operatorname{row}(\mathbf{B})$ . The row space is spanned by the $m$ rows of $\mathbf{B}$ , so $m \ge \dim\operatorname{row}(\mathbf{B})$ by Theorem 1.6.3 (b). Hence $m \ge n - k$ .

The count is the one promised by codimension: dimension counts free parameters, codimension counts independent equations, and in $F^n$ the two add up to $n$ .

Example (Equations for a plane in

\mathbb{R}^4

)

Let $U = \operatorname{span}(\mathbf{u}_1, \mathbf{u}_2) \subseteq \mathbb{R}^4$ , where $\mathbf{u}_1 = (1, 1, 0, 1)$ and $\mathbf{u}_2 = (0, 1, 1, 1)$ . Find a system of linear equations whose solution set is $U$ .

Solution. The two vectors are independent (compare first entries, then third), so $\dim U = 2$ , and we expect $4 - 2 = 2$ equations. For $\mathbf{a} = (a_1, a_2, a_3, a_4)$ , the functional $\varphi_{\mathbf{a}}$ lies in $U^{0}$ exactly when it vanishes at both spanning vectors (Theorem 5.2.3 (b)): $a_1 + a_2 + a_4 = 0, \qquad a_2 + a_3 + a_4 = 0 .$ This is the system $\mathbf{M}\mathbf{a} = \mathbf{0}$ for the matrix $\mathbf{M}$ whose rows are $\mathbf{u}_1^{\top}$ and $\mathbf{u}_2^{\top}$ . Subtracting the second row from the first gives the RREF $\mathbf{M} = \begin{pmatrix} 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 1 \end{pmatrix} \ \longrightarrow\ \begin{pmatrix} 1 & 0 & -1 & 0 \\ 0 & 1 & 1 & 1 \end{pmatrix},$ with free variables $a_3, a_4$ . By Theorem 3.5.4, a basis of the solutions is $(1, -1, 1, 0)$ (from $a_3 = 1, a_4 = 0$ ) and $(0, -1, 0, 1)$ (from $a_3 = 0, a_4 = 1$ ). The corresponding functionals form a basis of $U^{0}$ , and by Theorem 5.6.2, $U = \{ \mathbf{x} \in \mathbb{R}^4 : x_1 - x_2 + x_3 = 0, \ \ x_4 - x_2 = 0 \} .$ Check. Both equations hold at $\mathbf{u}_1$ : $1 - 1 + 0 = 0$ and $1 - 1 = 0$ ; and at $\mathbf{u}_2$ : $0 - 1 + 1 = 0$ and $1 - 1 = 0$ . The coefficient matrix $\begin{pmatrix} 1 & -1 & 1 & 0 \\ 0 & -1 & 0 & 1 \end{pmatrix}$ has rank 2, so its null space has dimension $4 - 2 = 2$ , and it contains the independent vectors $\mathbf{u}_1, \mathbf{u}_2$ ; hence it equals $U$ (Theorem 1.6.8). The implicit description says: $U$ consists of the vectors with $x_4 = x_2$ and $x_1 + x_3 = x_2$ .

5.6.3. From spans to equations and back

The example is an instance of a general procedure. Both directions of the conversion are “compute a null space”, applied to transposed data.

Algorithm. Parametric to implicit. Input: vectors $\mathbf{v}_1, \dots, \mathbf{v}_p \in F^n$ with $U = \operatorname{span}(\mathbf{v}_1, \dots, \mathbf{v}_p)$ .

Form $\mathbf{M} \in M_{p \times n}(F)$ whose $i$ -th row is $\mathbf{v}_i^{\top}$ .
Row reduce $\mathbf{M}$ and find a basis $\mathbf{n}_1, \dots, \mathbf{n}_d$ of $\operatorname{nul}(\mathbf{M})$ as in Theorem 3.5.4.
Output the matrix $\mathbf{A} \in M_{d \times n}(F)$ whose $j$ -th row is $\mathbf{n}_j^{\top}$ , that is, the equations $\mathbf{n}_j^{\top}\mathbf{x} = 0$ for $j = 1, \dots, d$ .

Implicit to parametric. Input: $\mathbf{A} \in M_{m \times n}(F)$ . Output: a basis of $\operatorname{nul}(\mathbf{A})$ , found by row reduction as in Theorem 3.5.4.

The second half was proved correct in Chapter 3. The first half is new.

Theorem 5.6.3 (Correctness of the Conversion)

Let $\mathbf{v}_1, \dots, \mathbf{v}_p \in F^n$ , $U = \operatorname{span}(\mathbf{v}_1, \dots, \mathbf{v}_p)$ , and let $\mathbf{M}$ and $\mathbf{A}$ be as in the algorithm. Then $\operatorname{nul}(\mathbf{A}) = U$ , and $\mathbf{A}$ has exactly $d = n - \dim U$ rows, which are linearly independent.

Idea. The only thing to see is what step 2 computes. The $i$ -th entry of $\mathbf{M}\mathbf{n}$ is $\mathbf{v}_i^{\top}\mathbf{n} = \varphi_{\mathbf{n}}(\mathbf{v}_i)$ . So $\mathbf{n} \in \operatorname{nul}(\mathbf{M})$ says that the functional $\varphi_{\mathbf{n}}$ vanishes at every $\mathbf{v}_i$ , that is, $\varphi_{\mathbf{n}} \in U^{0}$ . Step 2 therefore computes a basis of $U^{0}$ , and the theorem of the previous subsection does the rest.

Proof. For $\mathbf{n} \in F^n$ , the $i$ -th entry of $\mathbf{M}\mathbf{n}$ is $\mathbf{v}_i^{\top}\mathbf{n} = \mathbf{n}^{\top}\mathbf{v}_i = \varphi_{\mathbf{n}}(\mathbf{v}_i)$ , where the middle equality holds because both sides equal $\sum_j (\mathbf{v}_i)_j n_j$ . Hence $\mathbf{n} \in \operatorname{nul}(\mathbf{M}) \iff \varphi_{\mathbf{n}}(\mathbf{v}_i) = 0 \text{ for all } i \iff \varphi_{\mathbf{n}} \in \{\mathbf{v}_1, \dots, \mathbf{v}_p\}^{0} = U^{0},$ where the last equality is Theorem 5.2.3 (b). So the isomorphism $\mathbf{n} \mapsto \varphi_{\mathbf{n}}$ maps $\operatorname{nul}(\mathbf{M})$ onto $U^{0}$ . An isomorphism carries a basis to a basis (Theorem 2.5.2), so $(\varphi_{\mathbf{n}_1}, \dots, \varphi_{\mathbf{n}_d})$ is a basis of $U^{0}$ . In particular $d = \dim U^{0} = n - \dim U$ by Theorem 5.2.2, and the $\mathbf{n}_j$ , hence the rows $\mathbf{n}_j^{\top}$ , are independent. By Theorem 5.6.2 (a), the matrix $\mathbf{A}$ with rows $\mathbf{n}_1^{\top}, \dots, \mathbf{n}_d^{\top}$ satisfies $\operatorname{nul}(\mathbf{A}) = U$ .

The algorithm does not need the $\mathbf{v}_i$ to be independent. Redundant spanning vectors only produce zero rows in the RREF of $\mathbf{M}$ , and the count $d = n - \operatorname{rank} \mathbf{M}$ automatically uses $\dim U = \operatorname{rank} \mathbf{M}$ .

Running both halves in turn is a useful self-check. Starting from $\mathbf{A}$ in Example (Equations for a plane in $\mathbb{R}^4$ ) and computing $\operatorname{nul}(\mathbf{A})$ must return a basis of $U$ ; starting from that basis and running the first half must return equations with the same solution set, though not necessarily the same equations.

Warning. Equations for a subspace are far from unique, and more equations do not mean a smaller solution set. In Example (Equations for a plane in $\mathbb{R}^4$ ), the system $x_1 - x_2 + x_3 = 0$ , $x_4 - x_2 = 0$ , $x_1 + x_3 - x_4 = 0$ has the same solution set $U$ : the third equation is the sum of the first and the negative of the second, so it adds a functional already in $U^{0}$ . Three equations in $\mathbb{R}^4$ cut out a two-dimensional subspace here, not a one-dimensional one. Each new equation lowers the dimension by one only if its functional is not a combination of the previous ones. A theorem later in this section makes this precise.

5.6.4. Affine solution sets

An inhomogeneous equation $\mathbf{a}^{\top}\mathbf{x} = b$ with $\mathbf{a} \ne \mathbf{0}$ defines a set that is not a subspace when $b \ne 0$ . It is a translate of the hyperplane $H = \operatorname{ker}\varphi_{\mathbf{a}}$ : if $\mathbf{p}$ is one solution, then by Theorem 3.1.3 the solutions are $\mathbf{p} + H$ . We call a coset $\mathbf{p} + H$ of a hyperplane $H$ (Definition 4.4.2) an affine hyperplane. In $\mathbb{R}^3$ , the plane $x + y + z = 1$ is an affine hyperplane, parallel to the hyperplane $x + y + z = 0$ .

A system $\mathbf{A}\mathbf{x} = \mathbf{b}$ with rows $\mathbf{a}_i^{\top}$ and right-hand sides $b_i$ asks for the vectors lying on all the sets $\{ \mathbf{x} : \mathbf{a}_i^{\top}\mathbf{x} = b_i \}$ at once. Each such set is an affine hyperplane if $\mathbf{a}_i \ne \mathbf{0}$ ; if $\mathbf{a}_i = \mathbf{0}$ , it is all of $F^n$ (when $b_i = 0$ ) or empty (when $b_i \ne 0$ ). So the solution set of a linear system is an intersection of affine hyperplanes, apart from these trivial rows. The duality theorems give the converse.

Proposition 5.6.4 (Cosets as intersections of affine hyperplanes)

Let $U$ be a subspace of $F^n$ of dimension $k < n$ , and let $\mathbf{p} \in F^n$ . Let $\mathbf{A} \in M_{(n-k) \times n}(F)$ be as in Theorem 5.6.2 (a), with rows $\mathbf{a}_1^{\top}, \dots, \mathbf{a}_{n-k}^{\top}$ . Then $\mathbf{p} + U = \{ \mathbf{x} \in F^n : \mathbf{A}\mathbf{x} = \mathbf{A}\mathbf{p} \} = \bigcap_{i=1}^{n-k} \{ \mathbf{x} : \mathbf{a}_i^{\top}\mathbf{x} = \mathbf{a}_i^{\top}\mathbf{p} \},$ an intersection of $n - k$ affine hyperplanes.

Proof. By Theorem 5.6.2, $\operatorname{nul}(\mathbf{A}) = U$ . The vector $\mathbf{p}$ is one solution of $\mathbf{A}\mathbf{x} = \mathbf{A}\mathbf{p}$ , so by Theorem 3.1.3 its solution set is $\mathbf{p} + \operatorname{nul}(\mathbf{A}) = \mathbf{p} + U$ . The $i$ -th equation reads $\mathbf{a}_i^{\top}\mathbf{x} = \mathbf{a}_i^{\top}\mathbf{p}$ . Each $\varphi_{\mathbf{a}_i}$ is non-zero, because it belongs to a basis of $U^{0}$ ; so $\operatorname{ker}\varphi_{\mathbf{a}_i}$ is a hyperplane (Theorem 5.5.3), and $\{ \mathbf{x} : \mathbf{a}_i^{\top}\mathbf{x} = \mathbf{a}_i^{\top}\mathbf{p} \} = \mathbf{p} + \operatorname{ker}\varphi_{\mathbf{a}_i}$ is an affine hyperplane, again by Theorem 3.1.3 applied to this one equation.

Unlike hyperplanes, which all contain $\mathbf{0}$ , affine hyperplanes can be disjoint: $x_1 + x_2 = 0$ and $x_1 + x_2 = 1$ are parallel lines in $\mathbb{R}^2$ . That is the geometric picture of an inconsistent system.

5.6.5. The row space annihilates the null space

In Chapter 3, Theorem 3.5.7 said $\operatorname{rank} \mathbf{A} + \operatorname{nullity} \mathbf{A} = n$ , and its proof counted pivot and free columns in the RREF. The duality of this chapter explains the same equation without elimination: the rows of $\mathbf{A}$ are exactly the equations satisfied by the null space.

Theorem 5.6.5 (The Row Space Is the Annihilator of the Null Space)

Let $\mathbf{A} \in M_{m \times n}(F)$ . Identifying a row vector $\mathbf{a}^{\top} \in M_{1 \times n}(F)$ with the functional $\varphi_{\mathbf{a}} \in (F^n)^{*}$ , $\{ \varphi_{\mathbf{a}} : \mathbf{a}^{\top} \in \operatorname{row}(\mathbf{A}) \} = \operatorname{nul}(\mathbf{A})^{0} .$ Consequently $\dim \operatorname{row}(\mathbf{A}) + \dim \operatorname{nul}(\mathbf{A}) = n$ .

Idea. Let $T = T_{\mathbf{A}} \colon F^n \to F^m$ . Its kernel is $\operatorname{nul}(\mathbf{A})$ , and Theorem 5.4.3 says $\operatorname{im} T' = (\operatorname{ker} T)^{0}$ . So it is enough to see that $\operatorname{im} T'$ is the row space. Pull back a functional $\varphi_{\mathbf{y}}$ on $F^m$ : the result is $\mathbf{x} \mapsto \mathbf{y}^{\top} \mathbf{A}\mathbf{x}$ , which is multiplication by the row $\mathbf{y}^{\top} \mathbf{A}$ , the combination of the rows of $\mathbf{A}$ with coefficients $y_1, \dots, y_m$ . The transpose of Chapter 0 appears exactly here: $\mathbf{y}^{\top} \mathbf{A} = (\mathbf{A}^{\top}\mathbf{y})^{\top}$ .

Proof. Let $T = T_{\mathbf{A}} \colon F^n \to F^m$ , $T(\mathbf{x}) = \mathbf{A}\mathbf{x}$ , so that $\operatorname{ker} T = \operatorname{nul}(\mathbf{A})$ . Every functional on $F^m$ is $\varphi_{\mathbf{y}}$ for a unique $\mathbf{y} \in F^m$ , as recalled at the start of this section. By Definition 5.4.1, associativity of matrix multiplication, and Theorem 0.9.5, $\begin{aligned} T'(\varphi_{\mathbf{y}})(\mathbf{x}) &= \varphi_{\mathbf{y}}(\mathbf{A}\mathbf{x}) = \mathbf{y}^{\top}(\mathbf{A}\mathbf{x}) = (\mathbf{y}^{\top} \mathbf{A})\mathbf{x} \\ &= (\mathbf{A}^{\top}\mathbf{y})^{\top}\mathbf{x} = \varphi_{\mathbf{A}^{\top}\mathbf{y}}(\mathbf{x}) \qquad (\mathbf{x} \in F^n), \end{aligned}$ so $T'(\varphi_{\mathbf{y}}) = \varphi_{\mathbf{A}^{\top}\mathbf{y}}$ . The columns of $\mathbf{A}^{\top}$ are $\mathbf{a}_1, \dots, \mathbf{a}_m$ , where $\mathbf{a}_i^{\top}$ are the rows of $\mathbf{A}$ , so $\mathbf{A}^{\top}\mathbf{y} = y_1\mathbf{a}_1 + \dots + y_m\mathbf{a}_m$ by Theorem 0.9.3. As $\mathbf{y}$ runs over $F^m$ , these are all the combinations of $\mathbf{a}_1, \dots, \mathbf{a}_m$ , and since transposing respects combinations (Theorem 0.9.5), they are exactly the vectors $\mathbf{a}$ with $\mathbf{a}^{\top} \in \operatorname{row}(\mathbf{A})$ (Definition 3.5.2). Hence $\operatorname{im} T' = \{ \varphi_{\mathbf{a}} : \mathbf{a}^{\top} \in \operatorname{row}(\mathbf{A}) \} .$ By Theorem 5.4.3, $\operatorname{im} T' = (\operatorname{ker} T)^{0} = \operatorname{nul}(\mathbf{A})^{0}$ , which is the first claim.

For the count, $\mathbf{a}^{\top} \mapsto \varphi_{\mathbf{a}}$ is an isomorphism $M_{1 \times n}(F) \to (F^n)^{*}$ (transposition followed by $\mathbf{a} \mapsto \varphi_{\mathbf{a}}$ ), so $\dim \operatorname{row}(\mathbf{A}) = \dim \operatorname{nul}(\mathbf{A})^{0} = n - \dim\operatorname{nul}(\mathbf{A})$ by Theorem 5.2.2.

The count is Rank–Nullity for matrices once more, now as a statement about annihilators: $\operatorname{rank} \mathbf{A} = \dim\operatorname{row}(\mathbf{A})$ counts independent equations and $\operatorname{nullity} \mathbf{A}$ counts free parameters. It also says that the given equations generate all the equations satisfied by $\operatorname{nul}(\mathbf{A})$ : any linear equation that holds on the solution set of $\mathbf{A}\mathbf{x} = \mathbf{0}$ is a combination of the rows of $\mathbf{A}$ .

Corollary 5.6.6 (Same solutions, same row space)

Let $\mathbf{A} \in M_{m \times n}(F)$ and $\mathbf{B} \in M_{p \times n}(F)$ . Then $\operatorname{nul}(\mathbf{A}) = \operatorname{nul}(\mathbf{B})$ if and only if $\operatorname{row}(\mathbf{A}) = \operatorname{row}(\mathbf{B})$ .

Proof. $(\Leftarrow)$ If $\operatorname{row}(\mathbf{A}) = \operatorname{row}(\mathbf{B})$ , then $\operatorname{nul}(\mathbf{A})^{0} = \operatorname{nul}(\mathbf{B})^{0}$ by Theorem 5.6.5, so $\operatorname{nul}(\mathbf{A}) = \operatorname{nul}(\mathbf{B})$ by Corollary 5.3.5.

$(\Rightarrow)$ If $\operatorname{nul}(\mathbf{A}) = \operatorname{nul}(\mathbf{B})$ , then $\{ \varphi_{\mathbf{a}} : \mathbf{a}^{\top} \in \operatorname{row}(\mathbf{A}) \} = \operatorname{nul}(\mathbf{A})^{0} = \{ \varphi_{\mathbf{a}} : \mathbf{a}^{\top} \in \operatorname{row}(\mathbf{B}) \}$ by Theorem 5.6.5. Since $\mathbf{a}^{\top} \mapsto \varphi_{\mathbf{a}}$ is injective, $\operatorname{row}(\mathbf{A}) = \operatorname{row}(\mathbf{B})$ .

Chapter 3 showed that row operations preserve the null space (Theorem 3.5.1). The corollary gives a converse in terms of row spaces: two systems in the same unknowns have the same solutions exactly when each equation of one is a combination of the equations of the other.

5.6.6. Sums and intersections by duality

Parametric and implicit descriptions are good at different things. A sum is easy parametrically: $U + W$ is spanned by a spanning list of $U$ followed by one of $W$ (Proposition 1.7.2). An intersection is easy implicitly: if $U = \operatorname{nul}(\mathbf{A})$ and $W = \operatorname{nul}(\mathbf{B})$ , then $\mathbf{x} \in U \cap W$ exactly when $\mathbf{x}$ satisfies both systems, so $U \cap W = \operatorname{nul} \begin{pmatrix} \mathbf{A} \\ \mathbf{B} \end{pmatrix},$ the null space of the matrix with the rows of $\mathbf{A}$ above the rows of $\mathbf{B}$ . Duality explains why each is easy where it is. The rows of the stacked matrix span $\operatorname{row}(\mathbf{A}) + \operatorname{row}(\mathbf{B})$ , which corresponds to $U^{0} + W^{0} = (U \cap W)^{0}$ by Theorem 5.6.5 and Theorem 5.2.3 (d); and $(U + W)^{0} = U^{0} \cap W^{0}$ says that the equations of a sum are the equations common to both pieces.

Example (An intersection computed from equations)

In $\mathbb{R}^4$ , let $U = \operatorname{span}((1, 0, 1, 2), (0, 1, 1, 1))$ and $W = \operatorname{span}((1, 1, 0, 1), (1, 3, 0, 1))$ , as in Example (A basis of an intersection). Find $U \cap W$ by first finding equations for $U$ and for $W$ .

Solution. Equations for $U$ . A row $(a_1, a_2, a_3, a_4)$ annihilates both spanning vectors when $a_1 + a_3 + 2a_4 = 0$ and $a_2 + a_3 + a_4 = 0$ . This system is already in RREF, with free $a_3, a_4$ ; the basic solutions are $(-1, -1, 1, 0)$ and $(-2, -1, 0, 1)$ . Changing signs, which does not change the kernels, $U = \{ x_1 + x_2 - x_3 = 0, \ \ 2x_1 + x_2 - x_4 = 0 \} .$ Equations for $W$ . Here $a_1 + a_2 + a_4 = 0$ and $a_1 + 3a_2 + a_4 = 0$ . Subtracting gives $a_2 = 0$ , and then $a_1 = -a_4$ , with $a_3$ free. The basic solutions are $(0, 0, 1, 0)$ and $(-1, 0, 0, 1)$ , so $W = \{ x_3 = 0, \ \ x_4 - x_1 = 0 \} .$ Intersection. Stack the four equations. From $W$ : $x_3 = 0$ and $x_4 = x_1$ . Then $x_1 + x_2 - x_3 = 0$ gives $x_2 = -x_1$ , and the last equation $2x_1 + x_2 - x_4 = 2x_1 - x_1 - x_1 = 0$ holds automatically. So $U \cap W = \{ (t, -t, 0, t) : t \in \mathbb{R} \} = \operatorname{span}((1, -1, 0, 1)),$ in agreement with Chapter 3.

The redundancy of the fourth equation is not a coincidence. The four rows span $U^{0} + W^{0} = (U \cap W)^{0}$ , which has dimension $4 - 1 = 3$ , so exactly one of the four equations must be a consequence of the others.

Contrast with Chapter 3. There we put the four spanning vectors as columns of one matrix and read the intersection off a null vector, a relation $\mathbf{u}_1 - \mathbf{u}_2 = 2\mathbf{w}_1 - \mathbf{w}_2$ . Here we computed two small null spaces (the equations) and then one more (the intersection). The equation method pays off when the subspaces are given by equations in the first place, or when several intersections with the same $U$ are needed: the equations of $U$ are computed once.

5.6.7. Independent functionals

The warning above said that $k$ equations cut out codimension $k$ only when they are independent. We now make that precise, in any dimension. Given $\varphi_1, \dots, \varphi_k \in V^{*}$ , bundle them into one linear map $\Phi \colon V \to F^k, \qquad \Phi(\mathbf{v}) = (\varphi_1(\mathbf{v}), \dots, \varphi_k(\mathbf{v})),$ which is linear because each entry is. Its kernel is $\operatorname{ker}\varphi_1 \cap \dots \cap \operatorname{ker}\varphi_k$ , the common solution set of the $k$ equations.

Theorem 5.6.7 (Independent Functionals)

Let $V$ be a vector space over $F$ , of any dimension, and let $\varphi_1, \dots, \varphi_k \in V^{*}$ . The following are equivalent:

(a) $(\varphi_1, \dots, \varphi_k)$ is linearly independent in $V^{*}$ ;
(b) $\Phi \colon V \to F^k$ is surjective;
(c) $\operatorname{ker}\varphi_1 \cap \dots \cap \operatorname{ker}\varphi_k$ has codimension exactly $k$ .

Idea. A dependence $\sum c_i\varphi_i = 0$ says that $\sum c_iy_i = 0$ for every $\mathbf{y} = \Phi(\mathbf{v})$ in the image: the image lies in the kernel of a non-zero functional on $F^k$ . Conversely, if the image is a proper subspace of $F^k$ , some non-zero functional on $F^k$ kills it, and its coefficients give a dependence. The First Isomorphism Theorem turns “surjective” into “codimension $k$ ”.

Proof.

(a) $\Rightarrow$ (b). Suppose $\Phi$ is not surjective. Then $\operatorname{im}\Phi$ is a proper subspace of $F^k$ , so $\dim\operatorname{im}\Phi < k$ and, by Theorem 5.2.2, $(\operatorname{im}\Phi)^{0} \ne \{0\}$ . Take a non-zero functional in it; as at the start of this section it is $\varphi_{\mathbf{c}}$ , $\mathbf{y} \mapsto c_1y_1 + \dots + c_ky_k$ , for a non-zero $\mathbf{c} \in F^k$ . For every $\mathbf{v} \in V$ , $\Phi(\mathbf{v}) \in \operatorname{im}\Phi$ , so $(c_1\varphi_1 + \dots + c_k\varphi_k)(\mathbf{v}) = \varphi_{\mathbf{c}}(\Phi(\mathbf{v})) = 0 .$ Thus $c_1\varphi_1 + \dots + c_k\varphi_k = 0$ with $\mathbf{c} \ne \mathbf{0}$ , and the list is dependent. This proves the contrapositive.
(b) $\Rightarrow$ (a). Suppose $\Phi$ is surjective and $c_1\varphi_1 + \dots + c_k\varphi_k = 0$ . For each $j$ , choose $\mathbf{v}_j$ with $\Phi(\mathbf{v}_j) = \mathbf{e}_j$ , that is, $\varphi_i(\mathbf{v}_j) = \delta_{ij}$ . Evaluating the relation at $\mathbf{v}_j$ gives $c_j = 0$ . So the list is independent.
(c) $\Leftrightarrow$ (c). By Theorem 4.4.7, $V/\operatorname{ker}\Phi \cong \operatorname{im}\Phi$ , and $\operatorname{ker}\Phi = \bigcap_i \operatorname{ker}\varphi_i$ . So the codimension of $\bigcap_i\operatorname{ker}\varphi_i$ is $\dim\operatorname{im}\Phi$ , which equals $k$ exactly when $\operatorname{im}\Phi = F^k$ (Theorem 1.6.8).

For $V = F^n$ and $\varphi_i = \varphi_{\mathbf{a}_i}$ , the map $\Phi$ is $T_{\mathbf{A}}$ , where $\mathbf{A}$ has rows $\mathbf{a}_i^{\top}$ . The theorem then says: the rows of $\mathbf{A}$ are independent if and only if $\mathbf{A}\mathbf{x} = \mathbf{b}$ is solvable for every $\mathbf{b} \in F^k$ . Independent equations never contradict each other.

Quick check. In $\mathbb{R}^3$ , consider $\varphi_1 = x + y$ , $\varphi_2 = y + z$ , $\varphi_3 = x - z$ . What is the codimension of $\operatorname{ker}\varphi_1 \cap \operatorname{ker}\varphi_2 \cap \operatorname{ker}\varphi_3$ ? Is the system $x + y = 1$ , $y + z = 1$ , $x - z = 1$ solvable?

Solution. $\varphi_3 = \varphi_1 - \varphi_2$ , so the list is dependent, while $(\varphi_1, \varphi_2)$ is independent (look at the coefficients of $x$ and $z$ ). The three kernels intersect in $\operatorname{ker}\varphi_1 \cap \operatorname{ker}\varphi_2$ , of codimension 2 by Theorem 5.6.7, so the intersection is a line, not $\{\mathbf{0}\}$ . The system is not solvable: any solution would give $1 = x - z = (x + y) - (y + z) = 1 - 1 = 0$ . This is (b) failing: $(1, 1, 1) \notin \operatorname{im}\Phi$ .

5.6.8. Summary and transfer

The chapter has built a dictionary. On the left is a finite-dimensional space $V$ of dimension $n$ , or a linear map $T \colon V \to W$ between finite-dimensional spaces; on the right is its mirror image in the dual. Every entry has been proved in this chapter, and every arrow reverses inclusions or directions.

In $V$ (vectors)	In $V^{*}$ (measurements)
a subspace $U$ , $\dim U = k$	its annihilator $U^{0}$ , $\dim U^{0} = n - k$
$U \subseteq W$	$W^{0} \subseteq U^{0}$
$U + W$	$U^{0} \cap W^{0}$
$U \cap W$	$U^{0} + W^{0}$
$U$ itself, recovered as $U^{00}$	$U^{0}$ determines $U$
the quotient $V/U$	the subspace $U^{0} \cong (V/U)^{*}$
the subspace $U$	the quotient $V^{}/U^{0} \cong U^{}$
a hyperplane $H$	a non-zero functional, up to scale
a spanning list (parametric form)	a list of equations (implicit form)
dimension (free parameters)	codimension (independent equations)
a basis $(\mathbf{v}_1, \dots, \mathbf{v}_n)$	its dual basis $(\varphi_1, \dots, \varphi_n)$
$T \colon V \to W$	$T' \colon W^{} \to V^{}$ , backwards
$T$ injective	$T'$ surjective
$T$ surjective	$T'$ injective
$\operatorname{ker} T$	$\operatorname{im} T' = (\operatorname{ker} T)^{0}$
$\operatorname{im} T$	$\operatorname{ker} T' = (\operatorname{im} T)^{0}$
$\operatorname{rank} T$	$\operatorname{rank} T' = \operatorname{rank} T$
the matrix $\mathbf{A} = [T]_{\mathcal{B}}^{\mathcal{C}}$	the transpose $\mathbf{A}^{\top} = [T']_{\mathcal{C}^{}}^{\mathcal{B}^{}}$
$\operatorname{nul}(\mathbf{A})$	$\operatorname{row}(\mathbf{A})$ , as $\operatorname{nul}(\mathbf{A})^{0}$
$V$	$V^{**}$ , naturally isomorphic via $\operatorname{ev}_V$

Three moves make the dictionary usable, and they transfer to any situation with a pairing between two spaces.

Test against functionals. To show a vector is zero, or lies in a subspace, check that enough functionals vanish on it (Theorem 5.1.5, Lemma 5.6.1).
Pass to the dual and count. A question about a subspace can be translated into one about its annihilator, where $\dim U + \dim U^{0} = n$ often settles it. The third proof of row rank = column rank (Corollary 5.4.4) and the count in Theorem 5.6.5 both work this way.
Prefer the natural map. Isomorphisms such as $V \cong V^{**}$ , $(V/U)^{*} \cong U^{0}$ and $U^{*} \cong V^{*}/U^{0}$ are defined without a basis, so they can be used in any coordinates and survive changes of basis. Isomorphisms such as $V \cong V^{*}$ depend on a choice, and a proof that uses one must say which.

In Chapter 11, an inner product will give a chosen isomorphism $V \cong V^{*}$ , and the annihilator $U^{0}$ will reappear inside $V$ itself as the orthogonal complement. The dictionary above is the part of that story that needs no inner product.

5.6.9. Exercises

A. Check your understanding

Exercise (A1)

(a) Explain how a row vector $\mathbf{a}^{\top}$ (with $\mathbf{a} \in F^n$ ) defines a linear functional on $F^n$ , and why every functional arises this way.
(b) What is the least number of homogeneous linear equations whose solution set is a given $3$ -dimensional subspace of $F^7$ ?
(c) True or false: every system of three homogeneous equations in $\mathbb{R}^5$ has a solution set of dimension $2$ . Justify your answer.
(d) State the relation between $\operatorname{row}(\mathbf{A})$ and $\operatorname{nul}(\mathbf{A})$ in terms of annihilators.
(e) True or false: if $\mathbf{A}$ and $\mathbf{B}$ have $n$ columns and $\operatorname{nul}(\mathbf{A}) = \operatorname{nul}(\mathbf{B})$ , then $\mathbf{A}$ and $\mathbf{B}$ have the same number of rows. Justify your answer.
(f) Name the dual counterparts of: a sum of subspaces; an injective linear map; the matrix of a linear map.

Solution.

(a) $\varphi_{\mathbf{a}}(\mathbf{x}) = \mathbf{a}^{\top}\mathbf{x}$ is linear by the rules of matrix multiplication (Theorem 0.9.4). A functional $\varphi$ equals $\varphi_{\mathbf{a}}$ with $a_j = \varphi(\mathbf{e}_j)$ , because both agree on the standard basis (Theorem 2.1.5); this is Theorem 5.1.1.
(b) $7 - 3 = 4$ , by Theorem 5.6.2.
(c) False. The equations may be dependent: $x_1 = 0$ written three times has a solution set of dimension $4$ . The dimension is $5 - \operatorname{rank} \mathbf{A}$ , which is $2$ only when the three rows are independent.
(d) Identifying rows with functionals, $\operatorname{row}(\mathbf{A}) = \operatorname{nul}(\mathbf{A})^{0}$ (Theorem 5.6.5).
(e) False. By Corollary 5.6.6 they have the same row space, but not necessarily the same number of rows: $\mathbf{A} = \begin{pmatrix} 1 & 0 \end{pmatrix}$ and $\mathbf{B} = \begin{pmatrix} 1 & 0 \\ 2 & 0 \end{pmatrix}$ both have null space $\operatorname{span}(\mathbf{e}_2)$ .
(f) An intersection of annihilators, $(U + W)^{0} = U^{0} \cap W^{0}$ ; a surjective dual map; the transpose matrix.

B. Practice

Exercise (B1: Equations for a span)

Let $U = \operatorname{span}((1, 2, 0, -1), (2, 1, 1, 0), (3, 3, 1, -1)) \subseteq \mathbb{R}^4$ .

(a) Find $\dim U$ .
(b) Find a system of homogeneous linear equations with solution set $U$ , using as few equations as possible.
(c) Hence write the affine plane $(1, 0, 0, 0) + U$ as the solution set of a linear system.

Solution.

(a) The third vector is the sum of the first two, so $U = \operatorname{span}((1, 2, 0, -1), (2, 1, 1, 0))$ by Theorem 1.3.5. These two vectors are independent, since neither is a multiple of the other, so they form a basis of $U$ and $\dim U = 2$ .
(b) By Theorem 5.6.3, we need a basis of $\operatorname{nul}(\mathbf{M})$ , where $\mathbf{M}$ has the three vectors as rows. Row reduction gives $\mathbf{M} = \begin{pmatrix} 1 & 2 & 0 & -1 \\ 2 & 1 & 1 & 0 \\ 3 & 3 & 1 & -1 \end{pmatrix} \longrightarrow \begin{pmatrix} 1 & 0 & \tfrac23 & \tfrac13 \\ 0 & 1 & -\tfrac13 & -\tfrac23 \\ 0 & 0 & 0 & 0 \end{pmatrix}.$ The free variables are the third and fourth. Setting them to $(3, 0)$ and $(0, 3)$ to clear denominators gives the null vectors $(-2, 1, 3, 0)$ and $(-1, 2, 0, 3)$ . So $U = \{ \mathbf{x} \in \mathbb{R}^4 : -2x_1 + x_2 + 3x_3 = 0, \ \ -x_1 + 2x_2 + 3x_4 = 0 \} .$ Check on the first two spanning vectors, which suffice since they span $U$ : $-2 + 2 + 0 = 0$ , $-1 + 4 - 3 = 0$ ; $-4 + 1 + 3 = 0$ , $-2 + 2 + 0 = 0$ . Two equations is the minimum, by Theorem 5.6.2 (b).
(c) By Proposition 5.6.4, replace each right-hand side by the value of the left-hand side at $(1, 0, 0, 0)$ : $(1, 0, 0, 0) + U = \{ \mathbf{x} : -2x_1 + x_2 + 3x_3 = -2, \ \ -x_1 + 2x_2 + 3x_4 = -1 \} .$

Exercise (B2: A spanning list for a system)

Let $U = \{ \mathbf{x} \in \mathbb{R}^4 : x_1 + x_2 - x_3 + 2x_4 = 0, \ \ 2x_1 + 2x_2 + x_3 + x_4 = 0 \}$ .

(a) Find a basis of $U$ .
(b) Run the parametric-to-implicit algorithm on your basis, and check that the resulting equations have the same solution set as the given ones, by comparing row spaces.

Solution.

(a) Row reduce the coefficient matrix: subtract twice row 1 from row 2 to get $(0, 0, 3, -3)$ , divide by 3, then add row 2 to row 1: $\begin{pmatrix} 1 & 1 & -1 & 2 \\ 2 & 2 & 1 & 1 \end{pmatrix} \longrightarrow \begin{pmatrix} 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & -1 \end{pmatrix}.$ The pivots are in columns 1 and 3, and $x_2, x_4$ are free. By Theorem 3.5.4, a basis is $\mathbf{n}_1 = (-1, 1, 0, 0)$ and $\mathbf{n}_2 = (-1, 0, 1, 1)$ .
(b) Put $\mathbf{n}_1^{\top}, \mathbf{n}_2^{\top}$ as the rows of $\mathbf{M}$ and solve $\mathbf{M}\mathbf{a} = \mathbf{0}$ : $-a_1 + a_2 = 0$ and $-a_1 + a_3 + a_4 = 0$ . So $a_2 = a_1$ and $a_3 = a_1 - a_4$ , with $a_1, a_4$ free; the basic solutions are $(1, 1, 1, 0)$ and $(0, 0, -1, 1)$ . The new system is $x_1 + x_2 + x_3 = 0$ , $-x_3 + x_4 = 0$ . Its rows lie in the row space of the original matrix, which equals the row space of the RREF (Theorem 3.5.1), since $(1, 1, 1, 0) = (1, 1, 0, 1) + (0, 0, 1, -1)$ and $(0, 0, -1, 1) = -(0, 0, 1, -1)$ . Both row spaces are two-dimensional, so they are equal (Theorem 1.6.8), and the two systems have the same solution set by Corollary 5.6.6.

Exercise (B3: Two planes in

\mathbb{R}^4

)

Let $U = \operatorname{span}((1, 0, 0, 1), (0, 1, 1, 0))$ and $W = \operatorname{span}((1, 1, 0, 0), (0, 0, 1, 1))$ in $\mathbb{R}^4$ .

(a) Find two equations for $U$ and two for $W$ .
(b) Use them to find $U \cap W$ .
(c) Find a single equation for $U + W$ , using $(U + W)^{0} = U^{0} \cap W^{0}$ .

Solution.

(a) Each pair is independent, so each plane has dimension 2 and needs two equations. The functionals $x_1 - x_4$ and $x_2 - x_3$ vanish at $(1, 0, 0, 1)$ and $(0, 1, 1, 0)$ , and they are independent; since $\dim U^{0} = 2$ (Theorem 5.2.2), they form a basis of $U^{0}$ . So $U = \{ x_1 = x_4, \ x_2 = x_3 \}$ by Theorem 5.6.2. In the same way $x_1 - x_2$ and $x_3 - x_4$ form a basis of $W^{0}$ , and $W = \{ x_1 = x_2, \ x_3 = x_4 \}$ .
(b) $U \cap W$ is the solution set of all four equations: $x_1 = x_4$ , $x_2 = x_3$ , $x_1 = x_2$ , $x_3 = x_4$ . They force $x_1 = x_2 = x_3 = x_4$ , so $U \cap W = \operatorname{span}((1, 1, 1, 1))$ .
(c) A functional in $U^{0} \cap W^{0}$ has the form $a(x_1 - x_4) + b(x_2 - x_3) = c(x_1 - x_2) + d(x_3 - x_4)$ . Comparing coefficients of $x_1, x_2, x_3, x_4$ : $a = c$ , $b = -c$ , $-b = d$ , $-a = -d$ . So $a = c = d$ and $b = -a$ , and $U^{0} \cap W^{0} = \operatorname{span}(x_1 - x_2 + x_3 - x_4)$ . By Theorem 5.2.3 (c) and Lemma 5.6.1, $U + W = \{ \mathbf{x} : x_1 - x_2 + x_3 - x_4 = 0 \},$ a hyperplane. Consistently, $\dim(U + W) = 2 + 2 - 1 = 3$ by Theorem 1.7.3.

C. Going deeper

Exercise (C1: Avoiding finitely many subspaces)

Let $F$ be an infinite field, $V$ a vector space over $F$ with $1 \le \dim V = n < \infty$ , and $U_1, \dots, U_k$ proper subspaces of $V$ .

(a) Prove that for each $i$ there is a non-zero $\varphi_i \in V^{*}$ with $U_i \subseteq \operatorname{ker}\varphi_i$ .
(b) Let $(\mathbf{b}_1, \dots, \mathbf{b}_n)$ be a basis of $V$ , and for $t \in F$ put $\mathbf{v}(t) = \mathbf{b}_1 + t\mathbf{b}_2 + t^2\mathbf{b}_3 + \dots + t^{n-1}\mathbf{b}_n$ . Show that $t \mapsto \varphi_i(\mathbf{v}(t))$ is given by a non-zero polynomial of degree at most $n - 1$ .
(c) Deduce that some vector of $V$ lies in none of $U_1, \dots, U_k$ . In other words, $V$ is not a union of finitely many proper subspaces.
(d) Show that the hypothesis that $F$ is infinite cannot be dropped: over $\mathbb{F}_q$ , the space $\mathbb{F}_q^2$ is the union of $q + 1$ proper subspaces.

Hint: for (c), use Lemma 3.7.2.

Solution.

(a) Since $U_i \ne V$ , pick $\mathbf{v} \notin U_i$ . By Lemma 5.6.1 there is $\varphi_i \in U_i^{0}$ with $\varphi_i(\mathbf{v}) \ne 0$ . Then $\varphi_i \ne 0$ and $U_i \subseteq \operatorname{ker}\varphi_i$ .
(b) By linearity, $\varphi_i(\mathbf{v}(t)) = \sum_{j=1}^{n} \varphi_i(\mathbf{b}_j)\,t^{j-1}$ , which is the value at $t$ of the polynomial $p_i(x) = \sum_{j=1}^{n} \varphi_i(\mathbf{b}_j)\,x^{j-1}$ of degree at most $n - 1$ . Its coefficients are $\varphi_i(\mathbf{b}_1), \dots, \varphi_i(\mathbf{b}_n)$ , which are not all zero, since otherwise $\varphi_i$ would vanish on a basis and be zero (Theorem 2.1.5). So $p_i \ne 0$ .
(c) By Lemma 3.7.2, each $p_i$ has at most $n - 1$ roots in $F$ , so together they have at most $k(n - 1)$ roots. Since $F$ is infinite, there is $t_0 \in F$ that is a root of none of them. Then $\varphi_i(\mathbf{v}(t_0)) = p_i(t_0) \ne 0$ , so $\mathbf{v}(t_0) \notin \operatorname{ker}\varphi_i \supseteq U_i$ , for every $i$ .
(d) $\mathbb{F}_q^2$ has $q^2 - 1$ non-zero vectors, and each line through $\mathbf{0}$ contains $q - 1$ of them (the non-zero multiples of one vector). Two distinct lines meet only in $\mathbf{0}$ , so there are $(q^2 - 1)/(q - 1) = q + 1$ lines, and every non-zero vector lies on one of them. Hence $\mathbb{F}_q^2$ is the union of its $q + 1$ lines, each a proper subspace. For $q = 2$ these are $\operatorname{span}((1, 0))$ , $\operatorname{span}((0, 1))$ and $\operatorname{span}((1, 1))$ , as in Exercise (C1: Covering a Space by Subspaces). The proof of (c) breaks exactly where it used infinitely many $t$ : here $k(n - 1) = q + 1$ exceeds $\lvert F \rvert = q$ .

Exercise (C2: The least number of equations for a system)

Let $\mathbf{A} \in M_{m \times n}(F)$ and $\mathbf{b} \in F^m$ , and suppose the solution set $S$ of $\mathbf{A}\mathbf{x} = \mathbf{b}$ is non-empty.

(a) Prove that if $\mathbf{B} \in M_{p \times n}(F)$ , $\mathbf{c} \in F^p$ and $\mathbf{B}\mathbf{x} = \mathbf{c}$ has the same solution set $S$ , then $\operatorname{nul}(\mathbf{B}) = \operatorname{nul}(\mathbf{A})$ .
(b) Deduce that every system with solution set $S$ has at least $\operatorname{rank} \mathbf{A}$ equations, and that some system with solution set $S$ has exactly $\operatorname{rank} \mathbf{A}$ equations.
(c) Show by an example that (b) fails without the hypothesis $S \ne \varnothing$ .

Solution.

(a) Fix $\mathbf{p} \in S$ . By Theorem 3.1.3, $S = \mathbf{p} + \operatorname{nul}(\mathbf{A})$ and also $S = \mathbf{p} + \operatorname{nul}(\mathbf{B})$ . For $\mathbf{h} \in \operatorname{nul}(\mathbf{A})$ , $\mathbf{p} + \mathbf{h} \in S = \mathbf{p} + \operatorname{nul}(\mathbf{B})$ , so $\mathbf{h} \in \operatorname{nul}(\mathbf{B})$ . Swapping the roles of $\mathbf{A}$ and $\mathbf{B}$ gives the reverse inclusion, so $\operatorname{nul}(\mathbf{A}) = \operatorname{nul}(\mathbf{B})$ .
(b) Let $k = \dim\operatorname{nul}(\mathbf{A}) = n - \operatorname{rank} \mathbf{A}$ (Theorem 3.5.7). If $\mathbf{B}\mathbf{x} = \mathbf{c}$ with $p$ equations has solution set $S$ , then $\operatorname{nul}(\mathbf{B}) = \operatorname{nul}(\mathbf{A})$ by (a), so $p \ge n - k = \operatorname{rank} \mathbf{A}$ by Theorem 5.6.2 (b). Conversely, take $\mathbf{A}_0 \in M_{(n-k) \times n}(F)$ with $\operatorname{nul}(\mathbf{A}_0) = \operatorname{nul}(\mathbf{A})$ , which exists by Theorem 5.6.2 (a) (if $k = n$ , take the empty system, whose solution set is $F^n = S$ ). By Proposition 5.6.4, or directly by Theorem 3.1.3, the system $\mathbf{A}_0\mathbf{x} = \mathbf{A}_0\mathbf{p}$ has solution set $\mathbf{p} + \operatorname{nul}(\mathbf{A}) = S$ , and it has $n - k = \operatorname{rank} \mathbf{A}$ equations.
(c) Over any field, $0x_1 = 1$ (in $F^1$ ) has empty solution set and coefficient matrix of rank $0$ , yet no system with $0$ equations has empty solution set, since the empty system is solved by every vector. So at least one equation is needed, which is more than $\operatorname{rank} \mathbf{A} = 0$ .