§2.7 Bases and dimension · A rough guide to linear algebra

We are now more than ready to start classifying vector spaces. Recall that this was our goal for studying vector spaces: classifying vector spaces up to isomorphism.

Let $V$ be a $k$-vector space and let $S \subseteq V$ be a subset (not a subspace) of $V$. The inclusion map $i : S \hookrightarrow V$ induces a linear map $f : k^{\oplus S} \to V$ by Proposition 2.4.3. We say that the set $S$ is

linearly independent if $f$ is injective, linearly dependent if $f$ is not injective,
generating or spanning if $f$ is surjective, and
a basis if $f$ is bijective.

Okay, this is some abstract definition. It would be helpful to know what they really mean in concrete terms.

Show that a subset $S \subseteq V$ is linearly independent if and only if the following condition holds: for arbitrary distinct vectors $v_1, \ldots, v_n \in S$ and scalars $a_1, \ldots, a_n \in k$, the equation

$$ a_1 v_1 + a_2 v_2 + \cdots + a_n v_n = 0 $$

implies $a_1 = a_2 = \cdots = a_n = 0$.

Show that a subset $S \subseteq V$ is generating if and only if the following condition holds: for each $v \in V$, there exist elements $v_1, \ldots, v_n \in S$ and scalars $a_1, \ldots, a_n \in k$ such that

$$ a_1 v_1 + a_2 v_2 + \cdots + a_n v_n = v. $$

Intuitively speaking, linear independence means that you cannot combine the vectors in $S$ in a nontrivial way to make $0$. For instance, if you have the vectors $\vec{v}_1 = (1, 0)$ and $\vec{v}_2 = (2, 3)$ in $\mathbb{R}^2$, they point in different directions, so you cannot make some linear combination and get $0$, unless you do something as meaningless as $0 \cdot \vec{v}_1 + 0 \cdot \vec{v}_2 = \vec{0}$.

A subset $S \subseteq V$ spans the vector space $V$ if every vector in $V$ can be written as a linear combination of vectors in $S$. I think it is quite clear what this means. For instance, $\lbrace (1, 0), (2, 3), (3, 5) \rbrace $ spans $\mathbb{R}^2$, because we can, for instance, write $(x, y) = x (1, 0) - 3y (2, 3) + 2y (3, 5)$. But it is not linearly independent because, say, $(1, 0) - 5 (2, 3) + 3 (3, 5) = (0, 0)$.

Let $S \subseteq V$ be an arbitrary subset of a vector space. The inclusion map $i : S \hookrightarrow V$ induces a linear map $f : k^{\oplus S} \to V$. We define the subspace spanned by $S$ as $\vspan(S) = \im f \subseteq V$.

It is clear that $\vspan(S)$ is the subspace consisting of vectors that can be expressed as a linear combination of elements of $S$. Also, $S$ is spanning if and only if $\vspan(S) = V$. The two conditions, linear independence and spanning, when put together, means something very nice.

Show that a subset $S \subseteq V$ is a basis if and only if the following condition holds: for each $v \in V$, there is a unique tuple $(a_s)_{s \in S}$ of elements in $k$ such that $a_s \neq 0$ only for finitely many $s$ and

$$ \sum_{s \in S}^{} a_s s = v. $$

One reason we care about bases is that a basis gives an isomorphism between $k^{\oplus S}$ and $V$, that is, an isomorphism between $V$ and a free vector space. We know exactly what a free vector space looks like, so such an isomorphism is going to be useful in studying properties of the vector space $V$.

The surprising fact that actually every vector space has a basis!

Every vector space has a basis.

Every vector space is isomorphic to $k^{\oplus S}$ for some set $S$.

