Karamata's Inequality (Majorization)

Convexity plus majorization: the inequality that generalizes Jensen.

The idea

Definition (Majorization).

Let $(x_i)$ and $(y_i)$ be two lists of $n$ real numbers, each written in decreasing order. Then $(x_i)$ majorizes $(y_i)$, written $x \succeq y$, when the totals agree, $\sum x_i = \sum y_i$, and every partial sum of the $x s dominates: $x_1 + \cdots + x_k \;\ge\; y_1 + \cdots + y_k \quad \text{for every } k.$

Theorem (Karamata's inequality).

If $f$ is convex and $x \succeq y$, then $\sum_{i} f(x_i) \;\ge\; \sum_{i} f(y_i).$

Karamata's inequality is also called the majorization inequality. For concave $f$ the inequality reverses, and when $f$ is strictly convex equality holds only when the two lists are the same.

Since the totals are equal, the partial-sum condition says the $x$-list concentrates more of the common total in its largest entries: $x$ distributes the total more unevenly than $y$. Plotted against $k$, as in the figure, the partial sums $X_k = x_1 + \cdots + x_k$ run on or above $Y_k = y_1 + \cdots + y_k$ at every step and meet them at $k = n$, where the totals agree.

So Karamata's inequality says that summing a convex function over the more uneven list gives the larger result. Every list majorizes the constant list with the same total, so the special case $y_1 = \cdots = y_n = \bar{x}$ recovers Jensen's inequality for equal weights.

Ways to work on it

• Walkthrough. Define majorization, check it, and apply Karamata with a convex function.
• Proof. The summation-by-parts proof: chord slopes decrease while partial sums dominate.
• Practice. Decide whether one list majorizes another.
• Hardest. Use Karamata and majorization to find an extremal sum of squares.

Not sure where to start? Take the ten-question placement test.