Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is the following statement true? Let $a_1\ge a_2\ge \cdots \ge a_n>0$, $b_1\ge b_2\ge \cdots \ge b_n>0$, then

$$\max\limits_{\sigma\in S_n}\;\;\prod\limits_{i=1}^n(a_i+b_{\sigma (i)})=\prod\limits_{i=1}^n(a_i+b_{n+1-i})$$ and $$\min\limits_{\sigma\in S_n}\;\;\prod\limits_{i=1}^n(a_i+b_{\sigma (i)})=\prod\limits_{i=1}^n(a_i+b_i)\;,$$ where $S_n$ means set of all the permuations on $\{1,\dots,n\}$.

If so, how to prove it? or any reference?

share|improve this question

2 Answers 2

up vote 2 down vote accepted

These are cousins of the usual rearrangement inequality. I will prove the second one; the first one should follow using similar ideas. The proof is similar to the proof of the standard inequality in wikipedia.

Define $$ F(\sigma) := \prod_{i=1}^n (a_i + b_{\sigma(i)}) . $$ Let $\sigma$ be any permutation that is not the identity permutation. Then $\sigma$ contains at least one inversion; i.e., a pair $(j,k)$ such that $j < k$ and $\sigma(j) > \sigma(k)$. Let $\tau$ be the permutation $\sigma \circ (a \leftrightarrow b)$, where $(a \leftrightarrow b)$ stands for the transposition that interchanges $a$ and $b$ and keeps the remaining elements fixed.

We now claim that $F(\tau) \leqslant F(\sigma)$. To prove this, consider: $$ (a_j + b_{\sigma(j)}) (a_k + b_{\sigma(k)}) - (a_j + b_{\sigma(k)}) (a_k + b_{\sigma(j)}) = (a_j - a_k)(b_{\sigma(k)} - b_{\sigma(j)}). \tag{$\ast$} $$ Note that $a_j \geqslant a_k$ and $b_{\sigma(k)} \geqslant b_{\sigma(j)}$. Therefore, $(\ast)$ is nonnegative, and it follows that $F(\tau) < F(\sigma)$.

Thus, by repeatedly swapping the inverted pairs, we progressively decrease $F(\cdot)$. But since every permutation is transformed into the identity permutation by repeatedly swapping the inverted pairs, it follows that the quantity $F(\sigma)$ is minimized for $\sigma$ being the identity.

share|improve this answer
1  
It's sometimes called the "rearrangement inequality for products of sums" (rather than the usual rearrangement inequality for sums of products). –  Mike Spivey Nov 15 '11 at 20:43

If $a_1 \geq a_2$ and $b_1 \geq b_2$, $$(a_1+b_2)(a_2+b_1) \geq (a_1+b_1)(a_2+b_2),$$ since $a_1 b_1 + a_2 b_2 \geq a_1 b_2 + a_2 b_1.$

Now induct on $n$. The maximizer $\sigma$ must satisfy $b_{\sigma(1)}=b_n$, since otherwise by the above exchanging $b_{\sigma(1)}$ and $b_n$ increases the product. By the inductive hypothesis the rest of the $b$s must be in ascending order as well.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.