Rearrangement inequality

For two real sequences sorted in the same order, the sum of their pairwise products is maximal; sorting them in opposite orders makes it minimal.

Swap argument: A proof technique that compares two arrangements by exchanging a pair of elements. Swapping an inverted pair shows that aligning the sequences cannot decrease the product sum.
Permutation: A rearrangement of the elements of a finite set into a different order. The inequality compares product sums across permutations of one sequence.
Cauchy–Schwarz inequality: An inequality bounding the absolute inner product of two vectors by the product of their lengths. It supplies a complementary bound on product sums without relying on sorted pairings.
Chebyshev's sum inequality: An inequality relating the average product of similarly ordered sequences to the product of their averages. Unlike rearrangement's extremal comparison across permutations, it compares one product average with separate averages.
Majorization: A partial order on vectors based on comparisons of their sorted partial sums. The inequality is one example of how aligned ordering controls sums of products.
Ordered set: A set equipped with a relation that specifies which elements precede others. Sorting real sequences depends on the usual order of real numbers.
Hölder's inequality: An inequality bounding sums of products using conjugate power norms. It generalizes product-sum bounds to exponents beyond the rearrangement setting.
Minkowski inequality: A triangle inequality for norms of sums of vectors or functions. It bounds a different operation: combining magnitudes rather than reordering paired products.
Birkhoff–von Neumann theorem: The theorem that every doubly stochastic matrix is a convex combination of permutation matrices. Its permutation structure connects rearrangement bounds to optimization over doubly stochastic matrices.
Finite sequence: An ordered list of a finite number of elements. The classical inequality compares two finite lists term by term.

Linked from 8 pages