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.

The rearrangement inequality is well known for two sequences $\{a_i\}_{i=1}^n$ and $\{b_i\}_{i=1}^n$ where each sequence is non-decreasing $a_1\le a_2\le \cdots \le a_n$ and $b_1 \le \cdots \le b_n$. The inequality states $$\sum_{i=1}^n a_i\cdot b_i\ge\sum_{i=1}^n a_i\cdot b_{\sigma(i)} \ge \sum_{i=1}^n a_i\cdot b_{n+1-i}$$ I have never seen a generalization of this inequality into multiple sequences, that is, given $k$ non-decreasing sequences $\{a_{1,i}\}_{i=0}^n, \cdots, \{a_{k,i}\}_{i=0}^n$, does some generalization of the rearrangement inequality hold? My guess would probably be something of the form $$\sum_{i=1}^n\prod_{j=1}^k a_{j,i}\ge\sum_{i=1}^n a_{1,i}\prod_{j=2}^ka_{j,\sigma_{j}(i)}$$ for permutations $\sigma_j$.

share|improve this question

2 Answers 2

I think there are problems if there are negative numbers. Say the sequences are $-5,1$; $-5,1$; and $1,2$. Keeping them in order gives you $27$, but you can rearrange to get $51$. If there are no negative terms, doesn't induction work?

share|improve this answer
How would you suggest I proceed with the induction? I don't see a clear way. –  EuYu Feb 15 '12 at 3:18
I thought I saw a way when I wrote my answer, but I think I was mistaken. –  Gerry Myerson Feb 15 '12 at 3:37
It may be possible to get an answer out of math.toronto.edu/almut/rearrange.pdf. That source deals with functions instead of sequences, so some translation work will be needed. Exercise 2.16 looks like the right thing, taking $\Phi(a_1,\dots,a_n)=a_1a_2\cdots a_n$. A statement is given without proof at sas.uwaterloo.ca/~cgsmall/worksheet3.pdf. Maybe the best source is Example 6 of math.ufl.edu/~avince/Papers/RearrangeInequality.pdf, or H D Ruderman, Two new inequalities, Amer Math Monthly 59 (1952) 29-32. –  Gerry Myerson Feb 15 '12 at 4:01
up vote 2 down vote accepted

This is a proof I came up with after looking at some suggestions. Hopefully it is complete.

Let us proceed by induction. First consider $k$ sequences of two terms each, $\{a_{i}^1\}_{i=1}^2,\ \{a_{i}^2\}_{i=1}^2, \cdots \{a_{i}^k\}_{i=1}^2$. Each sequence in the following discussion shall be positive non-increasing.

Suppose for the sake of contradiction that the maximum sum is produced by a permutation where the maximal elements are not together. Without loss of generality, suppose $a^1_1$ and $a^2_1$ are seperate: $$a_1^1\cdot a^2_2\cdot\prod_{i=2}^k a^i_{\sigma_{i}(1)} + a_2^1\cdot a^2_1\cdot\prod_{i=2}^k a^i_{\sigma_{i}(2)}$$ We can assume that $a^j_1 \neq a^j_2$ for all sequences, otherwise we simply factor the term out and continue. Let us partition each summand into two smaller products.

First, $b_1$, shall contain all terms in the first summand such that $a_{\sigma_{i}(1)} > a_{\sigma_{i}(2)}$ while $s_1$ shall contain all terms in the first summand such that $a_{\sigma_{i}(1)} < a_{\sigma_{i}(2)}$. Similarly, we partition the second summand into $b_2$ containing the terms $a_{\sigma_{i}(1)} < a_{\sigma_{i}(2)}$ and $s_2$ containing the terms $a_{\sigma_{i}(1)} > a_{\sigma_{i}(2)}$.

This gives the sum as $$a_1^1 \cdot a_2^2 \cdot s_1 \cdot b_1 + a_2^1 \cdot a_1^2 \cdot s_2 \cdot b_2$$ by construction, we have $$a_2^2\cdot s_1 < a^2_1\cdot b_2,\ \ a_2^1\cdot s_2 < a_1^1\cdot b_1$$ and so by the rearrangement inequality, we have $$a_1^1\cdot a_1^2 \cdot b_1 \cdot b_2 + a_2^1 \cdot a_2^2 \cdot s_1 \cdot s_2 \ge a_1^1\cdot a^2_2\cdot\prod_{i=2}^k a^i_{\sigma_{i}(1)} + a_2^1\cdot a^2_1\cdot\prod_{i=2}^k a^i_{\sigma_{i}(2)}$$ with equality if and only if $a_1^j = a_2^j$ for all sequences except $a^1$ or $a^2$. The process can be repeated to bring together all maximal elements. This contradicts the fact that the maximum sum is produced when maximal elements are seperate. This handles the two term case.

Now suppose the inequality holds for sequences of length $n$ and let us look at the inequality for sequences of length $n+1$. There are two cases to handle. If the maximal elements are all together, then we simply remove the term and apply the inductive hypothesis immediately. If the maximal elements are not together, we can use the procedure in the base case repeatedly to bring them together, where upon we remove term and apply the inductive hypothesis.

share|improve this answer

Your Answer


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.