The notion of dimension will appear constantly throughout linear algebra and beyond. Finite-dimensional vector spaces are determined up to isomorphism by a single integer, their dimension. We establish this through a sequence of lemmas about the interplay between spanning lists and linearly independent lists.
Definition 4.7.1 (Finite-dimensional). A vector space is finite-dimensional if it has a finite spanning list, i.e., vectors with . Otherwise, is infinite-dimensional.
Our first result shows that every finite spanning list contains a basis.
Lemma 4.7.2 (Spanning lists contain bases). If span , then some sublist of is a basis of .
Proof. We construct a basis by removing redundant vectors one at a time.
If are linearly independent, they already form a basis. Otherwise, there is a nontrivial relation with some . Then So the list with removed still spans : in any linear combination of we can substitute this expression for .
Remove and repeat. Since the list is finite, the process terminates, and when it does, the remaining vectors are linearly independent and still span , so they form a basis. (If , we may end with the empty list, which is a basis of .) ∎
Corollary 4.7.3 (Finite-dimensional spaces have bases). Every finite-dimensional vector space has a finite basis.
4.7.2 Extending Linearly Independent Lists to Bases
The dual result shows that every linearly independent list can be enlarged to a basis.
Lemma 4.7.4 (Linearly independent lists extend to bases). Let be finite-dimensional and let be linearly independent. Then can be extended to a basis of . More precisely, if span , then appending suitable vectors among to gives a basis of .
Proof. Let span ; such a list exists because is finite-dimensional. For let We show by induction on that has a basis consisting of followed by some of . For , the list is independent and spans , so it is a basis.
Suppose is such a basis of . If , then and we keep . If , then is linearly independent by Lemma 4.6.6, and it spans , since contains and . Either way is a basis of of the required form.
Finally, , so is a basis of containing . ∎
4.7.3 The Exchange Lemma and Invariance of Dimension
The next lemma is the heart of the theory: it compares the lengths of independent lists and spanning lists. Its proof exchanges vectors of a spanning list, one at a time, for vectors of an independent list.
Lemma 4.7.5 (Exchange lemma). If are linearly independent in and span , then .
Proof. We show by induction on that and that, after renumbering the ’s, the list spans . For this is the hypothesis. Suppose it holds for some . Since the list spans , we can write If all the were zero (in particular, if and no ’s are left), then would be a linear combination of , contradicting the independence of the ’s. So , and after renumbering we may assume . Solving for , So this span contains , which span ; hence it is . This completes the induction, and the case gives . ∎
Theorem 4.7.6 (All bases have the same size). If has a basis with elements, then every basis of has exactly elements.
Proof. Let be a basis and another basis of . Any distinct elements of are linearly independent, and span , so by the exchange lemma. Hence is finite, with elements. Exchanging the roles of the two bases gives . ∎
Definition 4.7.7 (Dimension). The dimension of a finite-dimensional vector space , denoted or , is the number of elements of any basis of . By the theorem this does not depend on the basis. The empty set is a basis of the zero space, so . If is infinite-dimensional we write .
Corollary 4.7.8 (Independent and spanning lists in dimension ). Let .
- Every linearly independent list in has at most vectors, and every spanning list has at least vectors.
- A linearly independent list of vectors is a basis, and so is a spanning list of vectors.
Proof. (a) Apply the exchange lemma with a basis of as the spanning list, respectively as the independent list.
(b) By Lemma 4.7.4, an independent list of vectors extends to a basis, which has elements, so no vectors were added. By Lemma 4.7.2, a spanning list of vectors contains a basis, which has elements, so no vectors were removed. ∎
Corollary 4.7.9 (Classification of finite-dimensional spaces). Every vector space of dimension is isomorphic to . Two finite-dimensional vector spaces are isomorphic if and only if they have the same dimension.
Proof. Let be a basis of . The map is linear, injective by Proposition 4.6.5 and surjective because the span; so it is an isomorphism.
If is an isomorphism and is a basis of , then is a basis of . It spans, since every is for some , so . It is independent, since means , so by injectivity and all . Hence isomorphic spaces have the same dimension. Conversely, two spaces of dimension are both isomorphic to , hence to each other. ∎
Note. The isomorphism depends on the choice of basis, and different bases give different isomorphisms. Choosing a basis amounts to choosing coordinates: we represent by the column vector of its coordinates. Much of linear algebra consists in using coordinates when they help and avoiding them when they do not.
4.7.4 Subspaces of Finite-Dimensional Spaces
Proposition 4.7.10 (Subspaces of finite-dimensional spaces). Let be finite-dimensional and a subspace. Then is finite-dimensional and , with equality if and only if .
Proof. Let . By the exchange lemma, every linearly independent list in has at most vectors, since it is also independent in . Choose an independent list in of the largest possible length; then . It spans : if some were not in , then would be a longer independent list in by Lemma 4.6.6. So is a basis of , and .
If , the dimensions agree. If , a basis of is a linearly independent list of vectors in , hence a basis of by Corollary 4.7.8; so , and . ∎
Proposition 4.7.11 (Complements exist). Let be finite-dimensional and a subspace. Then there is a subspace with .
Proof. By Proposition 4.7.10, has a basis . Extend it to a basis of (Lemma 4.7.4) and let . Every is a linear combination of the and , so . If , then , so , and independence gives ; thus . ∎
A subspace with is called a complement of in . It is far from unique: in , every line through the origin other than is a complement of .
4.7.5 Dimension of Sums and Direct Sums
Theorem 4.7.12 (Dimension formula for sums). Let and be finite-dimensional subspaces of a vector space . Then is finite-dimensional and In particular, if the sum is direct, then .
Proof. The subspace of is finite-dimensional by Proposition 4.7.10. Let be a basis of . By Lemma 4.7.4, extend it to a basis of and to a basis of . We claim that is a basis of .
Spanning: Any is with and . Writing and in the bases above expresses as a linear combination of the listed vectors.
Independence: Suppose . Then Since also , it lies in , so for some scalars . Then , and since is a basis of , all . Now , and since is a basis of , all and vanish.
Thus . ∎
Corollary 4.7.13 (Recognizing a direct sum decomposition). Let be finite-dimensional and subspaces. Then if and only if and .
Proof. If , then and the formula gives . Conversely, under the two conditions the formula gives , so by Proposition 4.7.10. ∎
Proposition 4.7.14 (Dimension of a direct sum).
- If and each is finite-dimensional, then putting together bases of gives a basis of ; so .
- If are finite-dimensional, then .
Proof. (a) Let be a basis of . Every is a sum with , and each is a combination of ; so the combined list spans . If , set . Then , so every by independence of the , and then every by independence of the basis of .
(b) The product is the internal direct sum of the subspaces , each isomorphic to and hence of dimension (Corollary 4.7.9). Apply (a). Explicitly, if is a basis of , then the vectors , with in position , form a basis of . ∎
Example 4.7.15. Dimensions:
- : the standard basis has elements.
- : the monomials form a basis.
- is infinite-dimensional: any finite list of polynomials has bounded degree, so its span contains no polynomial of larger degree.
- and are infinite-dimensional, since they contain the infinite-dimensional subspace , respectively the eventually zero sequences (Proposition 4.7.10).
Question 4.7.16.
- Show that the monomials are linearly independent in but do not span it.
- Suppose has a countable spanning set. Show that every linearly independent subset of is countable.
- Show that contains an uncountable linearly independent subset. Conclude that has no countable spanning set, and in particular no countable basis.
Show solution
(a) A linear combination of finitely many distinct monomials is a polynomial, which is only if all its coefficients are ; so the monomials are independent. For the same reason their span is , and a power series such as , with infinitely many nonzero coefficients, is not in it.
(b) Let span (a finite spanning set can be padded with zeros) and put . Every vector is a finite linear combination of the , so . Let be linearly independent. Any distinct elements of form an independent list in a space spanned by vectors, so by the exchange lemma has at most elements. Hence is a countable union of finite sets, and it is countable: list the elements of , then the new elements of , and so on.
(c) Let be the set of finite strings of ’s and ’s, including the empty string. It is countable, since there are strings of each length ; fix a bijection . For an infinite – sequence , let be the set of codes of the initial segments of , and let . Each is infinite, since initial segments of different lengths are different strings. If and the two sequences first differ at position , their common initial segments are those of length less than , so is finite. In particular .
The are linearly independent. Suppose with distinct . The set is infinite, since it is obtained from the infinite set by removing the finite sets ; for in it, the coefficient of in is . So , and likewise every .
An infinite – sequence is a function on the countably infinite set , and by Cantor’s theorem (Theorem 1.7.7 and the discussion after it). So the set of infinite – sequences is uncountable, and since is injective, is an uncountable linearly independent subset of . By (b), has no countable spanning set.
That has a basis at all follows from the theorem that every vector space has a basis, a consequence of Zorn’s lemma that we do not prove. The proof of that theorem gives no way of writing a basis down.