In mathematics , the rearrangement inequality is a statement about the change in the value of formal scalar products due to rearrangement.
Given are two n- tuples of real numbers and with
x
=
(
x
1
,
...
,
x
n
)
{\ displaystyle x = (x_ {1}, \ dots, x_ {n})}
y
=
(
y
1
,
...
,
y
n
)
{\ displaystyle y = (y_ {1}, \ dots, y_ {n})}
x
1
≤
⋯
≤
x
n
and
y
1
≤
⋯
≤
y
n
{\ displaystyle x_ {1} \ leq \ cdots \ leq x_ {n} \ quad {\ mbox {and}} \ quad y_ {1} \ leq \ cdots \ leq y_ {n}}
The tuple
x
σ
=
(
x
σ
(
1
)
,
...
,
x
σ
(
n
)
)
{\ displaystyle x _ {\ sigma} = \ left (x _ {\ sigma (1)}, \ dots, x _ {\ sigma (n)} \ right)}
be a permutation of the tuple . If one now regards the n- tuples as vectors and considers their standard scalar product, the rearrangement inequality says that
x
{\ displaystyle x}
x
1
y
1
+
⋯
+
x
n
y
n
≥
x
σ
(
1
)
y
1
+
⋯
+
x
σ
(
n
)
y
n
≥
x
n
y
1
+
⋯
+
x
1
y
n
.
{\ displaystyle x_ {1} y_ {1} + \ cdots + x_ {n} y_ {n} \ geq x _ {\ sigma (1)} y_ {1} + \ cdots + x _ {\ sigma (n)} y_ {n} \ geq x_ {n} y_ {1} + \ cdots + x_ {1} y_ {n}.}
The scalar product is therefore maximal if the elements of the n- tuples are ordered in the same way, and minimal if they are ordered in opposite directions.
Note that, unlike many other inequalities, no preconditions for the signs of and are necessary.
x
i
{\ displaystyle x_ {i}}
y
i
{\ displaystyle y_ {i}}
proofs Proof by means of swaps The proof idea is the smallest , which met, and that with regard to. Then so are and , therefore, and , so
i
{\ displaystyle i}
σ
(
i
)
≠
i
{\ displaystyle \ sigma (i) \ neq i}
j
{\ displaystyle j}
i
=
σ
(
j
)
{\ displaystyle i = \ sigma (j)}
σ
(
i
)
>
i
{\ displaystyle \ sigma (i)> i}
j
>
i
{\ displaystyle j> i}
x
σ
(
j
)
≤
x
σ
(
i
)
{\ displaystyle x _ {\ sigma (j)} \ leq x _ {\ sigma (i)}}
y
i
≤
y
j
{\ displaystyle y_ {i} \ leq y_ {j}}
(
x
σ
(
i
)
-
x
σ
(
j
)
)
(
y
i
-
y
j
)
≤
0
{\ displaystyle (x _ {\ sigma (i)} - x _ {\ sigma (j)}) (y_ {i} -y_ {j}) \ leq 0}
and therefore
x
σ
(
i
)
y
i
+
x
σ
(
j
)
y
j
≤
x
σ
(
j
)
y
i
+
x
σ
(
i
)
y
j
=
x
i
y
i
+
x
σ
(
i
)
y
j
.
{\ displaystyle x _ {\ sigma (i)} y_ {i} + x _ {\ sigma (j)} y_ {j} \ leq x _ {\ sigma (j)} y_ {i} + x _ {\ sigma (i) } y_ {j} = x_ {i} y_ {i} + x _ {\ sigma (i)} y_ {j}.}
As long as there is a with , the sum can be increased for tuples of the same order.
i
{\ displaystyle i}
σ
(
i
)
≠
i
{\ displaystyle \ sigma (i) \ neq i}
Analog one shows that the sum for opposite parent tuple can decrease as long as with exist.
i
{\ displaystyle i}
σ
(
i
)
≠
i
{\ displaystyle \ sigma (i) \ neq i}
Proof by induction This proof can also be carried out in more detail with complete induction . There are only two permutations for the beginning of induction , so it has to be shown that
n
=
2
{\ displaystyle n = 2}
x
2
y
1
+
x
1
y
2
≤
x
1
y
1
+
x
2
y
2
.
{\ displaystyle x_ {2} y_ {1} + x_ {1} y_ {2} \ leq x_ {1} y_ {1} + x_ {2} y_ {2}.}
But that is equivalent to
0
≤
(
y
1
-
y
2
)
(
x
1
-
x
2
)
,
{\ displaystyle 0 \ leq (y_ {1} -y_ {2}) (x_ {1} -x_ {2}),}
thus a prerequisite that both tuples are ordered in the same way.
In the induction step, let the index be The case is easy to handle, so let then hold
j
{\ displaystyle j}
σ
(
j
)
=
n
+
1.
{\ displaystyle \ sigma (j) = n + 1.}
j
=
n
+
1
{\ displaystyle j = n + 1}
j
≠
n
+
1.
{\ displaystyle j \ neq n + 1.}
∑
i
=
1
n
+
1
x
σ
(
i
)
y
i
=
∑
i
∉
{
j
,
n
+
1
}
x
σ
(
i
)
y
i
+
x
σ
(
j
)
y
j
+
x
σ
(
n
+
1
)
y
n
+
1
=
∑
i
∉
{
j
,
n
+
1
}
x
σ
(
i
)
y
i
+
x
n
+
1
y
j
+
x
σ
(
n
+
1
)
y
n
+
1
.
{\ displaystyle \ sum _ {i = 1} ^ {n + 1} x _ {\ sigma (i)} y_ {i} = \ sum _ {i \ not \ in \ {j, n + 1 \}} x_ {\ sigma (i)} y_ {i} + x _ {\ sigma (j)} y_ {j} + x _ {\ sigma (n + 1)} y_ {n + 1} = \ sum _ {i \ not \ in \ {j, n + 1 \}} x _ {\ sigma (i)} y_ {i} + x_ {n + 1} y_ {j} + x _ {\ sigma (n + 1)} y_ {n + 1 }.}
Now we apply the case proven in the beginning of induction and get
n
=
2
{\ displaystyle n = 2}
∑
i
∉
{
j
,
n
+
1
}
x
σ
(
i
)
y
i
+
x
n
+
1
y
j
+
x
σ
(
n
+
1
)
y
n
+
1
≤
∑
i
∉
{
j
,
n
+
1
}
x
σ
(
i
)
y
i
+
x
σ
(
n
+
1
)
y
j
+
x
n
+
1
y
n
+
1
.
{\ displaystyle \ sum _ {i \ not \ in \ {j, n + 1 \}} x _ {\ sigma (i)} y_ {i} + x_ {n + 1} y_ {j} + x _ {\ sigma (n + 1)} y_ {n + 1} \ leq \ sum _ {i \ not \ in \ {j, n + 1 \}} x _ {\ sigma (i)} y_ {i} + x _ {\ sigma (n + 1)} y_ {j} + x_ {n + 1} y_ {n + 1}.}
Define now for the permutation
i
=
1
,
...
,
n
{\ displaystyle i = 1, \ dots, n}
τ
(
i
)
=
{
σ
(
n
+
1
)
if
i
=
j
σ
(
i
)
otherwise
{\ displaystyle \ tau (i) = {\ begin {cases} \ sigma (n + 1) \ qquad {\ textrm {if}} \ quad i = j \\\ sigma (i) \ qquad {\ textrm {otherwise }} \ end {cases}}}
so follows from the induction hypothesis
∑
i
∉
{
j
,
n
+
1
}
x
σ
(
i
)
y
i
+
x
σ
(
n
+
1
)
y
j
+
x
n
+
1
y
n
+
1
=
∑
i
∉
{
j
,
n
+
1
}
x
τ
(
i
)
y
i
+
x
τ
(
j
)
y
j
+
x
n
+
1
y
n
+
1
=
∑
i
=
1
n
x
τ
(
i
)
y
i
+
x
n
+
1
y
n
+
1
≤
∑
i
=
1
n
x
i
y
i
+
x
n
+
1
y
n
+
1
,
{\ displaystyle \ sum _ {i \ not \ in \ {j, n + 1 \}} x _ {\ sigma (i)} y_ {i} + x _ {\ sigma (n + 1)} y_ {j} + x_ {n + 1} y_ {n + 1} = \ sum _ {i \ not \ in \ {j, n + 1 \}} x _ {\ tau (i)} y_ {i} + x _ {\ tau ( j)} y_ {j} + x_ {n + 1} y_ {n + 1} = \ sum _ {i = 1} ^ {n} x _ {\ tau (i)} y_ {i} + x_ {n + 1} y_ {n + 1} \ leq \ sum _ {i = 1} ^ {n} x_ {i} y_ {i} + x_ {n + 1} y_ {n + 1},}
thus exactly the claim for the maximum of the scalar product.
The proof for the minimum of the scalar product is analogous.
Applications Many known inequalities can be proven from the rearrangement inequality, for example the inequality of the arithmetic and geometric mean , Cauchy-Schwarz inequality, and the Chebyshev sum inequality .
literature
<img src="https://de.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">
