Help with a proof involving the span of a subset

  • Thread starter Thread starter paulrb
  • Start date Start date
  • Tags Tags
    Proof Span
paulrb
Messages
18
Reaction score
1

Homework Statement


Let S be a subset of a vector space V, and let v be an element of V. Show that span(S) = span(S U {v}) if and only if v is an element of span(S)


Homework Equations





The Attempt at a Solution



I'm honestly not sure how to get started, I've spent time looking through the text but it hasn't helped.
 
Physics news on Phys.org
You have to do two things.

1. Suppose that v is in span(S), show that span(S)=span(S u {v}).

2. Show that if span(S u {v}) = span(S) then v is in span(S).

Let's look at 2 and break down what you know.

Definition: span(X) is the space of all linear combinations of objects in X.

You need to show v is in span(S).

You know that v is in span(S u {v}) as it is a linear combination of elements of S U {v} trivially.

You know that span(S u {v}) = span(S).

Hence...

Now try 1.
 
Thanks for your help, it allowed me to finish the rest of the proof.
 
Thread 'Use greedy vertex coloring algorithm to prove the upper bound of χ'
Hi! I am struggling with the exercise I mentioned under "Homework statement". The exercise is about a specific "greedy vertex coloring algorithm". One definition (which matches what my book uses) can be found here: https://people.cs.uchicago.edu/~laci/HANDOUTS/greedycoloring.pdf Here is also a screenshot of the relevant parts of the linked PDF, i.e. the def. of the algorithm: Sadly I don't have much to show as far as a solution attempt goes, as I am stuck on how to proceed. I thought...
Back
Top