Inner Product Proof: Proving Sums with Algebra and Inner Product Concepts

[evilpostingmong]

Homework Statement

Prove that
(\suma_jb_j)²\leq\sumja_j²*\sum(b_j)²/j with j from 1 to n.

for all real numbers a1...an and b1...bn

Homework Equations

The Attempt at a Solution

I can prove this using algebra, but how is it done
using inner product concepts? If someone could start me up with a hint,
I could get somewhere. Thank you!
Note: It is apparent that those sums could possibly be inner products of vectors,
but I can't see how going into inner product notation would help me out.

 

[Dick]

Define a diagonal matrix N so that the diagonal entries are (sqrt(1),sqrt(2)...sqrt(n)). Can you write the rhs in terms of the transformation N? Think about using the inequality (a.b)^2<=(a.a)^2*(b.b)^2. I don't think it's all that easy to prove using algebra. Can you prove it that way for the n=2 case?

 

[Office_Shredder]

Do you know how to prove

(\sum a_j b_j)^2 \leq \sum a_j^2 \sum b_j^2?

If so, try looking at

a_j b_j = \sqrt{j} a_j \frac{b_j}{\sqrt{j}}

 

[evilpostingmong]

Define a diagonal matrix N so that the diagonal entries are (sqrt(1),sqrt(2)...sqrt(n)). Can you write the rhs in terms of the transformation N? Think about using the inequality (a.b)^2<=(a.a)^2*(b.b)^2. I don't think it's all that easy to prove using algebra. Can you prove it that way for the n=2 case?

so define v to be=a1v1+a2v2 and u to be b1u1+b2u2 and define N to be a matrix with (sqrt(1)...sqrt(n)) along its diagonal
with n=2.
The dot product of N(v) to itself is <N(v),N(v)>^2=(v,sqrt(2)v)^2=sqrt(a1^2+2*a2^2)^2=a1^2+2a2^2
and same for u except it turns out to be b1^2+b2^2/2
so it is (a1^2+2a2^2)*(b1^2+b2^2/2) how is it so far?
I think at this point, the proof is pretty obvious, but I can't expect it to be that easy,
thats why I asked here.

 

[Dick]

The algebraic proof that (a1*b1+a2*b2)^2<=(a1^2+2*a2^2)*(b1^2+b2^2/2) is not particularly obvious. You said you could, that's why I asked. It is pretty obvious using inner products (ha, ha, meaning it took me a while to see it). Can you try phrasing it in that language? I'll give you a hint. What's N^(-1)?

 

[evilpostingmong]

The algebraic proof that (a1*b1+a2*b2)^2<=(a1^2+2*a2^2)*(b1^2+b2^2/2) is not particularly obvious. You said you could, that's why I asked. It is pretty obvious using inner products (ha, ha, meaning it took me a while to see it). Can you try phrasing it in that language?

you mean the language of inner products, right?

 

[Dick]

you mean the language of inner products, right?

Are you stalling for time? Of course I mean that. What's the rhs in terms of the linear transformation N? I already asked you this. Yes, <Na,Na> is the first factor. What's the second one? BTW, is this a Knuth problem or is this from the linear algebra book?

 

[evilpostingmong]

The algebraic proof that (a1*b1+a2*b2)^2<=(a1^2+2*a2^2)*(b1^2+b2^2/2) is not particularly obvious. You said you could, that's why I asked. It is pretty obvious using inner products (ha, ha, meaning it took me a while to see it). Can you try phrasing it in that language? I'll give you a hint. What's N^(-1)?

the rhs is <a1, sqrt(2)a2>^2 *<b1, b2/sqrt(2)>^2 N^-1
takes it back to <a1,a2>^2*<b1,b2>^2

wait a minute, that's the same as <a1,b1>^2*<a2,b2>^2
or <a1,b1>^2*<sqrt(2)a2,b2/sqrt(2)>^2

 

[evilpostingmong]

Are you stalling for time? Of course I mean that. What's the rhs in terms of the linear transformation N? I already asked you this. Yes, <Na,Na> is the first factor. What's the second one? BTW, is this a Knuth problem or is this from the linear algebra book?

the linear algebra book

 

[Dick]

Sorry, but you have a real ability to scramble things up. I only mentioned the n=2 special case because you said you could prove it algebraically. I don't think you can. The sum(j*aj^2) part is <Na,Na> right, do you agree with with that? What the sum(bj^2/j) part in terms of the vector b and N?

 

[Dick]

the linear algebra book

Ok, had a Knuth feeling. But let's continue.

 

[evilpostingmong]

Sorry, but you have a real ability to scramble things up. I only mentioned the n=2 special case because you said you could prove it algebraically. I don't think you can. The sum(j*aj^2) part is <Na,Na> right, do you agree with with that? What the sum(bj^2/j) part in terms of the vector b and N?

<Nb,Nb>

 

[Dick]

<Nb,Nb> is b1*b1+2*b2*b2+3*b3*b3... Isn't it? That isn't what you want. Why don't you think about what you write actually means!? You want b1*b1+b2*b2/2+b3*b3/3... Don't you? Consider N^(-1).

 

[evilpostingmong]

<Nb,Nb> is b1*b1+2*b2*b2+3*b3*b3... Isn't it? That isn't what you want. You want b1*b1+b2*b2/2+b3*b3/3... Don't you? Consider N^(-1).

oh <N^(-1)b,N^(-1)b>
I think I see where this is going...
<Na,Na>*<N^(-1)b,N^(-1)b> = <Na,N^(-1)b><Na,N^(-1)b> = <Na,N(-1)b>^2 = <a,b>^2
or am I jumping the gun as usual?

 

[Dick]

Is that an "oh" as in "yes sir, I'll put in just what you say!" or is that an "oh" as in, "ok, I really understand what you are saying. And I realize my previous post was completely thoughtless and in the future I will actually think about what the symbols I'm posting mean before I thoughtlessly post them"? There is a reason why your threads go to high post counts and this is it.

 

[Dick]

oh <N^(-1)b,N^(-1)b>
I think I see where this is going...
<Na,Na>*<N^(-1)b,N^(-1)b> = <Na,N^(-1)b><Na,N^(-1)b> = <Na,N(-1)b>^2 = <a,b>^2
or am I jumping the gun as usual?

Jumping the gun. The equality is not true. The inequality is. You seem to be able to prove anything instantly. By moving symbols around without rhyme or reason. Stop it! Slap yourself for me. Sober up! You didn't post one single reason why anyone should think anything you did is true. You just 'rearranged things'. In seriously random ways. That IS NOT A PROOF. A proof involves giving reasons for what you do. On this issue you seem to still not get it.

 

[evilpostingmong]

Jumping the gun. The equality is not true. The inequality is. You seem to be able to prove anything instantly. By moving symbols around without rhyme or reason. Stop it! Slap yourself for me. Sober up! You didn't post one single reason why anyone should think anything you did is true. You just 'rearranged things'.

<Na,Na>*<N^(-1)b,N^(-1)b> ok so we have this to work with

 

[Dick]

<Na,Na>*<N^(-1)b,N^(-1)b> ok so we have this to work with

Yes, you have that to work with. Don't forget my hint to use <x,y>^2<=<x,x>^2*<y,y>^2. Office-Shredder made a useful suggestion on the first page. And don't forget my screaming from the first page. If I get one more proof by random symbol transposition, you are dead to me. Try to make it count. Give a reason for every step you take. I'm trusting in you.

 

[evilpostingmong]

Yes, you have that to work with. Don't forget my hint to use <x,y>^2<=<x,x>^2*<y,y>^2. Office-Shredder made the same suggestion I'm making. And don't forget my screaming from the first page. If I get one more proof by random symbol transposition, you are dead to me. Try to make it count.

ok...
Consider x>y. If x>y, then (<x,x>)^2 is >(<x,y>)^2. Since (<x,x>)^2*(<y,y>)^2 is
> (<x,x>)^2, (<x,x>)^2*(<y,y>)^2 is > (<x,y>)^2 for x>y.

How is this so far? It has "if" "then" and it looks like its trying
form an argument (not random symbol pushing).

heart: ba dub BA DUB BA DUB BA DUB

 

[Dick]

ok...
Consider x>y. If x>y, then (<x,x>)^2 is >(<x,y>)^2. Since (<x,x>)^2*(<y,y>)^2 is
> (<x,x>)^2, (<x,x>)^2*(<y,y>)^2 is > (<x,y>)^2 for x>y.

How is this so far? It has "if" "then" and it looks like its trying
form an argument (not random symbol pushing).

heart: ba dub BA DUB BA DUB BA DUB

