Results 1 to 14 of 14

Math Help - I'm trying to solve this problem. Could someone please help?. Thanks.

  1. #1
    Newbie
    Joined
    Aug 2012
    From
    australia
    Posts
    8

    Angry I'm trying to solve this problem. Could someone please help?. Thanks.

    x and y are row vectors having non-negative elements. The elements of x are arranged in the increasing order of magnitude. The positions of elements of y can be re-arranged. How can I show that xy' is maximum when the elements of y are also arranged in the increasing order of magnitude?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1

    Re: I'm trying to solve this problem. Could someone please help?. Thanks.

    Here is a suggestion to get you started. First consider the case where there are only two x's and two y's, i.e. the dimension of the vectors is 2. See if you can prove that case. Then you may be able to use that result to help prove the more general case.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2012
    From
    australia
    Posts
    8

    Re: I'm trying to solve this problem. Could someone please help?. Thanks.

    Thanks awkward. I went down that path and proved that it is true for 2 and 3 but then when I tried to use induction method, I couldn't prove it for n+1 after assuming that it is true for n. It is very involved. Is there any theorem that we can use to prove this?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1

    Re: I'm trying to solve this problem. Could someone please help?. Thanks.

    Instead of induction, you might try an indirect proof. Suppose the statement is false. Then what?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Mar 2012
    From
    Dresden
    Posts
    24
    Thanks
    1

    Re: I'm trying to solve this problem. Could someone please help?. Thanks.

    I'm not sure if I understand correctly.

    Do you mean that you have a finite-dimensional vector space with  x \in V, y \in V and then you construct
     \sum_{k=1}^n x_k y_k , where n is the dimension of you vector space?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1

    Re: I'm trying to solve this problem. Could someone please help?. Thanks.

    Yes, that's essentially correct, although I don't think viewing the sum as an inner product in a vector space is going to prove useful in this case. Just think of it as a sum.

    If the statement is false, then there must be a set of x's and y's where the x's are in ascending order, the y's are _not_ in ascending order, and the associated sum is maximized. There must be an i and j with i < j and y_i > y_j. What would it do to the sum if you switched them?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,369
    Thanks
    739

    Re: I'm trying to solve this problem. Could someone please help?. Thanks.

    if xi ≤ xj and yj < yi, (for i < j) then:

    xiyi + xjyj ≤ xjyi + xjyj < xjyi + xjyj

    the sum on the very LHS is from our supposedly "maximized" sum, and yet by switching just two terms (all the rest stay the same) we have created a "bigger sum" (on the far RHS). how can this be?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Aug 2012
    From
    australia
    Posts
    8

    Re: I'm trying to solve this problem. Could someone please help?. Thanks.

    Your proof is not clear to me. .....How did you get the two inequlities and how do you conclude that the question is incorrect? Please help.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Aug 2012
    From
    australia
    Posts
    8

    Re: I'm trying to solve this problem. Could someone please help?. Thanks.

    Yes, that's what it is. If you take them as vectors in vector space, I think swapping the elements of y would not change its magnitude but it will change the angle that it makes with vector x. So, the inner product will be different and could reach its maximum when the elements of y are arranged in the increasing order as well. Any thoughts mastermind2007?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,369
    Thanks
    739

    Re: I'm trying to solve this problem. Could someone please help?. Thanks.

    this has nothing to do with angle!
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Senior Member
    Joined
    Jul 2010
    From
    Vancouver
    Posts
    432
    Thanks
    16

    Re: I'm trying to solve this problem. Could someone please help?. Thanks.

    It does have something to do with the angle

    x \cdot y = |x||y|\cos\theta

    where \theta is the smallest angle between x and y. The dot product is maximized when \theta = 0. In general you will not be able to make \theta = 0 but by rearranging the elements of y you are going to make \theta as small as possible. The idea is that the two vectors will be close to one another in all the coordinates simultaneously. Ranjan is just thinking about this geometrically.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Newbie
    Joined
    Aug 2012
    From
    australia
    Posts
    8

    Re: I'm trying to solve this problem. Could someone please help?. Thanks.

    Thanks Vlasev. I'm still struggling to have this problem proved analytically though it seems to be correct. Any idea?
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Senior Member
    Joined
    Jul 2010
    From
    Vancouver
    Posts
    432
    Thanks
    16

    Re: I'm trying to solve this problem. Could someone please help?. Thanks.

    Ranjan, you have been told a lot already but it may be somewhat confusing. For example, what 'awkward' basically told you is to consider (for contradiction) a case where x is in ascending order but y is not in ascending order and their dot product is maximum. Deveno is not showing the the question is incorrect but is working out what 'awkward' suggested.

    Here is a slightly different view. We'll show that if y is not in ascending order, we can sort it a little bit (by swapping elements) to make it more so in ascending order and keep the dot product either the same or larger.

    Suppose that you are given x in ascending order and y not in ascending order. Then there must be entries y_i, y_j for which i < j but y_i > y_j. This is essentially a statement that y is not sorted. Now we sort y a little bit by swapping these two entries. Call this new vector y'. It is the same as y but now y_i' = y_j and y_j' = y_i. How much better is the dot product with y'? Well, we can check by taking the difference

    x\cdot y' - x \cdot y =  x_iy_i' + x_jy_j' -x_iy_i-x_iy_j = x_i y_j +x_j y_i - x_i y_i - x_j y_j

    This happens because y_k' = y_k when k \neq i,j. This equals

    -x_i (y_i-y_j) + x_j (y_i -  y_j) = (x_j - x_i) (y_i-y_j)

    Now x_j \ge x_i because x is in an ascending order and we have

    x\cdot y' - x \cdot y =  (x_j - x_i) (y_i-y_j) \ge 0

    That is, sorting y by swapping tow elements that are in the wrong order makes the dot product at least as big as the initial product. Since the vectors have finitely many entries, we can continue sorting y like this until we have all its entries in ascending order. The procedure above shows that the dot product stays the same (at worst) or increases a bit (if x_i < x_j). I hope this clarifies things for you.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Newbie
    Joined
    Aug 2012
    From
    australia
    Posts
    8

    Re: I'm trying to solve this problem. Could someone please help?. Thanks.

    Thanks Vlasev. That's really a nice proof.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Not sure how to solve this problem?
    Posted in the Algebra Forum
    Replies: 3
    Last Post: October 18th 2011, 10:33 AM
  2. Someone please help solve this problem
    Posted in the Algebra Forum
    Replies: 7
    Last Post: July 16th 2009, 04:24 PM
  3. i need help to solve these problem
    Posted in the Calculus Forum
    Replies: 0
    Last Post: March 28th 2009, 08:58 PM
  4. Anyone know how to solve this problem?
    Posted in the Pre-Calculus Forum
    Replies: 6
    Last Post: April 27th 2007, 03:22 AM
  5. Solve this problem please
    Posted in the Math Topics Forum
    Replies: 3
    Last Post: December 14th 2005, 03:24 PM

Search Tags


/mathhelpforum @mathhelpforum