# Rearrangement inequality for multiple sequences.

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$.

-

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.

-
Why do 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$ – Mark Aug 7 '14 at 1:11
@Mark By assumption we have $a_2^2 < a_1^2$ since each sequence is non-increasing (technically we can have equality, but that case is trivial). By definition, we partitioned all of the larger elements into $b_2$ and all of the smaller elements into $s_1$ and so $s_1 < b_2$ (my original intention in using $s$ and $b$ were to stand for smaller and bigger). Together we then have $a_2^2\cdot s_1 < a_1^2 \cdot b_2$. – EuYu Aug 7 '14 at 2:19
Hopefully an example will make it more clear. Suppose that we have $5$ sequences of two elements each, such that $a^i_1 > a^i_2$, and that we are considering the sum $$a_1^1\cdot a_2^2 \cdot a_1^3 \cdot a_2^4 \cdot a_2^5 + a_2^1\cdot a_1^2 \cdot a_2^3 \cdot a_1^4 \cdot a_1^5$$ Then by our definition we have $b_1 = a_1^3$, $s_1 = a_2^4\cdot a_2^5$ and $b_2 = a_1^4 \cdot a_1^5$, $s_2 = a_2^3$. I hope it's clear now why we must have $s_1 < b_2$ and $s_2 < b_1$. – EuYu Aug 7 '14 at 2:23
Oh I assumed that the sequences were non-decreasing like in the original version. I missed the change to non-increasing! Thanks! – Mark Aug 7 '14 at 2:43
A sum involving sequences of length $n+1$ has $n+1$ total terms in the sum. Of the $n+1$ terms, we must have a two term sum of the form $$a_1^1\cdot a_{i_2}^2 \cdot a_{i_3}^3 \cdots a_{i_{n+1}}^{n+1} + a_{j_1}^1\cdot a_1^2\cdot a_{j_3}^3 \cdots a_{j_{n+1}}^{n+1}$$ If we regard $(a_1^1,a_{j_1}^1),\ (a_1^2, a_{i_1}^2)$ and $(a_{i_k}^k,a_{j_k}^k)$ for $3 \le k \le n+1$ as our two term sequences, then our base case applies. – EuYu Aug 7 '14 at 4:16

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?

-
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