# Nonnegative solution of a linear system

Given three collections of parameters $\epsilon_1 > ... > \epsilon_N$, $(a_1,...,a_{N-1})$ and $(b_1,...,b_N)$ that satisfy the following conditions

1. $\forall i, a_i \geq 0, \sum_{i=1}^{N-1}{a_i}=1$
2. $\sum_{i=1}^{N}b_i=0$, and $\sum_{i=1}^{k}b_i \geq 0$ for all $1 \leq k \leq N$
3. $\sum_{i=1}^{N}{b_i \epsilon_i}=1$
4. $\forall 1 \leq i \leq j \leq S-1, \sum_{k=i}^{j}{a_k} \geq \sum_{k=i}^{j}{b_k(\epsilon_k-\epsilon_{j+1})}$

I want to show that the linear system below admits a solution whose elements $x_i^j$ are all nonnegative (by convention, sums over empty sets equal zero):

\begin{equation*} \left\{ \begin{array}{ll} \forall i \in \{1,...,N-1\}, \displaystyle \sum_{j=i+1}^{N}{x_i^j(\epsilon_i-\epsilon_j)} = a_i & \\ \forall i \in \{1,...,N\}, \displaystyle \sum_{j=i+1}^{N}{x_i^j} - \displaystyle \sum_{j=1}^{i-1}{x_j^{i}} = b_{i} & \end{array} \right. \end{equation*}

For instance, if $N=4$, my system is \begin{equation*} \begin{pmatrix} \epsilon_1-\epsilon_2 & \epsilon_1-\epsilon_3 & \epsilon_1-\epsilon_4 & 0 & 0 & 0 \\ 0 & 0 & 0 & \epsilon_2-\epsilon_3 & \epsilon_2-\epsilon_4 & 0 \\ 0 & 0 & 0 & 0 & 0 & \epsilon_3-\epsilon_4 \\ 1 & 1 & 1 & 0 & 0 & 0 \\ -1 & 0 & 0 & 1 & 1 & 0 \\ 0 & -1 & 0 & -1 & 0 & 1 \\ 0 & 0 & -1 & 0 & -1 & -1 \end{pmatrix} . x = \begin{pmatrix} a_1 \\ a_2 \\ a_3 \\ b_1 \\ b_2 \\ b_3 \\ b_4 \end{pmatrix} \end{equation*}

I am confident the result is true (it works on small examples, for instance for $N=4$), but I would like to obtain a general proof. I have tried to prove the result by induction, to simplify the system by Gaussian elimination method, to provide a constructive proof, and to use affine versions of Farkas lemma, but all in vain. Any help will be much appreciated! Thanks a lot in advance.

• There are couple of confusing features about this problem description. Is $x$ a matrix? (It has two indices, so apparently it is, but then how does the product $(\text{matrix}).x = (a_i|b_i)^T$ make sense? Also, the first of your braced equations for $i \in \{1,2\}$ gives $i=1$: $\sum_{j=2}^4 x_1^j (\epsilon_1 - \epsilon_j)$ or the row $(0, \epsilon_1-\epsilon_2, \epsilon_1-\epsilon_3, \epsilon_1 - \epsilon_4, 0,0,0)$ and for $i=2$: $(0, 0, \epsilon_2-\epsilon_3, \epsilon_2-\epsilon_4, 0, 0, 0)$. That is, the first two rows's nonzero elements overlap. Which of these was intended? – Eric Towers Jun 12 '15 at 22:31
• Sorry if it was confusing. $x$ is a vector obtained by concatenation of the vectors $(x_i^{i+1},\cdots,x_i^{n})$ for $i=1,\cdots,n-1$. That is: : $$x=(x_1^{2},x_1^{3},\cdots,x_1^{n},x_2^{3},\cdots,x_2^{n},\cdots,\cdots,x_{n-1}^{n})$$ Therefore for $i=1$ we get the first row of the matrix and for $i=2$ the second row. – Oliv Jun 13 '15 at 6:39