Bases and Dimension — Linear Algebra

Bases for a vector space. The concepts of generating sets and linearly independent sets were introduced in the preceding two sections. We now seek a generating set for an entire vector space that contains no redundancy. This leads to the concept of a basis for a vector space.

Definition 1.7.1. Let $$V$$ be a vector space. A subset $$S$$ of $$V$$ is called a basis for $$V$$ if $\operatorname{span}(S)=V$ and $$S$$ is linearly independent.

Example 1.7.2. The empty set $\varnothing$ is a basis for the zero vector space, because $\operatorname{span}(\varnothing)=\{0_V\}$ and $\varnothing$ is linearly independent.

Example 1.7.3. In the vector space $$F_n[x]$,$ the set $\{x^k: 0\le k\le n\}$ is a basis, called the standard basis for $$F_n[x]$.$ While $$F_n[x]$$ has a finite basis, the infinite set $\{x^k: k\in \mathbb Z_{\ge 0}\}$ is a basis for $$F[x]$.$

The definition of a basis requires a set to have two properties at the same time: generating and linear independence. The next theorem shows that extremeizing only one of the two conditions motivating the definition is sufficient to characterize a basis. Here, minimality and maximality are understood with respect to set inclusion.

Theorem 1.7.4. Let $$B$$ be a subset of a vector space $$V$.$ The following are equivalent:

The set $$B$$ is a basis for $$V$.$
The set $$B$$ is a minimal generating set for $$V$.$
The set $$B$$ is a maximal linearly independent subset of $$V$.$

Proof. Definition 1.6.2 immediately shows that the conditions (1) and (2) are equivalent. We now show that the conditions (1) and (3) are equivalent. If $$B$$ is a basis for $$V$,$ then $\operatorname{span}(B) = V$ and $$B$$ is linearly independent. By Theorem 1.6.5, every superset of $$B$$ not equal to $$B$$ is linearly dependent. Hence $$B$$ is maximal. Conversely, suppose that $$B$$ is a maximal linearly independent subset of $$V$.$ Then, by Theorem 1.6.5, $v\in \operatorname{span}(B)$ for all $$v\in V\setminus B$.$ Hence $$V\setminus B\subseteq \operatorname{span}(B)$.$ Since we also have $$B\subseteq \operatorname{span}(B)$,$ $$\operatorname{span}(B)=V$.$ $\square$

A basis provides an unambiguous representation of every vector. Generating guarantees that a representation exists, while linear independence ensures the uniqueness of that representation.

Theorem 1.7.5. Let $$V$$ be a vector space over a field $$F$,$ and let $$B\subseteq V$.$ Then, $$B$$ is a basis for $$V$$ if and only if every vector $v\in V$ has a unique representation in terms of $$B$.$

Proof. Suppose that $$B$$ is a basis for $$V$.$ Since $$\operatorname{span}(B)=V$,$ $v\in V$ implies $$v\in \operatorname{span}(B)$.$ By Proposition 1.4.14, $$v$$ has a representation in terms of $$B$.$ Since $$B$$ is linearly independent, Corollary 1.6.7 guarantees that this representation is unique. We now prove the converse. Since every $v\in V$ has a representation in terms of $$B$,$ $v\in\operatorname{span}(B)$ by Proposition 1.4.14. Hence $$\operatorname{span}(B)=V$.$ Since every vector has at most one representation in terms of $$B$,$ Corollary 1.6.7 implies that $$B$$ is linearly independent. Therefore $$B$$ is a basis for $$V$.$ $\square$

Definition 1.7.6. Let $$B$$ be a basis for a vector space $$V$$ over a field $$F$.$ For each $$v\in V$,$ the unique representation $c_v^B\colon B\to F$ of $$v$$ in terms of $$B$$ is called the coordinate function of $$v$$ with respect to $$B$.$ The associated coordinate map is the function

\[\tau_B\colon V\longrightarrow F^{(B)}, \qquad v\longmapsto c_v^B,\]

where $F^{(B)}$ denotes the set of all finitely supported functions from $$B$$ to $$F$.$

