On Malamud Majorization and the Extreme Points of its Level Sets

We consider two types of majorization relationships between sequences of vectors

and

x=(x_k)_{k=1}^\ell x = ( x k ) k = 1 ℓ

in

\mathbb{R}^n R n

with

\ell\le m ℓ ≤ m

. It is said that

x x

is majorized by

y y

,

x \prec y x ≺ y

, if the sum of any

k k

vectors from

x x

is in the convex hull of all possible sums of

k k

vectors from

y y

. It is said that

x x

is doubly stochastically majorized by

y y

,

x \prec_{\rm ds} y x ≺ d s y

, if

x_k = \sum_{j=1}^m m_{kj}y_j x k = ∑ j = 1 m m k j y j

,

k=1,...,\ell k = 1 , . . . , ℓ

, for some doubly stochastic matrix

M=(m_{kj})_{k,j=1}^{m,m} M = ( m k j ) 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 x ≺ y ⇔ x ≺ d s y

. We answer this question in the case when the vectors in

y 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\} L ≺ 2 ( y ) = { x : x ≺ y }

. Finally, we derive a set of algebraic conditions that characterize the extreme points of

L^\ell_{\prec}(y)=\{x: x \prec y\} L ≺ ℓ ( y ) = { x : x ≺ y }

for any

\ell \le m ℓ ≤ m

and

y y

.