1.5 Bases and Coordinates

Spanning lists and independent lists each solve half of a problem. A spanning list reaches every vector of the space, but it may reach some vectors in more than one way. An independent list never wastes a vector, but it may not reach everything. This section puts the two halves together. The result, a basis, turns an abstract vector space into columns of numbers, and we prove that every space spanned by a finite list has one.

1.5.1. What makes coordinates work

Start with the plane. Every vector of $\mathbb{R}^2$ can be written as $(x, y) = x\mathbf{e}_1 + y\mathbf{e}_2,$ and the pair $(x, y)$ is its address. Two separate facts make this addressing system work. First, every vector has an address: the list $(\mathbf{e}_1, \mathbf{e}_2)$ spans $\mathbb{R}^2$ . Second, every vector has only one address: if $x\mathbf{e}_1 + y\mathbf{e}_2 = x'\mathbf{e}_1 + y'\mathbf{e}_2$ , then $(x, y) = (x', y')$ , so $x = x'$ and $y = y'$ .

Nothing about this is special to $\mathbf{e}_1$ and $\mathbf{e}_2$ . Take instead the list $((1, 1), (1, -1))$ . To find an address for $(x, y)$ we solve $a(1, 1) + b(1, -1) = (x, y), \qquad\text{that is,}\qquad a + b = x, \quad a - b = y.$ Adding and subtracting the two equations gives $2a = x + y$ and $2b = x - y$ . So there is a solution, and it is the only one: $a = \frac{x + y}{2}, \qquad b = \frac{x - y}{2}.$ For example $(3, 1) = 2(1, 1) + 1(1, -1)$ , and no other pair of scalars works. The grid is slanted, but every point still has exactly one address.

Diagram. Labels: x, y, (1,1), (1,-1), 2(1,1), (3,1)

Look at which property did which job. Existence of an address is spanning. Uniqueness of the address is independence: by Theorem 1.4.3, a list is independent exactly when every vector in its span has only one expression as a combination of it. A coordinate system is a list that does both jobs at once.

A basis is a list with enough vectors to build everything and no vector to spare.

1.5.2. Bases

Definition 1.5.1 (Basis)

Let $V$ be a vector space over $F$ . A basis of $V$ is a list $(\mathbf{v}_1, \dots, \mathbf{v}_n)$ of vectors in $V$ such that

(B1) $(\mathbf{v}_1, \dots, \mathbf{v}_n)$ is linearly independent, and
(B2) $(\mathbf{v}_1, \dots, \mathbf{v}_n)$ spans $V$ , that is, $\operatorname{span}(\mathbf{v}_1, \dots, \mathbf{v}_n) = V$ .

We usually name a basis with a calligraphic letter, $\mathcal{B} = (\mathbf{v}_1, \dots, \mathbf{v}_n)$ , and call $n$ its length. The plural of basis is bases.

In words: (B1) says that the only combination of the $\mathbf{v}_i$ equal to $\mathbf{0}$ is the one with all coefficients zero, so no vector in the list is wasted. (B2) says that every vector of $V$ is some combination of the $\mathbf{v}_i$ , so nothing is out of reach. The basis is a list, so its entries come in a definite order, and a basis is always a basis of a particular space: $(\mathbf{e}_1, \mathbf{e}_2)$ is a basis of $\mathbb{R}^2$ , but not of $\mathbb{R}^3$ .

We start with the bases that come with the running examples.

Example (Standard Bases)

Show that each of the following lists is a basis. They are called the standard bases.

(a) $(\mathbf{e}_1, \dots, \mathbf{e}_n)$ in $F^n$ , where $\mathbf{e}_i$ has $1$ in position $i$ and $0$ elsewhere.
(b) $(1, x, x^2, \dots, x^n)$ in $F[x]_{\le n}$ .
(c) $(\mathbf{E}_{11}, \mathbf{E}_{12}, \dots, \mathbf{E}_{1n}, \mathbf{E}_{21}, \dots, \mathbf{E}_{mn})$ in $M_{m \times n}(F)$ , where the matrix unit $\mathbf{E}_{ij}$ has $1$ in entry $(i, j)$ and $0$ elsewhere, listed row by row.

Solution.

(a) (B2): every $(x_1, \dots, x_n) \in F^n$ equals $x_1\mathbf{e}_1 + \dots + x_n\mathbf{e}_n$ . (B1): let $a_1\mathbf{e}_1 + \dots + a_n\mathbf{e}_n = \mathbf{0}$ . The left side is the column $(a_1, \dots, a_n)$ , so comparing entries gives $a_1 = \dots = a_n = 0$ .
(b) (B2): by Definition 0.8.4, every element of $F[x]_{\le n}$ has the form $a_0 + a_1x + \dots + a_nx^n$ , which is a combination of $1, x, \dots, x^n$ . (B1): let $a_0 \cdot 1 + a_1x + \dots + a_nx^n = 0$ . Here $0$ is the zero polynomial, all of whose coefficients are $0$ . Two polynomials are equal exactly when their coefficients agree (Definition 0.8.1), so $a_0 = a_1 = \dots = a_n = 0$ .
(c) (B2): a matrix $\mathbf{A} = (a_{ij})$ equals $\sum_{i, j} a_{ij}\mathbf{E}_{ij}$ , since both sides have $a_{ij}$ in entry $(i, j)$ . (B1): if $\sum_{i, j} c_{ij}\mathbf{E}_{ij}$ is the zero matrix, then its $(i, j)$ entry $c_{ij}$ is $0$ for every $i, j$ .

The next examples show that a space has other bases, that the field matters, and what happens in the smallest space.

Example (Three More Bases)

Show that each list is a basis.

