In
mathematics, majorization is a
preorder on
vectors of
real numbers. Let
denote the
-th largest element of the vector
. Given
, we say that
weakly majorizes (or dominates)
from below (or equivalently, we say that
is weakly majorized (or dominated) by
from below) denoted as
if
for all
. If in addition
, we say that
majorizes (or dominates)
, written as
, or equivalently, we say that
is majorized (or dominated) by
. The order of the entries of the vectors
or
does not affect the majorization, e.g., the statement
is simply equivalent to
. As a consequence, majorization is not a
partial order
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a bina ...
, since
and
do not imply
, it only implies that the components of each vector are equal, but not necessarily in the same order.
The majorization partial order on finite dimensional vectors, described here, can be generalized to the
Lorenz ordering, a partial order on
distribution functions. For example, a
wealth distribution
The distribution of wealth is a comparison of the wealth of various members or groups in a society. It shows one aspect of economic inequality or economic heterogeneity.
The distribution of wealth differs from the income distribution in tha ...
is Lorenz-greater than another if its
Lorenz curve
In economics, the Lorenz curve is a graphical representation of the distribution of income or of wealth. It was developed by Max O. Lorenz in 1905 for representing inequality of the wealth distribution.
The curve is a graph showing the proportio ...
lies below the other. As such, a Lorenz-greater wealth distribution has a higher
Gini coefficient, and has more
income disparity
There are wide varieties of economic inequality, most notably income inequality measured using the distribution of income (the amount of money people are paid) and wealth inequality measured using the distribution of wealth (the amount of we ...
. Various other generalizations of majorization are discussed in chapters 14 and 15 of.
Examples
(Strong) majorization:
. For vectors with
components
:
(Weak) majorization:
. For vectors with
components:
:
Geometry of majorization
For
we have
if and only if
is in the convex hull of all vectors obtained by permuting the coordinates of
.
Figure 1 displays the convex hull in 2D for the vector
. Notice that the center of the convex hull, which is an interval in this case, is the vector
. This is the "smallest" vector satisfying
for this given vector
.
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
satisfying
for this given vector
.
Schur convexity
A function
is said to be
Schur convex when
implies
. Hence, Schur-convex functions translate the ordering of vectors to a standard ordering in
. Similarly,
is Schur concave when
implies
An example of a Schur-convex function is the max function,
. 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.
Equivalent conditions
Each of the following statements is true if and only if
:
*
for some
doubly stochastic matrix In mathematics, especially in probability and combinatorics, a doubly stochastic matrix
(also called bistochastic matrix) is a square matrix X=(x_) of nonnegative real numbers, each of whose rows and columns sums to 1, i.e.,
:\sum_i x_=\sum_j x_=1 ...
.
[Barry C. Arnold. "Majorization and the Lorenz Order: A Brief Introduction". Springer-Verlag Lecture Notes in Statistics, vol. 43, 1987.] This is equivalent to saying
can be represented as a
convex combination
In convex geometry and vector algebra, a convex combination is a linear combination of points (which can be vectors, scalars, or more generally points in an affine space) where all coefficients are non-negative and sum to 1. In other w ...
of the permutations of
; one can verify that there exists such a convex representation using at most
permutations of
.
* From
we can produce
by a finite sequence of "Robin Hood operations" where we replace two elements
and
with
and
, respectively, for some
.
[
* For every convex function , .][
**In fact, a special case suffices: and, for every , .][July 3, 2005 post by fleeting_guest o]
"The Karamata Inequality" thread
AoPS community forums.
Archived
11 November 2020.
*.
In linear algebra
* Suppose that for two real vectors , majorizes . Then it can be shown that there exists a set of probabilities and a set of permutations such that .[ Alternatively it can be shown that there exists a ]doubly stochastic matrix In mathematics, especially in probability and combinatorics, a doubly stochastic matrix
(also called bistochastic matrix) is a square matrix X=(x_) of nonnegative real numbers, each of whose rows and columns sums to 1, i.e.,
:\sum_i x_=\sum_j x_=1 ...
such that
*We say that a Hermitian operator
In mathematics, a self-adjoint operator on an infinite-dimensional complex vector space ''V'' with inner product \langle\cdot,\cdot\rangle (equivalently, a Hermitian operator in the finite-dimensional case) is a linear map ''A'' (from ''V'' to it ...
, , majorizes another, , if the set of eigenvalues of majorizes that of .
In computability theory
Given , then is said to ''majorize'' if, for all , . If there is some so that for all , then is said to ''dominate'' (or ''eventually dominate'') . Alternatively, the preceding terms are often defined requiring the strict inequality instead of in the foregoing definitions.
See also
* Muirhead's inequality In mathematics, Muirhead's inequality, named after Robert Franklin Muirhead, also known as the "bunching" method, generalizes the inequality of arithmetic and geometric means.
Preliminary definitions
''a''-mean
For any real vector
:a=(a_1,\dots ...
* Karamata's Inequality
* Schur-convex function
* Schur–Horn theorem relating diagonal entries of a matrix to its eigenvalues.
* For positive integer number
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language of ...
s, weak majorization is called Dominance order
In discrete mathematics, dominance order (synonyms: dominance ordering, majorization order, natural ordering) is a partial order on the set of partitions of a positive integer ''n'' that plays an important role in algebraic combinatorics and repr ...
.
* Leximin order
In mathematics, leximin order is a total preorder on finite-dimensional vectors. A more accurate, but less common term is leximin preorder. The leximin order is particularly important in social choice theory and fair division.
Definition
A vec ...
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
Ingram Olkin (July 23, 1924 – April 28, 2016) was a professor emeritus and chair of statistics and education at Stanford University and the Stanford Graduate School of Education. He is known for developing statistical analysis for evalua ...
, 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, {{ISBN, 978-0-521-54677-5
External links
Software
* OCTAVE/MATLAB
MATLAB (an abbreviation of "MATrix LABoratory") is a proprietary multi-paradigm programming language and numeric computing environment developed by MathWorks. MATLAB allows matrix manipulations, plotting of functions and data, implementa ...
br>code to check majorization
Order theory
Linear algebra