Difference between revisions of "12-240/Proofs in Vector Spaces"

From Drorbn
Jump to: navigation, search
 
(Theorems & Proofs)
 
Line 10: Line 10:
  
 
<b>Proof:</b> Let <math>\beta</math> be a basis for <math>V</math>. Then we know that <math>\beta</math> is a finite set since <math>V</math> is a finite dimensional. Then, for given a subspace <math>W</math>, let us construct a linearly independent set <math>L</math> by adding vectors from <math>W</math> such that <math>L=\{w_1,w_2, ... w_k\}</math> is maximally linearly independent. In other words, adding any other vector from <math>W</math> would make <math>L</math> linearly dependent. Here, L has to be a finite set by the Replacement Theorem, if we choose the generating set as <math>\beta</math>, so <math>k = |L|\leq |\beta| = dimV</math> since <math>L</math> is a some linearly independent subset of <math>V</math>. Now we want to show that <math>L</math> is a basis for <math>W</math>. Since <math>L</math> is linearly independent, it suffices to show that <math>span(L)=W</math>. Suppose not:<math>span(L)\neq W</math>. (We know that <math>L \subseteq span(L) \subseteq W</math> since <math>L</math> is made of vectors from <math>W</math>.) Then <math>\exists w_a \in W : w_a \notin span(L)</math> But this means <math>span(L)\cup \{w_a\}</math> is linearly independent, which contradicts with maximally linearly independence of <math>L</math>. Therefore <math>span(L)=W</math> and hence, <math>L</math> is a basis for <math>W</math>
 
<b>Proof:</b> Let <math>\beta</math> be a basis for <math>V</math>. Then we know that <math>\beta</math> is a finite set since <math>V</math> is a finite dimensional. Then, for given a subspace <math>W</math>, let us construct a linearly independent set <math>L</math> by adding vectors from <math>W</math> such that <math>L=\{w_1,w_2, ... w_k\}</math> is maximally linearly independent. In other words, adding any other vector from <math>W</math> would make <math>L</math> linearly dependent. Here, L has to be a finite set by the Replacement Theorem, if we choose the generating set as <math>\beta</math>, so <math>k = |L|\leq |\beta| = dimV</math> since <math>L</math> is a some linearly independent subset of <math>V</math>. Now we want to show that <math>L</math> is a basis for <math>W</math>. Since <math>L</math> is linearly independent, it suffices to show that <math>span(L)=W</math>. Suppose not:<math>span(L)\neq W</math>. (We know that <math>L \subseteq span(L) \subseteq W</math> since <math>L</math> is made of vectors from <math>W</math>.) Then <math>\exists w_a \in W : w_a \notin span(L)</math> But this means <math>span(L)\cup \{w_a\}</math> is linearly independent, which contradicts with maximally linearly independence of <math>L</math>. Therefore <math>span(L)=W</math> and hence, <math>L</math> is a basis for <math>W</math>
 +
 +
<b>Replacement Theorem:</b> Let <math>V</math> be a vector space generated by <math>G</math> (perhaps linearly dependent) where <math>|G|=n</math> and let <math>L</math> be a linearly independent subset of <math>V</math> such that <math>|L|=m</math>. Then <math>m \leq n</math> and there exists a subset <math>H</math> of <math>G</math> with <math>|H| = n-m</math> and <math>span(H \cup L)=V</math>.
 +
 +
<b>Proof:</b> We will prove by induction hypothesis on <math>m=|L|</math>:
 +
 +
For <math>m = 0</math>: <math>L = \emptyset</math>, <math>0 \leq n</math> and <math>H=G</math> so, <math>span(H \cup L) = span(H) = span(G) = V</math>
 +
 +
Now, suppose true for <math>m</math>:

Latest revision as of 02:35, 8 December 2012

Important Note About This Page

This page is intended for sharing/clarifying proofs. Here, you might add a proof, correct a proof, or request more detailed explanation of some specific parts of given proofs. To request an explanation for a proof, you may put a sign at that specific part by editing this page. For example:

...generating set as \beta, so k = |L|\leq |\beta| = dimV ***(explanation needed, why? [or your question])*** since L is a some linearly independent...

Theorems & Proofs

Theorem: Let W be a subspace of a finite dimensional vector space V. Then W is finite dimensional and dimW \leq dimV

Proof: Let \beta be a basis for V. Then we know that \beta is a finite set since V is a finite dimensional. Then, for given a subspace W, let us construct a linearly independent set L by adding vectors from W such that L=\{w_1,w_2, ... w_k\} is maximally linearly independent. In other words, adding any other vector from W would make L linearly dependent. Here, L has to be a finite set by the Replacement Theorem, if we choose the generating set as \beta, so k = |L|\leq |\beta| = dimV since L is a some linearly independent subset of V. Now we want to show that L is a basis for W. Since L is linearly independent, it suffices to show that span(L)=W. Suppose not:span(L)\neq W. (We know that L \subseteq span(L) \subseteq W since L is made of vectors from W.) Then \exists w_a \in W : w_a \notin span(L) But this means span(L)\cup \{w_a\} is linearly independent, which contradicts with maximally linearly independence of L. Therefore span(L)=W and hence, L is a basis for W

Replacement Theorem: Let V be a vector space generated by G (perhaps linearly dependent) where |G|=n and let L be a linearly independent subset of V such that |L|=m. Then m \leq n and there exists a subset H of G with |H| = n-m and span(H \cup L)=V.

Proof: We will prove by induction hypothesis on m=|L|:

For m = 0: L = \emptyset, 0 \leq n and H=G so, span(H \cup L) = span(H) = span(G) = V

Now, suppose true for m: