Majorization
Get Majorization essential facts below. View Videos or join the Majorization discussion. Add Majorization to your PopFlock.com topic list for future reference or share this resource on social media.
Majorization

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

${\displaystyle \sum _{i=1}^{k}a_{i}^{\downarrow }\geq \sum _{i=1}^{k}b_{i}^{\downarrow }\quad {\text{for }}k=1,\dots ,d,}$

Equivalently, we say that ${\displaystyle \mathbf {b} }$ is weakly majorized (or dominated) by ${\displaystyle \mathbf {a} }$ from below, written as ${\displaystyle \mathbf {b} \prec _{w}\mathbf {a} }$.

If ${\displaystyle \mathbf {a} \succ _{w}\mathbf {b} }$ and in addition ${\displaystyle \sum _{i=1}^{d}a_{i}=\sum _{i=1}^{d}b_{i}}$, we say that ${\displaystyle \mathbf {a} }$ majorizes (or dominates) ${\displaystyle \mathbf {b} }$, written as ${\displaystyle \mathbf {a} \succ \mathbf {b} }$. Equivalently, we say that ${\displaystyle \mathbf {b} }$ is majorized (or dominated) by ${\displaystyle \mathbf {a} }$, written as ${\displaystyle \mathbf {b} \prec \mathbf {a} }$.

Note that the majorization order does not depend on the order of the components of the vectors ${\displaystyle \mathbf {a} }$ or ${\displaystyle \mathbf {b} }$. Majorization is not a partial order, since ${\displaystyle \mathbf {a} \succ \mathbf {b} }$ and ${\displaystyle \mathbf {b} \succ \mathbf {a} }$ do not imply ${\displaystyle \mathbf {a} =\mathbf {b} }$, it only implies that the components of each vector are equal, but not necessarily in the same order.

Note that the notation is inconsistent in the mathematical literature: some use the reverse notation, e.g., ${\displaystyle \succ }$ is replaced with ${\displaystyle \prec }$.

A function ${\displaystyle f:\mathbb {R} ^{d}\to \mathbb {R} }$ is said to be Schur convex when ${\displaystyle \mathbf {a} \succ \mathbf {b} }$ implies ${\displaystyle f(\mathbf {a} )\geq f(\mathbf {b} )}$. Similarly, ${\displaystyle f(\mathbf {a} )}$ is Schur concave when ${\displaystyle \mathbf {a} \succ \mathbf {b} }$ implies ${\displaystyle 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. For example, a wealth distribution is Lorenz-greater than another iff its Lorenz curve lies below the other. As such, a Lorenz-greater wealth distribution has a higher Gini coefficient, and has more income inequality.

Examples

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

(Strong) majorization: ${\displaystyle (1,2,3)\prec (0,3,3)\prec (0,0,6)}$. For vectors with 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 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).}$

Geometry of majorization

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. 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 ${\displaystyle \mathbf {x} }$ satisfying ${\displaystyle \mathbf {x} \prec \mathbf {y} }$ for this given vector ${\displaystyle \mathbf {y} }$.

Equivalent conditions

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

• ${\displaystyle \mathbf {b} =D\mathbf {a} }$ for some doubly stochastic matrix ${\displaystyle D}$ (see Arnold,[1] Theorem 2.1). This is equivalent to saying ${\displaystyle \mathbf {b} }$ can be represented as a convex combination of the permutations of ${\displaystyle \mathbf {a} }$. Furthermore the permutations require ${\displaystyle d}$ at most.[2]
• From ${\displaystyle \mathbf {a} }$ we can produce ${\displaystyle \mathbf {b} }$ by a finite sequence of "Robin Hood operations" where we replace two elements ${\displaystyle a_{i}}$ and ${\displaystyle a_{j} with ${\displaystyle a_{i}-\varepsilon }$ and ${\displaystyle a_{j}+\varepsilon }$, respectively, for some ${\displaystyle \varepsilon \in (0,a_{i}-a_{j})}$ (see Arnold,[1] p. 11).
• For every convex function ${\displaystyle h:\mathbb {R} \to \mathbb {R} }$, ${\displaystyle \sum _{i=1}^{d}h(a_{i})\geq \sum _{i=1}^{d}h(b_{i})}$ (see Arnold,[1] Theorem 2.9).
• ${\displaystyle \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,[3])

In linear algebra

• Suppose that for two real vectors ${\displaystyle v,v'\in \mathbb {R} ^{d}}$, ${\displaystyle v}$ majorizes ${\displaystyle v'}$. Then it can be shown that there exists a set of probabilities ${\displaystyle (p_{1},p_{2},\ldots ,p_{d}),\sum _{i=1}^{d}p_{i}=1}$ and a set of permutations ${\displaystyle (P_{1},P_{2},\ldots ,P_{d})}$ such that ${\displaystyle v'=\sum _{i=1}^{d}p_{i}P_{i}v}$.[2] Alternatively it can be shown that there exists a doubly stochastic matrix ${\displaystyle D}$ such that ${\displaystyle vD=v'}$
• We say that a Hermitian operator, ${\displaystyle H}$, majorizes another, ${\displaystyle H'}$, if the set of eigenvalues of ${\displaystyle H}$ majorizes that of ${\displaystyle H'}$.

In recursion theory

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.

Generalizations

Various generalizations of majorization are discussed in chapters 14 and 15 of the reference work 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