Vector spaces and linear maps

1, the exchange bound. Let $S = \{v_1, \dots, v_n\}$ span $V$ and let $W \subseteq V$ have more than $n$ elements. A set with a dependent subset is itself dependent, the same relation serving both, so it is enough to produce a dependency among $n+1$ distinct members $w_1, \dots, w_{n+1}$ of $W$. Suppose instead that $\{w_1, \dots, w_{n+1}\}$ is independent.

We show by induction on $k$ that for $k = 0, 1, \dots, n$ there is an index set $J_k \subseteq \{1, \dots, n\}$ with $n - k$ elements such that $\{w_1, \dots, w_k\} \cup \{v_j : j \in J_k\}$ spans $V$. For $k = 0$ take $J_0 = \{1, \dots, n\}$, where the assertion is the hypothesis on $S$.

Assume it for some $k$ with $0 \le k \le n - 1$, so that $J_k$ has $n - k \ge 1$ elements, and expand the next of the $w$'s in the current spanning set:

Not every $b_j$ can vanish: otherwise $w_{k+1} - \sum_{i \le k} a_i w_i = 0$ would be a relation among the distinct vectors $w_1, \dots, w_{k+1}$ whose coefficient at $w_{k+1}$ is $1$, contradicting independence. Fix $m \in J_k$ with $b_m \neq 0$ and solve:

So $v_m$ lies in the span of $T = \{w_1, \dots, w_{k+1}\} \cup \{v_j : j \in J_k \setminus \{m\}\}$. Every other member of the old spanning set lies in $T$ itself, so $\operatorname{span} T$ contains the old spanning set and hence contains its span, which is $V$. Taking $J_{k+1} = J_k \setminus \{m\}$ completes the induction step.

At $k = n$ the set $J_n$ is empty and $\{w_1, \dots, w_n\}$ spans $V$. Then $w_{n+1} = \sum_{i \le n} c_i w_i$ for some scalars, which is again a nontrivial relation among $w_1, \dots, w_{n+1}$. This contradiction shows $\{w_1, \dots, w_{n+1}\}$ is dependent, and with it $W$.

2, a finite spanning set contains a basis. Let $S$ be finite with $\operatorname{span} S = V$. The subsets of $S$ that span $V$ are finite in number and include $S$, so one of them, $B$, has fewest elements. If $B$ were dependent there would be distinct $b_1, \dots, b_k \in B$ and scalars $a_i$, not all zero, with $\sum_i a_i b_i = 0$; choosing $a_j \neq 0$ gives $b_j = -a_j^{-1}\sum_{i \neq j} a_i b_i$, so $b_j \in \operatorname{span}(B \setminus \{b_j\})$. Then $B \setminus \{b_j\}$ has every member of $B$ in its span, so it spans $V$ as well, and it is smaller than $B$ - impossible. Hence $B$ is independent and spans: a basis. In particular a space spanned by finitely many vectors has a finite basis and is finite-dimensional. (For $V = \{0\}$ the smallest spanning subset is $\varnothing$, which is independent with $\operatorname{span}\varnothing = \{0\}$.)

3, invariance of dimension. Let $V$ be finite-dimensional and let $E$ be a finite basis, with $n$ elements. Since $E$ spans $V$, part 1 makes every subset of $V$ with more than $n$ elements dependent; a basis is independent, so no basis has more than $n$ elements, and in particular every basis is finite. If $F$ is a basis with $m$ elements then $m \le n$; exchanging the roles of $E$ and $F$ in the same sentence gives $n \le m$. So all bases have $n$ elements, and $\dim_{\mathbb{F}} V = n$ is well defined. Finally $\varnothing$ is a basis of $\{0\}$, so $\dim_{\mathbb{F}}\{0\} = 0$; and if $\dim_{\mathbb{F}} V = 0$ then some basis is empty, whence $V = \operatorname{span}\varnothing = \{0\}$.

