Majorization

This article is about a partial ordering of vectors on R^d. For functions, see Lorenz ordering.

In mathematics, majorization is a partial order on vectors of real numbers. For a vector $\mathbf{a}\in\mathbb{R}^d$, we denote by $\mathbf{a}^{\downarrow}\in\mathbb{R}^d$ the vector with the same components, but sorted in decreasing order. Given $\mathbf{a},\mathbf{b} \in \mathbb{R}^d$, we say that $\mathbf{a}$ weakly majorizes (or dominates) $\mathbf{b}$ written as $\mathbf{a} \succ_w \mathbf{b}$ iff

$\sum_{i=1}^k a_i^{\downarrow} \geq \sum_{i=1}^k b_i^{\downarrow} \quad \text{for } k=1,\dots,d,$

where $a^{\downarrow}_i$ and $b^{\downarrow}_i$ are the elements of $\mathbf{a}$ and $\mathbf{b}$, respectively, sorted in decreasing order. Equivalently, we say that $\mathbf{b}$ is weakly majorized (or dominated) by $\mathbf{a}$, denoted as $\mathbf{b} \prec_w \mathbf{a}$.

If $\mathbf{a} \succ_w \mathbf{b}$ and in addition $\sum_{i=1}^d a_i = \sum_{i=1}^d b_i$ we say that $\mathbf{a}$ majorizes (or dominates) $\mathbf{b}$ written as $\mathbf{a} \succ \mathbf{b}$. Equivalently, we say that $\mathbf{b}$ is majorized (or dominated) by $\mathbf{a}$, denoted as $\mathbf{b} \prec \mathbf{a}$.

Regrettably, to confuse the matter, some literature sources use the reverse notation, e.g., $\succ$ is replaced with $\prec$, most notably, in Horn and Johnson, Matrix analysis (Cambridge Univ. Press, 1985), Definition 4.3.24, while the same authors switch to the traditional notation, introduced here, later in their Topics in Matrix Analysis (1994).

A function $f:\mathbb{R}^d \to \mathbb{R}$ is said to be Schur convex when $\mathbf{a} \succ \mathbf{b}$ implies $f(\mathbf{a}) \geq f(\mathbf{b})$. Similarly, $f(\mathbf{a})$ is Schur concave when $\mathbf{a} \succ \mathbf{b}$ implies $f(\mathbf{a}) \leq f(\mathbf{b}).$

The majorization partial order on finite sets, described here, can be generalized to the Lorenz ordering, a partial order on distribution functions.

Examples

The order of the entries does not affect the majorization, e.g., the statement $(1,2)\prec (0,3)$ is simply equivalent to $(2,1)\prec (3,0)$.

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

$\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: $(1,2,3)\prec_w (1,3,3)\prec_w (1,3,4)$. For vectors with n components:

$\left(\frac{1}{n}, \ldots, \frac{1}{n}\right)\prec_w \left(\frac{1}{n-1}, \ldots, \frac{1}{n-1},1\right).$

Geometry of Majorization

Figure 1. 2D Majorization Example

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}$.

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. 3D Majorization Example

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}$.

Equivalent conditions

Each of the following statements is true if and only if $\mathbf{a}\succ \mathbf{b}$:

• $\mathbf{b} = D\mathbf{a}$ for some doubly stochastic matrix D (see Arnold,^[1] Theorem 2.1).
• From $\mathbf{a}$ we can produce $\mathbf{b}$ by a finite sequence of "Robin Hood operations" where we replace two elements a_i and a_j < a_i with a_i − ε and a_j + ε, respectively, for some $\varepsilon \in (0, a_i-a_j)$ (see Arnold,^[1] p. 11).
• For every convex function $h:\mathbb{R}\to \mathbb{R}$, $\sum_{i=1}^d h(a_i) \geq \sum_{i=1}^d h(b_i)$ (see Arnold,^[1] Theorem 2.9).
• $\forall t \in \mathbb{R} \quad \sum_{j=1}^d |a_j-t| \geq \sum_{j=1}^d |b_j-t|$. (see Nielsen and Chuang Exercise 12.17,^[2])

In linear algebra

• Suppose that for two real vectors $v,v' \in \mathbb{R}^d$, v majorizes v'. Then it can be shown that there exists a set of probabilities $(p_1,p_2,\ldots,p_d), \sum_{i=1}^d p_i=1$ and a set of permutations $(P_1,P_2,\ldots,P_d)$ such that $v'=\sum_{i=1}^d p_iP_iv$. Alternatively it can be shown that there exists a doubly stochastic matrix D such that vD = v'

• We say that a hermitian operator, H, majorizes another, H', if the set of eigenvalues of H majorizes that of H'.

In recursion theory

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

See also

• For positive integer numbers, weak majorization is called Dominance order.

Notes

1. ^ ^{a b c} Barry C. Arnold. "Majorization and the Lorenz Order: A Brief Introduction". Springer-Verlag Lecture Notes in Statistics, vol. 43, 1987.
2. ^ Nielsen and Chuang. "Quantum Computation and Quantum Information". Cambridge University Press, 2000

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 (In preparation) Albert W. Marshall, Ingram Olkin, Barry Arnold, ISBN 9780387400877
• Inequalities: Theory of Majorization and Its Applications (1980) Albert W. Marshall, Ingram Olkin, Academic Press, ISBN 9780124737501
• A tribute to Marshall and Olkin's book "Inequalities: Theory of Majorization and its Applications"
• Quantum Computation and Quantum Information, (2000) Michael A. Nielsen and Isaac L. Chuang, Cambridge University Press, ISBN 9780521635035
• Matrix Analysis (1996) Rajendra Bhatia, Springer, ISBN 9780387948461
• Topics in Matrix Analysis (1994) Roger A. Horn and Charles R. Johnson, Cambridge University Press, ISBN 9780521467131
• Majorization and Matrix Monotone Functions in Wireless Communications (2007) Eduard Jorswieck and Holger Boche, Now Publishers, ISBN 9781601980403
• The Cauchy Schwarz Master Class (2004) J. Michael Steele, Cambridge University Press, ISBN 9780521546775

External links

• Majorization in MathWorld
• Majorization in PlanetMath

Software

• OCTAVE/MATLAB code to check majorization