In fact, I'm intrested in such a question:




---


If $\sigma$ and $\pi$ are two permutations of $\{1,2,\ldots,n\}$
what is necessary and sufficient condition to be the following statement true. For all $a\_1\geqslant a\_2\geqslant \ldots \geqslant a\_n$ and $b\_1\geqslant b\_2\geqslant \ldots \geqslant b\_n$
$$
a\_1b\_{\sigma(1)}+a\_2b\_{\sigma(2)}+\ldots+a\_nb\_{\sigma(n)}\geqslant a\_1b\_{\pi(1)}+a\_2b\_{\pi(2)}+\ldots+a\_nb\_{\pi(n)}
$$




---


Consider graph $G$ with elements of $S\_n$ as a vertices and connect $\sigma$ and $\pi$ from $\sigma$ to $\pi$ when $\sigma(i)=\pi(i)$ for all $i\in \{1,2,\ldots,n\}\setminus \{k,l\}$, $\sigma(k)=\pi(l)$, $\sigma(l)=\pi(k)$ and $\sigma(k)>\sigma(l)$.


Then for all $a\_1\geqslant a\_2\geqslant \ldots \geqslant a\_n$ and $b\_1\geqslant b\_2\geqslant \ldots \geqslant b\_n$ we have
$$
a\_kb\_{\sigma(k)}+a\_lb\_{\sigma(l)}-a\_kb\_{\pi(k)}-a\_l{\pi(l)}=
(a\_k-a\_l)(b\_{\sigma(k)}-b\_{\sigma(l)})\geqslant 0
$$


In fact, if we can go from $\sigma$ to $\pi$ in $G$ then we can with certainty state that the inequality holds.


On the other hand, let's consider $\sigma$, $\pi\in S\_3$:
$\sigma(1)=1$, $\sigma(2)=3$, $\sigma(3)=2$ and $\sigma(1)=2$, $\sigma(2)=1$, $\sigma(3)=3$. Then 
$$
1\cdot 1+0\cdot 0+0\cdot 0\geqslant 1\cdot 0+0\cdot 1+0\cdot 0
$$
and
$$
0\cdot 0+0\cdot (-1)+(-1)\cdot 0\leqslant 0\cdot 0+0\cdot 0+(-1)\cdot (-1)
$$


So, I have no idea what to do in most general case.



On generalization of rearrangement inequality
Necessary and sufficient condition is the following: for all $k\in \{1,\dots,n\}$, the sequence $\sigma(1),\dots,\sigma(k)$ strongly minorates $\pi(1),\dots,\pi(k)$, that means: if $u\_1\leqslant \dots \leqslant u\_k$ is increasing permutation of $\sigma(1),\dots,\sigma(k)$ and $v\_1\leqslant \dots \leqslant v\_k$ is increasing permutation of $\pi(1),\dots,\pi(k)$, then $u\_i\leqslant v\_i$ for all $i=1,\dots,k$.


At first, why is it necessary. Assume that it fails for some $k$, choose such a $k$ and set $a\_1=\dots=a\_i=1$, $a\_{i+1}=\dots=a\_n=0$. We get $b\_{\sigma(1)}+\dots+b\_{\sigma(k)}\geqslant b\_{\pi(1)}+\dots+b\_{\pi(k)}$. Fix $i\leqslant k$ such that $u\_i>v\_i$ and consider a sequence $b\_m=\chi\_{m\leqslant v\_i}$. Then $b\_{\pi(1)}+\dots+b\_{\pi(k)}=i$, $b\_{\sigma(1)}+\dots+b\_{\sigma(k)}\leqslant i-1$, a contradiction.


Now why is it sufficient. As usual in such situations, we apply Abel transform. Denote $a\_k=a\_n+(c\_{k}+\dots+c\_{n-1})$ for $k=1,\dots,n-1$. Then $c\_i\geqslant 0$ and we have
$$
\sum a\_ib\_{\sigma(i)}=a\_n\sum b\_i+\sum\_{k=1}^{n-1} c\_k(b\_{\sigma(1)}+\dots+b\_{\sigma(k)}).
$$
Rewrite analogously $\sum a\_ib\_{\pi(i)}$ and note that for each $k$
$$
b\_{\sigma(1)}+\dots+b\_{\sigma(k)}=b\_{u\_1}+\dots+b\_{u\_k}\geqslant
b\_{v\_1}+\dots+b\_{v\_k}=b\_{\pi(1)}+\dots+b\_{\pi(k)}.
$$