4, coordinates. The basis spans, so $v$ is a linear combination of distinct basis vectors; adding the missing basis vectors with coefficient $0$ writes $v = \sum_{i=1}^{n} x_i e_i$. If also $v = \sum_i y_i e_i$ then $\sum_i (x_i - y_i) e_i = 0$. The entries of an ordered basis are distinct, so $(e_1, \dots, e_n)$ is an independent tuple, and therefore every coefficient $x_i - y_i$ vanishes.

5, enlarging an independent set. Let $\dim_{\mathbb{F}} V = n$ and let $A \subseteq V$ be independent; by part 1, $A$ has at most $n$ elements. If $\operatorname{span} A \neq V$, choose $v \in V \setminus \operatorname{span} A$. Then $A \cup \{v\}$ is independent: in a relation $\sum_i a_i u_i + c v = 0$ with distinct $u_i \in A$, the coefficient $c$ must vanish, since otherwise $v = -c^{-1}\sum_i a_i u_i$ would lie in $\operatorname{span} A$, and with $c = 0$ independence of $A$ kills the remaining coefficients. The enlarged set has one more element, and sizes cannot exceed $n$, so after at most $n - |A|$ such steps the set spans $V$ and is a basis containing $A$.

5, subspaces. Let $W \subseteq V$ be a subspace. An independent subset of $W$ is independent in $V$, hence has at most $n$ elements, so among the independent subsets of $W$ there is one, $A$, of greatest size. It spans $W$: otherwise the previous paragraph, applied inside $W$ to a vector of $W \setminus \operatorname{span} A$, would produce a larger independent subset of $W$. So $W$ is finite-dimensional with $\dim_{\mathbb{F}} W = |A| \le n$. If $\dim_{\mathbb{F}} W = n$, take a basis $B$ of $W$: it is an independent subset of $V$ with $n$ elements, so enlarging it to a basis of $V$ adds nothing, every basis of $V$ having exactly $n$ elements by part 3; hence $B$ is a basis of $V$ and $W = \operatorname{span} B = V$. The converse is immediate.

6, existence of a basis. Partially order the independent subsets of $V$ by inclusion. The collection is nonempty, containing $\varnothing$. A chain $\mathcal{C}$ of independent sets has its union $U$ as an upper bound, and $U$ is independent: a relation involves finitely many distinct vectors of $U$, each lying in some member of $\mathcal{C}$, and since $\mathcal{C}$ is totally ordered the largest of those finitely many members contains all of them, so independence there forces the coefficients to vanish. By Zorn's lemma there is a maximal independent $B \subseteq V$. It spans: a vector outside $\operatorname{span} B$ could be adjoined with independence preserved, by the computation in part 5, contradicting maximality. So $B$ is a basis. $\square$

Throughout, write $A = [T]_{F\leftarrow E}$, and recall that every $v\in V$ has one and only one expansion $v = \sum_j v_j e_j$ because $E$ is a basis (Vector spaces and bases).

Step 0: the matrix acts on components. Apply $T$ to that expansion. Linearity, used $n-1$ times, gives $Tv = \sum_j v_j\,Te_j$, and inserting $Te_j = \sum_i A_{ij}f_i$ and collecting the coefficient of each $f_i$ gives

Since the expansion in $F$ is unique, the $i$th component of $Tv$ is $\sum_j A_{ij}v_j$, which is the identity $[Tv]_F = A[v]_E$ asserted in the definition. Every part below rests on it.

Part 1, uniqueness. If $S,T\in L(V,W)$ satisfy $Se_j = Te_j$ for all $j$, then for any $v = \sum_j v_j e_j$ linearity gives $Sv = \sum_j v_j Se_j = \sum_j v_j Te_j = Tv$, so $S = T$. Only linearity and the spanning half of "basis" were used here.

Part 1, existence. Given $w_1,\dots,w_n\in W$, define $T$ by $Tv = \sum_j v_j w_j$, where $(v_1,\dots,v_n)$ are the components of $v$ in $E$. This is a well-defined map because those components exist and are unique. It is linear because components are: the components of $av + bv'$ are $av_j + bv'_j$, whence $T(av+bv') = \sum_j (av_j+bv'_j)w_j = aTv + bTv'$. Finally $e_j$ has components $\delta_{kj}$, so $Te_j = w_j$.

