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 b_2 \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=1}^n, \cdots, \{a_{k,i}\}_{i=1}^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$.
Inequality – Rearrangement Inequality for Multiple Sequences
inequality
Best Answer
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, \ldots, \{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 separate: $$a_1^1\cdot a^2_2\cdot\prod_{i=3}^k a^i_{\sigma_{i}(1)} + a_2^1\cdot a^2_1\cdot\prod_{i=3}^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 separate. 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.