An Inequality with Permutations, II


Let $a_1,a_2,\ldots,a_n$ and $b_1,b_2,\ldots,b_n$ be two monotone sequences of reals - both either nondecreasing or nonincreasing. Let $\sigma\in S_n$ be a permutation of the set $\{1,2,\ldots,n\}.$ Then,

$\displaystyle\sum_{i = 1}^{n}a_ib_{n + 1 - i}\le\sum_{i = 1}^{n}a_ib_{\sigma\left(i\right)}\le\sum_{i = 1}^{n}a_ib_i.$


Any permutation, if not a cycle itself, is a product of non-intersecting cycles: $\sigma = \sigma_{1}\sigma_{2}\ldots\sigma_{k},$ $k\ge 1.$ For simplicity, for a permutation $\tau$ of subset $I\subset\{1,2,\ldots,n\},$ let $\displaystyle\sum_{\tau}$ stand for $\displaystyle\sum_{i\in I}a_{i}b_{\tau (i)}.$ Then, clearly,

$\displaystyle\sum_{i = 1}^{n}a_ib_{\sigma (i)}=\sum_{j=1}^{k}\sum_{\sigma _{j}}.$

With this in mind, let's proceed to prove the right inequality


$\displaystyle\sum_{i = 1}^{n}a_ib_{\sigma\left(i\right)}\le\sum_{i = 1}^{n}a_ib_i.$

by induction. For $n=1,$ there is nothing to prove. For $n=2,$ the inequality becomes

$\displaystyle a_{1}b_{\sigma (1)}+a_{2}b_{\sigma (2)}\le a_{1}b_{1}+a_{1}b_{1}.$

There are two permutations of a set of two elements, the identical one for which $\sigma (1)=1$ and $\sigma (2)=2,$ the other with $\sigma (1)=2$ and $\sigma (2)=1.$ The former case reduces to double application of the basic step $(n=1).$ In the latter case,

$a_{1}b_{2}+a_{2}b_{1}\le a_{1}b_{1}+a_{2}b_{2}$

because this is equivalent to $(a_{1}-a_{2})(b_{2}-b_{1})\le 0$ which holds from the premises of the problem.

Now, let the inequality hold $n\le m.$

Consider now a permutation $\sigma$ of the set $\{1,2,\ldots,m,m+1\}$ and two monotone sequences $\{a_{i}\}$ and $\{b_{i}\},$ both either nondecreasing or nonincreasing. If $\sigma$ is the product of more than one cycle, the required inequality holds for each of the cycles by the inductive assumption and, for their product by an earlier remark. Assume then that $\sigma$ is a cycle of length $m+1.$ This in particular means that $\sigma (1)\gt 1$ and $\sigma (m+1)\gt m+1,$ implying the existence of a $j$ such that $\sigma (j)\gt j$ and also $\sigma (j)\gt\sigma (\sigma (j)).$ For simplicity, assume $\sigma (1)=3$ and $\sigma (3)=2.$ Consider then the terms $a_{1}b_{3}+a_{3}b_{2}.$ We have

$a_{1}b_{3}+a_{3}b_{2}\le a_{1}b_{2}+a_{3}b_{3}$

because the latter is equivalent to $(a_{1}-a_{3})(b_{3}-b_{2})\le 0.$ Let's define a permutation $\tau$ by $\tau (i)=\sigma (i),$ for all $i$ but $1$ and $3,$ setting $\tau (1)=2$ and $\tau (3)=3.$ (In the original terms this would mean $\tau (j)=\sigma (\sigma (j))$ and $\tau (\sigma (j))=\sigma (j).)$ So defined $\tau$ is a product of a permutation on $\{1,2,\ldots,m+1\}\setminus\{\sigma (j)\}$ and a 1-point cycle on $\{\sigma (j)\}.$ By reindexing the former we get a permutation on $\{1,2,\ldots,m\}$ for which (*) holds. Adding $a_{\sigma (j)}b_{\tau (\sigma (j))}=a_{\sigma (j)}b_{\sigma (j)}$ to both sides does not change that fact, and this proves the inductive step.

The left inequality is derived from the just proved right counterpart by replacing sequence $b_1,b_2,\ldots,b_n$ with, say, $c_{1}=-b_{n},c_{2}=-b_{n-1},\ldots,c_{n}=-b_{1},$ which is monotone in the same sence as $b_1,b_2,\ldots,b_n.$


The problem has been posted at the Short Mathematical Idea facebook page. But the problem is not new. There is, for example, Darij Grinberg's proof from 2010.

|Contact| |Front page| |Contents| |Induction| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny