Proving span and linear independancy of a matrix.

Printable View

October 16th 2009, 01:18 PM
joe909

Proving span and linear independancy of a matrix.

Ok I have two very smilar questions for you guys:

1) Prove that if (v1, . . .,vn) spans Rn, then so does the list

(
v1 −v2,v2−v3, . . .,vn−1−vn,vn).

2) Prove that if
(v1, . . .,vn) is linearly independent in Rn, then so is the list (v1 −v2,v2−v3, . . .,vn−1−vn,vn).

Proofs are new to me this year, and I seem to be struggling with a lot of them so far.

Any thoughts on this one?

Any help is very much appreciated :)
October 16th 2009, 02:05 PM
tonio

Quote:

Originally Posted by joe909

Ok I have two very smilar questions for you guys:

1) Prove that if (v1, . . .,vn) spans Rn, then so does the list

(

v1 −v2,v2−v3, . . .,vn−1−vn,vn).

2) Prove that if (v1, . . .,vn) is linearly independent in Rn, then so is the list (v1 −v2,v2−v3, . . .,vn−1−vn,vn).

Proofs are new to me this year, and I seem to be struggling with a lot of them so far.

Any thoughts on this one?

Any help is very much appreciated :)

In this case both questions are one and the same IF you already know that dim IR^n = n and n lin. independent vectors in IR^n are a basis.

Now we know that {v_1,...,v_n} are lin. ind. This means that the linear combination a_1*v_1 +...+ a_*v_n = 0 is possible iff a_1 =...= a_n = 0 , where the a_i are scalars in IR (real numbers).

Well, USING THIS, you have to prove that if b_1*(v_1 - v_2) +...+ b_n*(v_(n-1) - v_n) = 0 then IT MUST BE that the scalars b_1 =...= b_n = 0.
Hint: open parentheses, do some order and USE THE FIRST PART...

Tonio
October 16th 2009, 02:09 PM
Defunkt

Quote:

Originally Posted by joe909

Ok I have two very smilar questions for you guys:

1) Prove that if (v1, . . .,vn) spans Rn, then so does the list

(
v1 −v2,v2−v3, . . .,vn−1−vn,vn).

2) Prove that if
(v1, . . .,vn) is linearly independent in Rn, then so is the list (v1 −v2,v2−v3, . . .,vn−1−vn,vn).

Proofs are new to me this year, and I seem to be struggling with a lot of them so far.

Any thoughts on this one?

Any help is very much appreciated :)

For #1, recall that the condition for a set $A = \{v_1,v_2,...,v_n\}$ to span some space V (over a field F), is that $\forall v \in V$ , there exist some scalars $\alpha_1,\alpha_2,...,\alpha_n \in F$ , not all zero, such that $v = \alpha_1v_1 + \alpha_2v_2 + ... + \alpha_nv_n$ . That is to say, any element in V can be expressed as a linear combination of the set's elements.

In this question we are given that this is correct for the set $B=\{v_1,v_2,...,v_n\}$ and we need to prove that it is also correct for $B' = \{v_1-v_2,v_2-v_3,...,v_{n-1}-v_n,v_n\}$ .

Since it is correct for B, there exist $a_1,a_2,...,a_n \in F$ not all zero such that for any $v\in V, \ v=a_1v_1 + a_2v_2 + ... + a_nv_n$ . We want to find scalars $\beta_1,\beta_2,...,\beta_n \in F$ such that $v = \beta_1(v_1-v_2) + \beta_2(v_2-v_3) + ... + \beta_{n-1}(v_{n-1}-v_n) + \beta_nv_n$ . Try to see what happens if we let
$\beta_1 = \alpha_1$
$\beta_2 = \alpha_2 - \beta_1$
.
.
$\beta_i = \alpha_i - \beta_{i-1} \ \forall 2 \leq i \leq n$

Tonio: I think he has not reached the part of basis yet - this is why he is required to prove both claims... also, it is good practice to do so since he is only now starting with proofs!
October 16th 2009, 04:04 PM
joe909

Quote:

For #1, recall that the condition for a set http://www.mathhelpforum.com/math-he...cb91d69d-1.gif to span some space V (over a field F), is that http://www.mathhelpforum.com/math-he...318bf456-1.gif, there exist some scalars http://www.mathhelpforum.com/math-he...ce96290c-1.gif, not all zero, such that http://www.mathhelpforum.com/math-he...1cab6e45-1.gif. That is to say, any element in V can be expressed as a linear combination of the set's elements.

