Register to reply

What is the proof of this theorem in Vector Spaces ?

by Maths Lover
Tags: proof, spaces, theorem, vector
Share this thread:
Maths Lover
#1
Dec30-12, 03:04 AM
P: 62
Theorem :
if S ={ v1 , .... , vn} spans the V.Space V
, L={w1 , .... , wm} is set of linear independent vectors in V
then , n is bigger than or equal to m


How can we prove this ?

_____________

I read this theorem as a important note but the proof was ommited
Phys.Org News Partner Science news on Phys.org
Hoverbike drone project for air transport takes off
Earlier Stone Age artifacts found in Northern Cape of South Africa
Study reveals new characteristics of complex oxide surfaces
chiro
#2
Dec30-12, 03:21 AM
P: 4,572
Hey Maths Lover.

What can you say about the span of the space and a set of linear independent vectors with regard to the dimensionality of the space?

(Hint: How can you relate span to dimensionality and linear independence to said dimensionality of your vector space)?
Erland
#3
Dec30-12, 07:44 AM
P: 334
Quote Quote by Maths Lover View Post
Theorem :
if S ={ v1 , .... , vn} spans the V.Space V
, L={w1 , .... , wm} is set of linear independent vectors in V
then , n is bigger than or equal to m


How can we prove this ?

_____________

I read this theorem as a important note but the proof was ommited
Chiro, I think the results you suggest to be used are consequences of this theorem.

I know of two different proofs. One is based upon the thereom which says that a linear homogeneous equation system with more unknowns than equations has nontrivial solutions.

Another proof goes like this:

For each k (0<=k<=m), let Sk = {w1, w2, ... , wk, v1, v2, ... , vn}
Each Sk spans W, since S does.

Now, for each k (0<=k<=m), let Tk be the result when we remove from Sk all vectors which are linear combinations of the previous vectors in Sk. Then, each Tk is linearly independent. Since L is linearly independent, no wi will ever be removed when we form Tk, so w1, w2, ... wk in Tk for all k (0<=k<=m). But when we form T(k+1) (0<=k<m), we must remove at least all vectors from S(k+1) which we remove when we form Tk from Sk. But this is not enough, for if we only remove these vectors from S(k+1) to form T(k+1), w(k+1) would still be a linear combination of the other vectors in T(k+1), i.e. of the vectors in Tk, which contradicts that T(k+1) is linearly independent. Thus, we must remove at least one vector more to obtain T(k+1).

It follows that for each k (1<=k<=m), we must remove at least k vectors from Sk to form Tk, but none of the wi:s will be removed. In particular Tm contains all the vectors w1, w2, ... wm, and still it contains at least m vectors fewer than Sm, which contains m+n vectors. It follows that m<=(m+n)-m=m, that is: m<=n,

mathwonk
#4
Dec30-12, 11:17 AM
Sci Advisor
HW Helper
mathwonk's Avatar
P: 9,453
What is the proof of this theorem in Vector Spaces ?

"... if we only remove these vectors from S(k+1) to form T(k+1), w(k+1) would still be a linear combination of the other vectors in T(k+1), i.e. of the vectors in Tk,..."

it might help to state why this claim is true, i.e. Tk is not only independent but also spans.

(this proof is due to riemann, in the special case of proving invariance of rank of homology groups of a surface, but is usually attributed to steinitz.)
AlephZero
#5
Dec30-12, 12:34 PM
Engineering
Sci Advisor
HW Helper
Thanks
P: 6,932
You can get lost iin a sea of notation here. If we are talking about finite dimension vector spaces (whcih seems a reasonable assumption, from the notation of "m" and "n" vectors) then:

If the vectors in S are linearly independent, the dimension of V is n, and there can not be more than n independsnt vectors in L.

