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

Oguzhancan (Talk | contribs) |
Oguzhancan (Talk | contribs) (→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 , so *****(explanation needed, why? [or your question])***** since is a some linearly independent...

## Theorems & Proofs

**Theorem:** Let be a subspace of a finite dimensional vector space . Then is finite dimensional and

**Proof:** Let be a basis for . Then we know that is a finite set since is a finite dimensional. Then, for given a subspace , let us construct a linearly independent set by adding vectors from such that is maximally linearly independent. In other words, adding any other vector from would make linearly dependent. Here, L has to be a finite set by the Replacement Theorem, if we choose the generating set as , so since is a some linearly independent subset of . Now we want to show that is a basis for . Since is linearly independent, it suffices to show that . Suppose not:. (We know that since is made of vectors from .) Then But this means is linearly independent, which contradicts with maximally linearly independence of . Therefore and hence, is a basis for

**Replacement Theorem:** Let be a vector space generated by (perhaps linearly dependent) where and let be a linearly independent subset of such that . Then and there exists a subset of with and .

**Proof:** We will prove by induction hypothesis on :

For : , and so,

Now, suppose true for :