Majorization

In <a href="/facts/Mathematics/pxTouaz4">mathematics</a>, majorization is a <a href="/facts/Preorder/uubzHSWm">preorder</a> on <a href="/facts/Vector_space/M1pxMLx2">vectors</a> of <a href="/facts/Real_numbers/R02gw5Pb">real numbers</a>. For two such vectors, 
 
 
 
 
 x
 
 ,
  
 
 y
 
 ∈
 
 
 R
 
 
 n
 
 
 
 
 {\displaystyle \mathbf {x} ,\ \mathbf {y} \in \mathbb {R} ^{n}}
 
, we say that 
 
 
 
 
 x
 
 
 
 {\displaystyle \mathbf {x} }
 
 weakly majorizes (or dominates) 
 
 
 
 
 y
 
 
 
 {\displaystyle \mathbf {y} }
 
 from below, commonly denoted 
 
 
 
 
 x
 
 
 ≻
 
 w
 
 
 
 y
 
 ,
 
 
 {\displaystyle \mathbf {x} \succ _{w}\mathbf {y} ,}
 
 when

∑
 
 i
 =
 1
 
 
 k
 
 
 
 x
 
 i
 
 
 ↓
 
 
 ≥
 
 ∑
 
 i
 =
 1
 
 
 k
 
 
 
 y
 
 i
 
 
 ↓
 
 
 
 
 {\displaystyle \sum _{i=1}^{k}x_{i}^{\downarrow }\geq \sum _{i=1}^{k}y_{i}^{\downarrow }}
 
 for all 
 
 
 
 k
 =
 1
 ,
 
 …
 ,
 
 n
 
 
 {\displaystyle k=1,\,\dots ,\,n}
 
,
where 
 
 
 
 
 x
 
 i
 
 
 ↓
 
 
 
 
 {\displaystyle x_{i}^{\downarrow }}
 
 denotes 
 
 
 
 i
 
 
 {\displaystyle i}
 
th largest entry of 
 
 
 
 x
 
 
 {\displaystyle x}
 
. If 
 
 
 
 
 x
 
 ,
 
 y
 
 
 
 {\displaystyle \mathbf {x} ,\mathbf {y} }
 
 further satisfy 
 
 
 
 
 ∑
 
 i
 =
 1
 
 
 n
 
 
 
 x
 
 i
 
 
 =
 
 ∑
 
 i
 =
 1
 
 
 n
 
 
 
 y
 
 i
 
 
 
 
 {\displaystyle \sum _{i=1}^{n}x_{i}=\sum _{i=1}^{n}y_{i}}
 
, we say that 
 
 
 
 
 x
 
 
 
 {\displaystyle \mathbf {x} }
 
 majorizes (or dominates) 
 
 
 
 
 y
 
 
 
 {\displaystyle \mathbf {y} }
 
, commonly denoted 
 
 
 
 
 x
 
 ≻
 
 y
 
 
 
 {\displaystyle \mathbf {x} \succ \mathbf {y} }
 
. 
Both weak majorization and majorization are <a href="/facts/Partially_ordered_set/qb4a3FAX">partial orders</a> for vectors whose entries are non-decreasing, but only a <a href="/facts/Preorder/uubzHSWm">preorder</a> for general vectors, since majorization is agnostic to the ordering of the entries in vectors, e.g., the statement 
 
 
 
 (
 1
 ,
 2
 )
 ≺
 (
 0
 ,
 3
 )
 
 
 {\displaystyle (1,2)\prec (0,3)}
 
 is simply equivalent to 
 
 
 
 (
 2
 ,
 1
 )
 ≺
 (
 3
 ,
 0
 )
 
 
 {\displaystyle (2,1)\prec (3,0)}
 
.
Specifically, 
 
 
 
 
 x
 
 ≻
 
 y
 
 ∧
 
 y
 
 ≻
 
 x
 
 
 
 {\displaystyle \mathbf {x} \succ \mathbf {y} \wedge \mathbf {y} \succ \mathbf {x} }
 
 if and only if 
 
 
 
 
 x
 
 ,
 
 y
 
 
 
 {\displaystyle \mathbf {x} ,\mathbf {y} }
 
 are permutations of each other. Similarly for 
 
 
 
 
 ≻
 
 w
 
 
 
 
 {\displaystyle \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
 )
 ≥
 g
 (
 x
 )
 
 
 {\displaystyle f(x)\geq g(x)}
 
 for all 
 
 
 
 x
 
 
 {\displaystyle x}
 
 in the domain, or other technical definitions, such as majorizing measures in <a href="/facts/Probability_theory/mFBn51rE">probability theory</a>.

Majorization open-in-new

Majorization