Part 2. Write $\Phi(T) = [T]_{F\leftarrow E}$. It is linear: $(aS+bT)e_j = a\,Se_j + b\,Te_j$ by the definition of the operations on $L(V,W)$, and expanding both sides in $F$ and using uniqueness of the expansion gives $\Phi(aS+bT) = a\Phi(S)+b\Phi(T)$ entry by entry. It is injective: if $\Phi(T) = 0$ then $Te_j = 0$ for every $j$, and the zero map also sends every $e_j$ to $0$, so $T = 0$ by the uniqueness half of part 1. It is surjective: given $A\in M_{m\times n}(\mathbb{F})$, apply the existence half of part 1 to $w_j = \sum_i A_{ij}f_i$; the resulting $T$ has $\Phi(T) = A$. Hence $\Phi$ is an isomorphism. The $mn$ matrices with a single entry $1$ and the rest $0$ are a basis of $M_{m\times n}(\mathbb{F})$ — they span it, since $A = \sum_{i,j}A_{ij}$ times the $(i,j)$ one, and a vanishing combination has every coefficient zero because each coefficient is an entry of the combination — so $\dim_{\mathbb{F}}M_{m\times n}(\mathbb{F}) = mn$, and an isomorphism preserves dimension.

Part 3. Let $B = [S]_{G\leftarrow F}$, so $Sf_i = \sum_k B_{ki}g_k$. Then

the second equality by linearity of $S$ and the last by exchanging two finite sums. The bracket is $(BA)_{kj}$, so by uniqueness of the expansion in $G$ the matrix of $S\circ T$ is $BA$, which is the claim. For the identity, $\mathrm{id}_V e_j = e_j = \sum_i \delta_{ij}e_i$, so $[\mathrm{id}_V]_E = I_n$.

Part 4, forwards. Let $T$ be an isomorphism, so $T^{-1}$ exists and is linear. Apply part 3 to $T^{-1}\circ T = \mathrm{id}_V$ and to $T\circ T^{-1} = \mathrm{id}_W$:

With $n = m$ these say that $A$ is invertible with $A^{-1} = [T^{-1}]_{E\leftarrow F}$.

Part 4, backwards. Let $A$ be invertible. By the surjectivity shown in part 2, applied to the pair of bases $F$ and $E$, there is an $S\in L(W,V)$ with $[S]_{E\leftarrow F} = A^{-1}$. Part 3 gives $[S\circ T]_E = A^{-1}A = I_n = [\mathrm{id}_V]_E$ and $[T\circ S]_F = AA^{-1} = I_m = [\mathrm{id}_W]_F$, so by the injectivity shown in part 2 we get $S\circ T = \mathrm{id}_V$ and $T\circ S = \mathrm{id}_W$. Hence $T$ is bijective, with inverse $S$. The hypothesis $n=m$ entered when $A$ was required to be square. $\square$

The transition matrix is the matrix of the identity, and is invertible. The defining relation $\tilde e_j = \sum_i P_{ij}e_i$ says exactly that $\mathrm{id}_V\,\tilde e_j$ expands in $E$ with coefficients $P_{ij}$, that is,

Since $\mathrm{id}_V$ is an isomorphism and both bases have the same length $n$, part 4 of the previous statement makes $P$ invertible, with $P^{-1} = [\mathrm{id}_V]_{\tilde E\leftarrow E}$.

Part 1. By Step 0 of the previous proof applied to $\mathrm{id}_V$ with domain basis $\tilde E$ and codomain basis $E$,

and multiplying on the left by $P^{-1}$ gives the second form. The contrast with the display defining $P$ is the whole content of the last sentence of part 1: the same matrix $P$ sends new basis vectors to old-basis data and old components to new components only after inversion.

Part 2. Write $T = \mathrm{id}_W\circ T\circ \mathrm{id}_V$ and read each factor in the bases that make the composition rule applicable: