3
$\begingroup$

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?

2 Answers 2

2

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.

  • 1
    It's sometimes called the "rearrangement inequality for products of sums" (rather than the usual rearrangement inequality for sums of products).2011-11-15
1

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.