In mathematics, Karamata's inequality, named after Jovan Karamata, also known as the majorization inequality, is a theorem in elementary algebra for convex and concave real-valued functions, defined on an interval of the real line. It generalizes the discrete form of Jensen's inequality, and generalizes in turn to the concept of Schur-convex functions.
Statement of the inequality
Let I be an interval of the real line and let f denote a real-valued, convex function defined on I. If x1, …, xn and y1, …, yn are numbers in I such that (x1, …, xn) majorizes (y1, …, yn), then
(1) |
Here majorization means that x1, …, xn and y1, …, yn satisfies
and | (2) |
and we have the inequalities
for all i ∈ {1, …, n − 1}. | (3) |
and the equality
(4) |
If f is a strictly convex function, then the inequality (1) holds with equality if and only if we have xi = yi for all i ∈ {1, …, n}.
Remarks
- If the convex function f is non-decreasing, then the proof of (1) below and the discussion of equality in case of strict convexity shows that the equality (4) can be relaxed to
(5) - The inequality (1) is reversed if f is concave, since in this case the function −f is convex.
Example
The finite form of Jensen's inequality is a special case of this result. Consider the real numbers x1, …, xn ∈ I and let
denote their arithmetic mean. Then (x1, …, xn) majorizes the n-tuple (a, a, …, a), since the arithmetic mean of the i largest numbers of (x1, …, xn) is at least as large as the arithmetic mean a of all the n numbers, for every i ∈ {1, …, n − 1}. By Karamata's inequality (1) for the convex function f,
Dividing by n gives Jensen's inequality. The sign is reversed if f is concave.
Proof of the inequality
We may assume that the numbers are in decreasing order as specified in (2).
If xi = yi for all i ∈ {1, …, n}, then the inequality (1) holds with equality, hence we may assume in the following that xi ≠ yi for at least one i.
If xi = yi for an i ∈ {1, …, n}, then the inequality (1) and the majorization properties (3) and (4) are not affected if we remove xi and yi. Hence we may assume that xi ≠ yi for all i ∈ {1, …, n}.
It is a property of convex functions that for two numbers x ≠ y in the interval I the slope
of the secant line through the points (x, f (x)) and (y, f (y)) of the graph of f is a monotonically non-decreasing function in x for y fixed (and vice versa). This implies that
(6) |
for all i ∈ {1, …, n − 1}. Define A0 = B0 = 0 and
for all i ∈ {1, …, n}. By the majorization property (3), Ai ≥ Bi for all i ∈ {1, …, n − 1} and by (4), An = Bn. Hence,
(7) |
which proves Karamata's inequality (1).
To discuss the case of equality in (1), note that x1 > y1 by (3) and our assumption xi ≠ yi for all i ∈ {1, …, n − 1}. Let i be the smallest index such that (xi, yi) ≠ (xi+1, yi+1), which exists due to (4). Then Ai > Bi. If f is strictly convex, then there is strict inequality in (6), meaning that ci+1 < ci. Hence there is a strictly positive term in the sum on the right hand side of (7) and equality in (1) cannot hold.
If the convex function f is non-decreasing, then cn ≥ 0. The relaxed condition (5) means that An ≥ Bn, which is enough to conclude that cn(An−Bn) ≥ 0 in the last step of (7).
If the function f is strictly convex and non-decreasing, then cn > 0. It only remains to discuss the case An > Bn. However, then there is a strictly positive term on the right hand side of (7) and equality in (1) cannot hold.
References
- Kadelburg, Zoran; Đukić, Dušan; Lukić, Milivoje; Matić, Ivan (2005), "Inequalities of Karamata, Schur and Muirhead, and some applications" (PDF), The Teaching of Mathematics, 8 (1): 31–45, ISSN 1451-4966
- Karamata, Jovan (1932), "Sur une inégalité relative aux fonctions convexes" (PDF), Publ. Math. Univ. Belgrade (in French), 1: 145–148, Zbl 0005.20101
External links
An explanation of Karamata's inequality and majorization theory can be found here.
Categories: