Majorization

In mathematics, majorization is a preorder on vectors of real numbers. For two such vectors, \mathbf{x},\ \mathbf{y} \in \mathbb{R}^n , we say that \mathbf{x} weakly majorizes (or dominates) \mathbf{y} from below, commonly denoted \mathbf{x} \succ_w \mathbf{y}, when : \sum_{i=1}^k x_i^{\downarrow} \geq \sum_{i=1}^k y_i^{\downarrow} for all k=1,\,\dots,\,n , where x_i^{\downarrow} denotes the i th largest entry of \mathbf{x} . If \mathbf{x}, \mathbf{y} further satisfy \sum_{i=1}^n x_i = \sum_{i=1}^n y_i , we say that \mathbf{x} majorizes (or dominates) \mathbf{y} , commonly denoted \mathbf{x} \succ \mathbf{y} . Both weak majorization and majorization are partial orders for vectors whose entries are non-decreasing, but only a preorder for general vectors, since majorization is agnostic to the ordering of the entries in vectors, e.g., the statement (1,2)\prec (0,3) is simply equivalent to (2,1)\prec (3,0) . Specifically, \mathbf{x} \succ \mathbf{y} \wedge \mathbf{y} \succ \mathbf{x} if and only if \mathbf{x}, \mathbf{y} are permutations of each other. Similarly for \succ_w . Majorizing also sometimes refers to entrywise ordering, e.g. the real-valued function f majorizes the real-valued function g when f(x) \geq g(x) for all x in the domain, or other technical definitions, such as majorizing measures in probability theory.

In mathematics, majorization is a preorder on vectors of real numbers. For two such vectors, \mathbf{x},\ \mathbf{y} \in \mathbb{R}^n , we say that \mathbf{x} weakly majorizes (or dominates) \mathbf{y} from below, commonly denoted \mathbf{x} \succ_w \mathbf{y}, when \sum_{i=1}^k x_i^{\downarrow} \geq \sum_{i=1}^k y_i^{\downarrow} for all k=1,\,\dots,\,n , where x_i^{\downarrow} denotes the i th largest entry of \mathbf{x} . If \mathbf{x}, \mathbf{y} further satisfy \sum_{i=1}^n x_i = \sum_{i=1}^n y_i , we say that \mathbf{x} majorizes (or dominates) \mathbf{y} , commonly denoted \mathbf{x} \succ \mathbf{y} . Both weak majorization and majorization are partial orders for vectors whose entries are non-decreasing, but only a preorder for general vectors, since majorization is agnostic to the ordering of the entries in vectors, e.g., the statement (1,2)\prec (0,3) is simply equivalent to (2,1)\prec (3,0) . Specifically, \mathbf{x} \succ \mathbf{y} \wedge \mathbf{y} \succ \mathbf{x} if and only if \mathbf{x}, \mathbf{y} are permutations of each other. Similarly for \succ_w . Majorizing also sometimes refers to entrywise ordering, e.g. the real-valued function f majorizes the real-valued function g when f(x) \geq g(x) for all x in the domain, or other technical definitions, such as majorizing measures in probability theory. ==Equivalent conditions== For \mathbf{x},\ \mathbf{y} \in \mathbb{R}^n, we have \mathbf{x} \prec \mathbf{y} if and only if \mathbf{x} is in the convex hull of all vectors obtained by permuting the coordinates of \mathbf{y} . This is equivalent to saying that \mathbf{x} = \mathbf{D}\mathbf{y} for some doubly stochastic matrix \mathbf{D} . In particular, \mathbf{x} can be written as a convex combination of n permutations of \mathbf{y} . In other words, \mathbf{x} is in the permutahedron of \mathbf{y} . Figure 1 displays the convex hull in 2D for the vector \mathbf{y}=(3,\,1) . Notice that the center of the convex hull, which is an interval in this case, is the vector \mathbf{x}=(2,\,2) . This is the "smallest" vector satisfying \mathbf{x} \prec \mathbf{y} for this given vector \mathbf{y} . Figure 2 shows the convex hull in 3D. The center of the convex hull, which is a 2D polygon in this case, is the "smallest" vector \mathbf{x} satisfying \mathbf{x} \prec \mathbf{y} for this given vector \mathbf{y} . For every convex function h:\mathbb{R}\to \mathbb{R} , \sum_{i=1}^d h(x_i) \geq \sum_{i=1}^d h(y_i) . In fact, a special case suffices: \sum_i{x_i}=\sum_i{y_i} and, for every , \sum_{i=1}^d \max(0,x_i-t) \geq\sum_{i=1}^d \max(0,y_i-t) . For every t \in \mathbb{R} , \sum_{j=1}^d |x_j-t| \geq \sum_{j=1}^d |y_j-t| . Each vector \mathbf{x} can be plotted as a concave curve by connecting (0,0), (1, x_1^{\downarrow}), (2, x_1^{\downarrow}+x_2^{\downarrow}), \dots, (n, x_1^{\downarrow}+x_2^{\downarrow} + \dots +x_n^{\downarrow}) . Then \mathbf{x}\succ \mathbf{y} is equivalent to the curve of \mathbf{x} being higher than that of \mathbf{y} . ==Examples== Among non-negative vectors with three components, (1, 0, 0) and permutations of it majorize all other vectors (p_1, p_2, p_3) such that p_1 + p_2 + p_3 = 1 . For example, (1, 0, 0) \succ (1/2, 0, 1/2) . Similarly, (1/3, 1/3, 1/3) is majorized by all other such vectors, so (1/2, 0, 1/2) \succ (1/3, 1/3, 1/3) . This behavior extends to general-length probability vectors: the singleton vector majorizes all other probability vectors, and the uniform distribution is majorized by all probability vectors. An example of a Schur-convex function is the max function, \max(\mathbf{x})=x_{1}^{\downarrow} . Schur convex functions are necessarily symmetric that the entries of it argument can be switched without modifying the value of the function. Therefore, linear functions, which are convex, are not Schur-convex unless they are symmetric. If a function is symmetric and convex, then it is Schur-convex. ==See also== Muirhead's inequality Karamata's Inequality Schur-convex function Schur–Horn theorem relating diagonal entries of a matrix to its eigenvalues. For positive integer numbers, weak majorization is called Dominance order. Leximin order ==Notes== ==References== J. Karamata. "Sur une inegalite relative aux fonctions convexes." Publ. Math. Univ. Belgrade 1, 145–158, 1932. G. H. Hardy, J. E. Littlewood and G. Pólya, Inequalities, 2nd edition, 1952, Cambridge University Press, London. Inequalities: Theory of Majorization and Its Applications Albert W. Marshall, Ingram Olkin, Barry Arnold, Second edition. Springer Series in Statistics. Springer, New York, 2011. A tribute to Marshall and Olkin's book "Inequalities: Theory of Majorization and its Applications" Matrix Analysis (1996) Rajendra Bhatia, Springer, Topics in Matrix Analysis (1994) Roger A. Horn and Charles R. Johnson, Cambridge University Press, Majorization and Matrix Monotone Functions in Wireless Communications (2007) Eduard Jorswieck and Holger Boche, Now Publishers, The Cauchy Schwarz Master Class (2004) J. Michael Steele, Cambridge University Press, ==External links== Majorization in MathWorld Majorization in PlanetMath ==Software== OCTAVE/MATLAB code to check majorization

Text derived from https://en.wikipedia.org/w/index.php?oldid=1366049528 under CC BY-SA 4.0; modifications have been made.