In this question we are given that this is correct for the set http://www.mathhelpforum.com/math-he...94523ffb-1.gif and we need to prove that it is also correct for http://www.mathhelpforum.com/math-he...190f1b2a-1.gif.

Since it is correct for B, there exist http://www.mathhelpforum.com/math-he...12023e3e-1.gif not all zero such that for any http://www.mathhelpforum.com/math-he...462a28d9-1.gif. We want to find scalars http://www.mathhelpforum.com/math-he...2cf637bf-1.gif such that http://www.mathhelpforum.com/math-he...f3746752-1.gif. Try to see what happens if we let
http://www.mathhelpforum.com/math-he...626c4f50-1.gif
http://www.mathhelpforum.com/math-he...eeeb3e4b-1.gif
.
.
http://www.mathhelpforum.com/math-he...984ab136-1.gif

Tonio: I think he has not reached the part of basis yet - this is why he is required to prove both claims... also, it is good practice to do so since he is only now starting with proofs!

I'd like to thank you a lot for your help. Ill show you what I have and if you could let me know if im on the right track that would be great.

So i took your suggestion and I end up with the following

let alpha= a

v=a1v1 + (a2 - 2a1)(v2) + (a3-2a2-2a1)(v3)....

Im not really sure how this qualifies as a proof though. I see that all the a values are scalars so we combine them to one variable value, is that enough to say that its span is Rn?.

Also im not sure how we can make the assumption that http://www.mathhelpforum.com/math-he...626c4f50-1.gif.

Im sure theese are probably really bad questions, but im having a lot of trouble getting this for some reason.

Thanks again for your help :)
October 16th 2009, 04:53 PM
Defunkt

Quote:

Originally Posted by joe909

I'd like to thank you a lot for your help. Ill show you what I have and if you could let me know if im on the right track that would be great.

So i took your suggestion and I end up with the following

let alpha= a

v=a1v1 + (a2 - 2a1)(v2) + (a3-2a2-2a1)(v3)....

Im not really sure how this qualifies as a proof though. I see that all the a values are scalars so we combine them to one variable value, is that enough to say that its span is Rn?.

Also im not sure how we can make the assumption that http://www.mathhelpforum.com/math-he...626c4f50-1.gif.

Im sure theese are probably really bad questions, but im having a lot of trouble getting this for some reason.

Thanks again for your help :)

I don't really understand what you did in the first part...

Perhaps you misunderstood what I was saying. In order to prove that $B' = \{v_1-v_2, v_2-v_3,...,v_{n-1}-v_n,v_n\}$ spans $\mathbb{R}^n$ , you need to show that there exist some (it is up to you to find them) scalars, $\beta_1,\beta_2,...,\beta_{n-1},\beta_n \in F$ , not all of them zero, such that for any v in $\mathbb{R}^n$ , $v = \beta_1(v_1-v_2) + \beta_2(v_2-v_3) + ... + \beta_{n-1}(v_{n-1}-v_n) + \beta_nv_n$ .

That is to say, any element in V can be expressed as a linear combination of the elements of B'. So the proof is done by finding those coefficients ( $\beta_1,...,\beta_n$ ). We don't assume that $\beta_1=\alpha_1$ - we just let $\beta_1=\alpha_1$ . Surely we can do that.

Now we simply need to show that those specific coefficients satisfy the condition we want: that for every $v \in \mathbb{R}^n$ , given that $v = \alpha_1v_1 + \alpha_2v_2 + ... + \alpha_nv_n$ , this statement holds: $\beta_1(v_1-v_2) + \beta_2(v_2-v_3) + ... + \beta_{n-1}(v_{n-1}-v_n)+\beta_nv_n = v$ .

