Majorization

(Strong) majorization: ${\displaystyle (1,2,3)\prec (0,3,3)\prec (0,0,6)}$. For vectors with ${\displaystyle n}$ components

${\displaystyle \left({\frac {1}{n}},\ldots ,{\frac {1}{n}}\right)\prec \left({\frac {1}{n-1}},\ldots ,{\frac {1}{n-1}},0\right)\prec \cdots \prec \left({\frac {1}{2}},{\frac {1}{2}},0,\ldots ,0\right)\prec \left(1,0,\ldots ,0\right).}$

(Weak) majorization: ${\displaystyle (1,2,3)\prec _{w}(1,3,3)\prec _{w}(1,3,4)}$. For vectors with ${\displaystyle n}$ components:

${\displaystyle \left({\frac {1}{n}},\ldots ,{\frac {1}{n}}\right)\prec _{w}\left({\frac {1}{n-1}},\ldots ,{\frac {1}{n-1}},1\right).}$

Figure 1. 2D majorization example

For ${\displaystyle \mathbf {x} ,\ \mathbf {y} \in \mathbb {R} ^{n},}$ we have ${\displaystyle \mathbf {x} \prec \mathbf {y} }$ if and only if ${\displaystyle \mathbf {x} }$ is in the convex hull of all vectors obtained by permuting the coordinates of ${\displaystyle \mathbf {y} }$. Figure 1 displays the convex hull in 2D for the vector ${\displaystyle \mathbf {y} =(3,\,1)}$. Notice that the center of the convex hull, which is an interval in this case, is the vector ${\displaystyle \mathbf {x} =(2,\,2)}$. This is the "smallest" vector satisfying ${\displaystyle \mathbf {x} \prec \mathbf {y} }$ for this given vector ${\displaystyle \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 ${\displaystyle \mathbf {x} }$ satisfying ${\displaystyle \mathbf {x} \prec \mathbf {y} }$ for this given vector ${\displaystyle \mathbf {y} }$.

Figure 2. 3D Majorization Example

A function ${\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} }$ is said to be Schur convex when ${\displaystyle \mathbf {x} \succ \mathbf {y} }$ implies ${\displaystyle f(\mathbf {x} )\geq f(\mathbf {y} )}$. Hence, Schur-convex functions translate the ordering of vectors to a standard ordering in ${\displaystyle \mathbb {R} }$. Similarly, ${\displaystyle f(\mathbf {x} )}$ is Schur concave when ${\displaystyle \mathbf {x} \succ \mathbf {y} }$ implies ${\displaystyle f(\mathbf {x} )\leq f(\mathbf {y} ).}$

An example of a Schur-convex function is the max function, ${\displaystyle \max(\mathbf {x} )=x_{(1)}^{}}$. 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.

Each of the following statements is true if and only if ${\displaystyle \mathbf {x} \succ \mathbf {y} }$:

• ${\displaystyle \mathbf {y} =\mathbf {D} \mathbf {x} }$ for some doubly stochastic matrix ${\displaystyle \mathbf {D} }$.[4]^{: Thm. 2.1} This is equivalent to saying ${\displaystyle \mathbf {y} }$ can be represented as a convex combination of the permutations of ${\displaystyle \mathbf {x} }$; one can verify that there exists such a convex representation using at most ${\displaystyle n}$ permutations of ${\displaystyle \mathbf {x} }$.[5]
• From ${\displaystyle \mathbf {x} }$ we can produce ${\displaystyle \mathbf {y} }$ by a finite sequence of "Robin Hood operations" where we replace two elements ${\displaystyle x_{i}}$ and ${\displaystyle x_{j}<x_{i}}$ with ${\displaystyle x_{i}-\varepsilon }$ and ${\displaystyle x_{j}+\varepsilon }$, respectively, for some ${\displaystyle \varepsilon \in (0,x_{i}-x_{j})}$.[4]^: 11
• For every convex function ${\displaystyle h:\mathbb {R} \to \mathbb {R} }$, ${\displaystyle \sum _{i=1}^{d}h(x_{i})\geq \sum _{i=1}^{d}h(y_{i})}$.[4]^{: Thm. 2.9}
  • In fact, a special case suffices: ${\displaystyle \sum _{i}{x_{i}}=\sum _{i}{y_{i}}}$ and, for every t, ${\displaystyle \sum _{i=1}^{d}\max(0,x_{i}-t)\geq \sum _{i=1}^{d}\max(0,y_{i}-t)}$.[6]
• ${\displaystyle \forall t\in \mathbb {R} \quad \sum _{j=1}^{d}|x_{j}-t|\geq \sum _{j=1}^{d}|y_{j}-t|}$.[2]^{: Exercise 12.17}

We say that a Hermitian operator, ${\displaystyle \mathbf {H} }$, majorizes another, ${\displaystyle \mathbf {M} }$, if the set of eigenvalues of ${\displaystyle \mathbf {H} }$ majorizes that of ${\displaystyle \mathbf {M} }$.

Given ${\displaystyle f,\ g:\mathbb {N} \to \mathbb {N} }$, then ${\displaystyle f}$ is said to majorize ${\displaystyle g}$ if, for all ${\displaystyle x}$, ${\displaystyle f(x)\geq g(x)}$. If there is some ${\displaystyle n}$ so that ${\displaystyle f(x)\geq g(x)}$ for all ${\displaystyle x>n}$, then ${\displaystyle f}$ is said to dominate (or eventually dominate) ${\displaystyle g}$. Alternatively, the preceding terms are often defined requiring the strict inequality ${\displaystyle f(x)>g(x)}$ instead of ${\displaystyle f(x)\geq g(x)}$ in the foregoing definitions.

• 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

• 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. ISBN 978-0-387-40087-7
• A tribute to Marshall and Olkin's book "Inequalities: Theory of Majorization and its Applications"
• Matrix Analysis (1996) Rajendra Bhatia, Springer, ISBN 978-0-387-94846-1
• Topics in Matrix Analysis (1994) Roger A. Horn and Charles R. Johnson, Cambridge University Press, ISBN 978-0-521-46713-1
• Majorization and Matrix Monotone Functions in Wireless Communications (2007) Eduard Jorswieck and Holger Boche, Now Publishers, ISBN 978-1-60198-040-3
• The Cauchy Schwarz Master Class (2004) J. Michael Steele, Cambridge University Press, ISBN 978-0-521-54677-5

• Majorization in MathWorld
• Majorization in PlanetMath

• OCTAVE/MATLAB code to check majorization