Schur-Convexity

Majorization, Schur-convex functions, and the Schur-Ostrowski criterion.

The idea

Schur convexity identifies the functions that respect majorization, the order comparing how unevenly a fixed total is distributed among the entries of a vector.

Majorization comes first. Sort both vectors in decreasing order; then $x$ majorizes $y$, written $y \prec x$, when the two totals agree and, for every $k$, the first $k$ entries of $x$ sum to at least as much as the first $k$ entries of $y$. At a fixed total, larger leading sums mean more of the mass sits in fewer entries, so $y \prec x$ says $x$ is the more concentrated vector. The order is partial — two vectors with the same total need not be comparable — but it has a top and a bottom: every vector with total $s$ is majorized by $(s, 0, \dots, 0)$ and majorizes $(s/n, \dots, s/n)$.

A symmetric function $F$ is Schur-convex when $F(y) \le F(x) \quad \text{whenever } y \prec x,$ that is, when concentrating the input at a fixed total never decreases $F$. Such an $F$ attains its minimum at the flat vector and its maximum at the concentrated one, so a single structural property yields a whole family of inequalities. If instead $F(y) \ge F(x)$ whenever $y \prec x$, then $F$ is Schur-concave.

Ways to work on it

• Walkthrough. Majorization, Schur-convex functions, and the Schur-Ostrowski test.
• Practice. Use Schur-Ostrowski to decide if a symmetric function is Schur-convex.
• Hardest. Bound a symmetric sum from its majorization extremes.

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