On Malamud Majorization and the Extreme Points of its Level Sets

We consider two types of majorization relationships between sequences of vectors $y=(y_k)_{k=1}^m$ and $x=(x_k)_{k=1}^\ell$ in $\R^n$ with $\ell\le m$. It is said that $x$ is majorized by $y$, $x \prec y$, if the sum of any $k$ vectors from $x$ is in the convex hull of all possible sums of $k$ vectors from $y$. It is said that $x$ is doubly stochastically majorized by $y$, $x \prec_{\rm ds} y$, if $x_k = \sum_{j=1}^m m_{kj}y_j$, $k=1,...,\ell$, for some doubly stochastic matrix $M=(m_{kj})_{k,j=1}^{m,m}$. In a recent article ["Inverse spectral problem for normal matrices and the Gauss-Lucas Theorem", Trans. Amer. Math. Soc. 357(10) (2004) 4043–4064] S. M. Malamud formulated the problem of finding a geometric condition guaranteeing that $x\prec y \Leftrightarrow x \prec_{\rm ds} y$. We answer this question in the case when the vectors in $y$ are distinct and are extreme points of their convex hull. In particular, we derive a geometric characterization of the extreme points of the level set $L^2_{\prec}(y)=\{x: x \prec y\}$. Finally, we derive a set of algebraic conditions that characterize the extreme points of $L^\ell_{\prec}(y)=\{x: x \prec y\}$ for any $\ell \le m$ and $y$.