Sigh. You are making this up, aren't you? Do you read the text of the book before you start doing proofs or are you just improvising? i) What is x>y supposed to mean when x and y are vectors? If it's x1>y1, x2>y2, ... then take x=(0,0) and y=(-1,-1). Is <x,x> > <y,y>?? ii) if 'x>y' meant anything, is it something you can assume in the proof. Why?? Write me a 500 word essay on the history and significance of the 'Cauchy-Schwarz inequality, ok? In the essay, speculate on how using it can save you from writing bales of gibberish about vector inequalities.

 

[evilpostingmong]

That's pretty much what I meant. x>y means that the components of x are greater than
the components of y.

 

[Dick]

That's pretty much what I meant. x>y means that the components of x are greater than
the components of y.

Then you are pretty clear on why that is a useless assumption to make even if you could make it. I hope.

 

[Fredrik]

This thread is much more entertaining than I expected when I clicked it.

 

[evilpostingmong]

Yes, I am pretty clear. So the Cauchy Shwartz inequality is
l<x,y>l<=llxll llyll its obvious that if x is a zero vector, then x.y=0 and
llxll=sqrt(0^2)=0 and llxll*llyll=0 so the equality is true in this case, same for
when y=0. Is this right so far?

 

[Dick]

Yes, I am pretty clear. So the Cauchy Shwartz inequality is
l<x,y>l<=llxll llyll its obvious that if x is a zero vector, then x.y=0 and
llxll=sqrt(0^2)=0 and llxll*llyll=0 so the equality is true in this case, same for
when y=0. Is this right so far?

Sure. Now can you apply that to your problem?

 

[evilpostingmong]

ok we know that <x,y>^2<=<Nx,Nx>*<N^(-1)y,N^(-1)y>
Here we apply the Cauchy Schwartz inequality <x,y><=llNxll*llN^(-1)yll.
Consider x is a 0 vector. If x is a 0 vector, then x.y=0 and llNxll=sqrt(0^2)=0.
Multiplying llN^(-1)yll by 0 will give 0 so the equality holds if x (or y ) is a 0 vector.

 

[Dick]

ok we know that <x,y>^2<=<Nx,Nx>*<N^(-1)y,N^(-1)y>
Here we apply the Cauchy Schwartz inequality <x,y><=llNxll*llN^(-1)yll.
Consider x is a 0 vector. If x is a 0 vector, then x.y=0 and llNxll=sqrt(0^2)=0.
Multiplying llN^(-1)yll by 0 will give 0 so the equality holds if x (or y ) is a 0 vector.

Who cares about zero vectors? And that's not what Cauchy Schwarz says. The inequality says <a,b>^2<=<a,a>*<b,b> for any two vectors a and b. What a and b do you propose to put into that inequality? Tell me what a will equal and what b will equal. You can't just put a=x on one side and a=Nx on the other side.

 

[evilpostingmong]

The beginning may be a bit confusing, but it gets better later on.
This is the equality case of the inequality.
for l<a,b>l<=llall*llbll assume that w is orthogonal to b and that b is horizontal.
Assume cb is a scalar multiple of b and a is the "hypoteneuse." Let a=cb+w.
Let w=0 because it is orthogonal to b and cb and in future steps we will be dividing by b so we can't divide by 0.Here w=a-cb and let 0=<a-cb,b>. This comes out to be 0=<a,b>-c*llbll². Here c must=<a,b>/llbll² which would give (<a,b>/llbll²)*llbll²=<a,b>
thus we get 0=<a,b>-<a,b>. The value for c allows w to be=0 (why? Take w=a-cb and a-(<a,b>/llbll²)b=a-a*llbll²/llbll²=a-a=0) Now that we know what c is, plug in c into the equation
a=cb+w (or a=cb+(a-cb)) let a=<a,b>*b/llbll+w (note that w replaces a-cb for clarity's sake,
and take note that w=a-<a,b>*b/llbll²). Now, applying the Pyth.Theorem gives
llall²=ll<a,b>ll^2*llbll^2/llbll⁴+llwll²
or llall²= l<a,b>l²/llbll²+llwll².
Taking square roots on both sides gives llall=l<a,b>l/llbll+llwll Now that
we have an expression for llall, we need an expression for llall*llbll. That would
be (l<a,b>l/llbll+llwll)*llbll. Now, distributing llbll gives (l<a,b>l*llbll/llbll+llwll*llbll)
and since llwll*llbll=0 (since w is a zero vector and is orthogonal to b),
llall*llbll=(l<a,b>l)>=l<a,b>l. Note that the fact that w is orthogonal to a scalar
multiple of b, the fact that cb+w forms a right triangle with w touching
the "head" of a, and w being zero makes the equality case possible.

