1.7* Maximal Linearly Independent Subsets – Linear Algebra, 5th Edition

1.7* Maximal Linearly Independent Subsets

In this section, several significant results from Section 1.6 are extended to infinite-dimensional vector spaces. Our principal goal here is to prove that every vector space has a basis. This result is important in the study of infinite-dimensional vector spaces because it is often difficult to construct an explicit basis for such a space. Consider, for example, the vector space of real numbers over the field of rational numbers. There is no obvious way to construct a basis for this space, and yet it follows from the results of this section that such a basis does exist.

The difficulty that arises in extending the theorems of the preceding section to infinite-dimensional vector spaces is that the principle of mathematical induction, which played a crucial role in many of the proofs of Section 1.6, is no longer adequate. Instead, an alternate result called the Hausdorff maximal principle is needed. Before stating this principle, we need to introduce some terminology.

Definition.

Let F be a family of sets. A member M of F is called maximal (with respect to set inclusion) if M is contained in no member of F other than M itself.

Example 1

Let F be the family of all subsets of a nonempty set S. (This family F is called the power set of S.) The set S is easily seen to be a maximal element of F.

Example 2

Let S and T be disjoint nonempty sets, and let F be the union of their power sets. Then S and T are both maximal elements of F.

Example 3

Let F be the family of all finite subsets of an infinite set S. Then F has no maximal element. For if M is any member of F and S is any element of S that is not in M, then M{s} is a member of F that contains M as a proper subset.

Definition.

A collection of sets C is called a chain (or nest or tower) if for each pair of sets A and B in C, either AB or BA.

Example 4

For each positive integer n let An={1, 2, , n}. Then the collection of sets c={An: n=1, 2, 3, ...} is a chain. In fact, AmAn if and only if mn.

With this terminology we can now state the Hausdorff maximal principle.

Hausdorff Maximal Principle.4Let F be a family of sets. If, for each chain cF, there exists a member of F that contains all the members of C, then F contains a maximal member.

Because the Hausdorff maximal principle guarantees the existence of maximal elements in a family of sets satisfying the hypothesis above, it is useful to reformulate the definition of a basis in terms of a maximal property. In Theorem 1.12, we show that this is possible; in fact, the concept defined next is equivalent to a basis.

Definition.

Let S be a subset of a vector space V. A maximal linearly independent subset of S is a subset B of S satisfying both of the following conditions.

  1. (a) B is linearly independent.

  2. (b) The only linearly independent subset of S that contains B is B itself.

Example 5

Example 2 of Section 1.4 shows that

{x32x25x3, 3x35x24x9}

is a maximal linearly independent subset of

S={2x32x2+12x6, x32x25x3, 3x35x24x9}

in P3(R). In this case, however, any subset of S consisting of two polynomials is easily shown to be a maximal linearly independent subset of S. Thus maximal linearly independent subsets of a set need not be unique.

A basis β for a vector space V is a maximal linearly independent subset of V, because

  1. β is linearly independent by definition.

  2. If vV and vβ, then β{v} is linearly dependent by Theorem 1.7 (p. 40) because span(β)=V.

Our next result shows that the converse of this statement is also true.

Theorem 1.12.

Let V be a vector space and S a subset that generates V. If β is a maximal linearly independent subset of S , then β is a basis for V.

Proof. Let β be a maximal linearly independent subset of S. Because β is linearly independent, it suffices to prove that β generates V. We claim that Sspan(β), for otherwise there exists vS such that vspan(β). Since Theorem 1.7 (p. 40) implies that β{v} is linearly independent, we have contradicted the maximality of β. Therefore Sspan(β). Because span(S)=V, it follows from Theorem 1.5 (p. 31) that span(β)=V.

Thus a subset of a vector space is a basis if and only if it is a maximal linearly independent subset of the vector space. Therefore we can accomplish our goal of proving that every vector space has a basis by showing that every vector space contains a maximal linearly independent subset. This result follows immediately from the next theorem.

Theorem 1.13.

Let S be a linearly independent subset of a vector space V. There exists a maximal linearly independent subset of V that contains S.

Proof. Let F denote the family of all linearly independent subsets of V containing S. To show that F contains a maximal element, we show that if C is a chain in F, then there exists a member U of F containing each member of C. If C is empty, take U=S. Otherwise take U equal to the union of the members of C. Clearly U contains each member of C, and so it suffices to prove that UF (i.e., that U is a linearly independent subset of V that contains S). Because each member of C is a subset of V containing S, we have SUV. Thus we need only prove that U is linearly independent. Let u1, u2, , un be in U and a1, a2, , an be scalars such that a1u1+a2u2++anun=0. Because uiU for i=1, 2, , n, there exists a set Ai in C such that uiAi. But since C is a chain, one of these sets, say Ak, contains all the others. Thus uiAk for i=1, 2, , n. However, Ak is a linearly independent set; so a1u1+a2u2++anun=0 implies that a1=a2==an=0. It follows that U is linearly independent.

The Hausdorff maximal principle implies that F has a maximal element. This element is easily seen to be a maximal linearly independent subset of V that contains S.

Corollary.

Every vector space has a basis.

It can be shown, analogously to Corollary 1 of the replacement theorem (p. 47), that every basis for an infinite-dimensional vector space has the same cardinality. (Sets have the same cardinality if there is a one-to-one and onto mapping between them.) (See, for example, N. Jacobson, Lectures in Abstract Algebra, vol. 2, Linear Algebra, D. Van Nostrand Company, New York, 1953, p. 240.)

Exercises 47 extend other results from Section 1.6 to infinite-dimensional vector spaces.

Exercises

  1. Label the following statements as true or false.

    1. (a) Every family of sets contains a maximal element.

    2. (b) Every chain contains a maximal element.

    3. (c) If a family of sets has a maximal element, then that maximal element is unique.

    4. (d) If a chain of sets has a maximal element, then that maximal element is unique.

    5. (e) A basis for a vector space is a maximal linearly independent subset of that vector space.

    6. (f) A maximal linearly independent subset of a vector space is a basis for that vector space.

  2. Show that the set of convergent sequences is an infinite-dimensional subspace of the vector space of all sequences of real numbers. (See Exercise 21 in Section 1.3.)

  3. Let V be the set of real numbers regarded as a vector space over the field of rational numbers. Prove that V is infinite-dimensional. Hint: Use the fact that π is transcendental, that is, π is not a zero of any polynomial with rational coefficients.

  4. Let W be a subspace of a (not necessarily finite-dimensional) vector space V. Prove that any basis for W is a subset of a basis for V.

  5. Prove the following infinite-dimensional version of Theorem 1.8 (p. 44): Let β be a subset of an infinite-dimensional vector space V. Then β is a basis for V if and only if for each nonzero vector v in V, there exist unique vectors u1, u2, , un in β and unique nonzero scalars c1, c2, , cn such that v=c1u1+c2u2++cnun. Visit goo.gl/fNWSDM for a solution.

  6. Prove the following generalization of Theorem 1.9 (p. 45): Let S1 and S2 be subsets of a vector space V such that S1S2. If S1 is linearly independent and S2 generates V, then there exists a basis β for V such that S1βS2. Hint: Apply the Hausdorff maximal principle to the family of all linearly independent subsets of S2 that contain S1, and proceed as in the proof of Theorem 1.13.

  7. Prove the following generalization of the replacement theorem. Let β be a basis for a vector space V, and let S be a linearly independent subset of V. There exists a subset S1 of β such that SS1 is a basis for V.