Skip to main content
4 of 5
Clarification
Toni Mhax
  • 785
  • 5
  • 13

A sequence and majorization

For two positive vectors $a,b$ such that $a\prec b$, we know that there is an $m$ sequence of vectors $c^{(i)}$ such that $$a\prec c^{(1)}\prec \ldots \prec c^{(m)}\prec b$$ where each vector in the precedent formula differs from its successor by two entries. This is a classic result. See {A. W. Marshall,I. Olkin, B. C. Arnold, Inequalities: Theory of Majorization and Its Applications}. First figure. In the second figure i found a way to start from $a$ and arrive at $b$ and by some «example verification» i obtained the same sequence $c^{(i)}$ given in the algorithm of the third figure from an article INEQUALITIES OF KARAMATA, SCHUR AND MUIRHEAD, AND SOME APPLICATIONS Zoran Kadelburg, Dusan Dukic, Milivoje Lukic and Ivan Matic Can someone tell why?

Edit i guess i found the reason.

(Here in figure one the vector $a$ is $x$ and $b$ is $y$. $y^*$ is $c^{(m)}$ and $c$ is $c^{(1)}$. If you repeat the same algorithm applied to $a\prec c^{(m)}$ you obtain $c^{(m-1)}$ until you get $a$); whether if you apply the second (at each step delete the equal entries) you get first $c^{(1)}$ and then repeatedly arrive at $b$ where here the sequence is the same obtained from the third figure algorithm.

The algorithm in books

The algorithm found

The algorithm in the article

Toni Mhax
  • 785
  • 5
  • 13