A function that is both one-to-one and onto, that is if f(x) = f(y) then x = y, and for every y of the domain there is an x of the range so that f(x) = y. The set of real numbers. Let V be a vector space and let S subset of V be a nonempty subset. Then S is a basis for V if and only if S is a set of generators for V and S is linearly independent. Let V be a vector space. Then any two bases of V contain the same number of elements.
Back | Table of Contents

Basis and Dimension

In the preceding section, we observed that S = {e1, e2, ..., en} where

e1 = (1,0,0,...,0)
e2 = (0,1,0,...,0)
·
·
·
en = (0,0,0,...,1)

is a set of generators for the vector space Fn. Thus, every element v of Fn can be written in the form

(1)
v = sum over ialphaiei,     alphai element of F.

Actually, the set S of generators has a very special property: The elements alphai in (1) are uniquely determined. Indeed,

sum over ialphaiei = (alpha1, alpha2, ..., alphan),

so that if (1) holds, and v = (v1, ..., vn), then alphai = vi (1 < i < n).

Definition 1: Let V be a vector space over F. A basis of V is a subset {ei} of V (finite or infinite) with the property that every element v of V can be uniquely written in the form

v = sum over ialphaiei.

(Here we always assume that if {ei} is infinite, then alphai = 0 for all but a finite number of i, also that the sum is a finite sum.)

Example 1: {ei, ..., en} is a basis for Fn.

