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$.
$\begingroup$
$\endgroup$
1
-
$\begingroup$ Note that for two sequences they need not be positive, whereas for more sequences they do need to be. $\endgroup$– Bart MichelsCommented May 28, 2017 at 12:25
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
9
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.
-
$\begingroup$ 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$ $\endgroup$– MarkCommented Aug 7, 2014 at 1:11
-
1$\begingroup$ @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$. $\endgroup$– EuYuCommented Aug 7, 2014 at 2:19
-
$\begingroup$ 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$. $\endgroup$– EuYuCommented Aug 7, 2014 at 2:23
-
$\begingroup$ Oh I assumed that the sequences were non-decreasing like in the original version. I missed the change to non-increasing! Thanks! $\endgroup$– MarkCommented Aug 7, 2014 at 2:43
-
1$\begingroup$ 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. $\endgroup$– EuYuCommented Aug 7, 2014 at 4:16
$\begingroup$
$\endgroup$
3
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?
answered Feb 15, 2012 at 1:31
-
$\begingroup$ How would you suggest I proceed with the induction? I don't see a clear way. $\endgroup$– EuYuCommented Feb 15, 2012 at 3:18
-
$\begingroup$ I thought I saw a way when I wrote my answer, but I think I was mistaken. $\endgroup$ Commented Feb 15, 2012 at 3:37
-
1$\begingroup$ 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. $\endgroup$ Commented Feb 15, 2012 at 4:01
$\begingroup$
$\endgroup$
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.
