Rearrangement inequality for multiple sequences.

Solution 1:

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.

Solution 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?

Solution 3:

Dealing with monotonicity condition, the natural thing to do is Abel transform (which transforms monotonicity to positivity).

Namely, the non-decreasing non-negative sequence $a_{s,1},a_{s,2}, \dots, a_{s,n}$ may be written as $$a_{s,i}=b_{s,1}+b_{s,2}+\dots+b_{s,i}$$ for non-negative $b_{s,1},b_{s,2},\dots,b_{s,n}$. Now for fixed permutation $\pi_1,\pi_2,\dots,\pi_k\in S_n$ the sum $$S(\pi_1,\dots,\pi_k):=\sum_{i=1}^n a_{1,\pi_1(i)}a_{2,\pi_2(i)}\ldots a_{k,\pi_k(i)}$$ is a multilinear function of vectors $b_1,b_2,\dots,b_k$ (where $b_s=(b_{s,1},b_{s,2},\dots,b_{s,n})$. Look at each specific coefficient $$[b_{i,i_1}\cdot b_{2,i_2}\cdot \ldots \cdot b_{k,i_k}]S(\pi_1,\dots,\pi_k).$$ If $\pi_1=\pi_2=\dots =\pi_k=id$, this coefficient equals $n+1-\max(i_1,\dots,i_k)$. In all other cases it does not exceed $n+1-\max(i_1,\dots,i_k)$. Indeed, if $\max(i_1,\dots,i_k)=i_r$, for all $i_r-1$ values of index $j$ such that $\pi_r(j)<i_r$ the product $a_{1,\pi_1(i)}a_{2,\pi_2(i)}\ldots a_{k,\pi_k(i)}$ does not contain our monomial $b_{i,i_1}\cdot b_{2,i_2}\cdot \ldots \cdot b_{k,i_k}$. Therefore, equally sorted sum of products is coefficient-like greater or equal than any other sum of products.

The following version of this argument uses less amount of notations. Any non-negative non-decreasing sequence of length $n$ is a linear combination of sequences of the form $(0,0,\dots,0,1,1,\dots,1)$ with non-negative coefficients. So, by multilinearity, it suffices to check the inequality $S(\pi_1,\dots,\pi_k)\leqslant S(id,id,\dots,id)$ when each $a_1,\dots,a_k$ is such a sequence. This is obvious: right hand side equals equals to the minimum of $|a_1|,|a_2|,\dots,|a_k|$ (here $|a_i|$ denotes the number of 1's in the sequence $a_i$), and the left hand side does not exceed this minimum.