If the vectors in S are not linearly dependent, remove vectors from S one at a time until you are left with a set of k < n independent vectors that span V. Repeating the previous argument, there can not be more than k indepedent vectors in L.
Erland
#6
Dec30-12, 02:44 PM
P: 334
Quote Quote by AlephZero View Post
If the vectors in S are linearly independent, the dimension of V is n, and there can not be more than n independsnt vectors in L.
But you cannot prove this without the theorem in the OP. It is this theorem which makes it possible to talk about "the dimension" of a vector space. Without it, we wouldn't know that all bases have the same number of elements.
Fredrik
#7
Jan1-13, 07:31 AM
Emeritus
Sci Advisor
PF Gold
Fredrik's Avatar
P: 9,229
The definition of "dimension" that I use is that dim V=n if V contains a linearly independent set with cardinality n, but no linearly independent set with cardinality n+1. With this definition, we don't need a theorem to make it possible to talk about "the dimension" of a vector space.
Erland
#8
Jan1-13, 07:52 AM
P: 334
Quote Quote by Fredrik View Post
The definition of "dimension" that I use is that dim V=n if V contains a linearly independent set with cardinality n, but no linearly independent set with cardinality n+1. With this definition, we don't need a theorem to make it possible to talk about "the dimension" of a vector space.
OK, we can have such a definition. But it does not priori exclude that there exists a linearly independent set with k<n elements which cannot be extended to a linearly independent set with k+1 elements. We need a theorem like the one above, with a complex proof like the one above, to ensure this.
AlephZero
#9
Jan1-13, 12:16 PM
Engineering
Sci Advisor
HW Helper
Thanks
P: 6,932
Quote Quote by Erland View Post
OK, we can have such a definition. But it does not priori exclude that there exists a linearly independent set with k<n elements which cannot be extended to a linearly independent set with k+1 elements.
If a linearly independent set of vectors S spans a vector space, then every vector in the space has a unique representation as a linear combination of the vectors in S. (If there were two different representations, you could subtract them and get a linear dependency between the vectors in S).

You can use that fact to make a proof of the OP's theorem, by translating the argument about linear homegenous equations (which you mentioned) into the language of vector algebra.

People may have different opinions about whether that is a "simpler" proof than your (or Riemann's) proof, of course.
feyn4
#10
Jan1-13, 01:06 PM
P: 1
You can try with this proof (apagoge).

Suppose m > n.

Each vector of L is a linear combination of vectors v1, ... , vn, then:

w1 = a1(v1) + ... + an(vn)

At least one a_i coefficient is not zero (wlog, suppose a1 ≠ 0). Let's multiply both sides of equation by (a1)^(-1):

a1(v1) = w1 - a2(v2) - ... - an(vn)

[(a1)^(-1)](a1)(v1) = [(a1)^(-1)][w1 - a2(v2) - ... - an(vn)]

v1 = [(a1)^(-1)][w1 - a2(v2) - ... - an(vn)] (*)

Each vector of V is a linear combination of vectors v1, ... , vn, then:

v = b1(v1) + ... + bn(vn)

Recall the last result about v1:

v = b1(v1) + ... + bn(vn) = (b1)[(a1)^(-1)][w1 - a2(v2) - ... - an(vn)] + ... + bn(vn)

that is a linear combination of L1 = {w1, v2, ... vn}. This is another spanning set of V.

Let's express w2 as linear combination of L1 vectors:

w2 = c1(w1) + c2(v2) + ... + cn(vn)

There is at least one nonzero coefficient among c2...cn (otherwise w1 and w2 would not be linearly independent vectors). We can reiterate the procedure used to obtain (*), then L2 = {w1, w2, v3, ... vn} is another spanning set of V.

Replay this procedure n times, then Ln = L = {w1, ... , wn} is a spanning set of V.
Then, each vector of V is a linear combination of vectors of L, then

v = h1(w1) + ... + hn(wn)

In this case, it is true that

w_(n+1) = k1(w1) + ... + kn(wn)

but we supposed L to be a set of linearly independent vectors, then the last result is impossible and we proved the theorem.
mathwonk
#11
Jan1-13, 07:55 PM
Sci Advisor
HW Helper
mathwonk's Avatar
P: 9,453
the problem with Fredrik's definition is it is not clear that R^n has dimension n, without this theorem.


Register to reply

Related Discussions
Isomorphic Vector Spaces Proof Calculus & Beyond Homework 6
Proof of one of the properties of Real Coordinate Vector Spaces Calculus & Beyond Homework 6
Linear Algebra Proof (vector spaces and spans) Calculus & Beyond Homework 11
Simple Vector spaces proof Calculus & Beyond Homework 6
Proof, intersection and sum of vector spaces Linear & Abstract Algebra 4