(a) $((1, 1), (1, -1))$ in $\mathbb{R}^2$ .
(b) $(1, i)$ in $\mathbb{C}$ , regarded as a vector space over $\mathbb{R}$ .
(c) The empty list $()$ in the zero space $\{\mathbf{0}\}$ .

Solution.

(a) We showed above that for every $(x, y) \in \mathbb{R}^2$ the equation $a(1, 1) + b(1, -1) = (x, y)$ has a solution, so (B2) holds. Taking $(x, y) = (0, 0)$ , the only solution is $a = \frac{0 + 0}{2} = 0$ and $b = 0$ , so (B1) holds.
(b) The scalars are now real. (B2): every complex number is $a + bi = a \cdot 1 + b \cdot i$ with $a, b \in \mathbb{R}$ (Definition 0.6.1). (B1): let $a \cdot 1 + b \cdot i = 0$ with $a, b \in \mathbb{R}$ . A complex number is $0$ exactly when its real and imaginary parts are $0$ , so $a = b = 0$ .
(c) The empty list is linearly independent: there are no coefficients, so the condition “all coefficients are zero” holds vacuously. Its span is $\{\mathbf{0}\}$ by the convention for the empty span. So both (B1) and (B2) hold.

The degenerate case (c) matters more than it looks. Without it, the zero space would be the one space with no basis, and every theorem below would need an exception for it.

Non-examples by minimal change. Add one vector to the standard basis of $\mathbb{R}^2$ , making $((1, 0), (0, 1), (1, 1))$ . Spanning (B2) still holds, since the first two vectors already span. But (B1) fails: $1 \cdot (1, 0) + 1 \cdot (0, 1) + (-1) \cdot (1, 1) = (0, 0),$ with coefficients not all zero. The effect is exactly the loss of unique addresses: $(3, 1) = 3(1, 0) + 1(0, 1) + 0(1, 1) = 2(1, 0) + 0(0, 1) + 1(1, 1)$ .

Now remove a vector instead. In $\mathbb{R}^3$ , the list $((1, 0, 0), (0, 1, 0))$ is still independent, since $a(1, 0, 0) + b(0, 1, 0) = (a, b, 0) = \mathbf{0}$ forces $a = b = 0$ . But (B2) fails: every combination $(a, b, 0)$ has third entry $0$ , so $(0, 0, 1)$ is out of reach.

Quick check. Is $((1, 2), (2, 1), (0, 0))$ a basis of $\mathbb{R}^2$ ? If not, which of (B1) and (B2) fails?

Solution. No. (B2) holds: $(1, 2)$ and $(2, 1)$ already span $\mathbb{R}^2$ , because solving $a(1, 2) + b(2, 1) = (x, y)$ gives $a = \frac{2y - x}{3}$ and $b = \frac{2x - y}{3}$ . But (B1) fails, because the list contains the zero vector: $0(1, 2) + 0(2, 1) + 1(0, 0) = (0, 0)$ with a non-zero coefficient.

Why this definition. Drop (B1), and addresses stop being unique, as the list $((1, 0), (0, 1), (1, 1))$ showed. Drop (B2), and some vectors have no address at all. Keeping both is exactly what an addressing system needs. The name comes from the everyday word: the basis is what everything else is built on.

Remark. Why a list and not a set? Two reasons. Coordinates, defined below, are a column of numbers, and a column needs to know which scalar comes first. And a set would hide repeats: the list $((1, 0), (1, 0), (0, 1))$ is dependent, since $1(1, 0) - 1(1, 0) = \mathbf{0}$ , but as a set $\{(1, 0), (1, 0), (0, 1)\} = \{(1, 0), (0, 1)\}$ it would look like the standard basis.

Warning. Say a basis, not the basis. A space usually has many bases; a non-zero space over an infinite field such as $\mathbb{R}$ has infinitely many. For instance $((1, 0), (c, 1))$ is a basis of $\mathbb{R}^2$ for every real number $c$ , since $(x, y) = (x - cy)(1, 0) + y(c, 1)$ , and this is the only solution. The standard basis is a convenient choice, not a canonical one.

1.5.3. Unique representation and coordinates

We found the definition by asking for addresses that exist and are unique. The first result confirms that this is exactly what a basis delivers, and nothing more.

Theorem 1.5.1 (Unique Representation)

Let $V$ be a vector space over $F$ , and let $\mathcal{B} = (\mathbf{v}_1, \dots, \mathbf{v}_n)$ be a list in $V$ . Then $\mathcal{B}$ is a basis of $V$ if and only if every $\mathbf{v} \in V$ can be written as $\mathbf{v} = a_1\mathbf{v}_1 + \dots + a_n\mathbf{v}_n \qquad (a_1, \dots, a_n \in F)$ in exactly one way.

Proof. $(\Rightarrow)$ Let $\mathbf{v} \in V$ . Since $\mathcal{B}$ spans $V$ , there are scalars with $\mathbf{v} = a_1\mathbf{v}_1 + \dots + a_n\mathbf{v}_n$ . Suppose also $\mathbf{v} = b_1\mathbf{v}_1 + \dots + b_n\mathbf{v}_n$ . Subtracting the two expressions and regrouping with the vector space axioms, $(a_1 - b_1)\mathbf{v}_1 + \dots + (a_n - b_n)\mathbf{v}_n = \mathbf{v} - \mathbf{v} = \mathbf{0}.$ Since $\mathcal{B}$ is linearly independent, $a_i - b_i = 0$ for every $i$ . Hence the two expressions are the same.