How would one prove such a theorem? We need to construct a basis, which is a set that is both linearly independent and generating. Let us start with $S_0 = \emptyset$. This is clearly linearly independent, because there is no vector to form a nontrivial linear relation. But also, unless $V = 0$, the set is not spanning. So take any nonzero vector $v_1 \in V$ and throw it into the set $S_0$. After this step, we have $S_1 = \lbrace v_1\rbrace $. As long as $v_1 \neq 0$, the set $\lbrace v_1 \rbrace $ is linearly independent because $a_1 v_1 = 0$ implies $a_1 = 0$. If $V = \vspan(S_1) = \lbrace a_1 v_1 \rbrace $ then this is spanning as well, and we are done. Otherwise, we need more vectors, so pick another vector $v_2 \notin \vspan(S_1)$ and throw it into $S_1$. Then we get a set $S_2 = \lbrace v_1, v_2 \rbrace $ that is linearly independent, but not necessarily spanning. We are going to repeat this process, until we get a spanning set. One problem is that the process might continue on infinitely, and the Axiom of Choice is what will help us deal with this issue.

Let us make the above process formal. Let $S \subseteq V$ be a linearly independent subset. Suppose that $\vspan(S) \subsetneq V$, and pick a vector $v \in V$ with $v \notin \vspan(S)$. Show that $S \cup \lbrace v\rbrace $ is linearly independent as well.

One general tool for dealing with infinite processes is Zorn's lemma. We will only state and not prove the lemma. It is known that Zorn's lemma is equivalent to the Axiom of Choice.