Example 2: {e1 - e2,e1 + e2} is a basis for F2 since v = (v1,v2, then

v = (v1 - v2)/2(e1 - e2) + (v1 + v2)/2(e1 + e2),

and if v = alpha(e1 - e2) + beta(e1 + e2), then v = (alpha + beta, beta - alpha), so that alpha = (v1 - v2)/2, beta = (v1 + v2)/2. Thus, every element of F2 can be represented in one and only one way in the form alpha(e1 - e2) + beta(e1 + e2), so that {e1 - e2, e1 + e2} is a basis of F2.

The main goal of this section is to show that any two bases of a vector space V have the same number of elements, in the following sense: If one basis of V has a finite number of elements, then every basis has a finite number of elements, and every basis has the same number. If one basis of V is infinite, then every basis is infinite. Assuming this result for the moment, let us make the following definition.

Definition 2: Let V be a vector space. If V has a finite set of generators, then we say that V is finite-dimensional and we define its dimension, denoted dimFV, to be the minimum possible number of elements in such a set. If V does not have a finite set of generators, then we say the V is infinite-dimensional, and we define dimFV to be infinity.

For example, let V = {0}. Since S = empty is a set of generators for V, and since S is clearly as small as possible a set of generators, we see that dimFV = 0.

Assume no that V not equal {0} and that V is finite-dimensional. Let S = {v1, ..., vn} be a set of generators having as few elements as possible. (Since V not equal {0}, S is nonempty.) Then by definition of dimFV, we have dimFV = n. We will show that {v1,..., vn} is a basis of V. Indeed, Since S generates V, every element v of V can be written in the form

v = alphav1 + ... + alphanvn   (alphai element of F).

We assert that this representation is unique. For if v = beta1v1 + ... + betanvn with alpha1 not equal beta1, say, alpha1 - beta1 not equal 0 and

v1 = gamma2v2 + ... + gammanvn,

where gammai = (alpha1 - beta1)-1(betai + alphai) (2 < i < n). But w element of V, we may write

w = delta1v1 + ... + deltanvn,    (deltai element of F)
= (delta2 + delta1gamma2)v2 + ... + (deltan + delta1gamman)vn,

so that w can be written as a linear combination of v2, ..., vn. Then, since w element of V is arbitrary, {v2, ..., vn} is a set of generators for V, which contradicts the hypothesis that S is as small as possible. Thus the representation is unique, and S is a basis for V. We have shown that the dimension of V can be computed as the number of elements in a set of generators that is as small as possible and such a set of generators is a basis for V. We will show next that any two bases of V have the same number of elements. Thus, we will have prove that dimFV = the number of elements in a basis for V. By the way, we should remark that it is a consequence of our above reasoning that every nonzero finite-dimensional vector space has a basis. (Just take as a basis any set of generators that is as small as possible.) For example, dimFFn = n, since {e1, ..., en} is a basis for Fn.

Definition 3: Let S subset of V be a nonempty subset of V. Then S is said to be linearly dependent if there exist distinct elements s1, ..., sn belonging to S and alpha1, ..., alphan belonging to F, not all 0 such that

alpha1s1 + alpha2s2 + ...+ alphansn = 0.

If S is not linearly dependent, then we say that S is linearly independent.

Example 3: Let V = R2, S = {e1, 2e1}. Then S is linearly dependent since

(-2) · e1 + 1 · (2e1) = 0.

Example 4: Let V be arbitrary and let S = {0}. Then is linearly dependent since 1 · 0 = 0.

Example 5: Let V be arbitrary and let S be a basis of V. Then S is linearly independent, since if

alpha1s1 + alpha2s2 + ... + alphansn = 0,  alphai element of F,  si element of S,

then since

0 = 0 · s1 + 0 · s2 + ... + 0 · sn,

the fact that 0 is uniquely representable in terms of the basis implies that alpha1 = alpha2 = ... = alphan = 0.

Proposition 4: Let V be a vector space and let S subset of V be a nonempty subset. Then S is a basis for V if and only if S is a set of generators for V and S is linearly independent.

Proof:forward implication If S is a basis, then S is clearly a set of generators for V. Moreover, S is linearly independent by Example 5 above.

backwards implication Let v element of V/ Since S is a set of generators, there exist alphas (s element of S) belonging to F such that

(2)
v = sum over salphass,

where all but a finite number of the alphas are 0. Let us show that the representation (2) is unique. Indeed if

v = sum over sbetass,   betas element of F,

then

0 = v - v = sum over s(alphas - betas)s.

But since S is linearly independent, we see that alphas - betas = 0 for all s. Thus, alphas = betas for all s element of S and the representation (2) is unique. Thus, S is a basis of V.

Theorem 5: Let V be a vector space. Then any two bases of V contain the same number of elements.

Proof: Let us consider the special case where V has a finite basis {e1, ..., en}. We will prove that if {fi}ielement ofI is any other basis of V, then it is finite and contains n elements. Consideration of the special case suffices, for then if V has one infinite basis, then the special case implies that all bases must be infinite. Since {fi}ielement ofI is linearly independent, all the fi are nonzero. Let f1 be one of the fi. Since {e1, ..., en} is a basis for V, there exist alpha1,...,alphan element of F such that

f1 = alphae1 + ... + alphanen.

Since f1 not equal 0, not all alphaj are zero. Let us renumber the ej so that alpha1 not equal 0. Then, since F is a field,

(3)
e1 = alpha1-1f1 - alpha1-1alpha2e2 - ... - alpha1-1alphanen.

Let us show that {f1,e2,...,en} is a basis of V. Let v element of V. Then there exist beta1,...,beta element of F such that

v = beta1e1 + ... + betanen.

Therefore, by (3),

v = beta1'f1 + beta2'e2 + ... + betan'fn.

Thus, {f1,e2,...,en} is a set of generators for V. If {f1,e2,...,en} is linearly dependent, then there exist gamma1,...,gamman element of F such that

(4)
gamma1f1 + gamma2e2 + ... + gammanen = 0,

where gamma1,...,gamman are not all 0. If gamma = 0, then one of gamma2,...,gamman is nonzero and gamma2e2 + ... + gammanen = 0, which contradicts the fact that e2,...,en are linearly independent. Therefore, gamma1 not equal 0. Without loss of generality, we may multiply (4) by gamma1-1 and assume that gamma1 = 1. Then

alpha1e1 + (alpha2 + gamma2)e2 + ... + (alphan + gamman)en = 0,   alpha1 not equal 0,

which contradicts the fact that {e1,...,en} are linearly independent. The contradiction proves that {f1,e2...,en} is linearly independent, so that by Proposition 4, {f1,e2...,en} is a basis of V. If n = 1, then {f1} is a basis of V. Therefore, {fi}ielement ofI consists of a single element and the theorem is correct. Thus assume the n > 1. If {fi}ielement ofI consists only of the single element f1, then {f1} is a basis of V, which contradicts the fact that {f1,e2,...,en} is a basis of V and n > 1. Thus, {fi}ielement ofI consists of at least two elements. Let f2 element of{fi}ielement ofI, f2 not equal f1. Since {f1,e2,...,en} is a basis of V, there exist delta1,...,deltan element of F such that

f2 = delta1f1 + delta2e2 + ... + deltanen,

delta1,...,deltan not all 0. If delta2 = ... = deltan = 0, then f1 - deltaf1 = 0, which contradicts the fact that f1 and f2 are linearly independent. Thus, one of delta1,...,deltan is nonzero. Without loss of generality, assume that delta2 not equal 0. Repeating the above argument, we see that {f1,f2,e3...,en} is a basis of V. Continuing in this way, we find f1,...,fn in {fi}ielement ofI such that {f1,...,fn} is a basis of V. But since {fi}ielement ofI is also a basis for V, we see that {fi}ielement ofI consists of precisely n elements. For if fn+1 element of {fi}ielement ofI is distinct from f1,...,fn, then fn+1 = eta1f1 + etaf2 + ... + etanfn (etai element of F) since {f1,...fn} is a basis of V. But this contradicts the fact that {f1,...fn+1} are linearly independent. This completes the proof of the theorem.

Remarks: 1. It is possible to strengthen Theorem 5 in case V has infinite dimension. Namely, it is possible to show that not only are any two bases of V is infinite, but given any two bases of V, there exists a bijection of one of these into the other.

2. It is not clear from what we have said that any vector space has a basis. In order to prove this assertion, it is necessary to appeal to Zorn's lemma. If V is finite-dimensional, then the existence of a basis of V was proved. In most of what follows, we will be concerned only with finite-dimensional vector spaces, so we will not give proof of the existence of a basis in the most general case.
Back | Table of Contents