$(\Leftarrow)$ Every $\mathbf{v} \in V$ is a combination of $\mathcal{B}$ , so $\mathcal{B}$ spans $V$ . For independence, let $a_1\mathbf{v}_1 + \dots + a_n\mathbf{v}_n = \mathbf{0}$ . We also have $\mathbf{0} = 0\mathbf{v}_1 + \dots + 0\mathbf{v}_n$ . By uniqueness of the expression for the vector $\mathbf{0}$ , all $a_i = 0$ . Hence $\mathcal{B}$ is linearly independent, and $\mathcal{B}$ is a basis.

This is Theorem 1.4.3 in the special case where the span is the whole space. The theorem also gives a second way to check that a list is a basis: solve for the coefficients of a general vector, and see that there is always exactly one solution. We did exactly that for $((1, 1), (1, -1))$ .

Whenever something exists and is unique, it deserves a name.

Definition 1.5.2 (Coordinates)

Let $\mathcal{B} = (\mathbf{v}_1, \dots, \mathbf{v}_n)$ be a basis of a vector space $V$ over $F$ , and let $\mathbf{v} \in V$ . The unique scalars $a_1, \dots, a_n$ with $\mathbf{v} = a_1\mathbf{v}_1 + \dots + a_n\mathbf{v}_n$ are the coordinates of $\mathbf{v}$ with respect to $\mathcal{B}$ . The column $[\mathbf{v}]_{\mathcal{B}} \mathrel{:=} \begin{pmatrix} a_1 \\ \vdots \\ a_n \end{pmatrix} \in F^n$ is the coordinate vector of $\mathbf{v}$ with respect to $\mathcal{B}$ .

In the standard basis of $F^n$ , the coordinate vector of $(x_1, \dots, x_n)$ is the column $(x_1, \dots, x_n)$ itself. That is why we rarely notice coordinates in $F^n$ . In other bases and other spaces they carry real information.

Example (Coordinates of a Polynomial)

Show that $\mathcal{B} = (1, 1 + x, 1 + x + x^2)$ is a basis of $\mathbb{R}[x]_{\le 2}$ , and find $[p]_{\mathcal{B}}$ for $p = 3 - x + 2x^2$ .

Solution. We use Theorem 1.5.1. Let $q = q_0 + q_1x + q_2x^2 \in \mathbb{R}[x]_{\le 2}$ be arbitrary. For scalars $a, b, c$ , $a \cdot 1 + b(1 + x) + c(1 + x + x^2) = (a + b + c) + (b + c)x + cx^2.$ Two polynomials are equal exactly when their coefficients agree, so this equals $q$ if and only if $c = q_2, \qquad b + c = q_1, \qquad a + b + c = q_0.$ Solving from the top, $c = q_2$ , then $b = q_1 - q_2$ , then $a = q_0 - q_1$ . So every $q$ has exactly one expression, and $\mathcal{B}$ is a basis of $\mathbb{R}[x]_{\le 2}$ .

For $p = 3 - x + 2x^2$ we have $q_0 = 3$ , $q_1 = -1$ , $q_2 = 2$ . Hence $c = 2$ , $b = -1 - 2 = -3$ , and $a = 3 - (-1) = 4$ : $[p]_{\mathcal{B}} = \begin{pmatrix} 4 \\ -3 \\ 2 \end{pmatrix}.$ Check: $4 - 3(1 + x) + 2(1 + x + x^2) = (4 - 3 + 2) + (-3 + 2)x + 2x^2 = 3 - x + 2x^2$ . In the standard basis $(1, x, x^2)$ , the same polynomial has coordinate vector $(3, -1, 2)$ .

Warning. Coordinates depend on the basis and on its order. Take $\mathbf{v} = (3, 1) \in \mathbb{R}^2$ . With respect to the standard basis $\mathcal{E} = (\mathbf{e}_1, \mathbf{e}_2)$ , $[\mathbf{v}]_{\mathcal{E}} = (3, 1)$ . With respect to $\mathcal{B} = ((1, 1), (1, -1))$ , $[\mathbf{v}]_{\mathcal{B}} = (2, 1)$ . With respect to $\mathcal{B}' = ((1, -1), (1, 1))$ , the same two vectors in the other order, $[\mathbf{v}]_{\mathcal{B}'} = (1, 2)$ . A column of numbers means nothing until you say which ordered basis it refers to.

The point of coordinates is that they turn computations in $V$ into computations with columns. That works because they respect the two operations.

Theorem 1.5.2 (Coordinates Respect the Operations)

Let $\mathcal{B} = (\mathbf{v}_1, \dots, \mathbf{v}_n)$ be a basis of a vector space $V$ over $F$ . Then for all $\mathbf{u}, \mathbf{v} \in V$ and $c \in F$ , $[\mathbf{u} + \mathbf{v}]_{\mathcal{B}} = [\mathbf{u}]_{\mathcal{B}} + [\mathbf{v}]_{\mathcal{B}}, \qquad [c\mathbf{v}]_{\mathcal{B}} = c\,[\mathbf{v}]_{\mathcal{B}}.$ Moreover, every column $(a_1, \dots, a_n) \in F^n$ is the coordinate vector of exactly one vector of $V$ , namely $a_1\mathbf{v}_1 + \dots + a_n\mathbf{v}_n$ .

