Proving Spanning Sets in Vector Spaces

[Oxymoron]

I am in need of some guidance on a question concerning vector spaces and spanning sets.

Q) Suppose that V is a vector space over F and {v1,...,vn} ⊂ V.
a) Prove that if {v1,...,vn} spans V, then so does {v1-v2,v2-v3,...,v(n-1)-v(n),vn}.

 

[quantumdude]

Please post what you've got so far.

 

[Oxymoron]

What we have here is a vector space V (of unknown dimension, other than it is more than n) and a set S of n vectors (ie. dimS = n). We are given that S ⊂ V, ie. S is a subset of V. We want to prove that if S (of n vectors) spans V then so does T (also of n vectors) spans V. Where T = {v1-v2,v2-v3,...,v(n-1) - vn,vn} This is a good start because the number of vectors in S is the same as the number of vectors in T.

The question asks us to prove {v1-v2,v2-v3,...,v(n-1) - vn,vn} spans V IF S spans V. So we can assume S spans V without having to be concerned that it doesn't. Assuming S spans V opens up a lot of useful theorems that we can use to our advantage. Since S spans V then that means that every vector v in V must be able to be written as a linear combination of vectors in S.

PROOF:
Take any v ∈ V. Then since S spans V, v can be written as

v = c1v1 + c2v2 + ... + cnvn

Im not sure how to continue past this. I have a lot of fragmented ideas.

 

[matt grime]

S is just a set so dimS makes no sense.

If dimV is (strictly) greater than n, then S can't possibly span.

Can I guess that those are slips of the fingers, and answer what I think the question might be?

T spans the same subvector space as S since every vector in T is a combination of vectors in S and vice versa, do you see that?

 

[shmoe]

PROOF:
Take any v ∈ V. Then since S spans V, v can be written as

v = c1v1 + c2v2 + ... + cnvn

Im not sure how to continue past this. I have a lot of fragmented ideas.

You want to eventually get v as a linear combination of the vectors in T, in other words you want to find coefficients [tex]d_1,\ldots,d_n[/tex] where:

[tex]v=d_1(v_1-v_2)+d_2(v_2-v_3)+...+d_{n-1}(v_{n-1}-v_n)+d_nv_n[/tex]

Can you find some [tex]d_i[/tex]'s that satisfy this equation in terms of the [tex]c_i[/tex]'s, which you already know exist?

matt's method is simpler than directly applying the definition of span like this. You should be able to understand both ideas!

 

[matt grime]

i'd have just said that my idea was your idea without some of the messy bits left out (ie don't actually find the d's and c's since existence is all we require)

 

[shmoe]

I agree your way is simpler, but it's always usefull to have a slightly different way of tackling a problem. Whether the difference is large enough to call them different ideas is debatable, but I'd say it's significant enough to try to understand both approaches, especially for someone first learning linear algebra.

Knowing how to work out the d's from the c's will let you write the vectors of V in terms of the vectors in T. This of course isn't needed to solve this particular problem but can be a handy thing to have some practice doing. It also gives a more "hands on" feel to how linear combinations of S and T are related to one another.

 

[Oxymoron]

Thanks for the help guys. First question though: how do you LaTEX to display in your posts?

Matt, I see how every vector in T is a linear combination of vectors in S. Since S spansV and S is a subset of V then S contains a basis for V right?
Then since T is a linear combination of vectors in S, T also contains a basis for V. If T contains a basis of V, and since T ⊆ S ⊂ V then T must span V.

Take any v ∈ V.

v=c1v1 + c2v2 + ... + cnvn

then there exist di ∈ F such that

