2
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.