Theorem 1.7.7. Let $$V$$ be a vector space, and let $S\subseteq V$ be a finite generating set for $$V$.$ Then there exists a subset $B\subseteq S$ that is a basis for $$V$.$ Hence $$V$$ has a finite basis.

Proof. Let $\mathcal C$ be the collection of all subsets of $$S$$ that generate $$V$.$ Since $$S$$ is a finite generating set for $$V$,$ $\mathcal C$ is nonempty and finite. Hence there exists a minimal element in $$\mathcal C$;$ let $$B$$ be that element. By Theorem 1.7.4, $$B$$ is a basis for $$V$.$ $\square$

Theorem 1.7.7 guarantees the existence of a finite basis for every finitely generated vector space. However, it remains to determine whether different bases must have the same cardinality. To establish this invariance, it suffices to show that a finite linearly independent set cannot have more elements than a finite generating set. From a set-theoretic perspective, one way to establish this inequality is to construct an injection from the linearly independent set into the generating set. The exchange property suggests how such an injection might be obtained: introduce the linearly independent vectors one at a time, each time removing a distinct element of the original generating set without losing the generating property. If these replacements can always be carried out, the removed elements form a subset of the generating set with the same cardinality as the linearly independent set. The Steinitz¹ replacement theorem establishes this stronger replacement principle, without requiring the generating set to be finite.

Theorem 1.7.8 (Steinitz replacement theorem). Let $$V$$ be a vector space, let $S\subseteq V$ be a generating set for $$V$,$ and let $L\subseteq V$ be a finite linearly independent set. Then there exists a subset $R\subseteq S$ such that

\[|R|=|L| \quad \text{and} \quad \operatorname{span}((S\setminus R)\cup L)=V.\]

Proof. We proceed by induction on $$n=|L|$.$ If $$n=0$,$ take $$R=\varnothing$.$ Then $$|R|=|L|=0$$ and $$\operatorname{span}((S\setminus R)\cup L)=\operatorname{span}(S)=V$.$ Now suppose that the statement holds for $$n=k$.$ Let $$|L|=k+1$$ and choose $$\ell\in L$.$ Put $$L'=L\setminus\{\ell\}$.$ By Proposition 1.6.4(2), $$L'$$ is linearly independent, so the induction hypothesis gives $R'\subseteq S$ such that

