# Problem: Prove that, every basis of a vector space V has the same number of elements.

**Proof**: Suppose {u_{1} , u_{2} , . . . , u_{n} } is a basis of V, and suppose {v_{1} , v_{2} , . . .} is another basis of V. Because {u_{i}} spans V, the basis {v_{1} ,v_{2}, . . .} must contain n or less vectors, or else it is linearly dependent. On the other hand, if the basis {v_{1},v_{2}, . . .} contains less than n elements, then {u_{1} , u_{2} , . . . , u_{n} } is linearly dependent. Thus, the basis fv {v_{1}, v_{2}, . . .} contains exactly n vectors, and so the theorem is true. ▄

## Problem: Let V be a vector space of ﬁnite dimension n. Then

(i) Any n + 1 or more vectors must be linearly dependent.

(ii) Any linearly independent set S = {u_{1} , u_{2} , . . . , u_{n} } with n elements is a basis of V.

(iii) Any spanning set T = {v_{1},v_{2}, . ., v_{n}} of V with n elements is a basis of V.

**Proof**: Suppose B = {w_{1},w_{2}, . ., w_{n}} is a basis of V.

(i) Because B spans V, any n + 1 or more vectors are linearly dependent (ii), elements from B can be adjoined to S to form a spanning set of V with n elements.

Because S already has n elements, S itself is a spanning set of V. Thus, S is a basis of V.

(iii) Suppose T is linearly dependent. Then some v i is a linear combination of the preceding vectors. We know that V is spanned by the vectors in T without v_{i} and there are n –1 of them. We know that the independent set B cannot have more than n – 1 elements. This contradicts the fact that B has n elements. Thus, T is linearly independent, and hence T is a basis of V.▄

**Problem: Suppose S spans a vector space V**. Then

(i) Any maximum number of linearly independent vectors in S form a basis of V.

(ii) Suppose one deletes from S every vector that is a linear combination of preceding vectors in S. Then the remaining vectors form a basis of V.

**Proof**: (i) Suppose {v_{1},v_{2}, . ., v_{m}} is a maximum linearly independent subset of S, and suppose w ∊ S. Accordingly, {v_{1},v_{2}, . ., v_{m}} is linearly dependent. No v_{k} can be a linear combination of preceding vectors.

Hence, w is a linear combination of the v_{i} . Thus, w ∊ span (v_{i} ), and hence S span (v_{i}) . This leads to

V= span(S) ⊆ span (v_{i} ) ⊆ V

Thus, (v_{i}) spans V, and, as it is linearly independent, it is a basis of V.

(ii) The remaining vectors form a maximum linearly independent subset of S; hence, by (i), it is a basis of V.▄

**Problem**: Let V be a vector space of ﬁnite dimension and let S = {u_{1} , u_{2} , . . . , u_{r} } be a set of linearly independent vectors in V. Then S is part of a basis of V ; that is, S may be extended to a basis of V.

**Proof**: Suppose B = {w_{1},w_{2}, . ., w_{n}} is a basis of V. Then B spans V, and hence V is spanned by

S ⋃ B = {u_{1} , u_{2} , . . . , u_{r} ,v_{1},v_{2}, . ., v_{m}}

We can delete from S⋃B each vector that is a linear combination of preceding vectors to obtain a basis Bˊ for V. Because S is linearly independent, no u_{k} is a linear combination of preceding vectors. Thus, Bˊ contains every vector in S, and S is part of the basis Bˊ for V.▄

**Problem**: Let W be a subspace of an n-dimensional vector space V. Then dim

W ≤ n. In particular, if dim W= n, then W = V.

** Proof**: Because V is of dimension n, any n +1 or more vectors are linearly dependent. Furthermore, because a basis of W consists of linearly independent vectors, it cannot contain more than n elements. Accordingly, dim W ≤ n.

In particular, if {w_{1},w_{2}, . ., w_{n}} is a basis of W, then, because it is an independent set with n elements, it is

also a basis of V. Thus, W = V when dim W = n.▄