Now, if we let:
$\beta_1=\alpha_1$
$\beta_i = \alpha_i + \beta_{i-1}$ for all i between 2 and n (this was a mistake in my first post -- there shouldv'e been a plus sign here, not a minus)

And substitute them into $\beta_1(v_1-v_2) + \beta_2(v_2-v_3) + ... + \beta_{n-1}(v_{n-1}-v_n)+\beta_nv_n$ , we get:

$\beta_1(v_1-v_2) + \beta_2(v_2-v_3) + ... + \beta_{n-1}(v_{n-1}-v_n)+\beta_nv_n = \alpha_1(v_1-v_2) + (\alpha_2+\alpha_1)(v_2-v_3) + ... +$ $(\sum_{i=1}^{n-1}\alpha_i)(v_{n-1}-v_n) + (\sum_{i=1}^{n}\alpha_i)v_n$ (*)

I'll leave it to you to show that (*) = $\alpha_1v_1 + \alpha_2v_2 + ... + \alpha_nv_n$ and with that the proof will be done.
October 16th 2009, 08:42 PM
joe909

Quote:

I don't really understand what you did in the first part...

Perhaps you misunderstood what I was saying. In order to prove that http://www.mathhelpforum.com/math-he...a9c991d1-1.gif spans http://www.mathhelpforum.com/math-he...453d1310-1.gif, you need to show that there exist some (it is up to you to find them) scalars, http://www.mathhelpforum.com/math-he...f05e6aec-1.gif, not all of them zero, such that for any v in http://www.mathhelpforum.com/math-he...453d1310-1.gif , http://www.mathhelpforum.com/math-he...f3746752-1.gif.

That is to say, any element in V can be expressed as a linear combination of the elements of B'. So the proof is done by finding those coefficients (http://www.mathhelpforum.com/math-he...32881822-1.gif). We don't assume that http://www.mathhelpforum.com/math-he...423490a7-1.gif - we just let http://www.mathhelpforum.com/math-he...423490a7-1.gif. Surely we can do that.

Now we simply need to show that those specific coefficients satisfy the condition we want: that for every http://www.mathhelpforum.com/math-he...d2217417-1.gif, given that http://www.mathhelpforum.com/math-he...1cab6e45-1.gif, this statement holds: http://www.mathhelpforum.com/math-he...979697da-1.gif.

Now, if we let:
http://www.mathhelpforum.com/math-he...423490a7-1.gif
http://www.mathhelpforum.com/math-he...deec242c-1.gif for all i between 2 and n (this was a mistake in my first post -- there shouldv'e been a plus sign here, not a minus)

And substitute them into http://www.mathhelpforum.com/math-he...af635993-1.gif, we get:

http://www.mathhelpforum.com/math-he...45526de4-1.gif http://www.mathhelpforum.com/math-he...75902a28-1.gif (*)

I'll leave it to you to show that (*) = http://www.mathhelpforum.com/math-he...44d8b4cb-1.gif and with that the proof will be done.

Thank you very much. Not only was I able to finish the proof, but I now feel I better understand what I was trying to prove and why the proof works. The tip about the http://www.mathhelpforum.com/math-he...deec242c-1.gif helped a lot.

I really appreciate you spending the time to help with me this problem.
October 17th 2009, 04:40 AM
alexandrabel90

sorry, im new to this topic as well.

may i know how you know that Beta i can be expressed in terms of alpha and that it is

beta i = alpha i + beta (i-1)

can it be expressed in any forms of alpha or only like taht?

thanks!
October 17th 2009, 04:57 AM
Defunkt

Quote:

Originally Posted by alexandrabel90

sorry, im new to this topic as well.

may i know how you know that Beta i can be expressed in terms of alpha and that it is

beta i = alpha i + beta (i-1)

can it be expressed in any forms of alpha or only like taht?

thanks!

Well, you can simply write $\beta_i = \sum_{k=1}^{i} \alpha_k$

To prove that $\{v_1-v_2,...,v_{n-1}-v_n,v_n\}$ spans $\mathbb{R}^n$ , we need to show the existence of those $\beta_i$ s... that is - we need to find them and show that they withhold our condition. In other words, we want to find coefficients $\beta_1,\beta_2,...,\beta_n$ that solve this equation: $\beta_1(v_1-v_2) + \beta_2(v_2-v_3) + ... + \beta_{n-1}(v_{n-1}-v_n)+\beta_nv_n = \alpha_1v_1 + \alpha_2v_2+...+\alpha_nv_n$ (**)

My thought process on choosing those specific coefficients was this: Consider the fact that $v_1$ is only in one of the elements of $B'$ , and its coefficient in the RHS of (**) is $\alpha_1$ , so that will be the coefficient of its one element in the LHS as well. That's why $\beta_1=\alpha_1$ . Now consider $v_2$ -- its coefficient is now $(-\alpha_1)$ and we want to complete it to $\alpha_2$ with our remaining coefficient. So we will let $\beta_2 = \alpha_2+\alpha_1$ ==> the coefficient of $v_2$ is $\alpha_2+\alpha_1-\alpha_1 = \alpha_2$ just like we wanted. The same process continues for the rest of the elements of B'.
October 18th 2009, 07:29 AM
joe909

2) Prove that if
(v1, . . .,vn) is linearly independent in Rn, then so is the list (v1 −v2,v2−v3, . . .,vn−1−vn,vn).