\[|R'|=|L'|=k \quad \text{and} \quad \operatorname{span}((S\setminus R')\cup L')=V.\]

Put $$A=S\setminus R'$.$ Since $$L$$ is linearly independent, Theorem 1.6.5 gives $$\ell\notin\operatorname{span}(L')$.$ On the other hand, $$\ell\in\operatorname{span}(A\cup L')$.$ By Proposition 1.5.11, there exists a finite subset $T\subseteq A$ such that $$\ell\in\operatorname{span}(T \cup L')$.$ Among the subsets of $$T$$ satisfying this condition, choose a minimal one; denote it by $$T_0$.$ Since $$\ell\notin\operatorname{span}(L')$,$ the set $$T_0$$ is nonempty. Choose $t\in T_0$ and put $$C=(T_0\setminus\{t\})\cup L'$.$ By the minimality of $$T_0$,$

\[\ell\in\operatorname{span}(C\cup\{t\})\setminus\operatorname{span}(C).\]

The exchange property therefore gives

\[\operatorname{span}(C\cup\{t\})=\operatorname{span}(C\cup\{\ell\}).\]

In particular, since $$C\cup\{\ell\}\subseteq(A\setminus\{t\})\cup L$,$ we have

\[t\in\operatorname{span}(C\cup\{\ell\})\subseteq\operatorname{span}((A\setminus\{t\})\cup L).\]

All other vectors of $A\cup L'$ already belong to $$(A\setminus\{t\})\cup L$.$ It therefore follows that

\[\operatorname{span}((A\setminus\{t\})\cup L)=V.\]

Now put $$R=R'\cup\{t\}$.$ Since $$t\in A=S\setminus R'$,$ we have $R\subseteq S$ and

\[|R|=|R'|+1 = k+1 = |L|.\]

Moreover, $$S\setminus R=A\setminus\{t\}$,$ so

\[\operatorname{span}((S\setminus R)\cup L)=V.\tag*{$\square$}\]

The main purpose of the proof was to replace an element of $$A$$ with $$\ell$.$ By taking a minimal subset of $$A$$ indispensable for generating $$\ell$,$ we could construct a local situation in which the replacement is justified. From the conclusion of this theorem, we have the cardinality inequality sought above: a finite linearly independent set cannot have more elements than a generating set. Since every basis is both linearly independent and generating, this inequality suggests a way to compare the cardinalities of two bases by reversing their roles.

Corollary 1.7.9. Let $$V$$ be a vector space that admits a finite basis. Then every basis for $$V$$ is finite, and has the same cardinality.

Proof. Let $$B$$ be a finite basis for $$V$,$ and let $$C$$ be any basis for $$V$.$ Suppose that $$|C|>|B|$.$ Then there exists a finite subset $L\subseteq C$ such that $$|L|=|B|+1$.$ Since $$L$$ is linearly independent and $$B$$ generates $$V$,$ the Steinitz replacement theorem gives a subset $R\subseteq B$ such that

\[|R|=|L|=|B|+1,\]

contrary to $$R\subseteq B$.$ Hence $$|C|\le |B|$,$ so $$C$$ is finite. Conversely, since $$B$$ is finite and linearly independent and $$C$$ generates $$V$,$ the Steinitz replacement theorem gives a subset $S\subseteq C$ such that $$|S|=|B|$.$ Therefore $$|B|\le |C|$.$ Combining the two inequalities, we obtain $$|B|=|C|$.$ $\square$

The dimension of a vector space. Although the choice of a basis is generally not unique, its cardinality is determined by the vector space itself. This allows us to assign a well-defined numerical invariant to every finitely generated vector space, measuring the number of independent generators needed to describe it.

Definition 1.7.10. Let $$V$$ be a vector space over a field $$F$.$ We say that $$V$$ is finite-dimensional if it admits a finite basis. In this case, the dimension of $$V$,$ denoted by $\dim_F V$ or simply $$\dim V$,$ is defined by

\[\dim V=|B|,\]

where $$B$$ is any basis for $$V$.$ If $$V$$ admits no finite basis, then $$V$$ is said to be infinite-dimensional.

The dimension of a vector space is defined as the cardinality of a basis, but its significance extends beyond bases themselves. In a finite-dimensional vector space, dimension provides an upper bound on the cardinalities of linearly independent sets and a lower bound on those of generating sets. Both bounds are attained by bases.

Theorem 1.7.11. Let $$V$$ be a finite-dimensional vector space with $$\dim V=n$.$

If $S\subseteq V$ is linearly independent, then $$S$$ is finite and $$|S|\le n$.$
If $S\subseteq V$ generates $$V$,$ then $$|S|\ge n$.$

Proof. Let $B\subseteq V$ be a basis for $$V$.$ Then $$|B|=n$$ by Definition 1.7.10. Suppose that $$S$$ is linearly independent and $$|S|>n$.$ Choose $S_0\subset S$ such that $$|S_0|=n+1$.$ Since $$S_0$$ is finite and linearly independent, there exists a subset $$B_0$$ of $$B$$ with $$|B_0|=n+1$$ by the Steinitz replacement theorem. This contradicts the fact that $$|B|=n$.$ If $$S$$ generates $$V$,$ then there exists $S_0\subseteq S$ such that $$|S_0|=|B|$$ by the Steinitz replacement theorem. Therefore $$|S|\ge |S_0| =|B|=n$.$ $\square$

Theorem 1.7.4 characterizes bases in terms of minimality and maximality with respect to set inclusion. In a finite-dimensional vector space, dimension provides a numerical counterpart to these characterizations. In particular, if a subset has cardinality equal to the dimension of the space, either the generating property or linear independence alone is sufficient to guarantee that it is a basis.

Corollary 1.7.12. Let $$V$$ be a finite-dimensional vector space with $$\dim V=n$,$ and let $S\subseteq V$ satisfy $$|S|=n$.$ Then the following are equivalent:

The set $$S$$ is a basis for $$V$.$
The set $$S$$ generates $$V$.$
The set $$S$$ is linearly independent.

Proof. If $$S$$ is a basis for $$V$,$ then $$S$$ is a linearly independent set that generates $$V$$ by Definition 1.7.1. Suppose that $$S$$ generates $$V$.$ If $T\subseteq S$ generates $$V$,$ then $|T|\ge n$ by Theorem 1.7.11(2). Since $$|S|=n=|T|$,$ we have $$T=S$,$ so $$S$$ is a minimal generating set. By Theorem 1.7.4, $$S$$ is a basis for $$V$.$ Similarly, if $$S$$ is linearly independent, then $$S$$ is a maximal linearly independent set by Theorem 1.7.11(1). Hence $$S$$ is a basis for $$V$$ by Theorem 1.7.4. $\square$

Theorem 1.7.13. Let $$V$$ be a finite-dimensional vector space, and let $S\subseteq V$ be linearly independent. Then there exists a basis $$B$$ for $$V$$ such that $$S\subseteq B$.$

Proof. Let $\dim V = n$ and let $$B$$ be a basis for $$V$.$ Since $$S$$ is linearly independent, $$S$$ is finite by Theorem 1.7.11(1). By the Steinitz replacement theorem, there exists $B_0\subseteq B$ such that

\[\operatorname{span}((B\setminus B_0)\cup S) =V.\]

Put $$T=(B\setminus B_0)\cup S$.$ Then $$|T|\le n$.$ Since $$T$$ generates $$V$,$ $|T|\ge n$ by Theorem 1.7.11(2), so $$|T|=n$.$ By Corollary 1.7.12, $$T$$ is a basis for $$V$,$ and $$T\supseteq S$.$ $\square$

Together, Theorems 1.7.7 and 1.7.13 reveal two complementary ways of obtaining a basis in a finite-dimensional vector space: a linearly independent set can be extended to a basis by adjoining vectors, while a generating set can be reduced to a basis by removing redundant vectors.

Theorem 1.7.14. Let $$V$$ be a finite-dimensional vector space, and let $$W$$ be a subspace of $$V$.$ Then $$W$$ is finite-dimensional and

\[\dim W\le\dim V.\]

Moreover, equality holds if and only if $$W=V$.$

Proof. Let $$\dim V= n$.$ By Theorem 1.7.11, every linearly independent subset of $$V$$ has cardinality less than or equal to $$n$.$ Since $$W\subseteq V$,$ we can define

\[\mathcal N = \{|S|:S\subseteq W \text{ is linearly independent}\}.\]

Since $$0\in \mathcal N$,$ the set $\mathcal N$ is nonempty. Furthermore, $\mathcal N$ is finite, since $$\mathcal N\subseteq \{0,1,\ldots,n\}$.$ Therefore there is a maximal element of $$\mathcal N$;$ denote it by $$m$.$ Then, we have a linearly independent subset $$B$$ of $$W$$ with $$|B|=m$.$ If $$\operatorname{span}(B)\ne W$,$ then there is $$w\in W\setminus\operatorname{span}(B)$.$ By Theorem 1.6.5, $B\cup \{w\}$ is linearly independent and its cardinality is $$m+1$,$ which contradicts the fact that $$m$$ is a maximum of $$\mathcal N$.$ Therefore $$B$$ generates $$W$$ so it is a basis for $$V$.$ It follows that

\[\dim W = |B| = m\le n = \dim V.\]

If $$\dim W = \dim V = n$,$ then $$B$$ is also a basis for $$V$$ by Corollary 1.7.12. Hence $$W=\operatorname{span}(B)=V$.$ The converse is trivial. $\square$

In the term the Steinitz replacement theorem, “Steinitz” refers to the German mathematician Ernst Steinitz (1871–1928). He was an important figure in the development of modern abstract algebra, especially field theory. His 1910 paper Algebraische Theorie der Körper (“Algebraic Theory of Fields”) gave a systematic abstract treatment of fields and introduced or developed concepts that are now standard, such as prime fields, algebraic closure, separability, and transcendence degree. In English, the usual anglicized pronunciation of his surname is /ˈstaɪnɪts/, whereas the German pronunciation begins with the sound /ʃ/, approximately /ˈʃtaɪnɪts/. ↩