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 = (x1, ..., xn) be a linearly independent family of vectors in V.
(2) Let Y = (y1, ..., yn) be a family of vectors that spans a vector space V.
(3) Let i = 1
(4) Let Z0 = X
(5) If yi is not an element of [[Zi-1]], then let Zi = (Zi-1,yi).
(6) If yi is an element of [[Zi-1]], then let Zi = Zi-1
(7) Let i = i + 1
(8) If i ≤ n, then go to step #4.
(9) The answer is Zn
Done.
Theorem 1: Theorem of Exchange
Let V be a vector space. Let X = (x1, ..., xn) be a linearly independent family of vectors in V. Let Y = (y1, ..., yn) 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 = (x1, ..., xn) is linearly independent, we can conclude that for all i, xi ≠ 0. [See Corollary 2.1, here]
(2) For each i, xi is not a linear combination of its predecessors since X is linearly independent. [See Corollary 3.1, here]
(3) If yi ∈ Z, then the family of predecessors of yi is Zi-1 and by construction yi is not a linear combination of Zi-1 (or else yi 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 xi is in Z, so that xi ∈ [[Z]] (Since Z ⊆ [[Z]])
(9) If yi ∈ Z, then again yi ∈ [[Z]].
(10) But if yi is not in Z, then yi ∈ [[Zi-1]] since yi is added to Zi only when yi is not an element of [[Zi-1]].
(11) [[Zi-1]] ⊆ [[Z]] [See Corollary 1.2, here] since Z is obtained from Zi-1 by adjoining vectors.
(12) Hence, in any case yi ∈ [[Z]] since:
(a) Either yi ∈ Z or yi is not in Z.
(b) If yi ∈ Z, then yi ∈ [[Z]]
(c) If yi is not in Z, then yi ∈ [[Zi-1]]
(d) Since [[Zi-1]] ⊆ [[Z]], it follows that yi ∈ [[Z]]
(13) It follows that each element of [[X,Y]] belongs to [[Z]] since we have shown that yi ∈ [[X,Y]] implies that yi ∈ [[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 (y1, ..., yt) span V.
Then there is a basis for V consisting of some of the yi
Proof:
(1) Assume y1 ≠ 0
(2) Let X = (y1)
(3) Let Y = (y1, ..., yt)
(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 yi.
QED
Theorem 2:
Let (x1, .., xt) be a linearly independent family of vectors, and let (y1, ..., yu) = Z span V.
Then t ≤ u.
Proof:
(1) Let Z0 = Z
(2) Since X = (x1, ..., xt) is in V, it follows that x1 ∈ V.
(3) Using Theorem 1 above, we can construct a family Z1 = (x1, y1, ..., yp) such that Z1 is a basis for V.
(4) We can claim that p must be less than t since:
(a) Since x1 ∈ V and (y1, y2, ..., yt) spans V, there must exist αi such that:
x1 = α1y1 + ... + αtyt
(b) Therefore (x1, y1, ..., yt) 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 x1, y1, ..., yp
(5) This gives us that p + 1 ≤ t which allows us to conclude that:
|Z1| ≤ |Z0|
(6) This proves the base case.
(7) Now, we need only show that the proposition is true for |Zi-1| then it is also true for |Zi|.
(8) Assume that we have a basis Zi-1 = (x1, ..., xi-1,y1, ..., yr) for V where |Zi-1| = r + i - 1 ≤ u ≤ |Z0|.
(9) We can use Algorithm 1 to create a basis Zi = (x1, ..., xi, y1, ..., yq) where y1, .., yq ⊆ y1, ..., yr.
(10) Clearly, y1, ..., yq cannot consist of all the elements of y1, ..., yr since (x1, ..., xi-1,y1, ..., yr) is a basis for V and xi ∈ V.
(11) Therefore q is less than r so it follows that |Zi| = i + q ≤ (i - 1) + r = |Zi-1|
(12) After t such steps, we obtain a basis Zt = (x1, ..., xt, y1, ..., yl) where |Zt| = t + l ≤ |Zt-1|
(13) Clearly, t ≤ |Zt| and |Zt| ≤ |Zt-1| ≤ ... ≤ |Z0| = u.
(14) Hence, t ≤ u and the theorem is proved.
QED
References
- Hans Schneider, George Philip Barker, Matrices and Linear Algebra
, 1989.