v=d1(v1-v2) + d2(v1-v2) + ... + d(n-1)(v(n-1)-vn + dnvn

Therefore T is a linear combination of vectors in S (are you sure that you can just assume existence?).

 

[shmoe]

Thanks for the help guys. First question though: how do you LaTEX to display in your posts?

Click on the Latex in a post and it will display the code used. You can also check out https://www.physicsforums.com/misc/howtolatex.pdf

Matt, I see how every vector in T is a linear combination of vectors in S. Since S spansV and S is a subset of V then S contains a basis for V right?

Correct, but a basis is not needed for this problem. Since you know the vectors in T are linear combinations of the vectors in S, what can you say about the sets T and span S? What does this then tell you about the sets span T and span S?

Then since T is a linear combination of vectors in S, T also contains a basis for V.

This reasoning is incorrect. The set {v1-v1,v2-v2} is also composed of linear combinations of the vectors in S, but it's not going to contain a basis for V.

If T contains a basis of V, and since T ⊆ S ⊂ V then T must span V.

The part in bold could be left out and this is true by what it means for T to contain a basis of V. However, we don't know this is true yet.

Take any v ∈ V.

v=c1v1 + c2v2 + ... + cnvn

then there exist di ∈ F such that

v=d1(v1-v2) + d2(v1-v2) + ... + d(n-1)(v(n-1)-vn + dnvn

Therefore T is a linear combination of vectors in S (are you sure that you can just assume existence?).

I'm not sure what you are trying to say here, T isn't a linear combination of anything, it is a set. You can't just assume existence of the d's. But you can use the fact that those c's exist to find d's that work and make this second equation true.

 

[matt grime]

Here's how I think of this.

Let S be a spanning set of vectors for a vector space V.

Let T be another set of vectors such that every element in S is a linear combination of elements in T (as is clearly the case here)

Given any vector v in V, it can be written as a combination of elements in S. As every element in S can be written in terms of elements in T, T must span too.

For example, suppose the elements in S are s_1, s_2, ... s_n, and the elements in T are t_1,t_2 ,..., t_r note n and r are not necessarily the same.

suppose that s_1 = t_1+3t_3, for example

if S spans and v = as_1+bs_2+cs_3+...

then we can substitute for s_1 in terms of the elements in T, and repeat for all other s_i using the relations there.

Note which sets are which S spans V and every element in S is a combination of elements in T, hence T spans V too.

There is absolutely no need to invoke a the word basis at all in this question.

 

[Oxymoron]

Let T be another set of vectors such that every element in S is a linear combination of elements in T

Should this read "Let T be another set of vectors such that every element in T is a linear combination of elements in S"?

How exactly is T a set of vectors that are linear combinations of the vectors in S? I know this is a dumb question. I just don't see it

Given any vector v in V, v it can be written as a linear combination of elements in S. As every element in S can be written in terms of elements in T, T must span too

This is not enough to convince me. How do you know that [tex]v[/tex] can be written as a linear combination of elements in [tex]S[/tex] and how do you know that every element in [tex]S[/tex] can be written in terms of elements in [tex]T[/tex].

I am really NOT getting this! So I will write exactly what I have... I need to be able to write down a solid proof. I can't just say that take any v in V, then it can be written as a linear combination of etc... I know to start the proof I have to take any v in V.

Take any [tex]\textbf{v} \in V[/tex].

Then this vector can be written as a linear combination of vectors in [tex]S[/tex] because [tex]S[/tex] spans [tex]V[/tex].

[tex]\textbf{v} = c_1 v_1 + c_2 v_2 + \dots + c_n v_n[/tex]

Now I need to show that every vector in [tex]T[/tex] can be written as a linear combinations of vectors in [tex]S[/tex] such that [tex]T = \{ v_1 - v_2, \dots , v_{n-1} - v_n, v_n \}.[/tex] How would I show this?

Once I show that every vector in [tex]T[/tex] can be written as a linear combinations of vectors in [tex]S[/tex] then my chosen [tex]\textbf{v}[/tex] can also be written as a linear combination of vectors in [tex]T[/tex] such that

[tex]\textbf{v} = d_1(v_1 - v_2) + d_2(v_2 - v_3) + \dots + d_n(v_n)[/tex]

Therefore [tex]T[/tex] spans [tex]V[/tex] if I can find [tex]d_i[/tex]'s which satisfy the above equation.

I hope you guys understand that I appreciate your time spent on my issue. Hopefully some day I will understand this question! - I have still yet to prove that if S is a linearly independent subset of V then so is T. But one question at a time...

 

[shmoe]

This is not enough to convince me. How do you know that [tex]v[/tex] can be written as a linear combination of elements in [tex]S[/tex] and ...

This was your assumption that S is a spanning set of V.

...how do you know that every element in [tex]S[/tex] can be written in terms of elements in [tex]T[/tex].

You can sit down and do it. The left side of the equations below will be the vectors in S, the right side will be linear combinations of the vectors in T:

[tex]v_n=v_n[/tex]
[tex]v_{n-1}=(v_{n-1}-v_{n})+v_n[/tex]
[tex]v_{n-2}=(v_{n-2}-v_{n-1})+(v_{n-1}-v_{n})+v_n[/tex]

and so on (do you know how to get these linear combinations?). This will prove that the vectors in S are in span T. Once you know this, you are pretty much finished. Since S is a set of vectors contained in span T, and span T is a vector space, the span S is containted in span T (a linear combination of vectors in a vector space is in that vector space again). Can you fill in the last few details that finish it off?


We can carry on in a different direction though, one that's appealing directly to the definition of span:

I am really NOT getting this! So I will write exactly what I have... I need to be able to write down a solid proof. I can't just say that take any v in V, then it can be written as a linear combination of etc... I know to start the proof I have to take any v in V.

Take any [tex]\textbf{v} \in V[/tex].

Then this vector can be written as a linear combination of vectors in [tex]S[/tex] because [tex]S[/tex] spans [tex]V[/tex].

[tex]\textbf{v} = c_1 v_1 + c_2 v_2 + \dots + c_n v_n[/tex]

Fine so far.

Now I need to show that every vector in [tex]T[/tex] can be written as a linear combinations of vectors in [tex]S[/tex] such that [tex]T = \{ v_1 - v_2, \dots , v_{n-1} - v_n, v_n \}.[/tex] How would I show this?

There's more than one way. Since we have the vectors of S as linear combinations of vectors in T (see above), you can just substitute them into your [tex]\textbf{v} = c_1 v_1 + c_2 v_2 + \dots + c_n v_n[/tex] equation, and group the T vectors. Try doing this and report back on what you get.

Once I show that every vector in [tex]T[/tex] can be written as a linear combinations of vectors in [tex]S[/tex] then my chosen [tex]\textbf{v}[/tex] can also be written as a linear combination of vectors in [tex]T[/tex] such that

[tex]\textbf{v} = d_1(v_1 - v_2) + d_2(v_2 - v_3) + \dots + d_n(v_n)[/tex]

Therefore [tex]T[/tex] spans [tex]V[/tex] if I can find [tex]d_i[/tex]'s which satisfy the above equation.

This is fine. You should be able to actually write down the d's from the c's.

I hope you guys understand that I appreciate your time spent on my issue. Hopefully some day I will understand this question! - I have still yet to prove that if S is a linearly independent subset of V then so is T. But one question at a time...

It will come. This can be difficult the first time you see it, but it gets much easier with practice.

 

[matt grime]

Should this read "Let T be another set of vectors such that every element in T is a linear combination of elements in S"?

no i meant exactly what i said. consider the counter example where T is a subset of S with a strictly smaller span. T then doesn't span the same vector space S spans which is what I showed.

Every vector in S is a linear combination of vectors in T, as shmoe showed, therefore

span(S) < span(T)

here < means containment of vector spaces

every vector in T is also a combination of vectors in S

thus span(T) < span(S)

hence the spans are equal.

 

[mathwonk]

this is basically the same question: start from the square identity matrix and introduce a "minus one" just above all the diagonal entries except the first one. Then ask if you can return this matrix to the identity matrix by elementary row operations.

then exactly the same operations suffice to express your first set of vectors in terms of your second set.

 

[HallsofIvy]

I am in need of some guidance on a question concerning vector spaces and spanning sets.

Q) Suppose that V is a vector space over F and {v1,...,vn} ⊂ V.
a) Prove that if {v1,...,vn} spans V, then so does {v1-v2,v2-v3,...,v(n-1)-v(n),vn}.

You might want to start by writing out the definition of "span" .

 

[mathwonk]

or do my exercise with row operations and then you will have essentially been doing the operations in the definition of the word "span" (i.e. linear combinations).