Let $X$ be a set, and consider a relation $R \subseteq X \times X$. (We're going to write $(x, y) \in R$ as $x \preceq y$. As the notation suggests, this relation is supposed to represent an ordering.) Suppose this relation satisfies the following:

(1)
$x \preceq x$ for all $x \in X$,
(2)
if $x \preceq y$ and $y \preceq x$ then $x = y$,
(3)
if $x \preceq y$ and $y \preceq z$ then $x \preceq z$,
(4)
if $S \subseteq X$ is a subset such that either $x \preceq y$ or $y \preceq x$ for every $x, y \in S$, then there exists a $z \in X$ such that $x \preceq z$ for all $x \in S$.

Then there exists an element $m \in X$ such that $m \preceq x$ is true only for $x = m$.

The first three conditions capture a notion of ordering. A relation satisfying (1), (2), (3) is called a partial order, with “partial” meaning that not every two elements can be compared. The last condition (4) is the interesting one. It roughly says that every “chain” of comparable elements has an “upper bound”. The conclusion is that there is an element that is maximal in the sense that nothing is strictly bigger. If you are interested in learning the proof, the idea is the same as what we sketched for finding a basis. Pick an arbitrary element, which is probably not going to be maximal. If it is not maximal, you can find an element that is strictly bigger than it. If this is not maximal, then you can continue finding an element strictly bigger than that and so on. The condition (4) allows you to run the process transfinitely.

Proof of Theorem 2.7.3.

Let $V$ be a vector space, and consider the collection

$$ \mathcal{A} = \lbrace S \subseteq V : S \text{ is linearly independent} \rbrace $$

of linearly independent sets. Consider the inclusion order $S_1 \preceq S_2 \Leftrightarrow S_1 \subseteq S_2$ given on $\mathcal{A}$. By properties of sets, this automatically satisfies (1), (2), and (3) of Lemma 2.7.5.

We can also check the last condition (4). Suppose that $\mathcal{C} \subseteq \mathcal{A}$ is a collection of linearly independent sets, such that any two $S_1, S_2 \subseteq \mathcal{C}$ are ordered by inclusion. If we define

$$ S_M = \bigcup_{S \in \mathcal{C}} S, $$

then it is clear that $S_M$ is a set that contains all elements of $\mathcal{C}$. We also can check that $S_M \in \mathcal{A}$, i.e., $S_M$ is linearly independent. If not, there exist distinct vectors $v_1, \ldots, v_n \in S_M$ and $a_1, \ldots, a_n \in k$, not all zero, such that $a_1 v_1 + \cdots + a_n v_n = 0$. But each $v_i$ is in the union of $S \in \mathcal{C}$, so there exist $S_i \in \mathcal{C}$ such that $v_i \in S_i$. If we look at the sets $S_1, \ldots, S_n \in \mathcal{C}$, every two of them are comparable by inclusion. This means that we can assume $S_1 \subseteq S_2 \subseteq \cdots \subseteq S_n$ without loss of generality. Then $v_i \in S_i$ implies that $v_1, \ldots, v_n \in S_n$. This and $a_1 v_1 + \cdots + a_n v_n = 0$ contradicts that $S_n \in \mathcal{A}$ is linearly independent. Therefore $S_M$ has to be linearly independent, and is larger than all elements of $\mathcal{C}$. This verifies (4).

We now apply Lemma 2.7.5 to the collection $\mathcal{A}$ ordered by inclusion. There exists a maximal set $M \in \mathcal{A}$. (Maximality in this context means that $M \subseteq S$ and $S$ linearly independent implies $M = S$.) Because $M$ is already linearly independent, we are done if we can show that $M$ spans $V$. Suppose not, that $\vspan(M) \subsetneq V$. We can pick a vector $v \in V \setminus \vspan(M)$, and then by Exercise 2.7.D, $M \cup \lbrace v\rbrace $ is a linearly independent set that is strictly larger than $M$. (The vector $v$ can't already be in $M$, because then $v$ would be in $\vspan(M)$.) This contradicts our assumption on $M$, and therefore $\vspan(M) = V$. That is, $M$ is both linearly independent and spanning, hence a basis.

This is a difficult proof, probably one of the hardest you will encounter in linear algebra. But the main idea is simple: if the set is not spanning, add in vectors while keeping it linearly independent. The rest is simply a standard technique of using Zorn's lemma, which you will get used to after seeing it three times.

Let $B \subseteq V$ be a basis of a vector space $V$. For each vector space, show that the natural map

$$ \Hom_k(V, W) \to \prod_{b \in B}^{} W; \quad f \mapsto (f(b))_{b \in B} $$

is an isomorphism of vector spaces.

Let us prove something slightly stronger than just the existence of a basis. Let $V$ be a $k$-vector space and consider an arbitrary linearly independent subset $S \subseteq V$. Prove that there exists a superset $S \subseteq T$ such that $T$ is a basis of $V$. (Hint: we need to start the process from $S$ instead of the empty set. Consider the family of linearly independent sets already containing $S$.)

We can even put an upper bound in finding the basis. Let $V$ be a $k$-vector space and consider $S_1 \subseteq V$ a linearly independent set and $S_2 \subseteq V$ a spanning set. Suppose that $S_1 \subseteq S_2$. Prove that there exists a subset $T$ with $S_1 \subseteq T \subseteq S_2$ such that $T$ is a basis of $V$. (Hint: this time, we only add in elements of $S_2$ while running the process. Consider the linearly independent subsets containing $S_1$ and contained in $S_2$.)

So we have proven that all vector spaces are isomorphic to some $k^{\oplus S}$. But this does not finish the classification of vector spaces, because there certainly are multiplicities within this classification. For instance, it is possible that $k^{\oplus S} \cong k^{\oplus T}$ for distinct sets $S \neq T$. For instance, if $S$ and $T$ have the same number of elements, then probably $k^{\oplus S} \cong k^{\oplus T}$.

Suppose that $\alpha : S \to T$ is a map of sets. Show that the induced map $\alpha_\ast : k^{\oplus S} \to k^{\oplus T}$ is injective if and only if $\alpha$ is injective, and that $\alpha_\ast$ is surjective if and only if $\alpha$ is surjective. As a consequence, $\alpha_\ast$ is an isomorphism if $\alpha$ is bijective.

It is reasonable to guess that $k^{\oplus S} \cong k^{\oplus T}$ if and only if there is a bijection between $S$ and $T$. This turns out to be a true statement, but we need some preparation before proving it.

Let $f : V \twoheadrightarrow W$ be a surjective linear map. Then there exists a linear map $g : W \to V$ such that $f \circ g = \id_W$ is the identity map. (Such $g$ necessarily has to be injective.)

Proof.

Pick a basis $B \subseteq W$. From Exercise 2.7.E, we see that a map $g : W \to V$ is uniquely determined by the values $g(b)$ for $b \in B$. Because we want $f(g(b)) = b$ for each $b \in B$, we pick $g(b)$ as a vector in the inverse image $f^{-1}(b)$. Here, note that $f^{-1}(b)$ is nonempty because $f$ is surjective. But $f(g(b)) = b$ means that $f \circ g : W \to W$ and $\id_W : W \to W$ agree on all elements of $B$. Exercise 2.7.E immediately implies that $f \circ g = \id_W$ as linear maps.

Note that the function $g$ is far from being unique. Let's try to see what we did in the previous proof with an example of $f : \mathbb{R}^2 \to \mathbb{R}$ given by $f(x, y) = y$. We first pick a basis $B = \lbrace 1 \rbrace $ of $W = \mathbb{R}$. The proof tells us to pick $g(1)$ as any vector that is in $f^{-1}(1) = \lbrace (x, 1) \rbrace $. In general, let us pick $g_c(1) = (c, 1)$, so that $g_c(x) = (cx, x)$. It is clear that all these linear maps $g_c$ satisfy $f \circ g_c = \id_W$. See Figure 2.2.

Several sections of a projection between vector spaces. — Figure 2.2. Different sections (gray) of a projection map $f : V \to W$

Consider a short exact sequence

A short exact sequence of three vector spaces.

Then $f_2 : V_2 \to V_3$ is surjective, and hence there exists a linear map $g_2 : V_3 \to V_2$ such that $f_2 \circ g_2 = \id_{V_3}$. Show that every element $v_2 \in V_2$ can be uniquely presented as

$$ v_2 = f_1(v_1) + g_2(v_3) $$

for $v_1 \in V_1$ and $v_3 \in V_3$. (Uniqueness means that if $v_2 = f_1(v_1^\prime) + g_2(v_3^\prime)$ then $v_1^\prime = v_1$ and $v_3^\prime = v_3$.) Also show that there exists a linear map $g_1 : V_2 \to V_1$ such that $g_1 \circ f_1 = \id_{V_1}$.

For two vector spaces $V$ and $W$, show that there exists a surjective linear map $V \twoheadrightarrow W$ if and only if there exists an injective linear map $W \hookrightarrow V$. (Hint: use the previous exercise.)

We are now ready to prove that $k^{\oplus S} \cong k^{\oplus T}$ implies that there exists a bijection between the two sets $S$ and $T$. In fact, we will prove a much stronger statement. This is again a hard theorem, but try to at least grasp the main idea. If you are not familiar with set theory regarding cardinality, feel free to skip the case when $T$ is infinite.

For arbitrary sets $S$ and $T$, the following are equivalent:

(i)
There exists an injective linear map $k^{\oplus S} \hookrightarrow k^{\oplus T}$.
(ii)
There exists a surjective linear map $k^{\oplus T} \twoheadrightarrow k^{\oplus S}$.
(iii)
There exists an injective (set) map $S \hookrightarrow T$.
(iv)
Either there exists a surjective (set) map $T \twoheadrightarrow S$ or $S = \emptyset$.

Proof.

Exercise 2.7.J gives the equivalence between (i) and (ii). It follows from basic set theory that (iii) and (iv) are equivalent. (Actually (iv) $\Rightarrow$ (iii) requires the Axiom of Choice, but we're already assuming this.) So now we need to prove equivalence between (i) $\Leftrightarrow$ (ii) and (iii) $\Leftrightarrow$ (iv). One direction is immediate: (iii) $\Rightarrow$ (i) follows from Exercise 2.7.H. It suffices to show the other direction.

We are going to divide into two cases. First assume that $T$ is infinite, and consider a surjective linear map $f : k^{\oplus T} \twoheadrightarrow k^{\oplus S}$. We are going to prove (ii) $\Rightarrow$ (iv). For each element $t_j \in T$, we look at $f(\underline{t_{j}}) \in k^{\oplus S}$. Write

$$ f(\underline{t_{j}}) = a_{j,1} \underline{s_{j,1}} + a_{j,2} \underline{s_{j,2}} + \cdots + a_{j,n_j} \underline{s_{j,n_j}}. $$

Now we define a (set) map

$$ \alpha : \lbrace (t_j, m) \in T \times \mathbb{Z}_{\ge 0} : 1 \le m \le n_j \rbrace \to S; \quad (t_j, m) \mapsto s_{j,m}. $$

The point is that this map is a surjective map. If some $s \in S$ doesn't appear in the image of $\alpha$, this means that $s$ doesn't appear in any of the $f(\underline{t_j})$. Then the image of $f$ is contained in $k^{\oplus (S \setminus \lbrace s\rbrace )}$, which contradicts that $f$ is surjective. So we get a surjective map from a subset of $T \times \mathbb{Z}_{\ge 0}$ to $S$. Because $T$ is infinite, there exists a bijection between $T$ and $T \times \mathbb{Z}_{\ge 0}$ (this is another set-theoretic fact), and hence there exists a surjection from a subset of $T$ to $S$. This gives (iv).

Now let us deal with the case when $T = \lbrace t_1, \ldots, t_n\rbrace $ is finite. We are going to use the next lemma (Lemma 2.7.9) here to prove (ii) $\Rightarrow$ (iii). Consider a surjective map $f : k^{\oplus T} \twoheadrightarrow k^{\oplus S}$. Then $A = \lbrace f(\underline{t_1}), \ldots, f(\underline{t_n}) \rbrace $ is a spanning set for $k^{\oplus S}$, and on the other hand, $B = \lbrace \underline{s} : s \in S \rbrace = \lbrace \underline{s_1}, \underline{s_2}, \ldots \rbrace $ is a basis of $k^{\oplus S}$. By Lemma 2.7.9, we can remove one element in $B$ and replace it by an element of $A$ to get another basis. Let us remove $\underline{s_1}$ from $B$ and replace it with some element of $A$ to get a new basis

$$ B_1 = \lbrace f(\underline{t_{i_1}}), \underline{s_2}, \underline{s_3}, \ldots \rbrace . $$

Then we can remove $\underline{s_2}$ and replace it by some element of $A$ to get another basis

$$ B_2 = \lbrace f(\underline{t_{i_1}}), f(\underline{t_{i_2}}), \underline{s_3}, \ldots \rbrace . $$

Here, we must have $i_1 \neq i_2$, because otherwise $B_2$ is strictly a subset of $B_1$. This means that this process should not be allowed to continue for more than $n$ times, because $A$ has only $n$ elements and the same element cannot appear twice among $t_{i_1}, t_{i_2}, \ldots$. This shows that $B$ cannot have more than $n$ elements to start out with. Therefore $S$ has at most $n$ elements and there exists an injective (set) map $S \hookrightarrow T$.

Let $V$ be a $k$-vector space. Let $B \subseteq V$ be a basis, and $A \subseteq V$ be a spanning set. Then for each $b \in B$, there exists an $a \in A$ such that $(B \setminus \lbrace b\rbrace ) \cup \lbrace a\rbrace $ is again a basis.

Proof.

Because $A$ is spanning, there exists an $a \in A$ such that $a \notin \vspan(B \setminus \lbrace b\rbrace )$. Otherwise, $A \subseteq \vspan(B \setminus \lbrace b\rbrace )$ and so $V = \vspan A \subseteq \vspan(B \setminus \lbrace b\rbrace )$ gives a contradiction. By Exercise 2.7.D, the set $(B \setminus \lbrace b\rbrace ) \cup \lbrace a\rbrace $ is linearly independent. Let us now show that it is spanning. Because $B$ is a basis, there is a way to write

$$ a = c b + c_1 b_1 + c_2 b_2 + \cdots + c_n b_n $$

where $c, c_1, \ldots, c_n \in k$ and $b_1, \ldots, b_n \in B \setminus \lbrace b\rbrace $ are distinct. Because $a \notin \vspan(B \setminus \lbrace b\rbrace )$, we have $c \neq 0$. Then we can also write

$$ b = c^{-1} a - c^{-1} c_1 b_1 - c^{-1} c_2 b_2 - \cdots - c^{-1} c_n b_n. $$

This shows that $b \in \vspan((B \setminus \lbrace b\rbrace ) \cup \lbrace a\rbrace )$ and so $V = \vspan(B) \subseteq \vspan((B \setminus \lbrace b\rbrace ) \cup \lbrace a\rbrace )$. Therefore $(B \setminus \lbrace b\rbrace ) \cup \lbrace a\rbrace $ is a basis.

Translate Theorem 2.7.8 to the following statement. Let $V$ and $W$ be vector spaces, and let $B_V$ and $B_W$ be bases for $V$ and $W$ respectively. Then the following statements are equivalent:

(i)
There exists an injective linear map $V \hookrightarrow W$.
(ii)
There exists a surjective linear map $W \twoheadrightarrow V$.
(iii)
There exists an injective map $B_V \hookrightarrow B_W$.
(iv)
Either there exists a surjective map $B_W \twoheadrightarrow B_V$ or $B_V = \emptyset$.

If $B_1$ and $B_2$ are two bases of a $k$-vector space $V$, then $\lvert B_1 \rvert = \lvert B_2 \rvert$, i.e., there exists a bijection between $B_1$ and $B_2$.

Proof.

Because $\id_V : V \to V$ is injective, there exists an injective map $B_1 \hookrightarrow B_2$. But $\id_V : V \to V$ is also surjective, so there exists an injective map $B_2 \hookrightarrow B_1$. By the Schröder–Bernstein theorem, which we will not prove, there exists a bijection between the two sets $B_1$ and $B_2$.

So the number of elements of a basis of $V$ is an invariant of $V$, not depending on the choice of the basis. This allows us to define the dimension of $V$.

Let $V$ be a $k$-vector space. Show that the following two statements are equivalent:

(i)
There exists a basis $B \subseteq V$ such that $B$ is finite.
(ii)
Every basis $B \subseteq V$ is finite.

Let $V$ be a $k$-vector space. We say that $V$ is finite-dimensional if there exists a finite basis (and hence all bases are finite by the previous exercise). In this case, define the dimension of $V$ as

$$ \dim_k V = \lvert B \rvert $$

where $B$ is a basis of $V$. This cardinality is independent of the choice of the basis $B$, so the dimension is well-defined.

Even if $B$ is an infinite set, we can make sense of $\dim V$ by its “cardinality”. We are going to say that $\lvert S_1 \rvert = \lvert S_2 \rvert$ if there exists a bijection between the two sets $S_1$ and $S_2$, and we are going to say that $\lvert S_1 \rvert \le \lvert S_2 \rvert$ if there exists an injective map $S_1 \hookrightarrow S_2$. What Schröder–Bernstein says is that $\lvert S_1 \rvert \le \lvert S_2 \rvert$ and $\lvert S_2 \rvert \le \lvert S_1 \rvert$ implies $\lvert S_1 \rvert = \lvert S_2 \rvert$. But in most cases, we are only going to worry about finite-dimensional vector spaces when talking about dimension.

For any nonnegative integer $n$, we have $\dim_k k^n = n$ because $e_1, \ldots, e_n$ forms a basis.

Let $V$ and $W$ be finite-dimensional $k$-vector spaces, and let $B_V$ and $B_W$ be bases for $V$ and $W$ respectively. Then the following statements are equivalent:

(i)
There exists an injective linear map $V \hookrightarrow W$.
(ii)
There exists a surjective linear map $W \twoheadrightarrow V$.
(iii)
$\dim_k V \le \dim_k W$.

For finite-dimensional vector spaces $V_1, V_2, \ldots, V_n$, show that

$$ \dim_k (V_1 \oplus V_2 \oplus \cdots \oplus V_n) = \dim_k V_1 + \dim_k V_2 + \cdots + \dim_k V_n. $$

Let $W \subseteq V$ be a subspace of a finite-dimensional vector space $V$. Show that $W$ and $V/W$ are also finite-dimensional and

$$ \dim_k V = \dim_k W + \dim_k (V/W). $$

Consider an exact sequence

$$ 0 \to V_0 \to V_1 \to V_2 \to \cdots \to V_n \to 0, $$

where each $V_i$ is a finite-dimensional vector space. Then show that

$$ \dim_k V_0 - \dim_k V_1 + \dim_k V_2 - \cdots + (-1)^n \dim_k V_n = 0. $$

It is thanks to this fact that the Euler characteristic behaves very well.

Let $V$ and $W$ be finite-dimensional vector spaces with $\dim_k V = \dim_k W$. Show that any injective linear $V \hookrightarrow W$ is an isomorphism. Similarly, show that any surjective linear $V \twoheadrightarrow W$ is an isomorphism. Find counterexamples to both statements when $V$ and $W$ are allowed to be infinite. (Hint: try shifting sequences around in $\mathbb{R}^{\oplus \mathbb{Z}_{\ge 0}}$.)

Let $A$ and $B$ be $n \times n$ square matrices with entries in a field $k$. Show that $AB = I$ if and only if $BA = I$. (Here, $I$ denotes the identity matrix, corresponding to $\id : k^n \to k^n$.)

Let $V$ and $W$ be finite-dimensional vector spaces. We define the rank of a linear map $f : V \to W$ as $\rank f = \dim_k (\im f)$. Show that $\rank f \le \min \lbrace \dim_k V, \dim_k W \rbrace $.

Let us also do some computations with finite-dimensional vector spaces.

Consider the linear map $T : \mathbb{R}^3 \to \mathbb{R}^3$ given by the matrix

$$ T = \begin{bmatrix} -2 & -1 & 0 \\ -1 & 0 & 1 \\ 0 & 1 & 2 \end{bmatrix}. $$

(a)
Find a basis of $\ker T$. What is $\dim_\mathbb{R} (\ker T)$?
(b)
Find a basis of $\im T$. What is $\dim_\mathbb{R} (\im T)$?
(c)
Find a basis of $\coker T$. What is $\dim_\mathbb{R} (\coker T)$?
(d)
Recall that there are short exact-sequences $0 \to \ker T \to \mathbb{R}^3 \to \im T \to 0$ and $0 \to \im T \to \mathbb{R}^3 \to \coker T \to 0$. Verify that $\dim \ker T + \dim \im T = 3$ and $\dim \im T + \dim \coker T = 3$.

Let $A_1, \ldots, A_5 \in \mathbb{R}^2$ be five points on the plane. Consider

$$ V = \lbrace \text{polynomials in } x \text{ and } y \text{ with coefficients in } \mathbb{R} \text{ and total degree} \le 2 \rbrace . $$

(For instance, $x^2 + xy + y + 2 \in V$ while $x y^2 \notin V$, because total degree of $x y^2$ is $3$.)

(a)
Show that $V$ is a vector space over $\mathbb{R}$, and compute its dimension.
(b)
Consider the map $\Phi : V \to \mathbb{R}^5$ given by $p(x, y) \mapsto (p(A_1), \ldots, p(A_5))$. Check that this map is linear.
(c)
Show that there exists a nonzero polynomial $p(x, y) \in V$ such that $\Phi(p) = 0$.
(d)
Conclude that there exists a conic (or two lines) that passes through all five points $A_1, \ldots, A_5$.

Let $a_0 < a_1 < \cdots < a_n$ be distinct real numbers. Consider the space

$$ V = \lbrace \text{polynomials in } x \text{ with coefficients in } \mathbb{R} \text{ and degree} \le n \rbrace . $$

Compute $\dim_\mathbb{R} V$. Consider the map

$$ V \to \mathbb{R}^{n+1}; \quad p(x) \mapsto (p(a_0), \ldots, p(a_n)). $$

Show that this linear map is an isomorphism. (You only have to show either injectivity or surjectivity. You can go both ways: for injectivity, you can use polynomial division, and for surjectivity, you can use Lagrange interpolation.)

Let $V$ be a vector space with $\dim_k V = n$. Show that there is a bijection (of sets)

$$ \begin{aligned} \lbrace \text{isomorphisms } k^n \to V \rbrace &\leftrightarrow \lbrace (v_1, \ldots, v_n) \in V^n : \lbrace v_1, \ldots, v_n \rbrace \text{ is a basis} \rbrace \\ f &\mapsto (f(e_1), \ldots, f(e_n)). \end{aligned} $$

In other words, picking an isomorphism $k^n \cong V$ is equivalent to picking a basis and then ordering it. We shall say that $(v_1, \ldots, v_n) \in V^n$ is an ordered basis if $\lbrace v_1, \ldots, v_n\rbrace $ is a basis.

Let $V$ and $W$ be vector spaces with $\dim_k V = n$ and $\dim_k W = m$. Consider a linear map $T : V \to W$. We would like to say that $T$ corresponds to an $m \times n$ matrix, but we cannot immediately say this because a matrix is a linear map $k^n \to k^m$. (The reason we want to write down a map as a matrix is because matrices are computable.) So what we do is choose ordered bases $B$ of $V$ and $C$ of $W$, and consider the corresponding isomorphisms $\varphi_B : k^n \to V$ and $\varphi_C : k^m \to W$. Then the composition

$$ {}_C[T]^B = \varphi_C^{-1} \circ T \circ \varphi_B : k^n \xrightarrow{\varphi_B} V \xrightarrow{T} W \xrightarrow{\varphi_C^{-1}} k^m $$

is an $m \times n$ matrix. (This is not standard notation, by the way.) We can also write down vectors $v \in V$ as $n \times 1$ column matrices:

$$ {}_B[v] = \varphi_B^{-1}(v) \in k^n. $$

Let $V, W$ be finite-dimensional vector spaces with ordered bases $B, C$. For a linear map $T : V \to W$, show that ${}_C[T v] = {}_C[T]^B {}_B[v]$ as matrices.

Let $V, W, U$ be finite-dimensional vector spaces with ordered bases $B, C, D$. For linear maps $T : V \to W$ and $S : W \to U$, show that ${}_D[S \circ T]^B = {}_D[S]^C {}_C[T]^B$.

Coordinate diagram for composing two linear maps.

Let $V$ be a finite-dimensional vector space and consider two bases $B$ and $B^\prime$. Consider the matrix ${}_B[\id]^{B^\prime}$ representing the identify map $\id_V : V \to V$, where the two $V$ are considered using different bases.

(a)
Show that ${}_B[\id]^B = I$ is the identity matrix and ${}_{B^\prime}[\id]^B {}_B[\id]^{B^\prime} = {}_B[\id]^{B^\prime} {}_{B^\prime}[\id]^B = I$, that is, changing $B$ and $B^\prime$ gives the inverse matrix.
(b)
If $W$ is another vector space with ordered bases $C, C^\prime$, and $T : V \to W$ is a linear map, show that ${}_{C^\prime}[T]^{B^\prime} = {}_{C^\prime}[\id]^C {}_C[T]^B {}_B[\id]^{B^\prime}$.
(c)
If $T : V \to V$ is a linear map, show that ${}_{B^\prime}[T]^{B^\prime} = P {}_B[T]^B P^{-1}$ where $P = {}_{B^\prime}[\id]^B$.

Consider the linear map $T : \mathbb{R}^2 \to \mathbb{R}^2$ given by the matrix

$$ T = \begin{bmatrix} 1 & -3 \\ 2 & 0 \end{bmatrix}. $$

Consider ordered bases $B = ((1, 2), (-1,-1))$ and $B^\prime = ((-1,0), (4,1))$ of $\mathbb{R}^2$.

(a)
Compute the matrix ${}_B[T]^B$.
(b)
Compute the matrix ${}_{B^\prime}[T]^{B^\prime}$.
(c)
Compute the matrix $P = {}_{B^\prime}[\id]^B$.
(d)
Verify that ${}_{B^\prime}[T]^{B^\prime} = P {}_B[T]^B P^{-1}$.