Know that the reason why I didn't prove the exact problem at hand is because
I felt that I hadn't really understood the Cauchy Schwartz inequality and
since it's proof would allow me to solve this problem, I figured it would be
better for me to ignore N and work with a more general case.

 

[Dick]

This is just plain abusive to people trying to help you. I'm not going to even try to read that. It hurts too much. You were about three lines away from proving the original problem using Cauchy-Schwarz ages ago and now you back up and make a left turn into this swamp. There's multiple errors all through that. Here's only one. "llal^l2= l<a,b>|^2/llbll^2+llwll^2. Taking square roots on both sides gives llall=l<a,b>l/llbll+llwll". Do you have any idea how wrong that is? I didn't think so. If you were to undertake a special research project, could you figure out what's wrong with it? I doubt it, but prove me wrong. What's wrong with taking the square root of a^2+b^2=c^2 and concluding a+b=c?? Huh?? If you actually think about it and conclude there is nothing wrong, I can't help you.

I get the sense that you are trying to prove stuff in a super creative way, unlike ordinary people, using weird concepts of your own creation instead of actually learning how to how to do these problems. Which is the actual purpose of the forum. Some people continue in what you are doing their whole lives. They can prove ANYTHING. But no one believes them. They are called "cranks".

You don't want to be one of those, do you? Proving Cauchy-Schwarz isn't that obvious but it's not that hard. It involves what is essentially a trick. If you REALLY want to understand it, why don't you look up the standard proof and try to understand it? If you have problems understanding it then post here. If you have another crank proof, with numerous flaws, don't. It's not worth it. You could be doing something more interesting like, creating a false proof of Fermat's Last Theorem instead of something known. In spite of what Fredrik thinks, this is getting less amusing by the second.

 

[Fredrik]

Why don't you just do it like this?

Step 1: Prove that \langle x,y\rangle=\sum_n x_n y_n defines an inner product.
Step 2: Show that this definition turns the Cauchy-Schwartz inequality into

\left(\sum_j x_j y_j\right)^2\leq\left(\sum_j x_j^2\right)\left(\sum_j y_j^2\right)

Step 3: Make a specific choice of x_j and y_j that turns the inequality into the one you want, and explain why you're allowed to do that.

 

[Dick]

Why don't you just do it like this?

Step 1: Prove that \langle x,y\rangle=\sum_n x_n y_n defines an inner product.
Step 2: Show that this definition turns the Cauchy-Schwartz inequality into

\left(\sum_j x_j y_j\right)^2\leq\left(\sum_j x_j^2\right)\left(\sum_j y_j^2\right)

Step 3: Make a specific choice of x_j and y_j that turns the inequality into the one you want, and explain why you're allowed to do that.

Steps 1 and 2 are probably unnecessary. We are doing standard inner product, standard Cauchy-Schwarz. It's step 3 that seems to be the obstacle for these 30 posts. Good luck.

 

[Fredrik]

The beginning may be a bit confusing, but it gets better later on.

It didn't get much better, and let's be realistic, no one is going to read that far anyway unless you can make more sense in the beginning.

If you're trying to prove the Cauchy-Schwartz inequality, the standard trick is to note that \langle x,x\rangle\geq 0 for all x, and that this means that

0\leq\langle x+ty,x+ty\rangle

for all vectors x,y and all scalars t. You get the Cauchy-Schwartz inequality by using the properties of the inner product and choosing t to make the right-hand side as small as possible. This is the trick that all the books use, which makes me think that it's the easiest method by far. See Wikipedia for more details.

 

[Fredrik]

Steps 1 and 2 are probably unnecessary. We are doing standard inner product, standard Cauchy-Schwarz. It's step 3 that seems to be the obstacle for these 30 posts.

I guess that explains your frustration.

 

[evilpostingmong]

I read the proof, and it involves the quadratic formula. Dick's right, it does
have a weird trick that comes from nowhere (but makes sense anyway).
Seems kinda advanced, but understandable. I don't know why it was included as
problem #3 in my book.
Thanks for the help guys!