Dimension theorem for vector spaces

Proof

Assume that { a_i: i ∈ I } and { b_j: j ∈ J } are both bases, with the cardinality of I bigger than the cardinality of J. From this assumption we will derive a contradiction.

Case 1

Assume that I is infinite.

Every b_j can be written as a finite sum

Since the cardinality of I is greater than that of J and the E_j's are finite subsets of I, the cardinality of I is also bigger than the cardinality of ⋃ j ∈ J E j . (Note that this argument works only for infinite I.) So there is some i 0 ∈ I which does not appear in any E j . The corresponding a i 0 can be expressed as a finite linear combination of b j 's, which in turn can be expressed as finite linear combination of a i 's, not involving a i 0 . Hence a i 0 is linearly dependent on the other a i 's.

Case 2

Now assume that I is finite and of cardinality bigger than the cardinality of J. Write m and n for the cardinalities of I and J, respectively. Every a_i can be written as a sum

The matrix ( μ i , j : i ∈ I , j ∈ J ) has n columns (the j-th column is the m-tuple ( μ i , j : i ∈ I ) ), so it has rank at most n. This means that its m rows cannot be linearly independent. Write r i = ( μ i , j : j ∈ J ) for the i-th row, then there is a nontrivial linear combination

But then also ∑ i ∈ I ν i a i = ∑ i ∈ I ν i ∑ j ∈ J μ i , j b j = ∑ j ∈ J ( ∑ i ∈ I ν i μ i , j ) b j = 0 , so the a i are linearly dependent.

Alternative Proof

The proof above uses several non-trivial results. If these results are not carefully established in advance, the proof may give rise to circular reasoning. Here is a proof of the finite case which requires less prior development.

Theorem 1: If A = ( a 1 , … , a n ) ⊆ V is a linearly independent tuple in a vector space V , and B 0 = ( b 1 , . . . , b r ) is a tuple that spans V , then n ≤ r .

The argument is as follows:

Since B 0 spans V , the tuple ( a 1 , b 1 , … , b r ) also spans. Since a 1 ≠ 0 (because A is linearly independent), there is at least one t ∈ { 1 , … , r } such that b t can be written as a linear combination of B 1 = ( a 1 , b 1 , … , b t − 1 , b t + 1 , . . . b r ) . To see this, write a 1 as a linear combination of the b i , and note that because a i ≠ 0 , at least one of the coefficients of the b i must be non-zero. Isolating this term on one side of the equation and dividing by its coefficient - here we make critical use of the assumption that a vector space is always defined over a field - yields the result. Thus, B 1 is a spanning tuple, and its length is the same as B 0 's.

Repeat this process. Because A is linearly independent, we can always remove an element from the list B i which is not one of the a j 's that we prepended to the list in a prior step (because A is linearly independent, and so there must be some nonzero coefficient in front of one of the b i 's). Thus, after n iterations, the result will be a tuple B n = ( a 1 , … , a n , b m 1 , … , b m k ) (possibly with k = 0 ) of length r . In particular, A ⊆ B n , so | A | ≤ | B n | , i.e., n ≤ r .

To prove the finite case of the dimension theorem from this, suppose that V is a vector space and S = { v 1 , … , v n } and T = { w 1 , … , w m } are both bases of V . Since S is linearly independent and T spans, we can apply Theorem 1 to get m ≥ n . And since T is linearly independent and S spans, we get n ≥ m . From these, we get m = n .

Kernel extension theorem for vector spaces

This application of the dimension theorem is sometimes itself called the dimension theorem. Let

be a linear transformation. Then

that is, the dimension of U is equal to the dimension of the transformation's range plus the dimension of the kernel. See rank-nullity theorem for a fuller discussion.