Given $a_1 \ge \cdots \ge a_n$ and $b_1 \ge \cdots \ge b_n$, then show $\sum a_ib_{\pi(i)}$ is maximum when $\pi=id$.

Question

Suppose $a_1 \ge \cdots \ge a_n$ and $b_1 \ge \cdots \ge b_n$ are two sequences of positive real numbers. Then show $\sum a_ib_{\pi(i)}$ is maximum when $\pi=id$. Here, $\pi \in S_n$.

I understand that there are many sums of products, one due to each permutation. I have to find the one that gives the maximum value. I do not have any idea how to proceed. Can anyone give a hint?

user2566092 · Accepted Answer · 2015-06-24T17:13:03.713

4

Hint: Assume you have two terms that are out of order according to the permutation, i.e. $a_i > a_j$ and $b_{\pi (i)} \leq b_{\pi (j)}$. Then show that by exchanging these permutation values, i.e. swapping the values of $\pi(i)$ and $\pi(j)$ you can get a permutation that yields a higher value of your function.

edited Jun 24 '15 at 17:13

answered Jun 23 '15 at 21:08

user2566092

26,142

Ah. I was thinking in terms of writing $\pi$ as a product of disjoint cycles or a product of transpositions, etc. Hence it took me a minute to see what you meant; your "transposition" is not a permutation. Got it - if $i<j$ but $\pi(i)>\pi(j)$ then consider the permutation $\rho$, where $\rho(l)=\pi(l)$ for $l\ne i,j$, $\rho(j)=\pi(i)$ and $\rho(i)=\pi(j)$. Right. – David C. Ullrich Jun 23 '15 at 21:30
@DavidC.Ullrich Right I probably should have been more careful about how I used the word "transposition." I'll rephrase to make it more clear. The point is to take any permutation not the identity, and exchange the permutation values of two elements that are "out of order" – user2566092 Jun 24 '15 at 17:11
No problem - regardless of how sinful you were with the terminology, I didn't see the proof and then after I read your post I did. – David C. Ullrich Jun 24 '15 at 17:18

score 1 · Answer 2 · answered Jun 23 '15 at 21:11

1

I think this is kinda trivial by Rearrangement Inequality.

You have, by RI,

$$\sum_{k=1}^n a_kb_k\geq \sum_{k=1}^n a_kb_{\pi(k)}\implies \sum_{k=1}^n a_kb_{\pi(k)}\leq \sum_{k=1}^n a_kb_k$$

This is the same thing as $\sum a_ib_i\leq \sum a_ib_{id(i)}$

answered Jun 23 '15 at 21:11

Prasun Biswas

6,334

1

The rearrangement inequality makes the problem basically trivial. Hence probably the OP probably wouldn't have asked unless that was unavailable. – user2566092 Jun 23 '15 at 21:13
@user2566092, I completely agree with you but I mentioned it since OP didn't say anything about not using RI. I'm still wondering whether I should delete this answer or not... – Prasun Biswas Jun 23 '15 at 21:15
I wouldn't say it's trivial from RI, I'd say that (half of) RI was exactly what he was trying to prove! (I do like the hint for how to prove it at that link, though - as far as I can see it's saying that to prove RI it suffices to prove RI.) – David C. Ullrich Jun 23 '15 at 21:22

Given $a_1 \ge \cdots \ge a_n$ and $b_1 \ge \cdots \ge b_n$, then show $\sum a_ib_{\pi(i)}$ is maximum when $\pi=id$.

2 Answers2