majorize

Majorize is a relation between vectors used in inequality theory and convex analysis. For vectors x and y in R^n, let x^↓ and y^↓ denote the components sorted in nonincreasing order. x majorizes y, written x ≽ y, if for all k = 1, ..., n-1 we have sum_{i=1}^k x^↓_i ≥ sum_{i=1}^k y^↓_i, and the total sums are equal: sum_{i=1}^n x^↓_i = sum_{i=1}^n y^↓_i. If the sums are not equal, the relation is called weak or supermajorization in other contexts.

Equivalent formulations include: y lies in the convex hull of all permutations of x, or equivalently there exists a doubly stochastic matrix D with y = Dx (a consequence of the Birkhoff–von Neumann theorem). Majorization thus provides a way to compare the dispersion or spread of two vectors with the same total mass.

Key consequences and related concepts: if x ≽ y and f is a convex function, then by Karamata’s inequality sum f(x_i) ≥ sum f(y_i). Vectors can be compared using Schur-convex or Schur-concave functions, which preserve or reverse the majorization order. Majorization is a partial order on vectors with fixed sum.

Example: x = (3, 1, 0) and y = (2, 2, 0) satisfy x ≽ y, since 3 ≥ 2 and 3+1 = 4 ≥ 2+2 = 4, with total sums equal.

Applications span inequality theory, economics (income distribution and inequality measures), statistics (Lorenz order), and optimization, where majorization clarifies how redistribution affects dispersion.