Abstract

We consider two types of majorization relationships between sequences of vectors y=(yk)k=1my=(y_k)_{k=1}^m and x=(xk)k=1ℓx=(x_k)_{k=1}^\ell in Rn\R^n with ℓ≤m\ell\le m. It is said that xx is majorized by yy, x≺yx \prec y, if the sum of any kk vectors from xx is in the convex hull of all possible sums of kk vectors from yy. It is said that xx is doubly stochastically majorized by yy, x≺dsyx \prec_{\rm ds} y, if xk=∑j=1mmkjyjx_k = \sum_{j=1}^m m_{kj}y_j, k=1,...,ℓk=1,...,\ell, for some doubly stochastic matrix M=(mkj)k,j=1m,mM=(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≺y⇔x≺dsyx\prec y \Leftrightarrow x \prec_{\rm ds} y. We answer this question in the case when the vectors in yy 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(y)={x:x≺y}L^2_{\prec}(y)=\{x: x \prec y\}. Finally, we derive a set of algebraic conditions that characterize the extreme points of L≺ℓ(y)={x:x≺y}L^\ell_{\prec}(y)=\{x: x \prec y\} for any ℓ≤m\ell \le m and yy.

Author information

Contact details are reproduced from the original publication and may be historical.

Pal Fischer

Dept. of Mathematics and Statistics, University of Guelph, Guelph, Ontario N1G 2W1, Canada

pfischer@uoguelph.ca

Hristo Sendov

Dept. of Statistical and Actuarial Sciences, University of Western Ontario, London, Ontario N6A 5B7, Canada

hssendov@stats.uwo.ca

Keywords

  • Convex set
  • doubly stochastic majorization
  • Malamud majorization
  • extreme point
  • convex function
  • CVS class

Mathematics Subject Classification

52B11, 42A20

References

  1. R. Bhatia: Matrix Analysis, Springer, New York (1997).https://doi.org/10.1007/978-1-4612-0653-8Google Scholar
  2. A. L. Dontchev, R. T. Rockafellar: Implicit Functions and Solution Mappings. A View from Variational Analysis, Springer, New York (2008).https://doi.org/10.1007/978-0-387-87821-8Google Scholar
  3. B. Ćurgus, K. Kołodziejczyk: On a convex operator for finite sets, Discrete Appl. Math. 155 (2007) 1774–1792.https://doi.org/10.1016/j.dam.2007.04.028Google Scholar
  4. P. Fischer, J. A. R. Holbrook: Balayage defined by the nonnegative convex functions, Proc. Amer. Math. Soc. 79 (1980) 445–448.https://doi.org/10.1090/S0002-9939-1980-0567989-9Google Scholar
  5. S. M. Malamud: Inverse spectral problem for normal matrices and the Gauss-Lucas theorem, Trans. Amer. Math. Soc 357(10) (2004) 4043–4064.https://doi.org/10.1090/S0002-9947-04-03649-9Google Scholar
  6. A. W. Marshall, I. Olkin: Inequalities: Theory of Majorization and its Applications, Mathematics in Science and Engineering 143, Academic Press, New York (1979).Google Scholar
  7. A. L. Peressini, F. E. Sullivan, J. J. Uhl, Jr.: The Mathematics of Nonlinear Programming, Undergraduate Texts in Mathematics, Springer, New York (1988).https://doi.org/10.1007/978-1-4612-1025-2Google Scholar
  8. R. T. Rockefellar: Convex Analysis, Princeton University Press, Princeton (1970).https://doi.org/10.1515/9781400873173Google Scholar
  9. F. A. Valentine: Convex Sets, McGraw-Hill, New York (1964).Google Scholar

Suggested citation

P. Fischer, H. Sendov. “On Malamud Majorization and the Extreme Points of its Level Sets.” Journal of Convex Analysis 17 (2010), No. 2, 485–507. https://doi.org/10.68381/jca17033

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2010. Rights now held by Banach Press LLC.