Existence of a specific stochastic matrix

Question

Let $0\le x_1\le x_2\le \cdots\le x_n\le n-1$ be given. My question is as follows : Under which condition there exists a doubly stochastic matrix $M=(m_{i,j})_{1\le i,j\le n}$ s.t.

$$\sum_{j=1}^n (j-1)m_{i,j}=x_i \quad \mbox{for all } 1\le i\le n,$$

$$\sum_{j=k}^nm_{i,j}\le \sum_{j=k}^nm_{i+1,j},\quad \mbox{for all } 1\le i\le n-1 \mbox{ and } 1\le k\le n.$$

Here a double stochastic matrix refers to $\min_{1\le i,j\le n}m_{i,j}\ge 0$, $\sum_{j=1}^n m_{i,j}=1$ for all $1\le i\le n$ and $\sum_{i=1}^n m_{i,j}=1$ for all $1\le j\le n$. Any answers or comments are highly appreciated!

Answer 1

Let $$x = \left[\begin{matrix} x_1\\ x_2 \\ \vdots \\ x_n\end{matrix}\right] \quad \textrm{and} \quad y = \left[\begin{matrix}0 \\ 1 \\ \vdots \\ n-1\end{matrix}\right] $$ Your first condition, that there exists a doubly stochastic matrix $M=[m_{i,j}]$ $$ \sum_{j=1}^n (j-1)m_{i,j} = x_i \quad \textrm{for all}\ 1\leq i\leq n $$ becomes $My = x$ which by the Hardly-Littlewood-Polya Theorem is equivalent to $y \prec x$, or $y$ is majorized by $x$. In other words, $$ \sum_{j=k}^n (j-1) \leq \sum_{j=k}^n x_j \quad \textrm{for all} \ 1\leq k\leq n \quad \textrm{and} \quad \sum_{j=1}^n (j-1) = \sum_{j=1}^n x_j $$

In particular, one can choose $M$ such that $JMJ$, where $$ J = \left[\begin{matrix} &&1 \\ & \unicode{x22f0} & \\ 1&&\end{matrix}\right], $$ is a uniformly tapered doubly stochastic matrix: $$ m_{1,1} \geq m_{2,1} \geq \cdots \geq m_{1,n}, \ m_{1,n} \leq m_{2,n} \leq \cdots \leq m_{n,n}, \quad \textrm{and} \quad m_{i,j} + m_{i+1,j-1} \geq m_{i,j-1} + m_{i+1,j} $$ for $2\leq i, j \leq n-1$. See Defintion 2.B.5 and Theorem 2.B.6 in Marshall and Olkin's book.

This gets you some way towards your second set of inequalities on the columns of $M$, for instance, the $2\times 2$ case is satisfied. However, I am not sure if you can prove your inequalities from this in general.

Answer 2

I saw the question up. In fact this has a positive answer and it is a bit of a nice one. As mentioned and well known you basicaly have $Ay=x$ with $y= \begin{pmatrix}0 \\ 1 \\ \vdots \\ n-1\end{pmatrix}$ and $x = \begin{pmatrix} x_1\\ x_2 \\ \vdots \\ x_n\end{pmatrix}$ with $A$ doubly stochastic. This implies that $x\prec y$. For an easier presentation we rearrange everything so that $x_1\ge\cdots\ge x_n$ and $y_1\ge\cdots \ge y_n$; you want $A$ to verify $Ay=x$ and the condition: $$(\star) \quad\sum_{j=1}^ka_{i,j}\ge \sum_{j=1}^ka_{i+1,j},\quad \mbox{for all } 1\le i\le n-1 \mbox{ and } 1\le k\le n$$ Here we already take $x$ and $y$ random non negative vectors with $x\prec y$ $(Ay=x)$. A sketch of proof is as follows:

1. First if $A$ and $B$ are two doubly stochastic matrices verifying $(\star)$ then $A\cdot B$ also verifies $(\star)$.
2. By known results on majorization if $x\prec y$ then there is a sequence of vectors $z_i$ with $x=z_0\prec z_1\prec \cdots\prec z_i\prec z_{i+1}=y$ and such that two consecutive vectors differ by only two entries.
3. From these two it is sufficient to prove that such $A$ exist when $x$ and $y$ differs by only two entries. Up to a direct sum of identity matrices we take $y=\begin{pmatrix}r+h\\r\\\vdots\\r\\r-k\end{pmatrix}$ and $x=\begin{pmatrix}r+h-s\\r\\\vdots\\r\\r-k+s\end{pmatrix}$ and $h\ge s>0$, $k\ge s>0$, with $m$ common terms as $r$,$m\ge 1$ the case $m=0$ is easy. One can set $$A=\begin{cases}a_{1,1}=a\\a_{i,1}=c, 2\le i\le m+1\\a_{m+2,1}=1-a-mc\\a_{1,j}=u, 2\le j\le m+1\\a_{1,m+2}=1-a-mu\\a_{i,j}=v, 2\le i\le m+1 \,\& \,2\le j \le m+1\\a_{m+2,j}=1-u-mv, 1\le j\le m+1\\a_{i,m+2}=1-c-mv, 2\le i\le m+1\\a_{m+2,m+2}=1-m(1-c-mv)-(1-a-mu)\end{cases}$$ Solving $Ay=x$ in terms of $h,k, u,v$ and $s$ gives the expressions of $a$ and $c$. The condition $(\star)$ and the non negativity for the entries of $A$ reduce to a system of seven (linear) inequalities, in the plane $(u,v)$, with a non empty set of solutions.