1
$\begingroup$

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

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ This does need more detail. There are often many "Robin Hood" moves that can be done from any given vector (you get to choose which two entries to change), and until you specify the rule according to which you make this choice, you don't have a (deterministic) algorithm. $\endgroup$
    – darij grinberg
    Commented Jul 25, 2021 at 21:06
  • $\begingroup$ Hy thanks, the only rule is that two consecutive vectors in the expression differs only by two entries. If one is familiar with majorization the pretty known result i mentionned let us have $c^{(m)}$ then $c^{(m-1)}$ etc. The trig here i got a way to get from $a$ to $b$ reversely. $\endgroup$
    – Toni Mhax
    Commented Jul 25, 2021 at 21:51
  • $\begingroup$ It should be true for any two vectors $a\prec b$. I may put the two algorithms, but if you find a way to build the sequence from $a$ to $b$ as i guess did, after some examples i got the same exact sequence $c^{(i)}$ given in the books which goes from $b$ to $a$. $\endgroup$
    – Toni Mhax
    Commented Jul 25, 2021 at 21:56
  • $\begingroup$ Hence i posted here if someone can manage a transition $a---b$ we can compare the ways and perhaps know why i got the same sequence. In fact this is my goal. As i said the algorithm in the books is pretty known. Let me know if i should explain it. In Z. Kadelburg, D. Duki´c, M. Luki´c and I. Mati´c, Inequalities of Karamata, Schur and Muirhead and some applications, The Teaching of Mathematics, there is also an algorithm that gives $c^{m)}$ than $c^{(m-1)}$ it is close to the one i mentionned. $\endgroup$
    – Toni Mhax
    Commented Jul 25, 2021 at 22:00

1 Answer 1

Reset to default
0
$\begingroup$

If you have an algorithm "from big to small", couldn't you obtain an algorithm "from small to big" by replacing the vectors $a$, and $b$ by $x*1-a$ and $x*1-b$ respectively, where $1$ is the vector containing just ones and $x$ is a scalar, larger than the maximum of $a$ and $b$?

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .