Rearrangement inequality information

In mathematics, the rearrangement inequality^[1] states that for every choice of real numbers

x_{1}\leq \cdots \leq x_{n}\quad {\text{ and }}\quad y_{1}\leq \cdots \leq y_{n}

and every permutation

\sigma

of the numbers

1,2,\ldots n

we have

x_{1}y_{n}+\cdots +x_{n}y_{1}\leq x_{1}y_{\sigma (1)}+\cdots +x_{n}y_{\sigma (n)}\leq x_{1}y_{1}+\cdots +x_{n}y_{n}

.

(1)

Informally, this means that in these types of sums, the largest sum is achieved by pairing large $x$ values with large $y$ values, and the smallest sum is achieved by pairing small values with large values. This can be formalised in the case that the $x_{1},\ldots ,x_{n}$ are distinct, meaning that $x_{1}<\cdots <x_{n},$ then:

The upper bound in (1) is attained only for permutations $\sigma$ that keep the order of $y_{1},\ldots ,y_{n},$ that is, $y_{\sigma (1)}\leq \cdots \leq y_{\sigma (n)},$ or equivalently $(y_{1},\ldots ,y_{n})=(y_{\sigma (1)},\ldots ,y_{\sigma (n)}).$ Such a $\sigma$ can permute the indices of $y$ -values that are equal; in the case $y_{1}=\cdots =y_{n}$ every permutation keeps the order of $y_{1},\ldots ,y_{n}.$ If $y_{1}<\cdots <y_{n},$ then the only such $\sigma$ is the identiy.
Correspondingly, the lower bound in (1) is attained only for permutations $\sigma$ that reverse the order of $y_{1},\ldots ,y_{n},$ meaning that $y_{\sigma (1)}\geq \cdots \geq y_{\sigma (n)}.$ If $y_{1}<\cdots <y_{n},$ then $\sigma (i)=n-i+1$ for all $i=1,\ldots ,n,$ is the only permutation to do this.

Note that the rearrangement inequality (1) makes no assumptions on the signs of the real numbers, unlike inequalities such as the arithmetic-geometric mean inequality.

^ Hardy, G.H.; Littlewood, J.E.; Pólya, G. (1952), Inequalities, Cambridge Mathematical Library (2. ed.), Cambridge: Cambridge University Press, ISBN 0-521-05206-8, MR 0046395, Zbl 0047.05302, Section 10.2, Theorem 368

[1] Hardy, G.H.; Littlewood, J.E.; Pólya, G. (1952), Inequalities, Cambridge Mathematical Library (2. ed.), Cambridge: Cambridge University Press, ISBN 0-521-05206-8, MR 0046395, Zbl 0047.05302, Section 10.2, Theorem 368

Rearrangement inequality information

and 15 Related for: Rearrangement inequality information

Rearrangement inequality

Riesz rearrangement inequality

List of inequalities

Symmetric decreasing rearrangement

Rearrangement

Autocorrelation

Frigyes Riesz

Almut Burchard

Riemann series theorem

Convex conjugate

Comonotonicity

Trace inequality

Symmetrization methods

Entropic uncertainty

Absolute convergence