If you need to review vectors (see Definition 1 here), vector spaces (see Definition 2, here), linear combinations (see Definition 1, here) or family of vectors (see Definition 4, here), start here.

Algorithm 1:

Given a family of linear independent vectors and a family that spans vectors in V.

Produce a family of linear indepedent vectors that serves as a basic for V.

Here are the steps:

(1) Let X = (x

^{1}, ..., x

^{n}) be a linearly independent family of vectors in V.

(2) Let Y = (y

^{1}, ..., y

^{n}) be a family of vectors that spans a vector space V.

(3) Let i = 1

(4) Let Z

_{0}= X

(5) If y

^{i}is not an element of [[Z

_{i-1}]], then let Z

_{i}= (Z

_{i-1},y

^{i}).

(6) If y

^{i}is an element of [[Z

_{i-1}]], then let Z

_{i}= Z

_{i-1}

(7) Let i = i + 1

(8) If i ≤ n, then go to step #4.

(9) The answer is Z

_{n}

Done.

Theorem 1: Theorem of Exchange

Let V be a vector space. Let X = (x

^{1}, ..., x

^{n}) be a linearly independent family of vectors in V. Let Y = (y

^{1}, ..., y

^{n}) be a family of vectors that span V.

Then, we can form a new family of vectors Z consisting of all the vectors of X such that Z is a basis for V.

Proof:

(1) Since X = (x

^{1}, ..., x

^{n}) is linearly independent, we can conclude that for all i, x

^{i}≠ 0. [See Corollary 2.1, here]

(2) For each i, x

^{i}is not a linear combination of its predecessors since X is linearly independent. [See Corollary 3.1, here]

(3) If y

^{i}∈ Z, then the family of predecessors of y

^{i}is Z

_{i-1}and by construction y

^{i}is not a linear combination of Z

_{i-1}(or else y

^{i}would not be in Z).

(4) Hence, Z is linearly independent. [See Definition 1, here]

(5) Next, we need to show that Z spans V.

(6) By assumption V ⊆ [[Y]] since Y spans V.

(7) [[Y]] ⊆ [[X,Y]] [See Corollary 1.2, here]

(8) Further, each x

^{i}is in Z, so that x

^{i}∈ [[Z]] (Since Z ⊆ [[Z]])

(9) If y

^{i}∈ Z, then again y

^{i}∈ [[Z]].

(10) But if y

^{i}is not in Z, then y

^{i}∈ [[Z

_{i-1}]] since y

_{i}is added to Z

_{i}only when y

^{i}is not an element of [[Z

_{i-1}]].

(11) [[Z

_{i-1}]] ⊆ [[Z]] [See Corollary 1.2, here] since Z is obtained from Z

_{i-1}by adjoining vectors.

(12) Hence, in any case y

^{i}∈ [[Z]] since:

(a) Either y

^{i}∈ Z or y

^{i}is not in Z.

(b) If y

^{i}∈ Z, then y

^{i}∈ [[Z]]

(c) If y

^{i}is not in Z, then y

^{i}∈ [[Z

_{i-1}]]

(d) Since [[Z

_{i-1}]] ⊆ [[Z]], it follows that y

^{i}∈ [[Z]]

(13) It follows that each element of [[X,Y]] belongs to [[Z]] since we have shown that y

^{i}∈ [[X,Y]] implies that y

^{i}∈ [[Z]] [from step #12]

(14) This gives us that [[X,Y]] ⊆ [[Z]] [See Lemma 1, here]

(15) But each element of [[Z]] belongs to V which gives us that:

[[Z]] ⊆ V

(16) We obtain that:

V ⊆ [[Y]] ⊆ [[X,Y]] ⊆ [[Z]] ⊆ V.

(17) Hence, equality holds throughout and [[Z]] = V since we have shown that V ⊆ [[Z]] and [[Z]] ⊆ V.

QED

Corollary 1.1:

Assume that V is nonzero and let (y

^{1}, ..., y

^{t}) span V.

Then there is a basis for V consisting of some of the y

^{i}

Proof:

(1) Assume y

^{1}≠ 0

(2) Let X = (y

^{1})

(3) Let Y = (y

^{1}, ..., y

^{t})

(4) Using Theorem 1 above, we know that it is possible to construct a family of vectors Z such that Z is a basis for V.

(5) From Algorithm 1 above, it is clear that this consists of some of the y

^{i}.

QED

Theorem 2:

Let (x

^{1}, .., x

^{t}) be a linearly independent family of vectors, and let (y

^{1}, ..., y

^{u}) = Z span V.

Then t ≤ u.

Proof:

(1) Let Z

_{0}= Z

(2) Since X = (x

^{1}, ..., x

^{t}) is in V, it follows that x

^{1}∈ V.

(3) Using Theorem 1 above, we can construct a family Z

_{1}= (x

^{1}, y

^{1}, ..., y

^{p}) such that Z

_{1}is a basis for V.

(4) We can claim that p must be less than t since:

(a) Since x

^{1}∈ V and (y

^{1}, y

^{2}, ..., y

^{t}) spans V, there must exist α

_{i}such that:

x

^{1}= α

_{1}y

^{1}+ ... + α

_{t}y

^{t}

(b) Therefore (x

^{1}, y

^{1}, ..., y

^{t}) is linearly dependent (see Lemma 4, here)

(c) Therefore, using Algorithm 1 above, we would have removed one of the values of 1 .. t in order to create the set x

^{1}, y

^{1}, ..., y

^{p}

(5) This gives us that p + 1 ≤ t which allows us to conclude that:

|Z

_{1}| ≤ |Z

_{0}|

(6) This proves the base case.

(7) Now, we need only show that the proposition is true for |Z

_{i-1}| then it is also true for |Z

_{i}|.

(8) Assume that we have a basis Z

_{i-1}= (x

^{1}, ..., x

^{i-1},y

^{1}, ..., y

^{r}) for V where |Z

_{i-1}| = r + i - 1 ≤ u ≤ |Z

_{0}|.

(9) We can use Algorithm 1 to create a basis Z

_{i}= (x

^{1}, ..., x

^{i}, y

^{1}, ..., y

^{q}) where y

^{1}, .., y

^{q}⊆ y

^{1}, ..., y

^{r}.

(10) Clearly, y

^{1}, ..., y

^{q}cannot consist of all the elements of y

^{1}, ..., y

^{r}since (x

^{1}, ..., x

^{i-1},y

^{1}, ..., y

^{r}) is a basis for V and x

^{i}∈ V.

(11) Therefore q is less than r so it follows that |Z

_{i}| = i + q ≤ (i - 1) + r = |Z

_{i-1}|

(12) After t such steps, we obtain a basis Z

_{t}= (x

^{1}, ..., x

^{t}, y

^{1}, ..., y

^{l}) where |Z

_{t}| = t + l ≤ |Z

_{t-1}|

(13) Clearly, t ≤ |Z

_{t}| and |Z

_{t}| ≤ |Z

_{t-1}| ≤ ... ≤ |Z

_{0}| = u.

(14) Hence, t ≤ u and the theorem is proved.

QED

References

- Hans Schneider, George Philip Barker, Matrices and Linear Algebra, 1989.