• Aug 13th 2012, 07:52 PM
Ranjan
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?
• Aug 14th 2012, 02:21 PM
awkward
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.
• Aug 14th 2012, 09:30 PM
Ranjan
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?
• Aug 15th 2012, 03:25 AM
awkward
Instead of induction, you might try an indirect proof. Suppose the statement is false. Then what?
• Aug 15th 2012, 07:04 AM
mastermind2007
I'm not sure if I understand correctly.

Do you mean that you have a finite-dimensional vector space with $\displaystyle x \in V, y \in V$ and then you construct
$\displaystyle \sum_{k=1}^n x_k y_k$, where n is the dimension of you vector space?
• Aug 15th 2012, 01:47 PM
awkward
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 $\displaystyle y_i > y_j$. What would it do to the sum if you switched them?
• Aug 15th 2012, 04:47 PM
Deveno
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?
• Aug 15th 2012, 08:28 PM
Ranjan
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.
• Aug 15th 2012, 08:32 PM
Ranjan
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?
• Aug 15th 2012, 09:34 PM
Deveno
this has nothing to do with angle!
• Aug 15th 2012, 10:05 PM
Vlasev
It does have something to do with the angle

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

where $\displaystyle \theta$ is the smallest angle between $\displaystyle x$ and $\displaystyle y$. The dot product is maximized when $\displaystyle \theta = 0$. In general you will not be able to make $\displaystyle \theta = 0$ but by rearranging the elements of $\displaystyle y$ you are going to make $\displaystyle \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.
• Aug 15th 2012, 10:41 PM
Ranjan
Thanks Vlasev. I'm still struggling to have this problem proved analytically though it seems to be correct. Any idea?
• Aug 15th 2012, 11:41 PM
Vlasev
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 $\displaystyle x$ is in ascending order but $\displaystyle 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 $\displaystyle 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 $\displaystyle x$ in ascending order and $\displaystyle y$ not in ascending order. Then there must be entries $\displaystyle y_i, y_j$ for which $\displaystyle i < j$ but $\displaystyle y_i > y_j$. This is essentially a statement that $\displaystyle y$ is not sorted. Now we sort $\displaystyle y$ a little bit by swapping these two entries. Call this new vector $\displaystyle y'$. It is the same as $\displaystyle y$ but now $\displaystyle y_i' = y_j$ and $\displaystyle y_j' = y_i$. How much better is the dot product with $\displaystyle y'$? Well, we can check by taking the difference

$\displaystyle 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 $\displaystyle y_k' = y_k$ when $\displaystyle k \neq i,j$. This equals

$\displaystyle -x_i (y_i-y_j) + x_j (y_i - y_j) = (x_j - x_i) (y_i-y_j)$

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

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

That is, sorting $\displaystyle 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 $\displaystyle 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 $\displaystyle x_i < x_j$). I hope this clarifies things for you.
• Aug 16th 2012, 04:17 AM
Ranjan