Proof. Let $[\mathbf{u}]_{\mathcal{B}} = (a_1, \dots, a_n)$ and $[\mathbf{v}]_{\mathcal{B}} = (b_1, \dots, b_n)$ . By the vector space axioms, $\mathbf{u} + \mathbf{v} = \sum_{i=1}^n a_i\mathbf{v}_i + \sum_{i=1}^n b_i\mathbf{v}_i = \sum_{i=1}^n (a_i + b_i)\mathbf{v}_i, \qquad c\mathbf{v} = c\sum_{i=1}^n b_i\mathbf{v}_i = \sum_{i=1}^n (cb_i)\mathbf{v}_i.$ By Theorem 1.5.1 these are the only expressions of $\mathbf{u} + \mathbf{v}$ and $c\mathbf{v}$ in $\mathcal{B}$ , so their coefficients are the coordinates: $[\mathbf{u} + \mathbf{v}]_{\mathcal{B}} = (a_i + b_i)_i$ and $[c\mathbf{v}]_{\mathcal{B}} = (cb_i)_i$ , as claimed.

For the last statement, let $(a_1, \dots, a_n) \in F^n$ and $\mathbf{w} = a_1\mathbf{v}_1 + \dots + a_n\mathbf{v}_n$ . By Definition 1.5.2, $[\mathbf{w}]_{\mathcal{B}} = (a_1, \dots, a_n)$ . If also $[\mathbf{w}']_{\mathcal{B}} = (a_1, \dots, a_n)$ , then by definition $\mathbf{w}' = a_1\mathbf{v}_1 + \dots + a_n\mathbf{v}_n = \mathbf{w}$ .

So a basis of length $n$ sets up a one-to-one correspondence $\mathbf{v} \mapsto [\mathbf{v}]_{\mathcal{B}}$ between $V$ and $F^n$ that respects addition and scaling. Any question about sums and multiples in $V$ can be answered in $F^n$ instead. In Chapter 2 we will call such a correspondence an isomorphism.

1.5.4. Every finite spanning list contains a basis

Where do bases come from? A finite-dimensional space is, by Definition 1.3.4, a space spanned by some finite list. That list reaches everything but may contain waste, so the natural plan is to throw the waste away.

Care is needed about what to throw away. In $((1, 0), (0, 1), (1, 1))$ each vector is a combination of the other two. Any single one can go, but not two of them. So redundancy is not a property of one vector alone: it depends on which other vectors stay. The fix is to decide one vector at a time, reading from left to right, and to compare each vector only with the vectors already kept.

First, a small lemma that tells us when a kept list stays independent.

Lemma 1.5.3 (Appending a Vector to an Independent List)

Let $(\mathbf{u}_1, \dots, \mathbf{u}_k)$ be a linearly independent list in a vector space $V$ , and let $\mathbf{v} \in V$ . Then $(\mathbf{u}_1, \dots, \mathbf{u}_k, \mathbf{v})$ is linearly independent if and only if $\mathbf{v} \notin \operatorname{span}(\mathbf{u}_1, \dots, \mathbf{u}_k)$ .

Proof. $(\Rightarrow)$ Suppose $\mathbf{v} \in \operatorname{span}(\mathbf{u}_1, \dots, \mathbf{u}_k)$ , say $\mathbf{v} = c_1\mathbf{u}_1 + \dots + c_k\mathbf{u}_k$ . Then $c_1\mathbf{u}_1 + \dots + c_k\mathbf{u}_k + (-1)\mathbf{v} = \mathbf{0}$ , with the coefficient $-1 \ne 0$ . So the longer list is dependent. This proves $(\Rightarrow)$ by contraposition.

$(\Leftarrow)$ Suppose $\mathbf{v} \notin \operatorname{span}(\mathbf{u}_1, \dots, \mathbf{u}_k)$ , and let $a_1\mathbf{u}_1 + \dots + a_k\mathbf{u}_k + b\mathbf{v} = \mathbf{0}$ . If $b \ne 0$ , then $b^{-1}$ exists and $\mathbf{v} = -b^{-1}a_1\mathbf{u}_1 - \dots - b^{-1}a_k\mathbf{u}_k \in \operatorname{span}(\mathbf{u}_1, \dots, \mathbf{u}_k),$ a contradiction. Hence $b = 0$ . Then $a_1\mathbf{u}_1 + \dots + a_k\mathbf{u}_k = \mathbf{0}$ , and the independence of $(\mathbf{u}_1, \dots, \mathbf{u}_k)$ gives $a_1 = \dots = a_k = 0$ . So all coefficients are zero, and the longer list is independent.

The direction $(\Leftarrow)$ is Exercise (C2: Adding a Vector outside the Span). When $k = 0$ , the lemma says that the one-vector list $(\mathbf{v})$ is independent exactly when $\mathbf{v} \notin \operatorname{span}() = \{\mathbf{0}\}$ , that is, when $\mathbf{v} \ne \mathbf{0}$ , in agreement with Example (Degenerate Lists).

Now the procedure. Given a list $(\mathbf{v}_1, \dots, \mathbf{v}_m)$ in $V$ , sifting it means the following.

Algorithm. Start with the empty list $S_0 = ()$ . For $r = 1, 2, \dots, m$ in turn:

if $\mathbf{v}_r \notin \operatorname{span}(S_{r-1})$ , keep it: $S_r = (S_{r-1}, \mathbf{v}_r)$ ;
if $\mathbf{v}_r \in \operatorname{span}(S_{r-1})$ , discard it: $S_r = S_{r-1}$ .

The final list $S_m$ is the sifted list of $(\mathbf{v}_1, \dots, \mathbf{v}_m)$ .

Here $(S_{r-1}, \mathbf{v}_r)$ means the list $S_{r-1}$ with $\mathbf{v}_r$ appended at the end. Each $S_r$ is a sub-list of $(\mathbf{v}_1, \dots, \mathbf{v}_m)$ : it is obtained by deleting some entries and keeping the rest in their original order.

Theorem 1.5.4 (Sifting Theorem)

Let $(\mathbf{v}_1, \dots, \mathbf{v}_m)$ be a list in a vector space $V$ , and let $S_m$ be its sifted list. Then $S_m$ is linearly independent and $\operatorname{span}(S_m) = \operatorname{span}(\mathbf{v}_1, \dots, \mathbf{v}_m).$ In particular, every finite list that spans $V$ contains a sub-list that is a basis of $V$ .

Idea. Sifting protects two things at every step. A vector is kept only when it lies outside the span of what was kept before, so by Lemma 1.5.3 the kept list stays independent. A vector is discarded only when it is already in that span, so by Theorem 1.3.5 discarding it loses nothing. We turn “at every step” into an induction on $r$ , the number of vectors read so far, with the invariant: $S_r$ is independent and has the same span as $\mathbf{v}_1, \dots, \mathbf{v}_r$ .

Proof. We prove by induction on $r \in \{0, 1, \dots, m\}$ the statement

$P(r)$ : the list $S_r$ is linearly independent and $\operatorname{span}(S_r) = \operatorname{span}(\mathbf{v}_1, \dots, \mathbf{v}_r)$ .

Base case. $S_0$ is the empty list, which is linearly independent, and both sides of the span equation are the span of the empty list. So $P(0)$ holds.

Inductive step. Let $1 \le r \le m$ and suppose $P(r - 1)$ holds. Put $W = \operatorname{span}(S_{r-1})$ , so that $W = \operatorname{span}(\mathbf{v}_1, \dots, \mathbf{v}_{r-1})$ by $P(r - 1)$ .

Case 1: $\mathbf{v}_r \in W$ . Then $S_r = S_{r-1}$ , which is independent. Since $\mathbf{v}_r \in \operatorname{span}(\mathbf{v}_1, \dots, \mathbf{v}_{r-1})$ , Theorem 1.3.5 gives $\operatorname{span}(\mathbf{v}_1, \dots, \mathbf{v}_r) = \operatorname{span}(\mathbf{v}_1, \dots, \mathbf{v}_{r-1}) = W = \operatorname{span}(S_r)$ .

Case 2: $\mathbf{v}_r \notin W$ . Then $S_r = (S_{r-1}, \mathbf{v}_r)$ . Since $S_{r-1}$ is independent and $\mathbf{v}_r \notin \operatorname{span}(S_{r-1})$ , Lemma 1.5.3 shows that $S_r$ is independent. For the spans, recall from Theorem 1.3.1 that the span of a list is a subspace, and is contained in every subspace containing the entries of the list. Every entry of $S_r$ is one of $\mathbf{v}_1, \dots, \mathbf{v}_r$ , so $\operatorname{span}(S_r) \subseteq \operatorname{span}(\mathbf{v}_1, \dots, \mathbf{v}_r)$ . Conversely, $\operatorname{span}(S_r)$ is a subspace containing the entries of $S_{r-1}$ , so it contains $W$ , and with it $\mathbf{v}_1, \dots, \mathbf{v}_{r-1}$ ; it also contains $\mathbf{v}_r$ . Hence $\operatorname{span}(\mathbf{v}_1, \dots, \mathbf{v}_r) \subseteq \operatorname{span}(S_r)$ .

In both cases $P(r)$ holds. By induction $P(m)$ holds, which is the first statement.

Finally, suppose $(\mathbf{v}_1, \dots, \mathbf{v}_m)$ spans $V$ . Then $S_m$ is a sub-list of it that is independent and satisfies $\operatorname{span}(S_m) = V$ . So $S_m$ is a basis of $V$ .

Alternatively, one can delete instead of keep. As long as the list is dependent, the Linear Dependence Lemma (Theorem 1.4.1) locates an entry lying in the span of the entries before it, and deleting that entry does not change the span. Each deletion shortens the list, so the process stops after at most $m$ steps. Sifting performs the same idea in a single left-to-right pass.

The decision “is $\mathbf{v}_r$ in the span of the kept vectors?” is a small system of equations. For now we solve these systems by hand; Chapter 3 gives a systematic method.

Example (Sifting a List in

\mathbb{R}^3

)

Sift the list $(\mathbf{v}_1, \dots, \mathbf{v}_6)$ in $\mathbb{R}^3$ , where $\begin{aligned} &\mathbf{v}_1 = (1, 1, 1), \quad \mathbf{v}_2 = (2, 2, 2), \quad \mathbf{v}_3 = (1, 0, 0), \\ &\mathbf{v}_4 = (3, 2, 2), \quad \mathbf{v}_5 = (1, 1, 0), \quad \mathbf{v}_6 = (0, 0, 1). \end{aligned}$ Hence find a basis of $\mathbb{R}^3$ inside the list.

Solution. We go through the list once, comparing each vector with the vectors kept so far.

$\mathbf{v}_1$ : the kept list is empty, with span $\{\mathbf{0}\}$ . Since $\mathbf{v}_1 \ne \mathbf{0}$ , keep $\mathbf{v}_1$ .
$\mathbf{v}_2$ : $\mathbf{v}_2 = 2\mathbf{v}_1 \in \operatorname{span}(\mathbf{v}_1)$ . Discard.
$\mathbf{v}_3$ : if $(1, 0, 0) = a(1, 1, 1) = (a, a, a)$ , the first entry gives $a = 1$ and the second gives $a = 0$ , a contradiction. So $\mathbf{v}_3 \notin \operatorname{span}(\mathbf{v}_1)$ . Keep.
$\mathbf{v}_4$ : $2\mathbf{v}_1 + \mathbf{v}_3 = (2, 2, 2) + (1, 0, 0) = (3, 2, 2) = \mathbf{v}_4$ , so $\mathbf{v}_4 \in \operatorname{span}(\mathbf{v}_1, \mathbf{v}_3)$ . Discard.
$\mathbf{v}_5$ : suppose $(1, 1, 0) = a(1, 1, 1) + b(1, 0, 0) = (a + b, a, a)$ . The second entry gives $a = 1$ and the third gives $a = 0$ , a contradiction. So $\mathbf{v}_5 \notin \operatorname{span}(\mathbf{v}_1, \mathbf{v}_3)$ . Keep.
$\mathbf{v}_6$ : $\mathbf{v}_1 - \mathbf{v}_5 = (1, 1, 1) - (1, 1, 0) = (0, 0, 1) = \mathbf{v}_6$ , so $\mathbf{v}_6 \in \operatorname{span}(\mathbf{v}_1, \mathbf{v}_3, \mathbf{v}_5)$ . Discard.

The sifted list is $(\mathbf{v}_1, \mathbf{v}_3, \mathbf{v}_5) = ((1, 1, 1), (1, 0, 0), (1, 1, 0))$ . By Theorem 1.5.4 it is independent and has the same span as the original list. That span is all of $\mathbb{R}^3$ , since it contains $\mathbf{e}_1 = \mathbf{v}_3$ , $\mathbf{e}_2 = \mathbf{v}_5 - \mathbf{v}_3$ and $\mathbf{e}_3 = \mathbf{v}_6$ , and hence every combination of them. So $(\mathbf{v}_1, \mathbf{v}_3, \mathbf{v}_5)$ is a basis of $\mathbb{R}^3$ .

Sifting has no memory of the future, so its output depends on the order of the input.

Example (The Order Matters)

Sift $((1, 0), (0, 1), (1, 1))$ and $((1, 1), (1, 0), (0, 1))$ in $\mathbb{R}^2$ .

Solution. For the first list: $(1, 0) \ne \mathbf{0}$ , so keep it. Every multiple of $(1, 0)$ has second entry $0$ , so $(0, 1) \notin \operatorname{span}((1, 0))$ ; keep it. Then $(1, 1) = (1, 0) + (0, 1)$ ; discard it. The result is $((1, 0), (0, 1))$ .

For the second list: $(1, 1) \ne \mathbf{0}$ , so keep it. If $(1, 0) = a(1, 1) = (a, a)$ , then $a = 1$ and $a = 0$ , which is impossible; keep $(1, 0)$ . Then $(0, 1) = (1, 1) - (1, 0)$ ; discard it. The result is $((1, 1), (1, 0))$ .

Both results are bases of $\mathbb{R}^2$ (the lists span $\mathbb{R}^2$ because they contain $\mathbf{e}_1$ and $\mathbf{e}_2$ ), but they are different bases. A zero vector, by contrast, is discarded wherever it stands, because $\mathbf{0}$ lies in every span.

Quick check. Sift the list $(x, 2x, 1 + x, 1)$ in $\mathbb{R}[x]_{\le 1}$ . Which vectors are kept?

Solution. Keep $x$ , since $x \ne 0$ . Discard $2x = 2 \cdot x$ . Keep $1 + x$ : every multiple $ax$ has constant term $0$ , but $1 + x$ has constant term $1$ . Discard $1 = (1 + x) - x$ . The sifted list is $(x, 1 + x)$ .

The theorem answers the question we started with.

Corollary 1.5.5 (Existence of Bases)

Every finite-dimensional vector space has a basis.

Proof. Let $V$ be finite-dimensional. By Definition 1.3.4, $V$ is spanned by some finite list. By Theorem 1.5.4, that list contains a sub-list that is a basis of $V$ .

For $V = \{\mathbf{0}\}$ the proof still works: $\{\mathbf{0}\}$ is spanned by the empty list, and sifting it returns the empty list, which is the basis found in Example (Three More Bases).

We now know that bases exist, and we can find one inside any finite spanning list. But a space has many bases. The next section proves the fact that makes them measurable: all bases of the same space have the same length.

1.5.5. Exercises

A. Check your understanding

Exercise (A1)

(a) Define what it means for a list $(\mathbf{v}_1, \dots, \mathbf{v}_n)$ to be a basis of a vector space $V$ over $F$ .
(b) True or false: every list that spans $\mathbb{R}^2$ is a basis of $\mathbb{R}^2$ . Justify your answer.
(c) True or false: $((1, 0), (0, 1))$ and $((0, 1), (1, 0))$ are the same basis of $\mathbb{R}^2$ . Justify your answer.
(d) What is a basis of the zero space $\{\mathbf{0}\}$ ?
(e) When sifting a list, under what condition is the vector $\mathbf{v}_r$ discarded?
(f) True or false: if $\mathcal{B}$ is a basis of $V$ and $[\mathbf{u}]_{\mathcal{B}} = [\mathbf{v}]_{\mathcal{B}}$ , then $\mathbf{u} = \mathbf{v}$ . Justify your answer.

Solution.

(a) See Definition 1.5.1: the list is linearly independent and spans $V$ .
(b) False. $((1, 0), (0, 1), (1, 1))$ spans $\mathbb{R}^2$ , but it is dependent, since $(1, 0) + (0, 1) - (1, 1) = \mathbf{0}$ .
(c) False. A basis is a list, and the two lists have their entries in different orders. The difference is visible in coordinates: $(3, 1)$ has coordinate vector $(3, 1)$ in the first basis and $(1, 3)$ in the second.
(d) The empty list $()$ , by Example (Three More Bases) (c).
(e) When $\mathbf{v}_r$ lies in the span of the vectors kept before it, that is, $\mathbf{v}_r \in \operatorname{span}(S_{r-1})$ .
(f) True. If both coordinate vectors equal $(a_1, \dots, a_n)$ , then $\mathbf{u} = a_1\mathbf{v}_1 + \dots + a_n\mathbf{v}_n = \mathbf{v}$ by Definition 1.5.2, where $\mathcal{B} = (\mathbf{v}_1, \dots, \mathbf{v}_n)$ .

B. Practice

Exercise (B1: A Basis of

\mathbb{R}^3

and Coordinates)

Let $\mathcal{B} = ((1, 1, 0), (0, 1, 1), (1, 0, 1))$ . Show that $\mathcal{B}$ is a basis of $\mathbb{R}^3$ . Hence find $[\mathbf{v}]_{\mathcal{B}}$ for $\mathbf{v} = (2, 3, 5)$ .

Solution. Let $(p, q, r) \in \mathbb{R}^3$ . For scalars $a, b, c$ , $a(1, 1, 0) + b(0, 1, 1) + c(1, 0, 1) = (a + c, \; a + b, \; b + c),$ so this equals $(p, q, r)$ if and only if $a + c = p$ , $a + b = q$ and $b + c = r$ . Adding the three equations gives $2(a + b + c) = p + q + r$ , so $a + b + c = \frac{p + q + r}{2}$ . Subtracting each equation from this one, $b = \frac{-p + q + r}{2}, \qquad c = \frac{p - q + r}{2}, \qquad a = \frac{p + q - r}{2}.$ Conversely, these values satisfy the three equations: for instance $a + c = \frac{2p}{2} = p$ , and the other two are checked the same way. So every vector of $\mathbb{R}^3$ has exactly one expression in $\mathcal{B}$ , and $\mathcal{B}$ is a basis by Theorem 1.5.1.

For $(p, q, r) = (2, 3, 5)$ : $a = \frac{2 + 3 - 5}{2} = 0$ , $b = \frac{-2 + 3 + 5}{2} = 3$ , $c = \frac{2 - 3 + 5}{2} = 2$ . Check: $0(1, 1, 0) + 3(0, 1, 1) + 2(1, 0, 1) = (2, 3, 5)$ . Hence $[\mathbf{v}]_{\mathcal{B}} = (0, 3, 2)$ .

Exercise (B2: Sifting Polynomials)

Sift the list $(1 + x, \; 2 + 2x, \; x^2, \; 1 + x + x^2, \; x, \; 1)$ in $\mathbb{R}[x]_{\le 2}$ , justifying each decision. Hence find a basis of $\mathbb{R}[x]_{\le 2}$ contained in the list.

Solution. We read the list from left to right, comparing coefficients.

$1 + x \ne 0$ : keep.
$2 + 2x = 2(1 + x)$ : discard.
$x^2$ : every multiple $a(1 + x)$ has $x^2$ -coefficient $0$ , while $x^2$ has $x^2$ -coefficient $1$ . So $x^2 \notin \operatorname{span}(1 + x)$ : keep.
$1 + x + x^2 = (1 + x) + x^2$ : discard.
$x$ : suppose $x = a(1 + x) + bx^2 = a + ax + bx^2$ . The constant terms give $a = 0$ and the $x$ -coefficients give $a = 1$ , a contradiction. So $x \notin \operatorname{span}(1 + x, x^2)$ : keep.
$1 = (1 + x) - x$ : discard.

The sifted list is $(1 + x, x^2, x)$ . The original list contains $1$ , $x$ and $x^2$ , so its span contains every combination of them, which is all of $\mathbb{R}[x]_{\le 2}$ by Example (Standard Bases). Hence the list spans $\mathbb{R}[x]_{\le 2}$ , and by Theorem 1.5.4 the sifted list $(1 + x, x^2, x)$ is a basis of $\mathbb{R}[x]_{\le 2}$ .

Exercise (B3: Symmetric Matrices)

Let $U = \{ \mathbf{A} \in M_2(\mathbb{R}) : \mathbf{A}^{\top} = \mathbf{A} \}$ . Show that $(\mathbf{E}_{11}, \; \mathbf{E}_{12} + \mathbf{E}_{21}, \; \mathbf{E}_{22})$ is a basis of $U$ , and find the coordinate vector of $\begin{pmatrix} 2 & -1 \\ -1 & 5 \end{pmatrix}$ with respect to it.

Solution. Each of the three matrices is symmetric, so the list lies in $U$ .

Spanning. Let $\mathbf{A} \in U$ . Writing $\mathbf{A} = \begin{pmatrix} a & b \\ c & d \end{pmatrix}$ , the condition $\mathbf{A}^{\top} = \mathbf{A}$ says $c = b$ . Hence $\mathbf{A} = \begin{pmatrix} a & b \\ b & d \end{pmatrix} = a\mathbf{E}_{11} + b(\mathbf{E}_{12} + \mathbf{E}_{21}) + d\mathbf{E}_{22}.$

Independence. Let $a\mathbf{E}_{11} + b(\mathbf{E}_{12} + \mathbf{E}_{21}) + d\mathbf{E}_{22} = 0$ . The left side is $\begin{pmatrix} a & b \\ b & d \end{pmatrix}$ , so comparing entries with the zero matrix gives $a = b = d = 0$ .

Hence the list is a basis of $U$ . Reading off $a = 2$ , $b = -1$ , $d = 5$ , the coordinate vector is $(2, -1, 5)$ .

C. Going deeper

Exercise (C1: Polynomials Vanishing at 1)

Let $F$ be a field, $n \ge 1$ , and $U = \{ p \in F[x]_{\le n} : p(1) = 0 \}$ .

(a) Prove that $(x - 1, \; x^2 - 1, \; \dots, \; x^n - 1)$ is a basis of $U$ .
(b) For $n = 3$ , find the coordinate vector of $x^3 - 2x + 1$ with respect to this basis.

Hint: for $p = a_0 + a_1x + \dots + a_nx^n$ , what does $p(1) = 0$ say about $a_0$ ?

Solution.

(a) For $p = a_0 + a_1x + \dots + a_nx^n$ , evaluation gives $p(1) = a_0 + a_1 + \dots + a_n$ , since every power of $1$ is $1$ . In particular each $x^k - 1$ lies in $U$ , because $1 - 1 = 0$ .
Spanning. Let $p \in U$ . Then $a_0 = -(a_1 + \dots + a_n)$ , so $\begin{aligned} p &= a_1x + \dots + a_nx^n - (a_1 + \dots + a_n) \\ &= a_1(x - 1) + a_2(x^2 - 1) + \dots + a_n(x^n - 1). \end{aligned}$

Independence. Let $c_1(x - 1) + \dots + c_n(x^n - 1) = 0$ . For $1 \le k \le n$ , the coefficient of $x^k$ on the left is $c_k$ , since $x^k$ appears in no other term. The zero polynomial has all coefficients $0$ , so $c_k = 0$ for every $k$ .

Hence the list is a basis of $U$ .
(b) For $p = x^3 - 2x + 1$ we have $p(1) = 0$ , and $(a_1, a_2, a_3) = (-2, 0, 1)$ . By the formula in (a), $p = -2(x - 1) + 0(x^2 - 1) + 1(x^3 - 1)$ . Check: $-2x + 2 + x^3 - 1 = x^3 - 2x + 1$ . The coordinate vector is $(-2, 0, 1)$ .

Exercise (C2: The Same List over a Different Field)

(a) Explain why $((1, 1), (1, -1))$ is not a basis of $\mathbb{F}_2^2$ .
(b) Let $F$ be any field. Prove that $((1, 1), (1, -1))$ is a basis of $F^2$ if and only if $1 + 1 \ne 0$ in $F$ .

Solution.

(a) In $\mathbb{F}_2$ we have $-1 = 1$ , so the list is $((1, 1), (1, 1))$ . It is dependent: $1 \cdot (1, 1) + 1 \cdot (1, 1) = (1 + 1, 1 + 1) = (0, 0)$ with non-zero coefficients. (It also fails to span: every combination is $(c, c)$ , so $(1, 0)$ is out of reach.)
(b) Write $2 = 1 + 1 \in F$ .

$(\Leftarrow)$ Suppose $2 \ne 0$ , so $2^{-1}$ exists. Let $(x, y) \in F^2$ . The equation $a(1, 1) + b(1, -1) = (x, y)$ says $a + b = x$ and $a - b = y$ . If it holds, adding and subtracting gives $2a = x + y$ and $2b = x - y$ , so $a = 2^{-1}(x + y)$ and $b = 2^{-1}(x - y)$ . Conversely these values satisfy $a + b = 2^{-1} \cdot 2x = x$ and $a - b = 2^{-1} \cdot 2y = y$ . So every vector has exactly one expression, and the list is a basis by Theorem 1.5.1.

$(\Rightarrow)$ Suppose $2 = 0$ . Then $1 = -1$ , and the argument of (a) applies word for word: $1 \cdot (1, 1) + 1 \cdot (1, -1) = (2, 0) = (0, 0)$ , so the list is dependent and is not a basis. This proves $(\Rightarrow)$ by contraposition.

Exercise (C3: Rescaling a Basis)

Let $\mathcal{B} = (\mathbf{v}_1, \dots, \mathbf{v}_n)$ be a basis of $V$ over $F$ , and let $c_1, \dots, c_n \in F$ be non-zero.

(a) Prove that $\mathcal{B}' = (c_1\mathbf{v}_1, \dots, c_n\mathbf{v}_n)$ is a basis of $V$ .
(b) Express $[\mathbf{v}]_{\mathcal{B}'}$ in terms of $[\mathbf{v}]_{\mathcal{B}}$ .
(c) Explain why the conclusion of (a) can fail if some $c_i = 0$ .

Solution.

(a) Let $\mathbf{v} \in V$ and $[\mathbf{v}]_{\mathcal{B}} = (a_1, \dots, a_n)$ . Since each $c_i \ne 0$ , $c_i^{-1}$ exists, and $\mathbf{v} = \sum_{i=1}^n a_i\mathbf{v}_i = \sum_{i=1}^n (a_ic_i^{-1})(c_i\mathbf{v}_i).$ So $\mathbf{v}$ has an expression in $\mathcal{B}'$ . Suppose $\mathbf{v} = \sum_i b_i(c_i\mathbf{v}_i) = \sum_i (b_ic_i)\mathbf{v}_i$ . By uniqueness of the expression in $\mathcal{B}$ (Theorem 1.5.1), $b_ic_i = a_i$ for each $i$ , so $b_i = a_ic_i^{-1}$ . Hence the expression in $\mathcal{B}'$ is unique, and $\mathcal{B}'$ is a basis by Theorem 1.5.1.
(b) By (a), $[\mathbf{v}]_{\mathcal{B}'} = (a_1c_1^{-1}, \dots, a_nc_n^{-1})$ : divide the $i$ -th coordinate by $c_i$ .
(c) If $c_1 = 0$ , then $\mathcal{B}'$ contains $0\mathbf{v}_1 = \mathbf{0}$ , and $1 \cdot \mathbf{0} + 0 \cdot c_2\mathbf{v}_2 + \dots + 0 \cdot c_n\mathbf{v}_n = \mathbf{0}$ is a combination with a non-zero coefficient. So $\mathcal{B}'$ is dependent and is not a basis.