Saturday, May 12, 2007

Theorem of Exchange

The content in today's blog is taken from Schneider and Barker's Matrices and Linear Algebra.

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