The d-Majorization Polytope

• Published in: Linear algebra and its applications 2022-09, Vol.649, p.152-185
• Main Authors: vom Ende, Frederik, Dirr, Gunther
• Format: Article
• Language: English
• Subjects: Convex polytopes; d-Majorization polytope; Extreme points; Half spaces; Linear algebra; Majorization relative to d; Polytopes
• ISSN: 0024-3795; 1873-1856
• DOI: 10.1016/j.laa.2022.05.005

We investigate geometric and topological properties of d-majorization – a generalization of classical majorization to positive weight vectors d∈Rn. In particular, we derive a new, simplified characterization of d-majorization which allows us to work out a halfspace description of the corresponding d-majorization polytopes. That is, we write the set of all vectors which are d-majorized by some given vector y∈Rn as an intersection of finitely many half spaces, i.e. as solutions to an inequality of the type Mx≤b. Here b depends on y while M can be chosen independently of y. This description lets us prove continuity of the d-majorization polytope (jointly with respect to d and y) and, furthermore, lets us fully characterize its extreme points. Interestingly, for y≥0 one of these extreme points classically majorizes every other element of the d-majorization polytope. Moreover, we show that the induced preorder structure on Rn admits minimal and maximal elements. While the former are always unique the latter are unique if and only if they correspond to the unique minimal entry of the d-vector.