1.6 Bases and coordinates · Matrix Theory

In $𝐹^{𝑛}$ a vector is its list of entries: $𝐱 = (𝑥_{1}, \dots, 𝑥_{𝑛})$ is the linear combination $𝑥_{1} 𝐞_{1} + \dots + 𝑥_{𝑛} 𝐞_{𝑛}$ , and no other linear combination of $𝐞_{1}, \dots, 𝐞_{𝑛}$ represents it. A basis of a vector space $𝑉$ is a list that does for $𝑉$ what $𝐞_{1}, \dots, 𝐞_{𝑛}$ does for $𝐹^{𝑛}$ : every vector of $𝑉$ is represented by exactly one of its linear combinations. The coefficients of that combination are the coordinates of the vector. They name each vector of $𝑉$ by a column in $𝐹^{𝑛}$ , and they turn computations in $𝑉$ into computations with columns. This section defines bases, shows that every spanning list contains one, and develops coordinates.

1.6.1Bases

Throughout, $𝑉$ is a vector space over a field $𝐹$ .

Definition 1.6.1 (Basis). A list

ℬ︀

𝑉

is a basis of

𝑉

if every vector of

𝑉

is represented by exactly one linear combination of

ℬ︀

. The plural of basis is bases.

So $ℬ︀ = 𝐯_{1}, \dots, 𝐯_{𝑛}$ is a basis when, for every $𝐯 \in 𝑉$ , the equation

𝑎_{1} 𝐯_{1} + \dots + 𝑎_{𝑛} 𝐯_{𝑛} = 𝐯

has exactly one solution $(𝑎_{1}, \dots, 𝑎_{𝑛})$ . “Exactly one” is two claims: at least one solution, and at most one. The first is a statement about the span of $ℬ︀$ , and the second is the uniqueness that defines linear independence.

Proposition 1.6.2 (Bases are independent spanning lists). A list

ℬ︀

𝑉

is a basis of

𝑉

if and only if

ℬ︀

spans

𝑉

and

ℬ︀

is linearly independent.

Proof.routine

Uses. Definition 1.6.1 (Basis), Definition 1.3.12 (Spanning list), Definition 1.5.1 (Linear independence), Definition 1.3.10 (Span)

Hint 1. Split “exactly one linear combination represents

𝐯

” into “at least one” and “at most one”. Which of the two properties of

ℬ︀

is each of them?

Hint 2. Definition 1.5.1 asks for uniqueness only for vectors of

span (ℬ︀)

. If

ℬ︀

spans

𝑉

, which vectors are those?

Sketch. “At least one representation for every

𝐯 \in 𝑉

” says

span (ℬ︀) = 𝑉

. Given that, “at most one representation for every

𝐯 \in 𝑉

” is the same as “exactly one for every vector of

span (ℬ︀)

”, which is linear independence.

( $\Rightarrow$ ) Suppose that $ℬ︀$ is a basis of $𝑉$ . Every $𝐯 \in 𝑉$ is represented by some linear combination of $ℬ︀$ , so $𝑉 \subseteq span (ℬ︀)$ . The span consists of vectors of $𝑉$ , so $span (ℬ︀) = 𝑉$ . Every vector of $span (ℬ︀) = 𝑉$ is then represented by exactly one linear combination of $ℬ︀$ , which is Definition 1.5.1.

( $\Leftarrow$ ) Suppose that $ℬ︀$ spans $𝑉$ and is linearly independent, and let $𝐯 \in 𝑉$ . Since $𝐯 \in 𝑉 = span (ℬ︀)$ , some linear combination of $ℬ︀$ represents $𝐯$ , and by independence no other one does. □

The lecture defines a basis by unique representation and records the proposition as an equivalent form. The proposition splits the work of checking a basis into two familiar tasks: show that every vector is a linear combination of $ℬ︀$ (spanning), and show that $𝑎_{1} 𝐯_{1} +$ $\dots +$ $𝑎_{𝑛} 𝐯_{𝑛} =$ $𝟎$ forces every $𝑎_{𝑖} = 0$ (independence, by Theorem 1.5.5). The definition suggests doing both at once: solve $𝑎_{1} 𝐯_{1} +$ $\dots +$ $𝑎_{𝑛} 𝐯_{𝑛} =$ $𝐯$ for an arbitrary $𝐯$ . If the computation shows that the $𝑎_{𝑖}$ must be given by certain formulas, and these formulas do give a solution, then the solution exists and is unique.

Example 1.6.3 (First bases).

(a)In $ℝ^{2}$ , consider $(1, 1), (1, - 1)$ . For $(𝑥, 𝑦) \in ℝ^{2}$ , the equation $𝑎 (1, 1) +$ $𝑏 (1, - 1) =$ $(𝑥, 𝑦)$ reads $𝑎 + 𝑏 = 𝑥$ and $𝑎 - 𝑏 = 𝑦$ . Adding and subtracting, any solution has $𝑎 = (𝑥 + 𝑦) / 2$ and $𝑏 = (𝑥 - 𝑦) / 2$ , and these values are a solution. So each $(𝑥, 𝑦)$ is represented by exactly one linear combination, and $(1, 1), (1, - 1)$ is a basis of $ℝ^{2}$ . The same computation works over any field with $1 + 1 \neq 0$ . Over $𝔽_{2}$ the list is not a basis: there $(1, - 1) = (1, 1)$ , and a list with a repeated entry is dependent (Proposition 1.5.15).
(b)Let $𝑃 =$ ${(𝑥, 𝑦, 𝑧) \in ℝ^{3} | 𝑥 + 𝑦 + 𝑧 = 0}$ . The list $(1, 0, - 1), (0, 1, - 1)$ spans $𝑃$ (Exercise 1.3.16). It is independent, because $𝑎 (1, 0, - 1) +$ $𝑏 (0, 1, - 1) =$ $(𝑎, 𝑏, - 𝑎 - 𝑏)$ is $𝟎$ only if $𝑎 = 𝑏 = 0$ . So it is a basis of the plane $𝑃$ , a vector space in its own right (Definition 1.4.1).
(c)The zero space ${𝟎}$ has the empty list $()$ as a basis: $()$ spans ${𝟎}$ and is independent (Definition 1.3.10, Proposition 1.5.15). It is the only basis, since every nonempty list in ${𝟎}$ contains $𝟎$ and is therefore dependent.

Non-example 1.6.4 (One property without the other).

(a)In $ℝ^{3}$ , the list $(1, 0, 1), (0, 1, 1)$ is linearly independent, because $𝑎 (1, 0, 1) +$ $𝑏 (0, 1, 1) =$ $(𝑎, 𝑏, 𝑎 + 𝑏)$ , which is $𝟎$ only if $𝑎 = 𝑏 = 0$ . It does not span $ℝ^{3}$ : every vector $(𝑎, 𝑏, 𝑎 + 𝑏)$ of its span has third coordinate equal to the sum of the first two, and $(0, 0, 1)$ does not. So the vector $(0, 0, 1)$ has no representation at all.
(b)In $ℝ^{2}$ , the list $(1, 0), (0, 1), (1, 1)$ spans $ℝ^{2}$ , as its sublist $(1, 0), (0, 1)$ already does. It is dependent, since $(1, 0) +$ $(0, 1) -$ $(1, 1) =$ $𝟎$ . So every vector has many representations: $(1, 1) =$ $1 (1, 0) +$ $1 (0, 1) +$ $0 (1, 1) =$ $0 (1, 0) +$ $0 (0, 1) +$ $1 (1, 1)$ .

Whether a list is a basis depends on the field, since both spanning and independence do.

Example 1.6.5 (

ℂ

over

ℝ

and over

ℂ

). Regard

ℂ

as a vector space over

ℝ

(Example 1.2.20). The list

1, 𝑖

spans it, since every complex number is

𝑎 +

𝑏 𝑖 =

𝑎 \cdot

1 +

𝑏 \cdot

𝑖

with

𝑎, 𝑏 \in ℝ

, and it is independent over

ℝ

(Example 1.5.19). So

1, 𝑖

is a basis of

ℂ

over

ℝ

. Over

ℂ

the same list is dependent, as

𝑖 \cdot 1 + (- 1) \cdot 𝑖 = 0

, so it is not a basis of

ℂ

over

ℂ

. Instead, the list

1

is: every

𝑧 \in ℂ

𝑧 \cdot 1

for exactly one complex scalar, namely

𝑧

. So the same set has bases of length

2

over

ℝ

and of length

1

over

ℂ

Exercise 1.6.6.routine Let

𝑊 =

{𝑝 \in {ℝ [𝑥]}_{\leq 3} | 𝑝 (1) = 0}

. Show that

𝑥 - 1, 𝑥^{2} - 1, 𝑥^{3} - 1

is a basis of

𝑊

Solution.

Uses. Proposition 1.6.2 (Bases are independent spanning lists), Exercise 1.3.32, Proposition 1.5.24 (Distinct degrees)

Hint 1. By Proposition 1.6.2, check spanning and independence separately. One of them is already done in Section 1.3.

Hint 2. The three polynomials are nonzero and have different degrees.

Sketch. The list spans

𝑊

by Exercise 1.3.32. Its entries have degrees

1, 2, 3

, so it is independent by Proposition 1.5.24.

Each entry has degree at most

3

and value

1 - 1 = 0

1

, so the list lies in

𝑊

, and it spans

𝑊

by Exercise 1.3.32. Its entries are nonzero polynomials of the distinct degrees

1

2

, and

3

, so it is linearly independent by Proposition 1.5.24. By Proposition 1.6.2, it is a basis of

𝑊

1.6.2Standard bases

The spaces $𝐹^{𝑛}$ , $𝐹^{𝑚 \times 𝑛}$ , and ${𝐹 [𝑥]}_{\leq 𝑛}$ each come with a basis in which the coefficients of a vector are the numbers used to write it down.

Proposition 1.6.7 (Standard bases).

(a)In $𝐹^{𝑛}$ , the list $𝐞_{1}, \dots, 𝐞_{𝑛}$ is a basis, where $𝐞_{𝑖}$ has $1$ in position $𝑖$ and $0$ elsewhere.
(b)In $𝐹^{𝑚 \times 𝑛}$ , let $𝑈_{𝑖 𝑗}$ be the matrix with $1$ in position $(𝑖, 𝑗)$ and $0$ elsewhere. The $𝑚 𝑛$ matrices $𝑈_{𝑖 𝑗}$ , listed row by row as
$𝑈_{11}, 𝑈_{12}, \dots, 𝑈_{1 𝑛}, 𝑈_{21}, \dots, 𝑈_{2 𝑛}, \dots, 𝑈_{𝑚 1}, \dots, 𝑈_{𝑚 𝑛},$
form a basis.
(c)In ${𝐹 [𝑥]}_{\leq 𝑛}$ , the list $1, 𝑥, 𝑥^{2}, \dots, 𝑥^{𝑛}$ is a basis.

Proof.routine

Uses. Definition 1.6.1 (Basis), Definition 1.2.4 (The space $𝐹^{𝑛}$ ), Definition 1.2.7 (Matrices), Notation 1.2.15, Example 1.3.7 (Standard lists)

Hint 1. Use Definition 1.6.1 directly: compute the vector represented by an arbitrary linear combination, and compare with the vector you want to represent.

Hint 2. The combination

𝑐_{1} 𝐞_{1} + \dots + 𝑐_{𝑛} 𝐞_{𝑛}

is the column

(𝑐_{1}, \dots, 𝑐_{𝑛})

. What are the analogous statements for

\sum 𝑐_{𝑖 𝑗} 𝑈_{𝑖 𝑗}

and

𝑐_{0} +

𝑐_{1} 𝑥 +

\dots +

𝑐_{𝑛} 𝑥^{𝑛}

Sketch. In each case the combination with coefficients

𝑐

is the vector whose entries (or coefficients) are the

𝑐

’s:

\sum 𝑐_{𝑖} 𝐞_{𝑖} =

(𝑐_{1}, \dots, 𝑐_{𝑛})

\sum 𝑐_{𝑖 𝑗} 𝑈_{𝑖 𝑗}

has

(𝑖, 𝑗)

entry

𝑐_{𝑖 𝑗}

, and

\sum 𝑐_{𝑘} 𝑥^{𝑘}

has

𝑘

-th coefficient

𝑐_{𝑘}

. So the combination represents a given vector exactly when its coefficients are that vector’s entries.

(a) By the coordinatewise operations, the linear combination with coefficients $𝑐_{1}, \dots, 𝑐_{𝑛}$ represents $𝑐_{1} 𝐞_{1} +$ $\dots +$ $𝑐_{𝑛} 𝐞_{𝑛} =$ $(𝑐_{1}, \dots, 𝑐_{𝑛})$ (Example 1.3.7). This equals $𝐱 = (𝑥_{1}, \dots, 𝑥_{𝑛})$ if and only if $𝑐_{𝑖} = 𝑥_{𝑖}$ for every $𝑖$ . So every $𝐱 \in 𝐹^{𝑛}$ is represented by exactly one linear combination.

(b) By the entrywise operations, the $(𝑘, 𝑙)$ entry of $\sum_{𝑖, 𝑗} 𝑐_{𝑖 𝑗} 𝑈_{𝑖 𝑗}$ is $\sum_{𝑖, 𝑗} 𝑐_{𝑖 𝑗} {(𝑈_{𝑖 𝑗})}_{𝑘 𝑙} =$ $𝑐_{𝑘 𝑙}$ , since ${(𝑈_{𝑖 𝑗})}_{𝑘 𝑙}$ is $1$ for $(𝑖, 𝑗) = (𝑘, 𝑙)$ and $0$ otherwise. So the linear combination with coefficients $𝑐_{𝑖 𝑗}$ represents $𝐴 = (𝑎_{𝑖 𝑗})$ if and only if $𝑐_{𝑖 𝑗} = 𝑎_{𝑖 𝑗}$ for all $𝑖, 𝑗$ .

(c) By Notation 1.2.15, $𝑐_{0} +$ $𝑐_{1} 𝑥 +$ $\dots +$ $𝑐_{𝑛} 𝑥^{𝑛}$ is the polynomial with coefficients $(𝑐_{0}, \dots, 𝑐_{𝑛}, 0, 0, \dots)$ . A polynomial $𝑝 \in {𝐹 [𝑥]}_{\leq 𝑛}$ has the form $(𝑎_{0}, \dots, 𝑎_{𝑛}, 0, 0, \dots)$ , and the two are equal if and only if $𝑐_{𝑘} = 𝑎_{𝑘}$ for $0 \leq 𝑘 \leq 𝑛$ . □

Definition 1.6.8 (Standard bases). The bases of Proposition 1.6.7 are the standard bases of

𝐹^{𝑛}

𝐹^{𝑚 \times 𝑛}

, and

{𝐹 [𝑥]}_{\leq 𝑛}

. The vector

𝐞_{𝑖}

is the

𝑖

-th standard basis vector of

𝐹^{𝑛}

, and the

𝑈_{𝑖 𝑗}

are the matrix units of

𝐹^{𝑚 \times 𝑛}

The notation $𝐞_{𝑖}$ does not record $𝑛$ , which is always clear from the context: $𝐞_{1} = (1, 0)$ in $𝐹^{2}$ and $𝐞_{1} = (1, 0, 0)$ in $𝐹^{3}$ . For matrix units we avoid the name $𝐸_{𝑖 𝑗}$ , which Section 3.2 reserves for elementary matrices. Once matrices can be multiplied, $𝑈_{𝑖 𝑗} = 𝐞_{𝑖} 𝐞_{𝑗}^{𝖳}$ (Lemma 2.4.24). A column is an $𝑛 \times 1$ matrix, and the matrix units of $𝐹^{𝑛 \times 1}$ are the $𝑈_{𝑖 1} = 𝐞_{𝑖}$ , so (b) contains (a).

The standard bases have lengths $𝑛$ , $𝑚 𝑛$ , and $𝑛 + 1$ , and these numbers will turn out to be the dimensions of the three spaces: we will see in Section 4.1 that all bases of a vector space have the same length (Theorem 4.1.4). The space $𝐹^{𝑛}$ has many other bases, as Example 1.6.3(a) shows already for $𝑛 = 2$ . The standard basis is the one in which coefficients can be read off without computation.

1.6.3Every spanning list contains a basis

A spanning list fails to be a basis only by being dependent. The linear dependence lemma finds an entry whose deletion does not change the span, so we can delete it and still have a spanning list. Repeating this, the list gets shorter at each step, so the process stops, and it can only stop at an independent list. To turn “repeat until it stops” into a proof, we induct on the length of the list.

Technique 1.6.9 (Induction on the length of a list). Many statements are about all lists in $𝑉$ , or about linear combinations of every length. To prove one, induct on the length $𝑘$ . The base case is usually the empty list, where the claim tends to be immediate: $span (()) = {𝟎}$ , the empty list is independent, and the empty sum is $𝟎$ . In the inductive step, take a list of length $𝑘 + 1$ , produce from it a list of length $𝑘$ (by deleting a well-chosen entry, or by splitting off the last term of a sum), apply the inductive hypothesis to the shorter list, and carry the conclusion back to the original list.

Two things need care. First, the inductive hypothesis must cover every list of length $𝑘$ , since the shorter list is produced by the argument and is not known in advance. Second, if the statement has hypotheses (for instance, that the list spans $𝑉$ ), the shorter list must satisfy them too. Deleting an arbitrary entry of a spanning list can destroy spanning, which is why the deleted entry has to be chosen (Exercise 1.6.30).

Reach for it when removing one entry or one term reduces a claim to the same claim for a shorter list. The canonical example is Theorem 1.6.10, which deletes an entry supplied by Lemma 1.5.10. The arithmetic of linear combinations (Lemma 1.3.9) was proved by splitting off the last term, and so is Proposition 1.6.19(c) below. Later, the exchange lemma (Lemma 4.1.2) and Gram–Schmidt (Algorithm 6.4.14) are built the same way.

Used in 20 places and 1 practice exercise

Theorem 1.6.10, Proposition 1.6.19, Exercise 1.6.30, Exercise 1.7.10, Exercise 1.7.11, Problem 1.17, Theorem 2.1.3, Exercise 2.6.50, Lemma 4.1.2, Theorem 4.1.16, Corollary 4.1.35, Proposition 4.7.30, Exercise 4.7.61, Corollary 6.2.13, Corollary 6.3.6, Theorem 6.4.15, Exercise 6.4.62, Exercise 6.6.19, Proposition 7.1.22, Proposition 7.1.27; 1 practice exercise.

The lecture proves a slightly more general statement, about lists that need not span $𝑉$ . Any list spans its own span, so the general statement says that every list can be thinned to an independent list without losing any of its span.

Theorem 1.6.10 (Every spanning list contains a basis). Every list

ℒ︀

𝑉

has a linearly independent sublist

{ℒ︀}^{'}

with

span ({ℒ︀}^{'}) =

span (ℒ︀)

, and such an

{ℒ︀}^{'}

is a basis of

span (ℒ︀)

. In particular, if

ℒ︀

spans

𝑉

, then some sublist of

ℒ︀

is a basis of

𝑉

Once an independent sublist ${ℒ︀}^{'}$ with the same span is found, the rest is formal. The entries of ${ℒ︀}^{'}$ lie in the subspace $span (ℒ︀)$ (Proposition 1.4.14), ${ℒ︀}^{'}$ spans it, and ${ℒ︀}^{'}$ is independent there, because linear relations are computed with the same operations in $𝑉$ and in the subspace. So ${ℒ︀}^{'}$ is a basis of $span (ℒ︀)$ by Proposition 1.6.2, and if $ℒ︀$ spans $𝑉$ , then $span (ℒ︀) = 𝑉$ . We give three proofs that ${ℒ︀}^{'}$ exists. The first is the lecture’s induction; the second and third show what that induction is doing in two other forms.

Proof (induction on the length).standard

Uses. Lemma 1.5.10 (Linear dependence lemma), Proposition 1.5.15 (Short lists, zeros, and repeats), Notation 1.3.3

Techniques. Induction on the length of a list (Technique 1.6.9)

Hint 1. Induct on

𝑘 = | ℒ︀ |

. What is the empty list’s span, and is the empty list independent?

Hint 2. In the inductive step, if

ℒ︀

is independent there is nothing to do. Otherwise, which entry can be deleted without changing the span?

Hint 3. Delete the entry given by Lemma 1.5.10 and apply the inductive hypothesis to the shorter list. Why is a sublist of the shorter list also a sublist of

ℒ︀

Sketch. Induct on

| ℒ︀ |

. The empty list is independent. For a list of length

𝑘 + 1

: if it is independent, take

{ℒ︀}^{'} = ℒ︀

; if not, Lemma 1.5.10 gives an entry whose deletion keeps the span, and the inductive hypothesis, applied to the resulting list of length

𝑘

, gives an independent sublist with the same span, which is also a sublist of

ℒ︀

We prove by induction on $𝑘 \geq 0$ that every list of length $𝑘$ in $𝑉$ has a linearly independent sublist with the same span.

Base case. If $𝑘 = 0$ , then $ℒ︀ = ()$ , which is independent (Proposition 1.5.15(a)). Take ${ℒ︀}^{'} = ℒ︀$ .

Inductive step. Suppose that every list of length $𝑘$ in $𝑉$ has an independent sublist with the same span, and let $ℒ︀ = 𝐯_{1}, \dots, 𝐯_{𝑘 + 1}$ . If $ℒ︀$ is independent, take ${ℒ︀}^{'} = ℒ︀$ . Otherwise, by Lemma 1.5.10 there is an index $𝑗$ such that the list

{ℒ︀}_{𝑗} = 𝐯_{1}, \dots, 𝐯_{𝑗 - 1}, 𝐯_{𝑗 + 1}, \dots, 𝐯_{𝑘 + 1}

satisfies $span ({ℒ︀}_{𝑗}) =$ $span (ℒ︀)$ . The list ${ℒ︀}_{𝑗}$ has length $𝑘$ , so by the inductive hypothesis it has an independent sublist ${ℒ︀}^{'}$ with $span ({ℒ︀}^{'}) =$ $span ({ℒ︀}_{𝑗}) =$ $span (ℒ︀)$ . Deleting entries from ${ℒ︀}_{𝑗}$ amounts to deleting entries from $ℒ︀$ , so ${ℒ︀}^{'}$ is a sublist of $ℒ︀$ (Notation 1.3.3), as desired. □

Intuition (What the induction is doing). Unwinding the induction, the proof deletes redundant entries one at a time until none is left. The induction guarantees that this stops, because each deletion shortens the list. Another way to guarantee it is to look directly at the end result: a shortest sublist with the same span. Such a sublist exists because lengths are nonnegative integers, and it cannot be dependent, since the dependence lemma would shorten it further. This is the extremal form of the same argument (Technique 1.5.9).

Proof (a shortest sublist).standard

Uses. Lemma 1.5.10 (Linear dependence lemma), Notation 1.3.3

Techniques. Extremal choice and minimal counterexamples (Technique 1.5.9)

Hint 1. Among all sublists of

ℒ︀

with the same span as

ℒ︀

, choose one of the smallest length. Why is there at least one such sublist?

Hint 2. If the chosen sublist were dependent, what would Lemma 1.5.10 produce?

Sketch. The sublists of

ℒ︀

with span

span (ℒ︀)

include

ℒ︀

, so there is one,

{ℒ︀}^{'}

, of smallest length. If

{ℒ︀}^{'}

were dependent, deleting the entry given by Lemma 1.5.10 would give a shorter sublist of

ℒ︀

with the same span, contradicting minimality.

Let

𝑆

be the set of sublists of

ℒ︀

whose span is

span (ℒ︀)

. It is nonempty, since

ℒ︀ \in 𝑆

. The lengths of the members of

𝑆

are nonnegative integers, so some

{ℒ︀}^{'} \in 𝑆

has the smallest length. Suppose, to the contrary, that

{ℒ︀}^{'}

is dependent. By Lemma 1.5.10, deleting a suitable entry of

{ℒ︀}^{'}

gives a list

{ℒ︀}^{″}

with

span ({ℒ︀}^{″}) =

span ({ℒ︀}^{'}) =

span (ℒ︀)

. As a sublist of a sublist of

ℒ︀

{ℒ︀}^{″}

is a sublist of

ℒ︀

, so

{ℒ︀}^{″} \in 𝑆

, and it is shorter than

{ℒ︀}^{'}

. This contradicts the choice of

{ℒ︀}^{'}

. So

{ℒ︀}^{'}

is independent. □

Both proofs make a choice they cannot control: which redundant entry to delete, or which shortest sublist to take. The third proof makes no choices. It reads the list from left to right and keeps exactly the entries that are not in the span of the entries before them. This procedure, sifting, can be carried out by hand or by a computer, and its output is determined by $ℒ︀$ . In Section 4.2 the entries it keeps reappear as the pivot columns of a matrix.

Proof (sifting).standard

Uses. Corollary 1.5.13 (Independence, one entry at a time), Corollary 1.3.20 (Operations that preserve the span), Corollary 1.3.19 (Equal spans), Proposition 1.3.17 (A list lies in its span)

Techniques. Induction on the length of a list (Technique 1.6.9)

Hint 1. Let

{ℒ︀}^{'}

consist of the entries

𝐯_{𝑗}

with

𝐯_{𝑗} \notin

span (𝐯_{1}, \dots, 𝐯_{𝑗 - 1})

. Independence of

{ℒ︀}^{'}

should come from Corollary 1.5.13.

Hint 2. For each

𝑗

, compare

span (𝐯_{1}, \dots, 𝐯_{𝑗})

with the span of the entries of

{ℒ︀}^{'}

among

𝐯_{1}, \dots, 𝐯_{𝑗}

. Prove that they are equal by induction on

𝑗

Hint 3. In the inductive step, split into the cases where

𝐯_{𝑗}

is kept and where it is deleted. In the second case, Corollary 1.3.20(c) applies.

Sketch. Keep

𝐯_{𝑗}

exactly when

𝐯_{𝑗} \notin

𝑆_{𝑗 - 1} =

span (𝐯_{1}, \dots, 𝐯_{𝑗 - 1})

. By induction on

𝑗

, the kept entries among the first

𝑗

span

𝑆_{𝑗}

: a kept entry is added to both sides, and a deleted entry lies in

𝑆_{𝑗 - 1}

, so

𝑆_{𝑗} = 𝑆_{𝑗 - 1}

. Taking

𝑗 = 𝑘

gives the span. Each kept entry lies outside

𝑆_{𝑗 - 1}

, which is the span of the earlier kept entries, so the kept list is independent by Corollary 1.5.13.

Let $ℒ︀ = 𝐯_{1}, \dots, 𝐯_{𝑘}$ , and write $𝑆_{𝑗} =$ $span (𝐯_{1}, \dots, 𝐯_{𝑗})$ for $0 \leq 𝑗 \leq 𝑘$ , so $𝑆_{0} = {𝟎}$ . Call $𝐯_{𝑗}$ kept if $𝐯_{𝑗} \notin 𝑆_{𝑗 - 1}$ and deleted otherwise. Let ${ℒ︀}^{'}$ be the sublist of kept entries, and for $0 \leq 𝑗 \leq 𝑘$ let ${𝒦︀}_{𝑗}$ be the sublist of kept entries among $𝐯_{1}, \dots, 𝐯_{𝑗}$ .

We show by induction on $𝑗$ that $span ({𝒦︀}_{𝑗}) = 𝑆_{𝑗}$ . For $𝑗 = 0$ both sides are ${𝟎}$ . Let $𝑗 \geq 1$ and assume $span ({𝒦︀}_{𝑗 - 1}) =$ $𝑆_{𝑗 - 1}$ .

If $𝐯_{𝑗}$ is kept, then ${𝒦︀}_{𝑗} =$ ${𝒦︀}_{𝑗 - 1},$ $𝐯_{𝑗}$ . The entries of ${𝒦︀}_{𝑗}$ are entries of $𝐯_{1}, \dots, 𝐯_{𝑗}$ , so they lie in $𝑆_{𝑗}$ (Proposition 1.3.17). Conversely, $𝐯_{1}, \dots, 𝐯_{𝑗 - 1}$ lie in $𝑆_{𝑗 - 1} =$ $span ({𝒦︀}_{𝑗 - 1}) \subseteq$ $span ({𝒦︀}_{𝑗})$ , and $𝐯_{𝑗}$ is an entry of ${𝒦︀}_{𝑗}$ . By Corollary 1.3.19, $span ({𝒦︀}_{𝑗}) = 𝑆_{𝑗}$ .
If $𝐯_{𝑗}$ is deleted, then ${𝒦︀}_{𝑗} = {𝒦︀}_{𝑗 - 1}$ and $𝐯_{𝑗} \in 𝑆_{𝑗 - 1}$ , so $𝑆_{𝑗} = 𝑆_{𝑗 - 1}$ by Corollary 1.3.20(c). Hence $span ({𝒦︀}_{𝑗}) =$ $span ({𝒦︀}_{𝑗 - 1}) =$ $𝑆_{𝑗 - 1} =$ $𝑆_{𝑗}$ .

For $𝑗 = 𝑘$ this gives $span ({ℒ︀}^{'}) =$ $span ({𝒦︀}_{𝑘}) =$ $𝑆_{𝑘} =$ $span (ℒ︀)$ .

For independence, let $𝐯_{𝑗}$ be a kept entry. The entries of ${ℒ︀}^{'}$ that come before it form ${𝒦︀}_{𝑗 - 1}$ , whose span is $𝑆_{𝑗 - 1}$ , and $𝐯_{𝑗} \notin 𝑆_{𝑗 - 1}$ by definition. So no entry of ${ℒ︀}^{'}$ lies in the span of the entries of ${ℒ︀}^{'}$ before it, and ${ℒ︀}^{'}$ is independent by Corollary 1.5.13. □

Example 1.6.11 (Sifting a list of polynomials). In ${ℝ [𝑥]}_{\leq 2}$ , let

ℒ︀ = 𝐯_{1}, \dots, 𝐯_{5} = 1 + 𝑥, 2 + 2 𝑥, 𝑥 - 𝑥^{2}, 1 + 𝑥^{2}, 𝑥^{2} .

We sift. The entry $𝐯_{1} = 1 + 𝑥$ is nonzero, so it is kept. Next, $𝐯_{2} = 2 𝐯_{1}$ lies in $span (𝐯_{1})$ and is deleted. Every vector of $span (𝐯_{1}, 𝐯_{2}) =$ $span (1 + 𝑥)$ has degree at most $1$ , so $𝐯_{3} = 𝑥 - 𝑥^{2}$ is kept. Then $𝐯_{4} =$ $1 +$ $𝑥^{2} =$ $(1 + 𝑥) -$ $(𝑥 - 𝑥^{2})$ is deleted. Finally, a linear combination

𝑎 (1 + 𝑥) + 𝑏 (𝑥 - 𝑥^{2}) = 𝑎 + (𝑎 + 𝑏) 𝑥 - 𝑏 𝑥^{2}

equals $𝑥^{2}$ only if $𝑎 = 0$ , $𝑏 = - 1$ , and $𝑎 + 𝑏 = 0$ , which is impossible. So $𝐯_{5} = 𝑥^{2}$ is kept, and sifting produces

{ℒ︀}^{'} = 1 + 𝑥, 𝑥 - 𝑥^{2}, 𝑥^{2},

a basis of $span (ℒ︀)$ . Here $span (ℒ︀)$ is all of ${ℝ [𝑥]}_{\leq 2}$ , because $𝑥^{2}$ , $𝑥 = (𝑥 - 𝑥^{2}) + 𝑥^{2}$ , and $1 = (1 + 𝑥) - 𝑥$ lie in $span ({ℒ︀}^{'})$ (Proposition 1.3.18). So ${ℒ︀}^{'}$ is a basis of ${ℝ [𝑥]}_{\leq 2}$ .

Other sublists of $ℒ︀$ are bases too. For instance, $2 + 2 𝑥, 1 + 𝑥^{2}, 𝑥^{2}$ is independent and spans ${ℝ [𝑥]}_{\leq 2}$ , as one checks in the same way. So a spanning list usually contains several bases, and sifting picks a particular one, determined by the order of the entries: it keeps an entry exactly when the entries before it do not already account for it.

Exercise 1.6.12.routine Let

ℒ︀ =

(1, 0),

(1, 1),

(2, 2),

(0, 1)

ℝ^{2}

. Find all sublists of

ℒ︀

that are bases of

ℝ^{2}

Solution.

Uses. Proposition 1.6.2 (Bases are independent spanning lists), Proposition 1.5.15 (Short lists, zeros, and repeats), Exercise 1.3.37, Corollary 1.5.17 (Sublists)

Hint 1. Sort the sublists by length. A sublist of length

0

1

cannot span

ℝ^{2}

. Why?

Hint 2. Every sublist of length

3

4

has a dependence relation; find one in each case. For length

2

, use Proposition 1.5.15(d) and Exercise 1.3.37.

Sketch. Five sublists: all pairs except

(1, 1), (2, 2)

. Length

0

and

1

: the span is

{𝟎}

or a set of multiples of one vector, which misses

𝐞_{1}

𝐞_{2}

. Length

3

and

4

: each contains a dependent sublist, since

(2, 2) = 2 (1, 1)

and

(1, 1) = (1, 0) + (0, 1)

and

(2, 2) =

2 (1, 0) +

2 (0, 1)

. Length

2

(1, 1), (2, 2)

is dependent, and the other five pairs

(𝑎, 𝑏), (𝑐, 𝑑)

have

𝑎 𝑑 - 𝑏 𝑐 \neq 0

Length $0$ or $1$ . The span of $()$ is ${𝟎}$ . The span of a single vector $𝐯$ consists of its multiples. If both $𝐞_{1} = (1, 0)$ and $𝐞_{2} = (0, 1)$ were multiples of $𝐯 = (𝑎, 𝑏)$ , say $𝐞_{1} = 𝑐 𝐯$ and $𝐞_{2} = 𝑑 𝐯$ , then $𝑐 𝑎 = 1$ and $𝑐 𝑏 = 0$ would give $𝑐 \neq 0$ and $𝑏 = 0$ , while $𝑑 𝑏 = 1$ would give $𝑏 \neq 0$ . So no sublist of length $0$ or $1$ spans $ℝ^{2}$ .

Length $3$ or $4$ . The four sublists of length $3$ have the dependence relations

\begin{aligned} 2 (1, 1) - (2, 2) = 𝟎 & for (1, 0), (1, 1), (2, 2) and for (1, 1), (2, 2), (0, 1), \\ (1, 0) - (1, 1) + (0, 1) = 𝟎 & for (1, 0), (1, 1), (0, 1), \\ 2 (1, 0) - (2, 2) + 2 (0, 1) = 𝟎 & for (1, 0), (2, 2), (0, 1) . \end{aligned}

The whole list contains the dependent sublist $(1, 1), (2, 2)$ , so it is dependent by Corollary 1.5.17. None of these is a basis.

Length $2$ . The pair $(1, 1), (2, 2)$ is dependent. For each of the other five pairs $(𝑎, 𝑏), (𝑐, 𝑑)$ , namely

(1, 0), (1, 1) (1, 0), (2, 2) (1, 0), (0, 1) (1, 1), (0, 1) (2, 2), (0, 1),

the number $𝑎 𝑑 - 𝑏 𝑐$ is $1, 2, 1, 1, 2$ respectively, which is nonzero. So each of them spans $ℝ^{2}$ by Exercise 1.3.37(a). Neither vector of the pair is a multiple of the other: a multiple of $(1, 0)$ has second coordinate $0$ , a multiple of $(0, 1)$ has first coordinate $0$ , and a multiple of $(1, 1)$ or $(2, 2)$ has equal coordinates. So each pair is independent by Proposition 1.5.15(d). By Proposition 1.6.2, these five sublists are exactly the bases of $ℝ^{2}$ contained in $ℒ︀$ .

Minimal spanning lists and maximal independent lists

The first proof deletes entries until no entry can be deleted without shrinking the span. The next result says that this stopping condition characterizes bases, and that so does the mirror-image condition for independent lists, to which no vector can be appended.

Proposition 1.6.13 (Bases are minimal spanning lists and maximal independent lists). Let

ℬ︀ = 𝐯_{1}, \dots, 𝐯_{𝑛}

be a list in

𝑉

. The following are equivalent.

(i) $ℬ︀$ is a basis of $𝑉$ .
(ii) $ℬ︀$ spans $𝑉$ , and for every $𝑗$ , the list obtained by deleting $𝐯_{𝑗}$ from $ℬ︀$ does not span $𝑉$ .
(iii) $ℬ︀$ is linearly independent, and for every $𝐰 \in 𝑉$ , the list $ℬ︀, 𝐰$ is linearly dependent.

Proof.standard

Uses. Proposition 1.6.2 (Bases are independent spanning lists), Lemma 1.5.10 (Linear dependence lemma), Proposition 1.5.14 (Appending a vector), Theorem 1.5.5 (Independence is decided at zero)

Hint 1. Prove (i)

\Leftrightarrow

(ii) and (i)

\Leftrightarrow

(iii). In each, one half of the definition of a basis is common to both statements.

Hint 2. For (ii)

\Rightarrow

(i), suppose

ℬ︀

were dependent and apply Lemma 1.5.10. For (i)

\Rightarrow

(ii), if deleting

𝐯_{𝑗}

leaves a spanning list, write

𝐯_{𝑗}

as a combination of the others.

Hint 3. For (iii), use Proposition 1.5.14: for independent

ℬ︀

, the list

ℬ︀, 𝐰

is independent exactly when

𝐰 \notin span (ℬ︀)

Sketch. (i)

\Rightarrow

(ii): if the list without

𝐯_{𝑗}

spans

𝑉

, then

𝐯_{𝑗} =

\sum_{𝑖 \neq 𝑗} 𝑏_{𝑖} 𝐯_{𝑖}

, and the coefficients

𝑏_{𝑖}

and

- 1

form a dependence relation of

ℬ︀

. (ii)

\Rightarrow

(i): if

ℬ︀

were dependent, Lemma 1.5.10 would delete an entry without changing the span

𝑉

. (i)

\Leftrightarrow

(iii): for independent

ℬ︀

, by Proposition 1.5.14,

ℬ︀, 𝐰

is dependent for every

𝐰

exactly when every

𝐰

lies in

span (ℬ︀)

, that is, when

ℬ︀

spans

𝑉

Throughout we use Proposition 1.6.2: (i) says that $ℬ︀$ spans $𝑉$ and is independent. Write ${ℬ︀}_{𝑗}$ for $ℬ︀$ with $𝐯_{𝑗}$ deleted.

(i) $\Rightarrow$ (ii). Suppose that $ℬ︀$ is a basis, and suppose that ${ℬ︀}_{𝑗}$ spans $𝑉$ for some $𝑗$ . Then $𝐯_{𝑗} \in span ({ℬ︀}_{𝑗})$ , say $𝐯_{𝑗} =$ $\sum_{𝑖 \neq 𝑗} 𝑏_{𝑖} 𝐯_{𝑖}$ . The linear combination of $ℬ︀$ with coefficient $𝑏_{𝑖}$ on $𝐯_{𝑖}$ for $𝑖 \neq 𝑗$ and $- 1$ on $𝐯_{𝑗}$ represents $𝐯_{𝑗} - 𝐯_{𝑗} = 𝟎$ , and it is nontrivial. This contradicts the independence of $ℬ︀$ (Theorem 1.5.5). So no ${ℬ︀}_{𝑗}$ spans $𝑉$ .

(ii) $\Rightarrow$ (i). Suppose (ii). Then $ℬ︀$ spans $𝑉$ , and it remains to show that $ℬ︀$ is independent. If it were dependent, Lemma 1.5.10 would give an index $𝑗$ with $span ({ℬ︀}_{𝑗}) =$ $span (ℬ︀) =$ $𝑉$ , contradicting (ii).

(i) $\Leftrightarrow$ (iii). Both statements include the independence of $ℬ︀$ , so assume it. By Proposition 1.5.14, for $𝐰 \in 𝑉$ the list $ℬ︀, 𝐰$ is dependent if and only if $𝐰 \in span (ℬ︀)$ . So $ℬ︀, 𝐰$ is dependent for every $𝐰 \in 𝑉$ if and only if $𝑉 \subseteq span (ℬ︀)$ , that is, if and only if $ℬ︀$ spans $𝑉$ . □

In (ii), deleting one entry suffices: if some sublist of $ℬ︀$ shorter than $ℬ︀$ spans $𝑉$ , then so does any ${ℬ︀}_{𝑗}$ containing it, since enlarging a list can only enlarge its span (Corollary 1.3.20(b)). So (ii) says that $ℬ︀$ is a spanning list from which nothing can be removed, and (iii) says that $ℬ︀$ is an independent list to which nothing can be added. These are statements about removing and adding entries, not about lengths. In Section 4.1 they become statements about lengths: every independent list is at most as long as every spanning list (Lemma 4.1.2).

1.6.4Coordinates

Choosing a basis of $𝑉$ amounts to choosing a coordinate system for $𝑉$ . The lecture marks the next definition as important, and it is the reason bases are worth having: every vector of $𝑉$ gets a name in $𝐹^{𝑛}$ , and the name determines the vector.

Definition 1.6.14 (Coordinates). Let $ℬ︀ = 𝐯_{1}, \dots, 𝐯_{𝑛}$ be a basis of $𝑉$ , and let $𝐯 \in 𝑉$ . Let $𝑎_{1}, \dots, 𝑎_{𝑛}$ be the coefficients of the unique linear combination of $ℬ︀$ that represents $𝐯$ , so that $𝐯 =$ $𝑎_{1} 𝐯_{1} +$ $\dots +$ $𝑎_{𝑛} 𝐯_{𝑛}$ . The coordinate vector of $𝐯$ with respect to $ℬ︀$ , or the $ℬ︀$ -coordinates of $𝐯$ , is

{[𝐯]}_{ℬ︀} = (\begin{matrix} 𝑎_{1} \\ ⋮ \\ 𝑎_{𝑛} \end{matrix}) \in 𝐹^{𝑛},

and $𝑎_{𝑖}$ is the $𝑖$ -th coordinate of $𝐯$ with respect to $ℬ︀$ . The function $𝑉 \to 𝐹^{𝑛}$ , $𝐯 \mapsto {[𝐯]}_{ℬ︀}$ , is the coordinate map of $ℬ︀$ .

For $𝑛 = 0$ , that is, for the basis $()$ of ${𝟎}$ , we use the convention that $𝐹^{0} = {𝟎}$ consists of the empty column, so that ${[𝟎]}_{()} = 𝟎$ . With it, everything below holds for $𝑛 = 0$ as well.

The definition makes sense because $ℬ︀$ is a basis: some linear combination represents $𝐯$ since $ℬ︀$ spans, and only one does since $ℬ︀$ is independent. Read in reverse, it says that for every column $(𝑎_{1}, \dots, 𝑎_{𝑛}) \in 𝐹^{𝑛}$ ,

{[𝐯]}_{ℬ︀} = (𝑎_{1}, \dots, 𝑎_{𝑛}) if and only if 𝐯 = 𝑎_{1} 𝐯_{1} + \dots + 𝑎_{𝑛} 𝐯_{𝑛} .

(1.6.1)

The forward direction is the definition. For the backward direction, if the combination with coefficients $𝑎_{1}, \dots, 𝑎_{𝑛}$ represents $𝐯$ , then it is the combination representing $𝐯$ , by uniqueness. This is how coordinates are computed in practice: to find ${[𝐯]}_{ℬ︀}$ , find any linear combination of $ℬ︀$ that represents $𝐯$ . For instance, ${[𝐯_{𝑗}]}_{ℬ︀} = 𝐞_{𝑗}$ , since $𝐯_{𝑗}$ is the combination with coefficient $1$ on $𝐯_{𝑗}$ and $0$ elsewhere, and ${[𝟎]}_{ℬ︀} = 𝟎$ .

In the standard bases, coordinates are the familiar numbers. By the proof of Proposition 1.6.7, the coordinate vector of $𝐱 \in 𝐹^{𝑛}$ in the standard basis is $𝐱$ itself. That of $𝐴 \in 𝐹^{𝑚 \times 𝑛}$ is

(𝑎_{11}, 𝑎_{12}, \dots, 𝑎_{1 𝑛}, 𝑎_{21}, \dots, 𝑎_{𝑚 𝑛}) \in 𝐹^{𝑚 𝑛},

the entries of $𝐴$ read row by row. That of $𝑎_{0} +$ $𝑎_{1} 𝑥 +$ $\dots +$ $𝑎_{𝑛} 𝑥^{𝑛}$ is $(𝑎_{0}, 𝑎_{1}, \dots, 𝑎_{𝑛}) \in$ $𝐹^{𝑛 + 1}$ , the list of its coefficients; note the shift, as the $𝑖$ -th coordinate of a polynomial is its coefficient $𝑎_{𝑖 - 1}$ . For other bases, coordinates take some work to compute, and they carry information that the entries do not show directly.

Example 1.6.15 (Coordinates in the plane). In $ℝ^{2}$ , let $ℬ︀ =$ $𝐯_{1},$ $𝐯_{2} =$ $(1, 1),$ $(- 1, 1)$ . Solving $𝑎 (1, 1) +$ $𝑏 (- 1, 1) =$ $(𝑥, 𝑦)$ , that is, $𝑎 - 𝑏 = 𝑥$ and $𝑎 + 𝑏 = 𝑦$ , gives the unique solution $𝑎 = (𝑥 + 𝑦) / 2$ , $𝑏 = (𝑦 - 𝑥) / 2$ . So $ℬ︀$ is a basis, and

{[(𝑥, 𝑦)]}_{ℬ︀} = (\begin{matrix} (𝑥 + 𝑦) / 2 \\ (𝑦 - 𝑥) / 2 \end{matrix}) .

For $𝐰 = (1, 3)$ this gives ${[𝐰]}_{ℬ︀} = (2, 1)$ : indeed $𝐰 = 2 𝐯_{1} + 𝐯_{2}$ . The standard coordinates $(1, 3)$ say how to reach $𝐰$ along the horizontal and vertical grid lines: one step right, three steps up. The $ℬ︀$ -coordinates say how to reach it along the tilted grid of lines parallel to $𝐯_{1}$ and $𝐯_{2}$ : two steps along $𝐯_{1}$ , then one along $𝐯_{2}$ .

The basis

𝐯_{1},

𝐯_{2} =

(1, 1),

(- 1, 1)

and

𝐰 = (1, 3) = 2 𝐯_{1} + 𝐯_{2}

, so

{[𝐰]}_{ℬ︀} = (2, 1)

. In the interactive version, the coefficients that the explorer reports for

𝐰

are its

ℬ︀

-coordinates; drag

𝐰

to see them change. Drag

𝐯_{2}

onto the line through

𝐯_{1}

: the list becomes dependent,

𝐰

gets many representations or none, and coordinates no longer make sense.

The order of the entries of $ℬ︀$ matters. The list $𝐯_{2}, 𝐯_{1}$ is also a basis, and in it the coordinates of $𝐰$ are $(1, 2)$ . This is one reason bases are lists rather than sets.

Coordinates name every vector of $𝑉$ , and different vectors get different names. The lecture records this as an observation.

Proposition 1.6.16 (The coordinate map is a bijection). Let $ℬ︀ = 𝐯_{1}, \dots, 𝐯_{𝑛}$ be a basis of $𝑉$ . The coordinate map $𝑉 \to 𝐹^{𝑛}$ , $𝐯 \mapsto {[𝐯]}_{ℬ︀}$ , is a bijection. Its inverse is

𝐹^{𝑛} \to 𝑉, (𝑎_{1}, \dots, 𝑎_{𝑛}) \mapsto 𝑎_{1} 𝐯_{1} + \dots + 𝑎_{𝑛} 𝐯_{𝑛} .

Proof.routine

Uses. Definition 1.6.14 (Coordinates), (1.6.1)

Techniques. Uniqueness via two candidates (Technique 1.1.8)

Hint 1. Call the proposed inverse

Φ

. A function with a two-sided inverse is a bijection. Check

Φ ({[𝐯]}_{ℬ︀}) = 𝐯

and

{[Φ (𝐚)]}_{ℬ︀} = 𝐚

Hint 2. The first identity is the definition of

{[𝐯]}_{ℬ︀}

. For the second, which linear combination of

ℬ︀

represents

Φ (𝐚)

Sketch. Let

Φ (𝑎_{1}, \dots, 𝑎_{𝑛}) =

\sum 𝑎_{𝑖} 𝐯_{𝑖}

. By definition,

{[𝐯]}_{ℬ︀}

lists coefficients representing

𝐯

, so

Φ ({[𝐯]}_{ℬ︀}) = 𝐯

. The combination with coefficients

𝑎_{𝑖}

represents

Φ (𝐚)

, so by uniqueness

{[Φ (𝐚)]}_{ℬ︀} = 𝐚

((1.6.1)). So the two maps are inverse to each other.

Let

Φ : 𝐹^{𝑛} \to 𝑉

be the map

(𝑎_{1}, \dots, 𝑎_{𝑛}) \mapsto

𝑎_{1} 𝐯_{1} +

\dots +

𝑎_{𝑛} 𝐯_{𝑛}

. For

𝐯 \in 𝑉

with

{[𝐯]}_{ℬ︀} =

(𝑎_{1}, \dots, 𝑎_{𝑛})

, we have

𝐯 =

𝑎_{1} 𝐯_{1} +

\dots +

𝑎_{𝑛} 𝐯_{𝑛}

by Definition 1.6.14, that is,

Φ ({[𝐯]}_{ℬ︀}) = 𝐯

. For

𝐚 =

(𝑎_{1}, \dots, 𝑎_{𝑛}) \in

𝐹^{𝑛}

, the combination with coefficients

𝑎_{1}, \dots, 𝑎_{𝑛}

represents

Φ (𝐚)

, so

{[Φ (𝐚)]}_{ℬ︀} = 𝐚

by (1.6.1). So

Φ

is a two-sided inverse of the coordinate map, and both maps are bijections. □

For a fixed basis the correspondence is perfect, but it depends heavily on the basis, as the lecture’s example shows.

Example 1.6.17 (One polynomial, two bases). In ${ℝ [𝑥]}_{\leq 2}$ , let $ℬ︀ = 1, 𝑥, 𝑥^{2}$ be the standard basis and let $𝒞︀ =$ $1,$ $1 +$ $𝑥,$ $1 +$ $𝑥 +$ $𝑥^{2}$ . To see that $𝒞︀$ is a basis, solve

𝑎 \cdot 1 + 𝑏 (1 + 𝑥) + 𝑐 (1 + 𝑥 + 𝑥^{2}) = (𝑎 + 𝑏 + 𝑐) + (𝑏 + 𝑐) 𝑥 + 𝑐 𝑥^{2} = 𝑝_{0} + 𝑝_{1} 𝑥 + 𝑝_{2} 𝑥^{2} .

Comparing coefficients, $𝑐 = 𝑝_{2}$ , then $𝑏 = 𝑝_{1} - 𝑝_{2}$ , then $𝑎 = 𝑝_{0} - 𝑝_{1}$ , and these values do solve the equation. So every polynomial of degree at most $2$ is represented by exactly one linear combination of $𝒞︀$ , and

{[𝑝_{0} + 𝑝_{1} 𝑥 + 𝑝_{2} 𝑥^{2}]}_{𝒞︀} = (\begin{matrix} 𝑝_{0} - 𝑝_{1} \\ 𝑝_{1} - 𝑝_{2} \\ 𝑝_{2} \end{matrix}), while {[𝑝_{0} + 𝑝_{1} 𝑥 + 𝑝_{2} 𝑥^{2}]}_{ℬ︀} = (\begin{matrix} 𝑝_{0} \\ 𝑝_{1} \\ 𝑝_{2} \end{matrix}) .

For $𝑝 = 𝑥 + 𝑥^{2}$ ,

{[𝑥 + 𝑥^{2}]}_{ℬ︀} = (\begin{matrix} 0 \\ 1 \\ 1 \end{matrix}), {[𝑥 + 𝑥^{2}]}_{𝒞︀} = (\begin{matrix} - 1 \\ 0 \\ 1 \end{matrix}),

and indeed $𝑥 +$ $𝑥^{2} =$ $- 1 +$ $0 (1 + 𝑥) +$ $(1 + 𝑥 + 𝑥^{2})$ . The same vector has different coordinates in different bases, and the column $(0, 1, 1)$ names $𝑥 + 𝑥^{2}$ in $ℬ︀$ but names $(1 + 𝑥) +$ $(1 + 𝑥 + 𝑥^{2}) =$ $2 +$ $2 𝑥 +$ $𝑥^{2}$ in $𝒞︀$ . How ${[𝐯]}_{ℬ︀}$ and ${[𝐯]}_{𝒞︀}$ are related for two bases is the subject of Section 4.5.

Over $ℝ$ , the basis $1, 𝑖$ of $ℂ$ (Example 1.6.5) gives ${[𝑎 + 𝑏 𝑖]}_{(1, 𝑖)} =$ $(𝑎, 𝑏)$ . This is the identification of $ℂ$ with the plane $ℝ^{2}$ , and Proposition 1.6.16 makes it a bijection.

Exercise 1.6.18.routine Let $𝒯︀ =$ $1,$ $𝑥 -$ $1,$ $𝑥^{2} -$ $2 𝑥 +$ $1$ in ${𝐹 [𝑥]}_{\leq 2}$ .

(a)Show that $𝒯︀$ is a basis of ${𝐹 [𝑥]}_{\leq 2}$ .
(b)Show that ${[𝑎 + 𝑏 𝑥 + 𝑐 𝑥^{2}]}_{𝒯︀} =$ $(𝑎 + 𝑏 + 𝑐, 𝑏 + 2 𝑐, 𝑐)$ .
(c)Explain why the first coordinate of ${[𝑝]}_{𝒯︀}$ is $𝑝 (1)$ for every $𝑝 \in {𝐹 [𝑥]}_{\leq 2}$ .

Solution.

Uses. Exercise 1.3.33, Proposition 1.5.24 (Distinct degrees), Proposition 1.6.2 (Bases are independent spanning lists), (1.6.1), Proposition 1.2.18 (Degree and evaluation versus the operations)

Hint 1. For (a), the entries have degrees

0, 1, 2

. Use Exercise 1.3.33 and Proposition 1.5.24.

Hint 2. For (b), by (1.6.1) it suffices to expand the combination with the proposed coefficients and check that it gives

𝑎 + 𝑏 𝑥 + 𝑐 𝑥^{2}

Hint 3. For (c), evaluate

𝑝 =

𝛼 +

𝛽 (𝑥 - 1) +

𝛾 (𝑥^{2} - 2 𝑥 + 1)

1

Sketch. (a) Degrees

0, 1, 2

: spanning by Exercise 1.3.33, independence by Proposition 1.5.24. (b) Expanding

(𝑎 + 𝑏 + 𝑐) +

(𝑏 + 2 𝑐) (𝑥 - 1) +

𝑐 (𝑥^{2} - 2 𝑥 + 1)

gives

𝑎 + 𝑏 𝑥 + 𝑐 𝑥^{2}

. (c) Evaluation respects linear combinations, and the second and third entries of

𝒯︀

vanish at

1

(a) The entries of $𝒯︀$ have degrees $0$ , $1$ , and $2$ . So $𝒯︀$ spans ${𝐹 [𝑥]}_{\leq 2}$ by Exercise 1.3.33(a), and it is independent by Proposition 1.5.24. By Proposition 1.6.2, it is a basis.

(b) Expanding,

\begin{aligned} (𝑎 + 𝑏 + 𝑐) \cdot 1 + (𝑏 + 2 𝑐) (𝑥 - 1) + 𝑐 (𝑥^{2} - 2 𝑥 + 1) & = (𝑎 + 𝑏 + 𝑐 - 𝑏 - 2 𝑐 + 𝑐) + (𝑏 + 2 𝑐 - 2 𝑐) 𝑥 + 𝑐 𝑥^{2} \\ = 𝑎 + 𝑏 𝑥 + 𝑐 𝑥^{2} . \end{aligned}

By (1.6.1), ${[𝑎 + 𝑏 𝑥 + 𝑐 𝑥^{2}]}_{𝒯︀} =$ $(𝑎 + 𝑏 + 𝑐, 𝑏 + 2 𝑐, 𝑐)$ .

(c) Write ${[𝑝]}_{𝒯︀} =$ $(𝛼, 𝛽, 𝛾)$ , so $𝑝 =$ $𝛼 +$ $𝛽 (𝑥 - 1) +$ $𝛾 (𝑥^{2} - 2 𝑥 + 1)$ . By Proposition 1.2.18(c), evaluation at $1$ respects sums and scalar multiples, so

𝑝 (1) = 𝛼 + 𝛽 (1 - 1) + 𝛾 (1 - 2 + 1) = 𝛼 .

(In (b), this is the identity $𝑝 (1) = 𝑎 + 𝑏 + 𝑐$ .) Similarly, over $ℝ$ the second coordinate $𝑏 + 2 𝑐$ is the derivative of $𝑝$ at $1$ . These are the first terms of the Taylor expansion of $𝑝$ around $1$ .

Coordinates respect linear combinations

The coordinate map is a bijection, and it is compatible with the vector space operations: adding in $𝑉$ and then taking coordinates gives the same column as taking coordinates and then adding in $𝐹^{𝑛}$ . This is what makes coordinates useful for computation.

Proposition 1.6.19 (Coordinates respect linear combinations). Let $ℬ︀$ be a basis of $𝑉$ of length $𝑛$ .

(a)For all $𝐱, 𝐲 \in 𝑉$ , ${[𝐱 + 𝐲]}_{ℬ︀} =$ ${[𝐱]}_{ℬ︀} +$ ${[𝐲]}_{ℬ︀}$ .
(b)For all $𝑐 \in 𝐹$ and $𝐱 \in 𝑉$ , ${[𝑐 𝐱]}_{ℬ︀} = 𝑐 {[𝐱]}_{ℬ︀}$ .
(c)For all $𝑘 \geq 0$ , all $𝐱_{1}, \dots, 𝐱_{𝑘} \in 𝑉$ , and all $𝑐_{1}, \dots, 𝑐_{𝑘} \in 𝐹$ ,
${[𝑐_{1} 𝐱_{1} + \dots + 𝑐_{𝑘} 𝐱_{𝑘}]}_{ℬ︀} = 𝑐_{1} {[𝐱_{1}]}_{ℬ︀} + \dots + 𝑐_{𝑘} {[𝐱_{𝑘}]}_{ℬ︀} .$

On each left side the operations are those of $𝑉$ , and on each right side those of $𝐹^{𝑛}$ .

Proof.routine

Uses. Definition 1.6.14 (Coordinates), (1.6.1), Lemma 1.3.9 (Arithmetic of linear combinations), Definition 1.2.4 (The space $𝐹^{𝑛}$ ), (1.3.1)

Techniques. Induction on the length of a list (Technique 1.6.9)

Hint 1. By (1.6.1), to show

{[𝐰]}_{ℬ︀} =

(𝑑_{1}, \dots, 𝑑_{𝑛})

it suffices to exhibit

𝐰

\sum 𝑑_{𝑖} 𝐯_{𝑖}

Hint 2. For (a), write

𝐱 = \sum 𝑎_{𝑖} 𝐯_{𝑖}

and

𝐲 = \sum 𝑏_{𝑖} 𝐯_{𝑖}

, and combine the two sums with Lemma 1.3.9. Do (b) the same way.

Hint 3. For (c), induct on

𝑘

. Split off the last term

𝑐_{𝑘} 𝐱_{𝑘}

and apply (a), (b), and the inductive hypothesis.

Sketch. If

{[𝐱]}_{ℬ︀} = (𝑎_{𝑖})

and

{[𝐲]}_{ℬ︀} = (𝑏_{𝑖})

, then

𝐱 +

𝐲 =

\sum (𝑎_{𝑖} + 𝑏_{𝑖}) 𝐯_{𝑖}

and

𝑐 𝐱 =

\sum (𝑐 𝑎_{𝑖}) 𝐯_{𝑖}

by Lemma 1.3.9, so by (1.6.1) the coordinates are

(𝑎_{𝑖} + 𝑏_{𝑖})

and

(𝑐 𝑎_{𝑖})

, which are

{[𝐱]}_{ℬ︀} + {[𝐲]}_{ℬ︀}

and

𝑐 {[𝐱]}_{ℬ︀}

. For (c), induct on

𝑘

: the empty sum is

𝟎

with coordinates

𝟎

, and

{[𝐮 + 𝑐_{𝑘} 𝐱_{𝑘}]}_{ℬ︀} =

{[𝐮]}_{ℬ︀} +

𝑐_{𝑘} {[𝐱_{𝑘}]}_{ℬ︀}

by (a) and (b).

Write $ℬ︀ = 𝐯_{1}, \dots, 𝐯_{𝑛}$ .

(a) Let ${[𝐱]}_{ℬ︀} =$ $(𝑎_{1}, \dots, 𝑎_{𝑛})$ and ${[𝐲]}_{ℬ︀} =$ $(𝑏_{1}, \dots, 𝑏_{𝑛})$ , so that $𝐱 = \sum_{𝑖} 𝑎_{𝑖} 𝐯_{𝑖}$ and $𝐲 = \sum_{𝑖} 𝑏_{𝑖} 𝐯_{𝑖}$ . By Lemma 1.3.9(a),

𝐱 + 𝐲 = \sum_{𝑖 = 1}^{𝑛} 𝑎_{𝑖} 𝐯_{𝑖} + \sum_{𝑖 = 1}^{𝑛} 𝑏_{𝑖} 𝐯_{𝑖} = \sum_{𝑖 = 1}^{𝑛} (𝑎_{𝑖} + 𝑏_{𝑖}) 𝐯_{𝑖} .

So the combination with coefficients $𝑎_{1} +$ $𝑏_{1},$ $\dots,$ $𝑎_{𝑛} +$ $𝑏_{𝑛}$ represents $𝐱 + 𝐲$ , and by (1.6.1),

{[𝐱 + 𝐲]}_{ℬ︀} = (\begin{matrix} 𝑎_{1} + 𝑏_{1} \\ ⋮ \\ 𝑎_{𝑛} + 𝑏_{𝑛} \end{matrix}) = (\begin{matrix} 𝑎_{1} \\ ⋮ \\ 𝑎_{𝑛} \end{matrix}) + (\begin{matrix} 𝑏_{1} \\ ⋮ \\ 𝑏_{𝑛} \end{matrix}) = {[𝐱]}_{ℬ︀} + {[𝐲]}_{ℬ︀},

where the middle equality is the definition of addition in $𝐹^{𝑛}$ (Definition 1.2.4).

(b) With ${[𝐱]}_{ℬ︀} =$ $(𝑎_{1}, \dots, 𝑎_{𝑛})$ as before, Lemma 1.3.9(b) gives $𝑐 𝐱 =$ $\sum_{𝑖} (𝑐 𝑎_{𝑖}) 𝐯_{𝑖}$ . So ${[𝑐 𝐱]}_{ℬ︀} =$ $(𝑐 𝑎_{1}, \dots, 𝑐 𝑎_{𝑛}) =$ $𝑐 {[𝐱]}_{ℬ︀}$ , by (1.6.1) and the definition of scalar multiplication in $𝐹^{𝑛}$ .

(c) We induct on $𝑘$ . For $𝑘 = 0$ both sides are empty sums: the left side is ${[𝟎]}_{ℬ︀} = 𝟎$ , and the right side is $𝟎 \in 𝐹^{𝑛}$ . Suppose that (c) holds for combinations of length $𝑘$ , and let $𝐮 =$ $𝑐_{1} 𝐱_{1} +$ $\dots +$ $𝑐_{𝑘} 𝐱_{𝑘}$ . By (1.3.1), then (a), then (b) and the inductive hypothesis,

\begin{aligned} {[𝑐_{1} 𝐱_{1} + \dots + 𝑐_{𝑘 + 1} 𝐱_{𝑘 + 1}]}_{ℬ︀} & = {[𝐮 + 𝑐_{𝑘 + 1} 𝐱_{𝑘 + 1}]}_{ℬ︀} = {[𝐮]}_{ℬ︀} + {[𝑐_{𝑘 + 1} 𝐱_{𝑘 + 1}]}_{ℬ︀} \\ = (𝑐_{1} {[𝐱_{1}]}_{ℬ︀} + \dots + 𝑐_{𝑘} {[𝐱_{𝑘}]}_{ℬ︀}) + 𝑐_{𝑘 + 1} {[𝐱_{𝑘 + 1}]}_{ℬ︀}, \end{aligned}

as desired. □

The lecture calls (c) the “Mega-Prop”: the coordinate map respects linear combinations. Functions between vector spaces with this property are the linear maps of Section 2.1 (Definition 2.1.1), and the induction in (c) shows in general that (a) and (b) are enough to check (Theorem 2.1.3). So the coordinate map of a basis is a linear map, and by Proposition 1.6.16 it is a bijection. Such a map is an isomorphism (Section 4.5): once a basis of length $𝑛$ is chosen, $𝑉$ and $𝐹^{𝑛}$ are the same vector space with different names for the vectors.

The practical consequence is that every question about linear combinations in $𝑉$ can be asked in $𝐹^{𝑛}$ instead.

Proposition 1.6.20 (Coordinates translate questions about $𝑉$ into $𝐹^{𝑛}$ ). Let $ℬ︀$ be a basis of $𝑉$ of length $𝑛$ , and let $𝐱_{1}, \dots, 𝐱_{𝑘}, 𝐰 \in 𝑉$ . For all $𝑐_{1}, \dots, 𝑐_{𝑘} \in 𝐹$ ,

𝑐_{1} 𝐱_{1} + \dots + 𝑐_{𝑘} 𝐱_{𝑘} = 𝐰 if and only if 𝑐_{1} {[𝐱_{1}]}_{ℬ︀} + \dots + 𝑐_{𝑘} {[𝐱_{𝑘}]}_{ℬ︀} = {[𝐰]}_{ℬ︀} .

Consequently:

(a) $𝐱_{1}, \dots, 𝐱_{𝑘}$ is linearly independent in $𝑉$ if and only if ${[𝐱_{1}]}_{ℬ︀},$ $\dots,$ ${[𝐱_{𝑘}]}_{ℬ︀}$ is linearly independent in $𝐹^{𝑛}$ ;
(b) $𝐰 \in$ $span (𝐱_{1}, \dots, 𝐱_{𝑘})$ if and only if ${[𝐰]}_{ℬ︀} \in$ $span ({[𝐱_{1}]}_{ℬ︀}, \dots, {[𝐱_{𝑘}]}_{ℬ︀})$ ;
(c) $𝐱_{1}, \dots, 𝐱_{𝑘}$ spans $𝑉$ if and only if ${[𝐱_{1}]}_{ℬ︀},$ $\dots,$ ${[𝐱_{𝑘}]}_{ℬ︀}$ spans $𝐹^{𝑛}$ . In particular, $𝐱_{1}, \dots, 𝐱_{𝑘}$ is a basis of $𝑉$ if and only if ${[𝐱_{1}]}_{ℬ︀},$ $\dots,$ ${[𝐱_{𝑘}]}_{ℬ︀}$ is a basis of $𝐹^{𝑛}$ .

Proof.routine

Uses. Proposition 1.6.19 (Coordinates respect linear combinations), Proposition 1.6.16 (The coordinate map is a bijection), Theorem 1.5.5 (Independence is decided at zero), Definition 1.3.10 (Span), Proposition 1.6.2 (Bases are independent spanning lists)

Hint 1. For the displayed equivalence, apply the coordinate map to the left equation, and use that it is injective for the converse.

Hint 2. Then (a) is the case

𝐰 = 𝟎

, and (b) is a restatement. For (c), every vector of

𝐹^{𝑛}

{[𝐰]}_{ℬ︀}

for some

𝐰 \in 𝑉

Sketch. By Proposition 1.6.19(c),

{[\sum 𝑐_{𝑖} 𝐱_{𝑖}]}_{ℬ︀} =

\sum 𝑐_{𝑖} {[𝐱_{𝑖}]}_{ℬ︀}

, and the coordinate map is injective, so

\sum 𝑐_{𝑖} 𝐱_{𝑖} = 𝐰

exactly when the coordinates agree. So the two lists have the same linear relations (take

𝐰 = 𝟎

), and

𝐰

is in one span exactly when

{[𝐰]}_{ℬ︀}

is in the other. Since the coordinate map is surjective, (b) for all

𝐰

gives (c).

By Proposition 1.6.19(c), ${[𝑐_{1} 𝐱_{1} + \dots + 𝑐_{𝑘} 𝐱_{𝑘}]}_{ℬ︀} =$ $𝑐_{1} {[𝐱_{1}]}_{ℬ︀} +$ $\dots +$ $𝑐_{𝑘} {[𝐱_{𝑘}]}_{ℬ︀}$ . The coordinate map is injective (Proposition 1.6.16), so two vectors of $𝑉$ are equal if and only if their coordinate vectors are. Applying this to $\sum_{𝑖} 𝑐_{𝑖} 𝐱_{𝑖}$ and $𝐰$ proves the displayed equivalence.

(a) Since ${[𝟎]}_{ℬ︀} = 𝟎$ , the case $𝐰 = 𝟎$ says that the two lists have exactly the same linear relations. So one has only the trivial relation if and only if the other does, and (a) follows from Theorem 1.5.5.

(b) By the displayed equivalence, some $𝑐_{1}, \dots, 𝑐_{𝑘}$ satisfy the left equation if and only if they satisfy the right one.

(c) Suppose that the $𝐱_{𝑖}$ span $𝑉$ , and let $𝐲 \in 𝐹^{𝑛}$ . The coordinate map is surjective, so $𝐲 = {[𝐰]}_{ℬ︀}$ for some $𝐰 \in 𝑉$ . Since $𝐰 \in$ $span (𝐱_{1}, \dots, 𝐱_{𝑘})$ , (b) gives $𝐲 \in$ $span ({[𝐱_{1}]}_{ℬ︀}, \dots, {[𝐱_{𝑘}]}_{ℬ︀})$ . Conversely, if the coordinate vectors span $𝐹^{𝑛}$ , then for every $𝐰 \in 𝑉$ , ${[𝐰]}_{ℬ︀}$ lies in their span, so $𝐰 \in$ $span (𝐱_{1}, \dots, 𝐱_{𝑘})$ by (b). The last statement follows from (a), (c), and Proposition 1.6.2. □

Example 1.6.21 (Testing polynomials through their coordinates). In

{𝐹 [𝑥]}_{\leq 2}

, consider

1 + 𝑥 + 𝑥^{2}

1 + 2 𝑥 + 3 𝑥^{2}

1 + 4 𝑥 + 9 𝑥^{2}

. Their coordinate vectors in the standard basis are

(1, 1, 1),

(1, 2, 3),

(1, 4, 9)

. In Exercise 1.5.29 we reduced a linear relation among these columns to

2 𝑐 = 0

, using steps that are valid over every field, so the columns are independent when

1 + 1 \neq 0

. When

1 + 1 = 0

, the last two columns are both

(1, 0, 1)

, so they are dependent. By Proposition 1.6.20(a), the three polynomials are linearly independent if and only if

1 + 1 \neq 0

𝐹

. Nothing about polynomials was used beyond their coordinates. In the same way, questions about matrices in

𝐹^{𝑚 \times 𝑛}

become questions about columns in

𝐹^{𝑚 𝑛}

, and Section 3.1 solves such questions systematically.

Exercise 1.6.22.routine Let

ℬ︀ = 𝐯_{1}, \dots, 𝐯_{𝑛}

and

𝒞︀ = 𝐰_{1}, \dots, 𝐰_{𝑛}

be bases of

𝑉

such that

{[𝐯]}_{ℬ︀} = {[𝐯]}_{𝒞︀}

for every

𝐯 \in 𝑉

. Show that

ℬ︀ = 𝒞︀

Solution.

Uses. Definition 1.6.14 (Coordinates), (1.6.1)

Hint 1. Which vector of

𝑉

has

ℬ︀

-coordinates

𝐞_{𝑗}

Hint 2. Compute

{[𝐯_{𝑗}]}_{𝒞︀}

using the hypothesis, and read it in reverse.

Sketch.

{[𝐯_{𝑗}]}_{𝒞︀} =

{[𝐯_{𝑗}]}_{ℬ︀} =

𝐞_{𝑗}

, so

𝐯_{𝑗} = 𝐰_{𝑗}

by (1.6.1).

Fix

𝑗

. Since

𝐯_{𝑗}

is represented by the combination of

ℬ︀

with coefficient

1

𝐯_{𝑗}

and

0

elsewhere,

{[𝐯_{𝑗}]}_{ℬ︀} = 𝐞_{𝑗}

. By hypothesis

{[𝐯_{𝑗}]}_{𝒞︀} = 𝐞_{𝑗}

as well, which by Definition 1.6.14 means

𝐯_{𝑗} =

0 𝐰_{1} +

\dots +

1 𝐰_{𝑗} +

\dots +

0 𝐰_{𝑛} =

𝐰_{𝑗}

. This holds for every

𝑗

, and the lists have the same length, so

ℬ︀ = 𝒞︀

1.6.5Finite and infinite dimension

Theorem 1.6.10 produces a basis from any spanning list. It applies exactly to the spaces that have a spanning list.

Definition 1.6.23 (Finite-dimensional). A vector space

𝑉

is finite-dimensional if some list in

𝑉

spans

𝑉

. Otherwise

𝑉

is infinite-dimensional.

The name anticipates Section 4.1, where the dimension of a finite-dimensional space is defined as the common length of its bases (Definition 4.1.5). Every space in Section 1.6.2 is finite-dimensional, as are ${𝟎}$ (spanned by $()$ ), $ℂ$ over $ℝ$ , and the span of any list.

Corollary 1.6.24 (Bases exist in finite dimensions). Every finite-dimensional vector space has a basis. More precisely, every spanning list of

𝑉

contains a basis of

𝑉

as a sublist.

Proof.routine

Uses. Definition 1.6.23 (Finite-dimensional), Theorem 1.6.10 (Every spanning list contains a basis)

Hint 1. What does the definition of finite-dimensional provide?

Hint 2. Apply Theorem 1.6.10 to it.

Sketch. A finite-dimensional space has a spanning list, and by Theorem 1.6.10 that list has a sublist which is a basis.

𝑉

is finite-dimensional, some list

ℒ︀

spans

𝑉

. By Theorem 1.6.10, some sublist of

ℒ︀

is a basis of

𝑉

. The same argument applies to every spanning list of

𝑉

. □

Not every vector space is finite-dimensional. The basic example is $𝐹 [𝑥]$ , and the reason is the degree.

Proposition 1.6.25 (No finite list spans

𝐹 [𝑥]

). For every list

𝑝_{1}, \dots, 𝑝_{𝑘}

𝐹 [𝑥]

span (𝑝_{1}, \dots, 𝑝_{𝑘}) \neq

𝐹 [𝑥]

. So

𝐹 [𝑥]

is infinite-dimensional.

Proof.routine

Uses. Example 1.4.9 (Polynomials), Proposition 1.4.14 (The span is the smallest subspace containing a list), Definition 1.2.16 (Degree)

Hint 1. Every linear combination of

𝑝_{1}, \dots, 𝑝_{𝑘}

has degree at most the largest of the degrees

deg 𝑝_{𝑖}

. Find a polynomial of larger degree.

Hint 2. Let

𝑑

be the largest of

0,

deg 𝑝_{1},

\dots,

deg 𝑝_{𝑘}

. Then every

𝑝_{𝑖}

lies in the subspace

{𝐹 [𝑥]}_{\leq 𝑑}

. What does Proposition 1.4.14 say about the span?

Sketch. With

𝑑 =

max (0, deg 𝑝_{1}, \dots, deg 𝑝_{𝑘})

, all

𝑝_{𝑖}

lie in the subspace

{𝐹 [𝑥]}_{\leq 𝑑}

, hence so does their span (Proposition 1.4.14). But

𝑥^{𝑑 + 1} \notin {𝐹 [𝑥]}_{\leq 𝑑}

Let

𝑑

be the largest of the integers

0,

deg 𝑝_{1},

\dots,

deg 𝑝_{𝑘}

, where an entry

deg 𝑝_{𝑖} = - \infty

(for

𝑝_{𝑖} = 𝟎

) does not affect the maximum, and

𝑑 = 0

𝑘 = 0

. Then

𝑝_{1},

\dots,

𝑝_{𝑘} \in

{𝐹 [𝑥]}_{\leq 𝑑}

, which is a subspace of

𝐹 [𝑥]

(Example 1.4.9). By Proposition 1.4.14(b),

span (𝑝_{1}, \dots, 𝑝_{𝑘}) \subseteq

{𝐹 [𝑥]}_{\leq 𝑑}

. The polynomial

𝑥^{𝑑 + 1}

has degree

𝑑 + 1 > 𝑑

, so it is not in

{𝐹 [𝑥]}_{\leq 𝑑}

, and hence not in

span (𝑝_{1}, \dots, 𝑝_{𝑘})

. So no list spans

𝐹 [𝑥]

, and

𝐹 [𝑥]

is infinite-dimensional by Definition 1.6.23. □

So $𝐹 [𝑥]$ has no basis in our sense, since a basis is a finite list that spans. Other infinite-dimensional spaces are $ℝ$ over $ℚ$ (Exercise 1.3.45) and the space of finitely supported functions on an infinite set. Function spaces such as $ℝ^{ℝ}$ and $𝐶 [0, 1]$ are infinite-dimensional too, but proving it is easier with the tools of Section 4.1, which show that a subspace of a finite-dimensional space is finite-dimensional (Proposition 4.1.21).

Remark 1.6.26 (Thinning down and growing up). Proposition 1.6.13 suggests two ways to reach a basis. Thinning down: start with a spanning list and delete redundant entries, as in Theorem 1.6.10. Growing up: start with an independent list and, as long as it does not span $𝑉$ , append a vector outside its span, which keeps it independent by Proposition 1.5.14. By Proposition 1.6.13, either process can only stop at a basis.

The difference is that thinning always stops, because a list has only finitely many entries to delete, while growing need not stop. In $𝐹 [𝑥]$ it never stops, whatever vectors are appended, because no list spans $𝐹 [𝑥]$ (Proposition 1.6.25). For instance, starting from the empty list and appending $1$ , then $𝑥$ , then $𝑥^{2}$ , and so on, every stage $1, 𝑥, \dots, 𝑥^{𝑛}$ is independent (Example 1.5.7), and there is always a next power of $𝑥$ outside its span. In a finite-dimensional space growing does stop, because an independent list can never be longer than a spanning list (Lemma 4.1.2). That is how Section 4.1 proves that every independent list extends to a basis (Theorem 4.1.16). In infinite dimensions, making “grow forever” produce a basis needs set theory, which the next aside describes.

Aside (Bases of infinite-dimensional spaces).Beyond 21-242 Allowing bases to be infinite subsets fixes the problem. A subset

𝐵 \subseteq 𝑉

is called a basis (or Hamel basis) of

𝑉

if every vector of

𝑉

is represented by exactly one linear combination of finitely many distinct elements of

𝐵

, up to terms with coefficient

0

. Equivalently,

𝐵

is linearly independent (Aside (Independent sets)) and spans

𝑉

(Aside (Spans of infinite sets)). The set

{1, 𝑥, 𝑥^{2}, \dots}

is a basis of

𝐹 [𝑥]

in this sense, and the coordinates of a polynomial with respect to it are its coefficient sequence, which is how Definition 1.2.13 defined

𝐹 [𝑥]

in the first place. Every vector space has a basis in this sense, but the proof uses Zorn’s lemma and gives no way to write one down for

ℝ

over

ℚ

or for

ℝ^{ℝ}

(Section 15.1).

Exercises

Exercise 1.6.27.routine Decide whether each list is a basis of the given space, and justify your answer.

(a) $(1, 2, 0),$ $(0, 1, 2),$ $(2, 0, 1)$ in $𝐹^{3}$ . (The answer depends on $𝐹$ .)
(b) $1 +$ $𝑥^{2},$ $𝑥 -$ $𝑥^{2},$ $2 +$ $𝑥 +$ $𝑥^{2}$ in ${ℝ [𝑥]}_{\leq 2}$ .
(c) $𝑈_{11},$ $𝑈_{12} +$ $𝑈_{21},$ $𝑈_{22}$ in $ℝ^{2 \times 2}$ .

Solution.

Uses. Definition 1.6.1 (Basis), Proposition 1.6.2 (Bases are independent spanning lists), Theorem 1.5.5 (Independence is decided at zero), Proposition 1.1.17 (No zero divisors), Example 1.4.11 (Matrices)

Hint 1. For (a), solve

𝑎 (1, 2, 0) +

𝑏 (0, 1, 2) +

𝑐 (2, 0, 1) =

(𝑥, 𝑦, 𝑧)

by expressing

𝑎

in terms of

𝑐

, then

𝑏

, and substituting into the last equation. Which element of

𝐹

do you need to divide by?

Hint 2. For (b), look for a way to write

2 + 𝑥 + 𝑥^{2}

using the other two entries. For (c), which matrices can a combination of these three be?

Sketch. (a) The equations give

9 𝑐 = 4 𝑥 - 2 𝑦 + 𝑧

, and cyclically for

𝑎

and

𝑏

. If

3 \neq 0

𝐹

, there is exactly one solution, so the list is a basis. If

3 = 0

, the three vectors add up to

(3, 3, 3) = 𝟎

. (b) No:

2 +

𝑥 +

𝑥^{2} =

2 (1 + 𝑥^{2}) +

(𝑥 - 𝑥^{2})

. (c) No: the combinations are the symmetric matrices, and

𝑈_{12}

is not symmetric. The list is a basis of the symmetric matrices, though.

(a) For $(𝑥, 𝑦, 𝑧) \in 𝐹^{3}$ , the equation $𝑎 (1, 2, 0) +$ $𝑏 (0, 1, 2) +$ $𝑐 (2, 0, 1) =$ $(𝑥, 𝑦, 𝑧)$ reads

𝑎 + 2 𝑐 = 𝑥, 2 𝑎 + 𝑏 = 𝑦, 2 𝑏 + 𝑐 = 𝑧 .

Any solution has $𝑎 = 𝑥 - 2 𝑐$ , then $𝑏 =$ $𝑦 -$ $2 𝑎 =$ $𝑦 -$ $2 𝑥 +$ $4 𝑐$ , and then the third equation becomes $2 𝑦 - 4 𝑥 + 8 𝑐 + 𝑐 = 𝑧$ , that is,

9 𝑐 = 4 𝑥 - 2 𝑦 + 𝑧 .

Suppose $3 \neq 0$ in $𝐹$ . Then $9 = 3 \cdot 3 \neq 0$ by Proposition 1.1.17, so $𝑐 = (4 𝑥 - 2 𝑦 + 𝑧) / 9$ , and then

𝑎 = \frac{𝑥 + 4 𝑦 - 2 𝑧}{9}, 𝑏 = \frac{- 2 𝑥 + 𝑦 + 4 𝑧}{9} .

So there is at most one solution. These values are a solution: for instance $𝑎 +$ $2 𝑐 =$ $(𝑥 + 4 𝑦 - 2 𝑧 + 8 𝑥 - 4 𝑦 + 2 𝑧) / 9 =$ $𝑥$ , and the other two equations check the same way, as the formulas are cyclic shifts of each other. So every vector of $𝐹^{3}$ has exactly one representation, and the list is a basis (Definition 1.6.1).

Suppose $3 = 0$ in $𝐹$ , as in $𝔽_{3}$ . Then $(1, 2, 0) +$ $(0, 1, 2) +$ $(2, 0, 1) =$ $(3, 3, 3) =$ $𝟎$ is a dependence relation, so the list is not a basis.

(b) Not a basis: $2 (1 + 𝑥^{2}) +$ $(𝑥 - 𝑥^{2}) =$ $2 +$ $𝑥 +$ $𝑥^{2}$ , so $2 (1 + 𝑥^{2}) +$ $(𝑥 - 𝑥^{2}) -$ $(2 + 𝑥 + 𝑥^{2}) =$ $𝟎$ is a dependence relation.

(c) Not a basis. Every linear combination

𝑎 𝑈_{11} + 𝑏 (𝑈_{12} + 𝑈_{21}) + 𝑑 𝑈_{22} = (\begin{matrix} 𝑎 & 𝑏 \\ 𝑏 & 𝑑 \end{matrix})

has equal off-diagonal entries, so $𝑈_{12}$ is not in the span, and the list does not span $ℝ^{2 \times 2}$ . (The display also shows that each symmetric matrix $(\begin{matrix} 𝑎 & 𝑏 \\ 𝑏 & 𝑑 \end{matrix})$ is represented by exactly one combination, so the list is a basis of the subspace $𝑆$ of symmetric matrices of Example 1.4.11.)

Exercise 1.6.28.routine

(a)Show that $ℬ︀ =$ $(1, 1, 1),$ $(0, 1, 1),$ $(0, 0, 1)$ is a basis of $𝐹^{3}$ , find ${[(𝑥, 𝑦, 𝑧)]}_{ℬ︀}$ , and find the vector $𝐯 \in 𝐹^{3}$ with ${[𝐯]}_{ℬ︀} = (1, 2, 3)$ .
(b)In $𝐹^{2 \times 2}$ , let
$𝒞︀ = 𝑈_{11}, 𝑈_{11} + 𝑈_{12}, 𝑈_{11} + 𝑈_{12} + 𝑈_{21}, 𝑈_{11} + 𝑈_{12} + 𝑈_{21} + 𝑈_{22} .$
Show that $𝒞︀$ is a basis and find ${[𝐴]}_{𝒞︀}$ for $𝐴 = (\begin{matrix} 𝑝 & 𝑞 \\ 𝑟 & 𝑠 \end{matrix})$ .

Solution.

Uses. Definition 1.6.1 (Basis), Definition 1.6.14 (Coordinates), (1.6.1)

Hint 1. Solve for the coefficients directly. In (a), the combination

𝑎 (1, 1, 1) +

𝑏 (0, 1, 1) +

𝑐 (0, 0, 1)

(𝑎, 𝑎 + 𝑏, 𝑎 + 𝑏 + 𝑐)

Hint 2. In (b), write the combination with coefficients

𝛼, 𝛽, 𝛾, 𝛿

as a single matrix and solve from the bottom right entry up.

Sketch. (a)

(𝑎, 𝑎 + 𝑏, 𝑎 + 𝑏 + 𝑐) =

(𝑥, 𝑦, 𝑧)

has the unique solution

(𝑥, 𝑦 - 𝑥, 𝑧 - 𝑦)

, which is

{[(𝑥, 𝑦, 𝑧)]}_{ℬ︀}

; and

𝐯 =

(1, 1 + 2, 1 + 2 + 3) =

(1, 3, 6)

. (b) The combination is

(\begin{matrix} 𝛼 + 𝛽 + 𝛾 + 𝛿 & 𝛽 + 𝛾 + 𝛿 \\ 𝛾 + 𝛿 & 𝛿 \end{matrix})

, so

{[𝐴]}_{𝒞︀} =

(𝑝 - 𝑞, 𝑞 - 𝑟, 𝑟 - 𝑠, 𝑠)

(a) The combination with coefficients $𝑎, 𝑏, 𝑐$ represents $(𝑎, 𝑎 + 𝑏, 𝑎 + 𝑏 + 𝑐)$ . This equals $(𝑥, 𝑦, 𝑧)$ if and only if $𝑎 = 𝑥$ , $𝑏 = 𝑦 - 𝑥$ , and $𝑐 = 𝑧 - 𝑦$ . So each vector has exactly one representation, $ℬ︀$ is a basis, and

{[(𝑥, 𝑦, 𝑧)]}_{ℬ︀} = (𝑥, 𝑦 - 𝑥, 𝑧 - 𝑦) .

By (1.6.1), the vector with coordinates $(1, 2, 3)$ is $1 (1, 1, 1) +$ $2 (0, 1, 1) +$ $3 (0, 0, 1) =$ $(1, 3, 6)$ .

(b) The combination with coefficients $𝛼, 𝛽, 𝛾, 𝛿$ represents

(\begin{matrix} 𝛼 + 𝛽 + 𝛾 + 𝛿 & 𝛽 + 𝛾 + 𝛿 \\ 𝛾 + 𝛿 & 𝛿 \end{matrix}) .

This equals $(\begin{matrix} 𝑝 & 𝑞 \\ 𝑟 & 𝑠 \end{matrix})$ if and only if $𝛿 = 𝑠$ , $𝛾 = 𝑟 - 𝑠$ , $𝛽 = 𝑞 - 𝑟$ , and $𝛼 = 𝑝 - 𝑞$ . So every $𝐴 \in 𝐹^{2 \times 2}$ has exactly one representation, $𝒞︀$ is a basis, and ${[𝐴]}_{𝒞︀} =$ $(𝑝 - 𝑞, 𝑞 - 𝑟, 𝑟 - 𝑠, 𝑠)$ .

Exercise 1.6.29.routine For which

𝑐 \in ℝ

1 +

𝑥^{2},

𝑥 +

𝑥^{2},

1 +

𝑥 +

𝑐 𝑥^{2}

a basis of

{ℝ [𝑥]}_{\leq 2}

? Work with coordinate vectors.

Solution.

Uses. Proposition 1.6.20 (Coordinates translate questions about $𝑉$ into $𝐹^{𝑛}$ ), Definition 1.6.1 (Basis)

Hint 1. By Proposition 1.6.20, the list is a basis exactly when

(1, 0, 1),

(0, 1, 1),

(1, 1, 𝑐)

is a basis of

ℝ^{3}

Hint 2. Solve

𝑎 (1, 0, 1) +

𝑏 (0, 1, 1) +

𝑑 (1, 1, 𝑐) =

(𝑥, 𝑦, 𝑧)

. You will need to divide by

𝑐 - 2

Sketch. The coordinate vectors are

(1, 0, 1),

(0, 1, 1),

(1, 1, 𝑐)

. The equations

𝑎 + 𝑑 = 𝑥

𝑏 + 𝑑 = 𝑦

𝑎 + 𝑏 + 𝑐 𝑑 = 𝑧

give

(𝑐 - 2) 𝑑 = 𝑧 - 𝑥 - 𝑦

, which has a unique solution for every right side exactly when

𝑐 \neq 2

. For

𝑐 = 2

1 +

𝑥 +

2 𝑥^{2} =

(1 + 𝑥^{2}) +

(𝑥 + 𝑥^{2})

In the standard basis $1, 𝑥, 𝑥^{2}$ the coordinate vectors are $(1, 0, 1)$ , $(0, 1, 1)$ , and $(1, 1, 𝑐)$ . By Proposition 1.6.20(c), the polynomials form a basis of ${ℝ [𝑥]}_{\leq 2}$ if and only if these columns form a basis of $ℝ^{3}$ . The equation $𝑎 (1, 0, 1) +$ $𝑏 (0, 1, 1) +$ $𝑑 (1, 1, 𝑐) =$ $(𝑥, 𝑦, 𝑧)$ reads

𝑎 + 𝑑 = 𝑥, 𝑏 + 𝑑 = 𝑦, 𝑎 + 𝑏 + 𝑐 𝑑 = 𝑧 .

Any solution has $𝑎 = 𝑥 - 𝑑$ and $𝑏 = 𝑦 - 𝑑$ , and then the last equation becomes $(𝑐 - 2) 𝑑 = 𝑧 - 𝑥 - 𝑦$ .

If $𝑐 \neq 2$ , this forces $𝑑 =$ $(𝑧 - 𝑥 - 𝑦) / (𝑐 - 2)$ , and then $𝑎$ and $𝑏$ are determined; conversely, these values solve all three equations. So every column has exactly one representation, and the list is a basis.

If $𝑐 = 2$ , the columns satisfy $(1, 0, 1) +$ $(0, 1, 1) -$ $(1, 1, 2) =$ $𝟎$ , so they are dependent, and so are the polynomials: $1 +$ $𝑥 +$ $2 𝑥^{2} =$ $(1 + 𝑥^{2}) +$ $(𝑥 + 𝑥^{2})$ . So the list is a basis exactly when $𝑐 \neq 2$ .

Exercise 1.6.30.routine

(a)Find the error in the following argument.
Claim. Every spanning list of $𝑉$ contains a basis of $𝑉$ .
Proof. We induct on the length $𝑘$ of the spanning list $ℒ︀$ . If $𝑘 = 0$ , then $ℒ︀ = ()$ spans $𝑉$ , so $𝑉 = {𝟎}$ , and $()$ is a basis of $𝑉$ . Suppose the claim holds for spanning lists of length $𝑘$ , and let $ℒ︀ = 𝐯_{1}, \dots, 𝐯_{𝑘 + 1}$ span $𝑉$ . If $ℒ︀$ is independent, it is a basis. Otherwise, delete its last entry. The list $𝐯_{1}, \dots, 𝐯_{𝑘}$ has length $𝑘$ , so by the inductive hypothesis it contains a basis of $𝑉$ , which is also a sublist of $ℒ︀$ .
(b)Repair the argument.

Solution.

Uses. Lemma 1.5.10 (Linear dependence lemma), Example 1.5.11 (Which entries are redundant), Theorem 1.6.10 (Every spanning list contains a basis)

Techniques. Induction on the length of a list (Technique 1.6.9)

Hint 1. The inductive hypothesis is about spanning lists of length

𝑘

. Is

𝐯_{1}, \dots, 𝐯_{𝑘}

one?

Hint 2. Test the step on the dependent spanning list

(1, 0), (2, 0), (0, 1)

ℝ^{2}

Sketch. The inductive hypothesis applies only to lists that span

𝑉

, and deleting the last entry of a dependent spanning list can destroy spanning:

(1, 0), (2, 0), (0, 1)

spans

ℝ^{2}

, but

(1, 0), (2, 0)

does not. The repair deletes the entry

𝐯_{𝑗}

given by Lemma 1.5.10, which keeps the span equal to

𝑉

(a) The inductive hypothesis is a statement about lists of length $𝑘$ that span $𝑉$ . The argument applies it to $𝐯_{1}, \dots, 𝐯_{𝑘}$ without checking that this list spans $𝑉$ , and it need not. In $ℝ^{2}$ , the list $(1, 0), (2, 0), (0, 1)$ spans $ℝ^{2}$ and is dependent (Example 1.5.11), but deleting its last entry leaves $(1, 0), (2, 0)$ , whose span is the first axis. The claim itself is true (Theorem 1.6.10); only the choice of the deleted entry is wrong.

(b) Since $ℒ︀$ is dependent, Lemma 1.5.10 gives an index $𝑗$ such that deleting $𝐯_{𝑗}$ from $ℒ︀$ does not change the span. The resulting list has length $𝑘$ and spans $span (ℒ︀) = 𝑉$ , so the inductive hypothesis applies to it, and the rest of the argument goes through. (In the example, the lemma deletes $(2, 0)$ .)

Exercise 1.6.31.routine The list $ℒ︀ =$ $(1, 0),$ $(0, 1),$ $(1, 1)$ spans $ℝ^{2}$ . A student defines ${[𝐯]}_{ℒ︀} \in ℝ^{3}$ to be “the coefficients of a linear combination of $ℒ︀$ that represents $𝐯$ ”, and concludes that $𝐯 \mapsto {[𝐯]}_{ℒ︀}$ is a function $ℝ^{2} \to ℝ^{3}$ satisfying ${[𝐱 + 𝐲]}_{ℒ︀} =$ ${[𝐱]}_{ℒ︀} +$ ${[𝐲]}_{ℒ︀}$ , by the proof of Proposition 1.6.19.

(a)What is wrong with the definition, and which step of the proof of Proposition 1.6.19(a) fails for $ℒ︀$ ?
(b)Let $𝑐 : ℝ^{2} \to ℝ^{3}$ be any function such that $𝑐 (𝐯)$ is the list of coefficients of some linear combination of $ℒ︀$ representing $𝐯$ , for every $𝐯$ . Show that $𝑐$ is injective but not surjective.

Solution.

Uses. Definition 1.6.14 (Coordinates), (1.6.1), Non-example 1.6.4 (One property without the other)

Hint 1. How many linear combinations of

ℒ︀

represent

𝟎

? What does “the coefficients” refer to?

Hint 2. For (b), consider

Φ (𝑎, 𝑏, 𝑑) =

𝑎 (1, 0) +

𝑏 (0, 1) +

𝑑 (1, 1)

. Then

Φ (𝑐 (𝐯)) = 𝐯

. Which two elements of

ℝ^{3}

does

Φ

send to

𝟎

Sketch. (a)

ℒ︀

is dependent, so a vector has many representations, and “the” coefficients do not name one column; the proof’s step “so the coordinates of

𝐱 + 𝐲

are

𝑎_{𝑖} + 𝑏_{𝑖}

” needs the backward direction of (1.6.1), which uses uniqueness. (b)

Φ \circ 𝑐

is the identity, so

𝑐

is injective. Both

(0, 0, 0)

and

(1, 1, - 1)

represent

𝟎

, but

𝑐 (𝟎)

is only one of them, and the other is

𝑐 (𝐯)

for no

𝐯

(a) The list $ℒ︀$ is dependent (Non-example 1.6.4), so a vector of $ℝ^{2}$ is represented by many linear combinations of $ℒ︀$ ; for instance $(1, 1)$ has coefficients $(1, 1, 0)$ and $(0, 0, 1)$ . So “the coefficients” does not specify a column, and the student has not defined a function. In the proof of Proposition 1.6.19(a), the step that fails is the last one: from “ $𝐱 +$ $𝐲 =$ $\sum (𝑎_{𝑖} + 𝑏_{𝑖}) 𝐯_{𝑖}$ ” it concludes that $(𝑎_{𝑖} + 𝑏_{𝑖})$ is the coordinate vector of $𝐱 + 𝐲$ . That is the backward direction of (1.6.1), which holds because a basis allows only one representation. For $ℒ︀$ the column $(𝑎_{𝑖} + 𝑏_{𝑖})$ is one representation among many, and it need not be the one the student’s rule picks for $𝐱 + 𝐲$ .

(b) Let $Φ : ℝ^{3} \to ℝ^{2}$ , $Φ (𝑎, 𝑏, 𝑑) =$ $𝑎 (1, 0) +$ $𝑏 (0, 1) +$ $𝑑 (1, 1)$ . The hypothesis on $𝑐$ says $Φ (𝑐 (𝐯)) = 𝐯$ for every $𝐯 \in ℝ^{2}$ . If $𝑐 (𝐯) = 𝑐 (𝐯^{'})$ , then $𝐯 =$ $Φ (𝑐 (𝐯)) =$ $Φ (𝑐 (𝐯^{'})) =$ $𝐯^{'}$ , so $𝑐$ is injective.

Now $Φ (0, 0, 0) = 𝟎$ and $Φ (1, 1, - 1) =$ $(1, 0) +$ $(0, 1) -$ $(1, 1) =$ $𝟎$ . Let $𝐚$ be whichever of these two columns differs from $𝑐 (𝟎)$ . If $𝐚 = 𝑐 (𝐯)$ for some $𝐯$ , then $𝐯 =$ $Φ (𝑐 (𝐯)) =$ $Φ (𝐚) =$ $𝟎$ , so $𝐚 = 𝑐 (𝟎)$ , contradicting the choice of $𝐚$ . So $𝐚$ is not a value of $𝑐$ , and $𝑐$ is not surjective. By contrast, the coordinate map of a basis is a bijection (Proposition 1.6.16).

Exercise 1.6.32.standard Let $𝑛 \geq 1$ , and let $𝑆 \subseteq 𝐹^{𝑛 \times 𝑛}$ be the subspace of symmetric matrices, those with $𝑎_{𝑗 𝑖} = 𝑎_{𝑖 𝑗}$ for all $𝑖, 𝑗$ (Example 1.4.11). Let $𝐾$ be the set of $𝐴 \in 𝐹^{𝑛 \times 𝑛}$ with $𝑎_{𝑗 𝑖} = - 𝑎_{𝑖 𝑗}$ for all $𝑖, 𝑗$ .

(a)Find a basis of $𝑆$ of length $𝑛 (𝑛 + 1) / 2$ .
(b)Suppose that $1 + 1 \neq 0$ in $𝐹$ . Find a basis of $𝐾$ of length $𝑛 (𝑛 - 1) / 2$ .
(c)What are $𝐾$ and a basis of $𝐾$ when $𝐹 = 𝔽_{2}$ ?

Solution.

Uses. Definition 1.6.1 (Basis), Definition 1.6.8 (Standard bases), Proposition 1.1.17 (No zero divisors), Theorem 1.4.3 (Subspace criterion)

Hint 1. A symmetric matrix is determined by its entries on and above the diagonal. For each position

(𝑖, 𝑗)

with

𝑖 < 𝑗

, use

𝑈_{𝑖 𝑗} + 𝑈_{𝑗 𝑖}

Hint 2. For (b), what does

𝑎_{𝑖 𝑖} = - 𝑎_{𝑖 𝑖}

say when

1 + 1 \neq 0

? For (c), what is

- 1

𝔽_{2}

Sketch. (a)

𝑈_{𝑖 𝑖}

(

1 \leq 𝑖 \leq 𝑛

) and

𝑈_{𝑖 𝑗} + 𝑈_{𝑗 𝑖}

(

𝑖 < 𝑗

): a combination with coefficients

𝑐

has entries

𝑐_{𝑖 𝑖}

on the diagonal and

𝑐_{𝑖 𝑗}

in both positions

(𝑖, 𝑗)

and

(𝑗, 𝑖)

, so each symmetric

𝐴

is represented exactly by

𝑐 =

its entries on and above the diagonal. Count

𝑛 + 𝑛 (𝑛 - 1) / 2

. (b)

(1 + 1) 𝑎_{𝑖 𝑖} = 0

forces a zero diagonal; use

𝑈_{𝑖 𝑗} - 𝑈_{𝑗 𝑖}

𝑖 < 𝑗

. (c) In

𝔽_{2}

- 𝑎 = 𝑎

, so

𝐾 = 𝑆

, with the basis from (a).

(a) Consider the list consisting of the $𝑈_{𝑖 𝑖}$ for $1 \leq 𝑖 \leq 𝑛$ and the $𝑈_{𝑖 𝑗} + 𝑈_{𝑗 𝑖}$ for $1 \leq 𝑖 < 𝑗 \leq 𝑛$ , in any fixed order. Each entry is symmetric. A linear combination with coefficient $𝑐_{𝑖 𝑖}$ on $𝑈_{𝑖 𝑖}$ and $𝑐_{𝑖 𝑗}$ on $𝑈_{𝑖 𝑗} + 𝑈_{𝑗 𝑖}$ is the matrix with diagonal entries $𝑐_{𝑖 𝑖}$ and with $𝑐_{𝑖 𝑗}$ in both positions $(𝑖, 𝑗)$ and $(𝑗, 𝑖)$ for $𝑖 < 𝑗$ . So it equals a given $𝐴 \in 𝑆$ if and only if $𝑐_{𝑖 𝑗} = 𝑎_{𝑖 𝑗}$ for all $𝑖 \leq 𝑗$ ; these values work because $𝑎_{𝑗 𝑖} = 𝑎_{𝑖 𝑗}$ . Every $𝐴 \in 𝑆$ is represented by exactly one combination, and the list is a basis of $𝑆$ (Definition 1.6.1). Its length is $𝑛 +$ $𝑛 (𝑛 - 1) / 2 =$ $𝑛 (𝑛 + 1) / 2$ .

(b) The set $𝐾$ is a subspace by Theorem 1.4.3: the zero matrix satisfies $0 = - 0$ , and the conditions $𝑎_{𝑗 𝑖} = - 𝑎_{𝑖 𝑗}$ are preserved by entrywise sums and scalar multiples. For $𝐴 \in 𝐾$ , the condition with $𝑗 = 𝑖$ gives $𝑎_{𝑖 𝑖} = - 𝑎_{𝑖 𝑖}$ , that is, $(1 + 1) 𝑎_{𝑖 𝑖} = 0$ , so $𝑎_{𝑖 𝑖} = 0$ by Proposition 1.1.17. Consider the matrices $𝑈_{𝑖 𝑗} - 𝑈_{𝑗 𝑖}$ for $𝑖 < 𝑗$ , which lie in $𝐾$ . A combination with coefficients $𝑐_{𝑖 𝑗}$ has zero diagonal, $𝑐_{𝑖 𝑗}$ in position $(𝑖, 𝑗)$ , and $- 𝑐_{𝑖 𝑗}$ in position $(𝑗, 𝑖)$ , for $𝑖 < 𝑗$ . It equals $𝐴 \in 𝐾$ if and only if $𝑐_{𝑖 𝑗} = 𝑎_{𝑖 𝑗}$ for all $𝑖 < 𝑗$ : the diagonal entries of $𝐴$ are $0$ , and $𝑎_{𝑗 𝑖} = - 𝑎_{𝑖 𝑗}$ . So this list of length $𝑛 (𝑛 - 1) / 2$ is a basis of $𝐾$ .

(c) In $𝔽_{2}$ , $- 𝑎 = 𝑎$ for every $𝑎$ , so the condition $𝑎_{𝑗 𝑖} = - 𝑎_{𝑖 𝑗}$ is the condition $𝑎_{𝑗 𝑖} = 𝑎_{𝑖 𝑗}$ , and $𝐾 = 𝑆$ . A basis is the one from (a), of length $𝑛 (𝑛 + 1) / 2$ . The argument of (b) breaks down because $(1 + 1) 𝑎_{𝑖 𝑖} = 0$ holds for every $𝑎_{𝑖 𝑖}$ ; for instance $𝑈_{11} \in 𝐾$ .

Exercise 1.6.33.standard Let $𝑍 \subseteq 𝐹^{3 \times 3}$ be the set of matrices in which every row and every column sums to $0$ . For $𝑘, 𝑙 \in {1, 2}$ , let

𝑍_{𝑘 𝑙} = 𝑈_{𝑘 𝑙} - 𝑈_{𝑘 3} - 𝑈_{3 𝑙} + 𝑈_{33} .

Show that $𝒵︀ =$ $𝑍_{11},$ $𝑍_{12},$ $𝑍_{21},$ $𝑍_{22}$ is a basis of $𝑍$ , and that for $𝐴 \in 𝑍$ ,

{[𝐴]}_{𝒵︀} = (𝑎_{11}, 𝑎_{12}, 𝑎_{21}, 𝑎_{22}) .

Solution.

Uses. Definition 1.6.1 (Basis), (1.6.1), Definition 1.6.8 (Standard bases), Theorem 1.4.3 (Subspace criterion)

Hint 1. A matrix in

𝑍

is determined by its top-left

2 \times 2

block. Express the entries in row

3

and column

3

in terms of that block.

Hint 2. Compute every entry of

\sum_{𝑘, 𝑙 \leq 2} 𝑐_{𝑘 𝑙} 𝑍_{𝑘 𝑙}

. Its top-left block is

(𝑐_{𝑘 𝑙})

Sketch. Each

𝑍_{𝑘 𝑙}

lies in

𝑍

. The combination

\sum 𝑐_{𝑘 𝑙} 𝑍_{𝑘 𝑙}

has top-left block

(𝑐_{𝑘 𝑙})

, so at most one combination represents a given

𝐴

, with

𝑐_{𝑘 𝑙} = 𝑎_{𝑘 𝑙}

. That one works: its entries in column

3

, row

3

, and the corner are

- (𝑐_{𝑘 1} + 𝑐_{𝑘 2})

- (𝑐_{1 𝑙} + 𝑐_{2 𝑙})

, and

\sum 𝑐_{𝑘 𝑙}

, and for

𝐴 \in 𝑍

the zero row and column sums give exactly these values.

First, $𝑍$ is a subspace of $𝐹^{3 \times 3}$ : the zero matrix lies in it, and if every row and column of $𝐴$ and of $𝐵$ sums to $0$ , the same holds for $𝐴 + 𝐵$ and $𝑐 𝐴$ , since sums of entries respect the entrywise operations (Theorem 1.4.3). Each $𝑍_{𝑘 𝑙}$ lies in $𝑍$ : its nonzero entries are $1$ in positions $(𝑘, 𝑙)$ and $(3, 3)$ and $- 1$ in positions $(𝑘, 3)$ and $(3, 𝑙)$ , so every row and every column contains either no nonzero entry or one $1$ and one $- 1$ .

Let $𝑀 =$ $\sum_{𝑘, 𝑙 \in {1, 2}} 𝑐_{𝑘 𝑙} 𝑍_{𝑘 𝑙}$ . Its entry in position $(𝑘, 𝑙)$ with $𝑘, 𝑙 \leq 2$ is $𝑐_{𝑘 𝑙}$ , its entry $(𝑘, 3)$ is $- (𝑐_{𝑘 1} + 𝑐_{𝑘 2})$ , its entry $(3, 𝑙)$ is $- (𝑐_{1 𝑙} + 𝑐_{2 𝑙})$ , and its entry $(3, 3)$ is $𝑐_{11} +$ $𝑐_{12} +$ $𝑐_{21} +$ $𝑐_{22}$ .

Now let $𝐴 \in 𝑍$ . If $𝑀 = 𝐴$ , comparing the top-left blocks gives $𝑐_{𝑘 𝑙} = 𝑎_{𝑘 𝑙}$ , so at most one combination represents $𝐴$ . Conversely, take $𝑐_{𝑘 𝑙} = 𝑎_{𝑘 𝑙}$ . Since rows $1$ and $2$ of $𝐴$ sum to $0$ , $𝑎_{𝑘 3} =$ $- (𝑎_{𝑘 1} + 𝑎_{𝑘 2})$ , which is the $(𝑘, 3)$ entry of $𝑀$ . Since columns $1$ and $2$ sum to $0$ , $𝑎_{3 𝑙} =$ $- (𝑎_{1 𝑙} + 𝑎_{2 𝑙})$ , the $(3, 𝑙)$ entry of $𝑀$ . Since row $3$ sums to $0$ ,

𝑎_{33} = - (𝑎_{31} + 𝑎_{32}) = (𝑎_{11} + 𝑎_{21}) + (𝑎_{12} + 𝑎_{22}),

the $(3, 3)$ entry of $𝑀$ . So $𝑀 = 𝐴$ . Every $𝐴 \in 𝑍$ is represented by exactly one linear combination, the list is a basis of $𝑍$ (Definition 1.6.1), and by (1.6.1) the coordinates of $𝐴$ are $(𝑎_{11}, 𝑎_{12}, 𝑎_{21}, 𝑎_{22})$ .

Exercise 1.6.34.standard Let $𝑛 \geq 1$ , and let $𝑝_{0},$ $\dots,$ $𝑝_{𝑛} \in$ ${𝐹 [𝑥]}_{\leq 𝑛}$ .

(a)Show that if $deg 𝑝_{𝑘} = 𝑘$ for each $𝑘$ , then $𝑝_{0}, \dots, 𝑝_{𝑛}$ is a basis of ${𝐹 [𝑥]}_{\leq 𝑛}$ .
(b)Show that if no $𝑝_{𝑘}$ has degree $𝑛$ , then $𝑝_{0}, \dots, 𝑝_{𝑛}$ is not a basis of ${𝐹 [𝑥]}_{\leq 𝑛}$ .
(c)Find a basis of ${𝐹 [𝑥]}_{\leq 𝑛}$ all of whose entries have degree $𝑛$ .

Solution.

Uses. Exercise 1.3.33, Proposition 1.5.24 (Distinct degrees), Example 1.4.9 (Polynomials), Proposition 1.4.14 (The span is the smallest subspace containing a list), Proposition 1.3.18 (Comparing spans), Example 1.3.11 (Small spans)

Hint 1. For (a), see Exercise 1.3.33 and Proposition 1.5.24. For (b), which subspace contains every

𝑝_{𝑘}

Hint 2. For (c), start with

𝑥^{𝑛}

and add

𝑥^{𝑛}

to each lower power of

𝑥

Sketch. (a) Spanning by Exercise 1.3.33, independence by Proposition 1.5.24. (b) All

𝑝_{𝑘}

lie in the subspace

{𝐹 [𝑥]}_{\leq 𝑛 - 1}

, so their span does too, and

𝑥^{𝑛}

is missing. (c)

𝑥^{𝑛},

𝑥^{𝑛} +

1,

𝑥^{𝑛} +

𝑥,

\dots,

𝑥^{𝑛} +

𝑥^{𝑛 - 1}

: each

𝑥^{𝑘} =

(𝑥^{𝑛} + 𝑥^{𝑘}) -

𝑥^{𝑛}

is in the span, and in a relation the coefficient of

𝑥^{𝑘}

for

𝑘 < 𝑛

is the coefficient of

𝑥^{𝑛} + 𝑥^{𝑘}

(a) The list spans ${𝐹 [𝑥]}_{\leq 𝑛}$ by Exercise 1.3.33(a). Its entries are nonzero (they have degrees $𝑘 \geq 0$ ) and have distinct degrees, so it is independent by Proposition 1.5.24. So it is a basis.

(b) Each $𝑝_{𝑘}$ has degree at most $𝑛$ and not equal to $𝑛$ , so $𝑝_{𝑘} \in {𝐹 [𝑥]}_{\leq 𝑛 - 1}$ , a subspace (Example 1.4.9). By Proposition 1.4.14(b), $span (𝑝_{0}, \dots, 𝑝_{𝑛}) \subseteq$ ${𝐹 [𝑥]}_{\leq 𝑛 - 1}$ , which does not contain $𝑥^{𝑛}$ . So the list does not span ${𝐹 [𝑥]}_{\leq 𝑛}$ .

(c) Let $𝑞_{𝑛} = 𝑥^{𝑛}$ and $𝑞_{𝑘} = 𝑥^{𝑛} + 𝑥^{𝑘}$ for $0 \leq 𝑘 < 𝑛$ , and consider $𝑞_{𝑛},$ $𝑞_{0},$ $𝑞_{1},$ $\dots,$ $𝑞_{𝑛 - 1}$ . Each entry has degree $𝑛$ , since $𝑘 < 𝑛$ .

Spanning. $𝑥^{𝑛} = 𝑞_{𝑛}$ and $𝑥^{𝑘} = 𝑞_{𝑘} - 𝑞_{𝑛}$ for $𝑘 < 𝑛$ , so $1, 𝑥, \dots, 𝑥^{𝑛}$ lie in the span, and the span is ${𝐹 [𝑥]}_{\leq 𝑛}$ by Proposition 1.3.18 and Example 1.3.11.

Independence. Suppose that $𝑐 𝑞_{𝑛} +$ $\sum_{𝑘 = 0}^{𝑛 - 1} 𝑐_{𝑘} 𝑞_{𝑘} =$ $𝟎$ . The left side is

(𝑐 + 𝑐_{0} + \dots + 𝑐_{𝑛 - 1}) 𝑥^{𝑛} + 𝑐_{0} + 𝑐_{1} 𝑥 + \dots + 𝑐_{𝑛 - 1} 𝑥^{𝑛 - 1} .

Its coefficient of $𝑥^{𝑘}$ for $𝑘 < 𝑛$ is $𝑐_{𝑘}$ , so every $𝑐_{𝑘} = 0$ , and then its coefficient of $𝑥^{𝑛}$ is $𝑐 = 0$ . So the list is a basis. Degrees alone therefore do not decide whether a list is a basis: (a) is a sufficient condition, not a necessary one.

Exercise 1.6.35.standard Prove or disprove each statement.

(a)If $ℬ︀$ is a basis of $𝑉$ and $𝑈$ is a subspace of $𝑉$ , then some sublist of $ℬ︀$ is a basis of $𝑈$ .
(b)If $ℬ︀$ and $𝒞︀$ are bases of $𝑉$ and $𝑉 \neq {𝟎}$ , then the concatenation $ℬ︀, 𝒞︀$ is not a basis of $𝑉$ .
(c)If $𝐯_{1}, \dots, 𝐯_{𝑛}$ is a basis of $𝑉$ and $𝑐_{1}, \dots, 𝑐_{𝑛} \in 𝐹$ are nonzero, then $𝑐_{1} 𝐯_{1}, \dots, 𝑐_{𝑛} 𝐯_{𝑛}$ is a basis of $𝑉$ .
(d)If $ℒ︀$ is a list in $𝑉$ such that every vector of $𝑉$ is represented by at most one linear combination of $ℒ︀$ , then $ℒ︀$ is a basis of $𝑉$ .
(e)If $ℒ︀$ spans $𝑉$ , then exactly one sublist of $ℒ︀$ is a basis of $𝑉$ .

Solution.

Uses. Proposition 1.6.2 (Bases are independent spanning lists), Corollary 1.5.13 (Independence, one entry at a time), Proposition 1.5.18 (Operations that preserve independence), Definition 1.5.1 (Linear independence), Example 1.6.11 (Sifting a list of polynomials)

Techniques. Finding counterexamples and minimal examples (Technique 1.4.18)

Hint 1. Test (a) with the standard basis of

ℝ^{2}

and a line that is not an axis. For (b), the first entry of

𝒞︀

comes after all of

ℬ︀

Hint 2. For (d), what does “at most one” say about vectors outside the span? For (e), look at Example 1.6.11.

Sketch. (a) False:

𝑈 = span ((1, 1))

ℝ^{2}

contains no sublist of

𝐞_{1}, 𝐞_{2}

that spans it. (b) True:

𝒞︀ \neq ()

and its first entry lies in

span (ℬ︀) = 𝑉

, so Corollary 1.5.13 makes

ℬ︀, 𝒞︀

dependent. (c) True: scaling by nonzero scalars preserves span and independence (Proposition 1.5.18(b)). (d) False: “at most one” is independence;

𝐞_{1}

ℝ^{2}

. (e) False:

(1, 0), (0, 1), (1, 1)

contains three bases of

ℝ^{2}

(a) False. In $ℝ^{2}$ , let $ℬ︀ = 𝐞_{1}, 𝐞_{2}$ and $𝑈 = span ((1, 1))$ . The sublists of $ℬ︀$ are $()$ , $𝐞_{1}$ , $𝐞_{2}$ , and $ℬ︀$ . The last three contain $𝐞_{1}$ or $𝐞_{2}$ , which are not in $𝑈$ (they are not multiples of $(1, 1)$ ), so they are not lists in $𝑈$ at all; and $()$ spans ${𝟎} \neq 𝑈$ .

(b) True. Since $𝑉 \neq {𝟎}$ , neither $ℬ︀$ nor $𝒞︀$ is the empty list (it spans only ${𝟎}$ ). Let $𝐰$ be the first entry of $𝒞︀$ . In $ℬ︀, 𝒞︀$ the entries before $𝐰$ are those of $ℬ︀$ , and $𝐰 \in 𝑉 = span (ℬ︀)$ . So $ℬ︀, 𝒞︀$ is dependent by Corollary 1.5.13, and it is not a basis.

(c) True. Replacing $𝐯_{𝑗}$ by $𝑐_{𝑗} 𝐯_{𝑗}$ with $𝑐_{𝑗} \neq 0$ preserves both the span and independence (Proposition 1.5.18(b)). Doing this for $𝑗 = 1, \dots, 𝑛$ in turn produces a list that spans $𝑉$ and is independent, which is a basis by Proposition 1.6.2.

(d) False. Every vector outside $span (ℒ︀)$ is represented by no combination, so the hypothesis says exactly that every vector of $span (ℒ︀)$ is represented by at most one combination, which is independence (Definition 1.5.1). Independent lists need not span: in $ℝ^{2}$ , the list $𝐞_{1}$ satisfies the hypothesis and is not a basis.

(e) False. In $ℝ^{2}$ , the spanning list $(1, 0), (0, 1), (1, 1)$ has the three sublists $(1, 0), (0, 1)$ and $(1, 0), (1, 1)$ and $(0, 1), (1, 1)$ , each of which is a basis (check spanning and independence as in Example 1.6.3(a)). See also Example 1.6.11.

Exercise 1.6.36.standard Let $ℬ︀ = 𝐯_{1}, \dots, 𝐯_{𝑛}$ be a basis of $𝑉$ , let $𝐰 \in 𝑉$ with ${[𝐰]}_{ℬ︀} =$ $(𝑎_{1}, \dots, 𝑎_{𝑛})$ , and fix $𝑗$ . Let ${ℬ︀}^{'}$ be the list obtained from $ℬ︀$ by replacing $𝐯_{𝑗}$ with $𝐰$ .

(a)Show that ${ℬ︀}^{'}$ is a basis of $𝑉$ if and only if $𝑎_{𝑗} \neq 0$ .
(b)Deduce that if $𝐰 \neq 𝟎$ , then $𝐰$ can replace some entry of $ℬ︀$ so that the result is still a basis.

Solution.

Uses. Proposition 1.6.2 (Bases are independent spanning lists), Corollary 1.3.19 (Equal spans), Theorem 1.5.5 (Independence is decided at zero), Proposition 1.6.16 (The coordinate map is a bijection), Exercise 1.3.34

Hint 1. If

𝑎_{𝑗} = 0

, then

𝐰

is a combination of the other entries of

{ℬ︀}^{'}

. If

𝑎_{𝑗} \neq 0

, solve

𝐰 = \sum 𝑎_{𝑖} 𝐯_{𝑖}

for

𝐯_{𝑗}

Hint 2. For independence when

𝑎_{𝑗} \neq 0

, substitute

𝐰 = \sum_{𝑖} 𝑎_{𝑖} 𝐯_{𝑖}

into a relation of

{ℬ︀}^{'}

and use the independence of

ℬ︀

Hint 3. For (b), which column is

{[𝟎]}_{ℬ︀}

Sketch. If

𝑎_{𝑗} = 0

, then

𝐰 = \sum_{𝑖 \neq 𝑗} 𝑎_{𝑖} 𝐯_{𝑖}

, which gives a relation of

{ℬ︀}^{'}

with coefficient

- 1

𝐰

. If

𝑎_{𝑗} \neq 0

, then

𝐯_{𝑗} =

𝑎_{𝑗}^{- 1} (𝐰 - \sum_{𝑖 \neq 𝑗} 𝑎_{𝑖} 𝐯_{𝑖})

, so

{ℬ︀}^{'}

spans

𝑉

; and a relation

\sum_{𝑖 \neq 𝑗} 𝑐_{𝑖} 𝐯_{𝑖} +

𝑐 𝐰 =

𝟎

becomes

\sum_{𝑖 \neq 𝑗} (𝑐_{𝑖} + 𝑐 𝑎_{𝑖}) 𝐯_{𝑖} +

𝑐 𝑎_{𝑗} 𝐯_{𝑗} =

𝟎

, so

𝑐 𝑎_{𝑗} = 0

𝑐 = 0

, and then all

𝑐_{𝑖} = 0

. (b)

{[𝐰]}_{ℬ︀} \neq 𝟎

since the coordinate map is injective, so some

𝑎_{𝑗} \neq 0

(a) Write $𝐰 =$ $𝑎_{1} 𝐯_{1} +$ $\dots +$ $𝑎_{𝑛} 𝐯_{𝑛}$ .

Suppose $𝑎_{𝑗} = 0$ . Then $𝐰 = \sum_{𝑖 \neq 𝑗} 𝑎_{𝑖} 𝐯_{𝑖}$ , and the combination of ${ℬ︀}^{'}$ with coefficients $𝑎_{𝑖}$ on $𝐯_{𝑖}$ ( $𝑖 \neq 𝑗$ ) and $- 1$ on $𝐰$ represents $𝟎$ . It is nontrivial, so ${ℬ︀}^{'}$ is dependent and not a basis.

Suppose $𝑎_{𝑗} \neq 0$ . Spanning. Solving for $𝐯_{𝑗}$ ,

𝐯_{𝑗} = 𝑎_{𝑗}^{- 1} 𝐰 + \sum_{𝑖 \neq 𝑗} (- 𝑎_{𝑗}^{- 1} 𝑎_{𝑖}) 𝐯_{𝑖} \in span ({ℬ︀}^{'}) .

The other entries of $ℬ︀$ are entries of ${ℬ︀}^{'}$ , so $ℬ︀ \subseteq span ({ℬ︀}^{'})$ , and also ${ℬ︀}^{'} \subseteq 𝑉 = span (ℬ︀)$ . By Corollary 1.3.19, $span ({ℬ︀}^{'}) =$ $span (ℬ︀) =$ $𝑉$ . (This is also Exercise 1.3.34, after moving $𝐯_{𝑗}$ to the end; its hypothesis that $𝐰$ is not in the span of the other entries holds because $𝑎_{𝑗} \neq 0$ and coordinates are unique.) Independence. Suppose $\sum_{𝑖 \neq 𝑗} 𝑐_{𝑖} 𝐯_{𝑖} +$ $𝑐 𝐰 =$ $𝟎$ . Substituting for $𝐰$ and collecting terms,

\sum_{𝑖 \neq 𝑗} (𝑐_{𝑖} + 𝑐 𝑎_{𝑖}) 𝐯_{𝑖} + 𝑐 𝑎_{𝑗} 𝐯_{𝑗} = 𝟎 .

Since $ℬ︀$ is independent, $𝑐 𝑎_{𝑗} = 0$ , so $𝑐 = 0$ because $𝑎_{𝑗} \neq 0$ , and then $𝑐_{𝑖} =$ $𝑐_{𝑖} +$ $𝑐 𝑎_{𝑖} =$ $0$ for all $𝑖 \neq 𝑗$ . So ${ℬ︀}^{'}$ is independent, and it is a basis by Proposition 1.6.2.

(b) Since ${[𝟎]}_{ℬ︀} = 𝟎$ and the coordinate map is injective (Proposition 1.6.16), $𝐰 \neq 𝟎$ implies ${[𝐰]}_{ℬ︀} \neq 𝟎$ , so $𝑎_{𝑗} \neq 0$ for some $𝑗$ . By (a), replacing $𝐯_{𝑗}$ with $𝐰$ gives a basis. Repeating such replacements is the idea behind the exchange lemma of Section 4.1 (Lemma 4.1.2).

Exercise 1.6.37.standard Let $𝑓 : 𝑉 \to 𝐹^{𝑛}$ be a bijection that respects linear combinations:

𝑓 (𝑐_{1} 𝐱_{1} + \dots + 𝑐_{𝑘} 𝐱_{𝑘}) = 𝑐_{1} 𝑓 (𝐱_{1}) + \dots + 𝑐_{𝑘} 𝑓 (𝐱_{𝑘})

for all $𝑘 \geq 0$ , all $𝐱_{𝑖} \in 𝑉$ , and all $𝑐_{𝑖} \in 𝐹$ . Show that there is exactly one basis $𝒞︀$ of $𝑉$ such that $𝑓 (𝐯) = {[𝐯]}_{𝒞︀}$ for every $𝐯 \in 𝑉$ . In other words, the coordinate maps of bases are exactly the bijections $𝑉 \to 𝐹^{𝑛}$ that respect linear combinations.

Solution.

Uses. Definition 1.6.1 (Basis), (1.6.1), Proposition 1.6.19 (Coordinates respect linear combinations), Proposition 1.6.16 (The coordinate map is a bijection)

Hint 1. If

𝑓 = {[\cdot]}_{𝒞︀}

with

𝒞︀ = 𝐜_{1}, \dots, 𝐜_{𝑛}

, then

𝑓 (𝐜_{𝑗}) = 𝐞_{𝑗}

. So there is only one candidate for

𝒞︀

Hint 2. Let

𝐜_{𝑗} = 𝑓^{- 1} (𝐞_{𝑗})

. To show

𝒞︀

is a basis, write

𝑓 (𝐯) =

(𝑎_{1}, \dots, 𝑎_{𝑛}) =

\sum 𝑎_{𝑖} 𝐞_{𝑖}

and apply

𝑓^{- 1}

, using that

𝑓

respects linear combinations.

Sketch. Uniqueness:

{[𝐜_{𝑗}]}_{𝒞︀} = 𝐞_{𝑗}

forces

𝐜_{𝑗} = 𝑓^{- 1} (𝐞_{𝑗})

. Existence: with this

𝒞︀

𝑓 (\sum 𝑏_{𝑖} 𝐜_{𝑖}) =

\sum 𝑏_{𝑖} 𝐞_{𝑖} =

(𝑏_{1}, \dots, 𝑏_{𝑛})

. Since

𝑓

is injective,

\sum 𝑏_{𝑖} 𝐜_{𝑖} = 𝐯

holds exactly when

(𝑏_{1}, \dots, 𝑏_{𝑛}) =

𝑓 (𝐯)

; so each

𝐯

has exactly one representation, with coefficients

𝑓 (𝐯)

Uniqueness. Suppose $𝒞︀ = 𝐜_{1}, \dots, 𝐜_{𝑛}$ is a basis with $𝑓 (𝐯) = {[𝐯]}_{𝒞︀}$ for all $𝐯$ . Then $𝑓 (𝐜_{𝑗}) =$ ${[𝐜_{𝑗}]}_{𝒞︀} =$ $𝐞_{𝑗}$ , so $𝐜_{𝑗} = 𝑓^{- 1} (𝐞_{𝑗})$ for each $𝑗$ . So $𝒞︀$ is determined by $𝑓$ .

Existence. Let $𝐜_{𝑗} = 𝑓^{- 1} (𝐞_{𝑗})$ and $𝒞︀ = 𝐜_{1}, \dots, 𝐜_{𝑛}$ . For all $𝑏_{1}, \dots, 𝑏_{𝑛} \in 𝐹$ , since $𝑓$ respects linear combinations,

𝑓 (𝑏_{1} 𝐜_{1} + \dots + 𝑏_{𝑛} 𝐜_{𝑛}) = 𝑏_{1} 𝐞_{1} + \dots + 𝑏_{𝑛} 𝐞_{𝑛} = (𝑏_{1}, \dots, 𝑏_{𝑛}) .

Let $𝐯 \in 𝑉$ . Since $𝑓$ is injective, $\sum_{𝑖} 𝑏_{𝑖} 𝐜_{𝑖} = 𝐯$ holds if and only if $𝑓 (\sum_{𝑖} 𝑏_{𝑖} 𝐜_{𝑖}) =$ $𝑓 (𝐯)$ , that is, if and only if $(𝑏_{1}, \dots, 𝑏_{𝑛}) =$ $𝑓 (𝐯)$ . So exactly one linear combination of $𝒞︀$ represents $𝐯$ , namely the one with coefficients $𝑓 (𝐯)$ . Hence $𝒞︀$ is a basis (Definition 1.6.1) and ${[𝐯]}_{𝒞︀} = 𝑓 (𝐯)$ (Definition 1.6.14).

Conversely, every coordinate map is a bijection that respects linear combinations, by Proposition 1.6.16 and Proposition 1.6.19(c). In the language of Section 4.5, the coordinate maps $𝑉 \to 𝐹^{𝑛}$ are the isomorphisms $𝑉 \to 𝐹^{𝑛}$ .

Exercise 1.6.38.standard Let $𝐹$ be a finite field with $𝑞$ elements, and let $𝑛 \geq 1$ .

(a)Show that a list in $𝐹^{𝑛}$ is a basis of $𝐹^{𝑛}$ if and only if it is linearly independent and has length $𝑛$ .
(b)How many bases does $𝐹^{𝑛}$ have? List all bases of $𝔽_{2}^{2}$ .

Solution.

Uses. Exercise 1.5.43, Proposition 1.6.2 (Bases are independent spanning lists), Proposition 1.6.7 (Standard bases)

Hint 1. By Exercise 1.5.43(a), an independent list of length

𝑘

spans a set of exactly

𝑞^{𝑘}

elements. How many elements does

𝐹^{𝑛}

have?

Hint 2. For (b), (a) turns the count of bases into the count of independent lists of length

𝑛

, which Exercise 1.5.43(b) computes.

Sketch. (a) If

ℒ︀

is independent of length

𝑘

, then

| span (ℒ︀) | = 𝑞^{𝑘}

, while

| 𝐹^{𝑛} | = 𝑞^{𝑛}

. So an independent list spans

𝐹^{𝑛}

exactly when

𝑞^{𝑘} = 𝑞^{𝑛}

, that is,

𝑘 = 𝑛

. (b)

(𝑞^{𝑛} - 1) (𝑞^{𝑛} - 𝑞) \dots (𝑞^{𝑛} - 𝑞^{𝑛 - 1})

. For

𝔽_{2}^{2}

this is

3 \cdot 2 = 6

: the ordered pairs of distinct vectors among

(1, 0), (0, 1), (1, 1)

(a) $𝐹^{𝑛}$ has $𝑞^{𝑛}$ elements. Let $ℒ︀$ be an independent list of length $𝑘$ . By Exercise 1.5.43(a), $span (ℒ︀)$ has $𝑞^{𝑘}$ elements. Since $span (ℒ︀) \subseteq 𝐹^{𝑛}$ , it equals $𝐹^{𝑛}$ if and only if $𝑞^{𝑘} = 𝑞^{𝑛}$ , which holds if and only if $𝑘 = 𝑛$ , because $𝑞 \geq 2$ . So an independent list spans $𝐹^{𝑛}$ exactly when its length is $𝑛$ . By Proposition 1.6.2, the bases of $𝐹^{𝑛}$ are the independent lists of length $𝑛$ .

(b) By (a) and Exercise 1.5.43(b), $𝐹^{𝑛}$ has exactly

(𝑞^{𝑛} - 1) (𝑞^{𝑛} - 𝑞) (𝑞^{𝑛} - 𝑞^{2}) \dots (𝑞^{𝑛} - 𝑞^{𝑛 - 1})

bases. For $𝑞 = 2$ and $𝑛 = 2$ this is $(4 - 1) (4 - 2) = 6$ . An independent list of length $2$ in $𝔽_{2}^{2}$ consists of a nonzero vector and a vector outside its span; the span of a nonzero $𝐯$ is ${𝟎, 𝐯}$ . So the bases are the ordered pairs of distinct vectors from $(1, 0), (0, 1), (1, 1)$ :

\begin{aligned} (1, 0), (0, 1) & (0, 1), (1, 0) & (1, 0), (1, 1) \\ (1, 1), (1, 0) & (0, 1), (1, 1) & (1, 1), (0, 1) . \end{aligned}

Part (a) shows that over a finite field every basis of $𝐹^{𝑛}$ has length $𝑛$ . Section 4.1 proves this over every field (Theorem 4.1.1), where counting elements is not available.

Exercise 1.6.39.hard Let $𝑋 = {0, 1, 2, \dots}$ , so that $ℝ^{𝑋}$ is the space of real sequences $𝐬 =$ $(𝑠_{0}, 𝑠_{1}, 𝑠_{2}, \dots)$ , and let

𝑉 = {𝐬 \in ℝ^{𝑋} | 𝑠_{𝑘 + 2} = 𝑠_{𝑘 + 1} + 𝑠_{𝑘} for all 𝑘 \geq 0} .

(a)Show that $𝑉$ is a subspace of $ℝ^{𝑋}$ , and that if $𝐬 \in 𝑉$ and $𝑠_{0} = 𝑠_{1} = 0$ , then $𝐬 = 𝟎$ .
(b)Let $𝐠, 𝐟 \in 𝑉$ be the sequences with $𝑔_{0} = 1, 𝑔_{1} = 0$ and $𝑓_{0} = 0, 𝑓_{1} = 1$ . (So $𝐟 =$ $(0, 1, 1, 2, 3, 5, \dots)$ is the Fibonacci sequence.) Show that $𝐠, 𝐟$ is a basis of $𝑉$ , and that ${[𝐬]}_{(𝐠, 𝐟)} =$ $(𝑠_{0}, 𝑠_{1})$ .
(c)Let $𝜑 = (1 + \sqrt{5}) / 2$ and $𝜓 = (1 - \sqrt{5}) / 2$ , the roots of $𝑡^{2} = 𝑡 + 1$ . Show that the geometric sequences $𝐚 = {(𝜑^{𝑘})}_{𝑘 \geq 0}$ and $𝐛 = {(𝜓^{𝑘})}_{𝑘 \geq 0}$ form a basis of $𝑉$ . By finding ${[𝐟]}_{(𝐚, 𝐛)}$ , prove that
$𝑓_{𝑘} = \frac{𝜑^{𝑘} - 𝜓^{𝑘}}{\sqrt{5}} for all 𝑘 \geq 0 .$

Solution.

Uses. Theorem 1.4.3 (Subspace criterion), Definition 1.6.1 (Basis), (1.6.1), Proposition 1.6.2 (Bases are independent spanning lists), induction on $𝑘$

Hint 1. For (a), check the subspace criterion one condition at a time. For the second claim, prove by induction on

𝑘

that

𝑠_{𝑘} = 𝑠_{𝑘 + 1} = 0

Hint 2. For (b), given

𝐬 \in 𝑉

, the sequence

𝐬 - 𝑠_{0} 𝐠 - 𝑠_{1} 𝐟

lies in

𝑉

. What are its first two terms?

Hint 3. For (c),

𝜑^{𝑘 + 2} =

𝜑^{𝑘} 𝜑^{2} =

𝜑^{𝑘} (𝜑 + 1)

. To represent

𝐬

, choose

𝛼, 𝛽

with

𝛼 + 𝛽 = 𝑠_{0}

and

𝛼 𝜑 + 𝛽 𝜓 = 𝑠_{1}

, and argue as in (b).

Sketch. (a) The recurrence is preserved by sums and multiples, and the zero sequence satisfies it; if

𝑠_{0} = 𝑠_{1} = 0

, induction gives

𝑠_{𝑘} = 0

for all

𝑘

. (b)

𝐬 - 𝑠_{0} 𝐠 - 𝑠_{1} 𝐟 \in 𝑉

starts

0, 0

, so it is

𝟎

; and a combination

𝑐 𝐠 + 𝑑 𝐟

starts

𝑐, 𝑑

, so the coefficients are forced. (c)

𝐚, 𝐛 \in 𝑉

because

𝜑^{2} = 𝜑 + 1

and

𝜓^{2} = 𝜓 + 1

. Since

𝜑 \neq 𝜓

, the system

𝛼 + 𝛽 = 𝑠_{0}

𝛼 𝜑 + 𝛽 𝜓 = 𝑠_{1}

has exactly one solution, and by (a) the coefficients represent

𝐬

. For

𝐟

𝛼 = 1 / \sqrt{5}

𝛽 = - 1 / \sqrt{5}

(a) The zero sequence satisfies $0 = 0 + 0$ . If $𝐬, 𝐭 \in 𝑉$ and $𝑐 \in ℝ$ , then $𝑠_{𝑘 + 2} +$ $𝑡_{𝑘 + 2} =$ $(𝑠_{𝑘 + 1} + 𝑡_{𝑘 + 1}) +$ $(𝑠_{𝑘} + 𝑡_{𝑘})$ and $𝑐 𝑠_{𝑘 + 2} =$ $𝑐 𝑠_{𝑘 + 1} +$ $𝑐 𝑠_{𝑘}$ for all $𝑘$ , since the operations of $ℝ^{𝑋}$ are termwise. So $𝑉$ is a subspace by Theorem 1.4.3. Now let $𝐬 \in 𝑉$ with $𝑠_{0} = 𝑠_{1} = 0$ . We show by induction on $𝑘$ that $𝑠_{𝑘} = 𝑠_{𝑘 + 1} = 0$ . For $𝑘 = 0$ this is the hypothesis. If $𝑠_{𝑘} = 𝑠_{𝑘 + 1} = 0$ , then $𝑠_{𝑘 + 2} =$ $𝑠_{𝑘 + 1} +$ $𝑠_{𝑘} =$ $0$ , so $𝑠_{𝑘 + 1} = 𝑠_{𝑘 + 2} = 0$ . Hence $𝑠_{𝑘} = 0$ for all $𝑘$ , and $𝐬 = 𝟎$ .

(b) (The sequences $𝐠$ and $𝐟$ exist and are unique: choose the first two terms and define the rest by the recurrence.) Let $𝐬 \in 𝑉$ and $𝑐, 𝑑 \in ℝ$ . The combination $𝑐 𝐠 + 𝑑 𝐟$ has first two terms $𝑐$ and $𝑑$ . So if it represents $𝐬$ , then $𝑐 = 𝑠_{0}$ and $𝑑 = 𝑠_{1}$ . Conversely, $𝐭 = 𝐬 - 𝑠_{0} 𝐠 - 𝑠_{1} 𝐟$ lies in $𝑉$ , since $𝑉$ is a subspace, and $𝑡_{0} = 𝑠_{0} - 𝑠_{0} = 0$ , $𝑡_{1} = 𝑠_{1} - 𝑠_{1} = 0$ . By (a), $𝐭 = 𝟎$ , that is, $𝐬 = 𝑠_{0} 𝐠 + 𝑠_{1} 𝐟$ . So $𝐬$ is represented by exactly one combination, $𝐠, 𝐟$ is a basis of $𝑉$ , and ${[𝐬]}_{(𝐠, 𝐟)} =$ $(𝑠_{0}, 𝑠_{1})$ .

(c) Since $𝜑^{2} = 𝜑 + 1$ , we get $𝜑^{𝑘 + 2} =$ $𝜑^{𝑘} 𝜑^{2} =$ $𝜑^{𝑘 + 1} +$ $𝜑^{𝑘}$ for all $𝑘$ , so $𝐚 \in 𝑉$ ; likewise $𝐛 \in 𝑉$ . Let $𝐬 \in 𝑉$ . A combination $𝛼 𝐚 + 𝛽 𝐛$ has first two terms $𝛼 + 𝛽$ and $𝛼 𝜑 + 𝛽 𝜓$ . The system

𝛼 + 𝛽 = 𝑠_{0}, 𝛼 𝜑 + 𝛽 𝜓 = 𝑠_{1}

has exactly one solution, because $𝜑 - 𝜓 = \sqrt{5} \neq 0$ : subtracting $𝜓$ times the first equation from the second gives $𝛼 = (𝑠_{1} - 𝜓 𝑠_{0}) / \sqrt{5}$ , and then $𝛽 = 𝑠_{0} - 𝛼$ . For these $𝛼, 𝛽$ , the sequence $𝐬 - 𝛼 𝐚 - 𝛽 𝐛$ lies in $𝑉$ and starts with $0, 0$ , so it is $𝟎$ by (a). For any other $𝛼, 𝛽$ , the combination differs from $𝐬$ in one of the first two terms. So $𝐬$ has exactly one representation, and $𝐚, 𝐛$ is a basis of $𝑉$ .

For $𝐟$ , $𝑠_{0} = 0$ and $𝑠_{1} = 1$ give $𝛼 = 1 / \sqrt{5}$ and $𝛽 = - 1 / \sqrt{5}$ . So ${[𝐟]}_{(𝐚, 𝐛)} =$ $(1 / \sqrt{5}, - 1 / \sqrt{5})$ , which means $𝐟 = (𝐚 - 𝐛) / \sqrt{5}$ . Comparing $𝑘$ -th terms, $𝑓_{𝑘} =$ $(𝜑^{𝑘} - 𝜓^{𝑘}) / \sqrt{5}$ .

The same space has two useful bases. In $𝐠, 𝐟$ the coordinates are the initial values, and in $𝐚, 𝐛$ the recurrence acts on each basis vector by a single multiplication, which is what makes the closed formula possible. Choosing such a basis is the idea of diagonalization (Section 7.4).

Exercise 1.6.40.hard Let $𝑆 \subseteq 𝐹^{3 \times 3}$ be the set of matrices whose three row sums and three column sums are all equal; for $𝐴 \in 𝑆$ , write $𝑠 (𝐴)$ for this common value. Let $𝑍 \subseteq 𝑆$ and $𝒵︀ =$ $𝑍_{11},$ $𝑍_{12},$ $𝑍_{21},$ $𝑍_{22}$ be as in Exercise 1.6.33, the case $𝑠 (𝐴) = 0$ .

(a)Show that $𝑆$ is a subspace of $𝐹^{3 \times 3}$ , that $𝐼,$ $𝑍_{11},$ $𝑍_{12},$ $𝑍_{21},$ $𝑍_{22}$ is a basis of $𝑆$ , where $𝐼 = 𝑈_{11} + 𝑈_{22} + 𝑈_{33}$ , and that for $𝐴 \in 𝑆$ with $𝑠 = 𝑠 (𝐴)$ ,
${[𝐴]}_{(𝐼, 𝒵︀)} = (𝑠, 𝑎_{11} - 𝑠, 𝑎_{12}, 𝑎_{21}, 𝑎_{22} - 𝑠) .$
(b)Let $𝐽$ be the matrix all of whose entries are $1$ . Find ${[𝐽]}_{(𝐼, 𝒵︀)}$ , and determine for which fields $𝐽 \in 𝑍$ .
(c)A permutation matrix has exactly one entry $1$ in each row and each column, and $0$ elsewhere. Show that the six $3 \times 3$ permutation matrices span $𝑆$ , and find a dependence relation among them.

Solution.

Uses. Exercise 1.6.33, Theorem 1.4.3 (Subspace criterion), Definition 1.6.1 (Basis), (1.6.1), Proposition 1.3.18 (Comparing spans), Proposition 1.4.14 (The span is the smallest subspace containing a list)

Hint 1. For (a), if

𝐴 \in 𝑆

has common sum

𝑠

, what are the row and column sums of

𝐴 - 𝑠 𝐼

Hint 2. For uniqueness in (a), compute the first row sum of

𝑐_{0} 𝐼 +

\sum 𝑐_{𝑘 𝑙} 𝑍_{𝑘 𝑙}

; then use the uniqueness in Exercise 1.6.33.

Hint 3. For (c), it is enough to write

𝐼

and the four

𝑍_{𝑘 𝑙}

as combinations of permutation matrices. Each

𝑍_{𝑘 𝑙}

is a difference of two of them. For the relation, add up the three permutation matrices that place the

1

of row

1

in different columns “cyclically”.

Sketch. (a) Line sums are preserved by sums and scalar multiples, so

𝑆

is a subspace. For

𝐴 \in 𝑆

with sum

𝑠

𝐴 - 𝑠 𝐼 \in 𝑍

, so

𝐴 =

𝑠 𝐼 +

\sum {(𝐴 - 𝑠 𝐼)}_{𝑘 𝑙} 𝑍_{𝑘 𝑙}

by Exercise 1.6.33. Conversely, the first row sum of

𝑐_{0} 𝐼 +

\sum 𝑐_{𝑘 𝑙} 𝑍_{𝑘 𝑙}

𝑐_{0}

, which forces

𝑐_{0} = 𝑠

, and then the

𝑐_{𝑘 𝑙}

are the

𝒵︀

-coordinates of

𝐴 - 𝑠 𝐼

. (b)

𝑠 (𝐽) = 3

, so

[𝐽] =

(3, - 2, 1, 1, - 2)

;

𝐽 \in 𝑍

iff

3 = 0

𝐹

. (c) With

𝑇_{𝑘}

the permutation matrix fixing position

𝑘

and

𝐶, 𝐶^{'}

the two cyclic ones:

𝑍_{11} = 𝐼 - 𝑇_{2}

𝑍_{22} = 𝐼 - 𝑇_{1}

𝑍_{12} = 𝑇_{3} - 𝐶^{'}

𝑍_{21} = 𝑇_{3} - 𝐶

. Relation:

𝐼 +

𝐶 +

𝐶^{'} =

𝐽 =

𝑇_{1} +

𝑇_{2} +

𝑇_{3}

(a) Subspace. The zero matrix lies in $𝑆$ with $𝑠 = 0$ . If $𝐴, 𝐵 \in 𝑆$ and $𝑐 \in 𝐹$ , then every row and column of $𝐴 + 𝐵$ sums to $𝑠 (𝐴) + 𝑠 (𝐵)$ , and every row and column of $𝑐 𝐴$ sums to $𝑐 𝑠 (𝐴)$ , because sums of entries respect the entrywise operations. So $𝑆$ is a subspace by Theorem 1.4.3. The matrix $𝐼$ lies in $𝑆$ with $𝑠 (𝐼) = 1$ , and each $𝑍_{𝑘 𝑙}$ lies in $𝑍 \subseteq 𝑆$ .

Existence. Let $𝐴 \in 𝑆$ with $𝑠 = 𝑠 (𝐴)$ . Every row and column of $𝐴 - 𝑠 𝐼$ sums to $𝑠 - 𝑠 = 0$ , so $𝐴 - 𝑠 𝐼 \in 𝑍$ . By Exercise 1.6.33,

𝐴 - 𝑠 𝐼 = \sum_{𝑘, 𝑙 \in {1, 2}} {(𝐴 - 𝑠 𝐼)}_{𝑘 𝑙} 𝑍_{𝑘 𝑙},

where ${(𝐴 - 𝑠 𝐼)}_{𝑘 𝑙}$ is $𝑎_{𝑘 𝑙} - 𝑠$ for $𝑘 = 𝑙$ and $𝑎_{𝑘 𝑙}$ for $𝑘 \neq 𝑙$ . So $𝐴$ is represented with the coefficients claimed.

Uniqueness. Suppose $𝐴 =$ $𝑐_{0} 𝐼 +$ $\sum_{𝑘, 𝑙} 𝑐_{𝑘 𝑙} 𝑍_{𝑘 𝑙}$ . Every row of a matrix in $𝑍$ sums to $0$ , so the first row of the right side sums to $𝑐_{0}$ , and hence $𝑐_{0} = 𝑠$ . Then $\sum_{𝑘, 𝑙} 𝑐_{𝑘 𝑙} 𝑍_{𝑘 𝑙} =$ $𝐴 -$ $𝑠 𝐼$ , and the uniqueness in Exercise 1.6.33 gives $𝑐_{𝑘 𝑙} =$ ${(𝐴 - 𝑠 𝐼)}_{𝑘 𝑙}$ . So every $𝐴 \in 𝑆$ has exactly one representation, $𝐼, 𝒵︀$ is a basis of $𝑆$ , and the coordinates are as stated ((1.6.1)).

(b) Every row and column of $𝐽$ sums to $3 = 1 + 1 + 1$ , so $𝐽 \in 𝑆$ with $𝑠 (𝐽) = 3$ , and by (a)

{[𝐽]}_{(𝐼, 𝒵︀)} = (3, 1 - 3, 1, 1, 1 - 3) = (3, - 2, 1, 1, - 2) .

The matrix $𝐽$ lies in $𝑍$ exactly when its line sums are $0$ , that is, when $3 = 0$ in $𝐹$ , as in $𝔽_{3}$ . In that case its first coordinate is $0$ , and its coordinates are $(0, 1, 1, 1, 1)$ .

(c) Each permutation matrix lies in $𝑆$ , with every line sum equal to $1$ . There are six of them: $𝐼$ ; the two “cyclic” ones

𝐶 = 𝑈_{12} + 𝑈_{23} + 𝑈_{31}, 𝐶^{'} = 𝑈_{13} + 𝑈_{21} + 𝑈_{32};

and the three that keep exactly one $1$ of $𝐼$ in place,

𝑇_{1} = 𝑈_{11} + 𝑈_{23} + 𝑈_{32}, 𝑇_{2} = 𝑈_{13} + 𝑈_{22} + 𝑈_{31}, 𝑇_{3} = 𝑈_{12} + 𝑈_{21} + 𝑈_{33} .

Comparing entries,

𝑍_{11} = 𝐼 - 𝑇_{2}, 𝑍_{22} = 𝐼 - 𝑇_{1}, 𝑍_{12} = 𝑇_{3} - 𝐶^{'}, 𝑍_{21} = 𝑇_{3} - 𝐶 .

For instance, $𝐼 -$ $𝑇_{2} =$ $(𝑈_{11} + 𝑈_{22} + 𝑈_{33}) -$ $(𝑈_{13} + 𝑈_{22} + 𝑈_{31}) =$ $𝑈_{11} -$ $𝑈_{13} -$ $𝑈_{31} +$ $𝑈_{33} =$ $𝑍_{11}$ . So the basis $𝐼, 𝒵︀$ of $𝑆$ lies in the span of the permutation matrices, and $𝑆 \subseteq$ that span by Proposition 1.3.18. Conversely, the permutation matrices lie in the subspace $𝑆$ , so their span is contained in $𝑆$ (Proposition 1.4.14). Hence they span $𝑆$ .

The matrices $𝐼, 𝐶, 𝐶^{'}$ have their $1$ ′s in disjoint positions covering all nine, and so do $𝑇_{1}, 𝑇_{2}, 𝑇_{3}$ . Hence

𝐼 + 𝐶 + 𝐶^{'} = 𝐽 = 𝑇_{1} + 𝑇_{2} + 𝑇_{3},

and $𝐼 +$ $𝐶 +$ $𝐶^{'} -$ $𝑇_{1} -$ $𝑇_{2} -$ $𝑇_{3} =$ $0$ is a dependence relation, with coefficient $1$ on $𝐼$ , over every field. So six matrices span $𝑆$ , which has a basis of length $5$ , and they are dependent; Section 4.1 shows that this had to happen.

Exercise 1.6.41.hard Let $𝐾$ be a subfield of a field $𝐸$ , and let $𝑉$ be a vector space over $𝐸$ ; regard $𝐸$ and $𝑉$ as vector spaces over $𝐾$ by restricting scalars (Proposition 1.2.19). Suppose that $𝛼_{1}, \dots, 𝛼_{𝑚}$ is a basis of $𝐸$ over $𝐾$ and $𝐯_{1}, \dots, 𝐯_{𝑛}$ is a basis of $𝑉$ over $𝐸$ .

(a)Show that the $𝑚 𝑛$ vectors $𝛼_{𝑖} 𝐯_{𝑗}$ , listed as
$𝛼_{1} 𝐯_{1}, \dots, 𝛼_{𝑚} 𝐯_{1}, 𝛼_{1} 𝐯_{2}, \dots, 𝛼_{𝑚} 𝐯_{2}, \dots, 𝛼_{1} 𝐯_{𝑛}, \dots, 𝛼_{𝑚} 𝐯_{𝑛},$
form a basis of $𝑉$ over $𝐾$ .
(b)Write down the resulting basis of $ℂ^{2}$ over $ℝ$ , and the coordinates of $(1 + 2 𝑖, 3 - 𝑖)$ in it.

Solution.

Uses. Proposition 1.2.19 (Restriction of scalars), Proposition 1.6.2 (Bases are independent spanning lists), Theorem 1.5.5 (Independence is decided at zero), Definition 1.2.1 (Vector space), Lemma 1.3.9 (Arithmetic of linear combinations)

Hint 1. For spanning, write

𝐯 = \sum_{𝑗} 𝑎_{𝑗} 𝐯_{𝑗}

with

𝑎_{𝑗} \in 𝐸

, and then write each

𝑎_{𝑗}

as a

𝐾

-combination of the

𝛼_{𝑖}

Hint 2. For independence, group a

𝐾

-relation

\sum_{𝑖, 𝑗} 𝑏_{𝑖 𝑗} 𝛼_{𝑖} 𝐯_{𝑗} =

𝟎

\sum_{𝑗} (\sum_{𝑖} 𝑏_{𝑖 𝑗} 𝛼_{𝑖}) 𝐯_{𝑗} =

𝟎

. Use independence over

𝐸

, then over

𝐾

Sketch. Spanning:

𝐯 = \sum_{𝑗} 𝑎_{𝑗} 𝐯_{𝑗}

with

𝑎_{𝑗} =

\sum_{𝑖} 𝑏_{𝑖 𝑗} 𝛼_{𝑖}

𝑏_{𝑖 𝑗} \in 𝐾

, so

𝐯 =

\sum_{𝑖, 𝑗} 𝑏_{𝑖 𝑗} (𝛼_{𝑖} 𝐯_{𝑗})

by (A6) and (A8). Independence: a

𝐾

-relation regroups as

\sum_{𝑗} 𝑐_{𝑗} 𝐯_{𝑗} = 𝟎

with

𝑐_{𝑗} =

\sum_{𝑖} 𝑏_{𝑖 𝑗} 𝛼_{𝑖} \in

𝐸

; independence of the

𝐯_{𝑗}

over

𝐸

gives each

𝑐_{𝑗} = 0

, and independence of the

𝛼_{𝑖}

over

𝐾

gives each

𝑏_{𝑖 𝑗} = 0

. (b)

(1, 0),

(𝑖, 0),

(0, 1),

(0, 𝑖)

, and coordinates

(1, 2, 3, - 1)

Scalar multiplication of $𝐾$ on $𝑉$ is that of $𝐸$ , restricted to $𝐾$ , and the same holds on $𝐸$ , where it is multiplication in $𝐸$ . So the vector space axioms of $𝑉$ over $𝐸$ apply whenever the scalars lie in $𝐾$ or $𝐸$ .

(a) Spanning. Let $𝐯 \in 𝑉$ . Since $𝐯_{1}, \dots, 𝐯_{𝑛}$ spans $𝑉$ over $𝐸$ , $𝐯 = \sum_{𝑗} 𝑎_{𝑗} 𝐯_{𝑗}$ with $𝑎_{𝑗} \in 𝐸$ . Since $𝛼_{1}, \dots, 𝛼_{𝑚}$ spans $𝐸$ over $𝐾$ , each $𝑎_{𝑗} =$ $\sum_{𝑖} 𝑏_{𝑖 𝑗} 𝛼_{𝑖}$ with $𝑏_{𝑖 𝑗} \in 𝐾$ . By (A8) and (A6) in the $𝐸$ -vector space $𝑉$ ,

𝑎_{𝑗} 𝐯_{𝑗} = (\sum_{𝑖 = 1}^{𝑚} 𝑏_{𝑖 𝑗} 𝛼_{𝑖}) 𝐯_{𝑗} = \sum_{𝑖 = 1}^{𝑚} 𝑏_{𝑖 𝑗} (𝛼_{𝑖} 𝐯_{𝑗}),

so $𝐯 =$ $\sum_{𝑗 = 1}^{𝑛} \sum_{𝑖 = 1}^{𝑚} 𝑏_{𝑖 𝑗} (𝛼_{𝑖} 𝐯_{𝑗})$ is a $𝐾$ -linear combination of the list.

Independence. Suppose that $\sum_{𝑗 = 1}^{𝑛} \sum_{𝑖 = 1}^{𝑚} 𝑏_{𝑖 𝑗} (𝛼_{𝑖} 𝐯_{𝑗}) =$ $𝟎$ with all $𝑏_{𝑖 𝑗} \in 𝐾$ . Regrouping with the same axioms, $\sum_{𝑗} 𝑐_{𝑗} 𝐯_{𝑗} = 𝟎$ , where $𝑐_{𝑗} =$ $\sum_{𝑖} 𝑏_{𝑖 𝑗} 𝛼_{𝑖} \in$ $𝐸$ . Since $𝐯_{1}, \dots, 𝐯_{𝑛}$ is independent over $𝐸$ , every $𝑐_{𝑗} = 0$ (Theorem 1.5.5). So for each $𝑗$ , $\sum_{𝑖} 𝑏_{𝑖 𝑗} 𝛼_{𝑖} = 0$ is a $𝐾$ -relation of $𝛼_{1}, \dots, 𝛼_{𝑚}$ , and independence over $𝐾$ gives $𝑏_{𝑖 𝑗} = 0$ for all $𝑖$ . So the list is independent over $𝐾$ , and it is a basis by Proposition 1.6.2.

(b) Take $𝐾 = ℝ$ , $𝐸 = ℂ$ with basis $1, 𝑖$ (Example 1.6.5), and $𝑉 = ℂ^{2}$ with the standard basis $𝐞_{1}, 𝐞_{2}$ over $ℂ$ . The basis of (a) is

(1, 0), (𝑖, 0), (0, 1), (0, 𝑖) .

Since $(1 + 2 𝑖, 3 - 𝑖) =$ $1 (1, 0) +$ $2 (𝑖, 0) +$ $3 (0, 1) +$ $(- 1) (0, 𝑖)$ with real coefficients, its coordinates are $(1, 2, 3, - 1)$ by (1.6.1). In general, the coordinates of a vector of $ℂ^{𝑛}$ in this basis over $ℝ$ list the real and imaginary parts of its entries.

Exercise 1.6.42.challenge Let $𝑛 \geq 1$ , and let $𝑉 = 𝔽_{2}^{𝑋}$ be the space of all functions $𝑋 \to 𝔽_{2}$ , where $𝑋 = 𝔽_{2}^{𝑛}$ . For a subset $𝑆 \subseteq {1, \dots, 𝑛}$ , let $𝑚_{𝑆} \in 𝑉$ be the function

𝑚_{𝑆} (𝑦_{1}, \dots, 𝑦_{𝑛}) = \prod_{𝑖 \in 𝑆} 𝑦_{𝑖},

with $𝑚_{\emptyset} = 1$ (the constant function). Show that the $2^{𝑛}$ functions $𝑚_{𝑆}$ , listed in any order, form a basis of $𝑉$ . Deduce that every function $𝔽_{2}^{𝑛} \to 𝔽_{2}$ can be written in exactly one way as a sum of distinct products $𝑦_{𝑖_{1}} 𝑦_{𝑖_{2}} \dots 𝑦_{𝑖_{𝑟}}$ with $𝑖_{1} < \dots < 𝑖_{𝑟}$ (allowing the empty product $1$ ).

Solution.

Uses. Exercise 1.5.43, Proposition 1.6.2 (Bases are independent spanning lists), Definition 1.2.9 (Function spaces), Proposition 1.3.18 (Comparing spans)

Hint 1. Count:

𝑉

has

2^{2^{𝑛}}

elements, and the list has length

2^{𝑛}

. By Exercise 1.5.43(a), it is enough to show that the list spans

𝑉

Hint 2. For

𝐚 \in 𝑋

, let

𝛿_{𝐚}

1

𝐚

and

0

elsewhere. Every

𝑓

is a combination of the

𝛿_{𝐚}

. Show that

𝛿_{𝐚} (𝐲) =

\prod_{𝑖 = 1}^{𝑛} (𝑦_{𝑖} + 𝑎_{𝑖} + 1)

Hint 3. Expand that product of

𝑛

binomials. Each term is a constant times

\prod_{𝑖 \in 𝑆} 𝑦_{𝑖}

for some

𝑆

Sketch. Every

𝑓 = \sum_{𝐚} 𝑓 (𝐚) 𝛿_{𝐚}

. In

𝔽_{2}

𝑦_{𝑖} + 𝑎_{𝑖} + 1 = 1

exactly when

𝑦_{𝑖} = 𝑎_{𝑖}

, so

𝛿_{𝐚} (𝐲) =

\prod_{𝑖} ((𝑎_{𝑖} + 1) + 𝑦_{𝑖})

, and expanding gives

\sum_{𝑆} (\prod_{𝑖 \notin 𝑆} (𝑎_{𝑖} + 1)) 𝑚_{𝑆} (𝐲)

. So the

𝑚_{𝑆}

span

𝑉

. The span of a list of length

2^{𝑛}

then has

2^{2^{𝑛}}

elements, so by Exercise 1.5.43(a) the list is independent, hence a basis. The coordinates in this basis give the unique expression.

Write $𝑁 = 2^{𝑛}$ for the number of subsets $𝑆$ , and fix a listing $𝑚_{𝑆_{1}}, \dots, 𝑚_{𝑆_{𝑁}}$ . The space $𝑉$ has $2^{𝑁}$ elements, since a function $𝑋 \to 𝔽_{2}$ chooses one of two values at each of the $𝑁$ points of $𝑋$ .

Spanning. For $𝐚 \in 𝑋$ , let $𝛿_{𝐚} \in 𝑉$ be $1$ at $𝐚$ and $0$ elsewhere. Every $𝑓 \in 𝑉$ satisfies $𝑓 =$ $\sum_{𝐚 \in 𝑋} 𝑓 (𝐚) 𝛿_{𝐚}$ , since both sides take the value $𝑓 (𝐲)$ at each $𝐲$ (only the term with $𝐚 = 𝐲$ contributes). So by Proposition 1.3.18 it suffices to show that each $𝛿_{𝐚}$ lies in the span of the $𝑚_{𝑆}$ .

In $𝔽_{2}$ , the element $𝑦_{𝑖} + 𝑎_{𝑖} + 1$ is $1$ if $𝑦_{𝑖} = 𝑎_{𝑖}$ and $0$ if $𝑦_{𝑖} \neq 𝑎_{𝑖}$ (as $𝑎_{𝑖} + 𝑎_{𝑖} = 0$ and $1 + 1 = 0$ ). A product of elements of $𝔽_{2}$ is $1$ exactly when every factor is $1$ , so

𝛿_{𝐚} (𝐲) = \prod_{𝑖 = 1}^{𝑛} ((𝑎_{𝑖} + 1) + 𝑦_{𝑖}) for all 𝐲 \in 𝑋 .

Expanding a product of $𝑛$ sums $(𝑢_{𝑖} + 𝑦_{𝑖})$ by distributivity (induction on $𝑛$ ) gives the sum, over all subsets $𝑆 \subseteq {1, \dots, 𝑛}$ , of the products that take $𝑦_{𝑖}$ from the factors with $𝑖 \in 𝑆$ and $𝑢_{𝑖}$ from the others:

\prod_{𝑖 = 1}^{𝑛} (𝑢_{𝑖} + 𝑦_{𝑖}) = \sum_{𝑆 \subseteq {1, \dots, 𝑛}} (\prod_{𝑖 \notin 𝑆} 𝑢_{𝑖}) (\prod_{𝑖 \in 𝑆} 𝑦_{𝑖}) .

With $𝑢_{𝑖} = 𝑎_{𝑖} + 1$ , this says that $𝛿_{𝐚} = \sum_{𝑆} 𝑐_{𝑆} 𝑚_{𝑆}$ with $𝑐_{𝑆} =$ $\prod_{𝑖 \notin 𝑆} (𝑎_{𝑖} + 1) \in$ $𝔽_{2}$ , an identity of functions because it holds at every $𝐲$ . So the list spans $𝑉$ .

Independence. By Exercise 1.5.43(a), a list of length $𝑁$ over $𝔽_{2}$ is independent if and only if its span has exactly $2^{𝑁}$ elements. Our list has length $𝑁$ , and its span is $𝑉$ , which has $2^{𝑁}$ elements. So the list is independent, and it is a basis by Proposition 1.6.2.

The deduction. For $𝑓 \in 𝑉$ , Definition 1.6.1 gives exactly one list of coefficients $𝑐_{𝑆} \in 𝔽_{2}$ with $𝑓 = \sum_{𝑆} 𝑐_{𝑆} 𝑚_{𝑆}$ . Over $𝔽_{2}$ a coefficient is $0$ or $1$ , so this says that $𝑓$ is the sum of the $𝑚_{𝑆}$ with $𝑐_{𝑆} = 1$ , and the set of these $𝑆$ is uniquely determined. For instance, for $𝑛 = 2$ , the function that is $1$ exactly at $(0, 0)$ is $𝛿_{(0, 0)} =$ $(1 + 𝑦_{1}) (1 + 𝑦_{2}) =$ $1 +$ $𝑦_{1} +$ $𝑦_{2} +$ $𝑦_{1} 𝑦_{2}$ . This unique expression is the algebraic normal form of a Boolean function.

More practice

The practice bank has 77 exercises on this section’s topics.