For the second question is it enough to just say that
0=a1v1+a2v2+...anv such that a1 = 0, a2 = 0, ... ,an = 0.

And we know we can make http://www.mathhelpforum.com/math-he...979697da-1.gif.
= http://www.mathhelpforum.com/math-he...1cab6e45-1.gif
by letting
b1 = a1
b2 = a2+b1
ect.
so therefore (v1 −v2,v2−v3, . . .,vn−1−vn,vn) is also linearly independant?
is this not kind of cheating though as we are effectively just letting all the b values = 0? Or is this enough for the proof, or am i possibly on the complete wrong track.
October 18th 2009, 07:42 AM
aman_cc

Quote:

Originally Posted by joe909

2) Prove that if
(v1, . . .,vn) is linearly independent in Rn, then so is the list (v1 −v2,v2−v3, . . .,vn−1−vn,vn).

For the second question is it enough to just say that
0=a1v1+a2v2+...anv such that a1 = 0, a2 = 0, ... ,an = 0.

And we know we can make http://www.mathhelpforum.com/math-he...979697da-1.gif.
= http://www.mathhelpforum.com/math-he...1cab6e45-1.gif
by letting
b1 = a1
b2 = a2+b1
ect.
so therefore (v1 −v2,v2−v3, . . .,vn−1−vn,vn) is also linearly independant?
is this not kind of cheating though as we are effectively just letting all the b values = 0? Or is this enough for the proof, or am i possibly on the complete wrong track.

Hi - I trust you are correct in your approach but wrong in your argument. You demonstrated one set of values of b1,b2,,,bn which works. There might be other values. for e.g
0.v1 + 0.(2v1) = 0 but are they independent?
2.v1 + -1.(2v1) = 0 also works.
October 18th 2009, 08:31 AM
joe909

Quote:

Originally Posted by aman_cc

Hi - I trust you are correct in your approach but wrong in your argument. You demonstrated one set of values of b1,b2,,,bn which works. There might be other values. for e.g
0.v1 + 0.(2v1) = 0 but are they independent?
2.v1 + -1.(2v1) = 0 also works.

So is this what you are saying:

since we know (v1, . . .,vn) is linearly independent we know that
0=a1v1+a2v2+...anv such that a1 = 0, a2 = 0, ... ,an = 0. because in order for it to be linearly independant all the scalars must be 0 correct?

And from the first part we proved that we can convert http://www.mathhelpforum.com/math-he...979697da-1.gif.
into http://www.mathhelpforum.com/math-he...1cab6e45-1.gif by letting b1 = a1
b2 = a2+b1.

However you are saying that I need to prove that there arent other possible Beta values other then b1=a1, b2=a2+b1, ect. that will add up to 0? That makes sense to me, however im not sure how I would even begin going about doing that, any tips or suggestions?
October 18th 2009, 09:08 AM
aman_cc

Quote:

Originally Posted by joe909

So is this what you are saying:

since we know (v1, . . .,vn) is linearly independent we know that
0=a1v1+a2v2+...anv such that a1 = 0, a2 = 0, ... ,an = 0. because in order for it to be linearly independant all the scalars must be 0 correct?

And from the first part we proved that we can convert http://www.mathhelpforum.com/math-he...979697da-1.gif.
into http://www.mathhelpforum.com/math-he...1cab6e45-1.gif by letting b1 = a1
b2 = a2+b1.

However you are saying that I need to prove that there arent other possible Beta values other then b1=a1, b2=a2+b1, ect. that will add up to 0? That makes sense to me, however im not sure how I would even begin going about doing that, any tips or suggestions?

Hint - You need to use the fact that v1,v2....vn are independent !
I would also structure your problem better/clearer.
Known fact: a1v1+...+anvn = 0 => a1,a2....an =0
To prove:
http://www.mathhelpforum.com/math-he...979697da-1.gif = 0 => b1,b2,...,bn = 0

If you read this formulation is equivalent to what you are doing.
You have actually done it pretty much. It's trivial.