# Show that a system always admits a solution

Consider the following system with the vector of unknowns $$x\equiv (x_{y,v}: y\in \{0,1\}, v\in \mathcal{V})$$, where $$\mathcal{V}$$ is finite and $$|\mathcal{V}|\geq 2$$. \begin{aligned} & (1) \text{ }\sum_{v\in \mathcal{V}} x_{y,v}=q_y \text{ }\forall y\in \{0,1\} \\ & (2) \text{ }\sum_{v\in \mathcal{V}} x_{1,v}(z_{1,v}-z_{0,v})\geq 0 \\ & (3) \text{ }\sum_{v\in \mathcal{V}} x_{0,v}(z_{1,v}-z_{0,v})\leq 0\\ & (4) \text{ }\sum_{y\in \{0,1\}, v\in \mathcal{V}} x_{y,v}=1 \\ & (5) \text{ }0\leq x_{y,v}\leq 1 \text{ }\forall y\in \{0,1\}, \forall v \in \mathcal{V} \end{aligned}

We also know that $$q_0+q_1=1$$, $$q_0\geq 0$$, $$q_1\geq 0$$. I would like to show that the system admits a solution for any $$q_0, q_1, (z_{1,v}, z_{0,v}: v\in \mathcal{V})$$. Can you help?

How far I went: Observe that the upper bound in (5) is implied by (4) and the lower bound in (5). Also, (4) is implied by (2). Hence, the problem reduces to: \begin{aligned} &x_0 1_{|\mathcal{V}|}=q_0 \\ &x_1 1_{|\mathcal{V}|}=q_1 \\ &x_1 z^\top \geq 0 \\ & x_0 z^\top \leq 0 \\ &x_0\geq 0 \\ & x_1\geq 0 \end{aligned} where \begin{aligned} &x_{y}\equiv (x_{y,v}: v \in \mathcal{V})\\ &z_{y}\equiv (z_{y,v}: v \in \mathcal{V})\\ &z\equiv z_1-z_0\\ &1_{|\mathcal{V}|}\text{ is a column vector of ones of size |\mathcal{V}|\times 1.} \end{aligned}

How can I proceed from here?

• You need $z\geq0$ as a hypothesis. Jan 12 at 20:29

## 1 Answer

1. First case ($$z$$ can be less than $$0$$):

Let $$\mathcal{V}=\{A\}$$, and let $$z_{A}=z_{1,A}-z_{0,A}=-1$$

$$$$\begin{split} x_{1,A}=& \ \ q_{1}\\ x_{0,A}=&\ \ q_{0}, \end{split}$$$$

implies that $$x_{1,A}\cdot z_{A}=q_{1}\cdot z_{A}<0$$, so the system doesn't have solutions.

1. Second case ($$z_{v}\geq0,\ \forall v\in \mathcal{V}$$):

Conditions (2) and (3) holds becasuse of $$x_{y,v}$$ being non negative. If condition (1) holds, then (4) too due to $$q_{0}+q_{1}=1$$. So you have to check only condition (1).

You can find $$x_{y,v}$$ satisfiyng condition (1) if and only if $$q_{y}\leq |\mathcal{V}|$$, where $$|\mathcal{V}|$$ denotes the number of elements in $$\mathcal{V}$$.

1. $$|\mathcal{V}|\geq 2$$.

First of all, recall that given $$\lambda \in [0,1]$$, $$x,y\in \mathbb{R}$$, then $$\lambda x + (1-\lambda)y\in [x,y]$$ is a convex combination of $$x$$ and $$y$$. Besides, $$\sum_{i\in I}\lambda_{i}=1$$ implies that $$w=\sum_{i\in I}\lambda_{i}x_{i}$$ is a convex combination of the points in $$\{x_{i}\in \mathbb{R}:i\in I\}$$, so $$w\in[\min_{i\in I}(x_{i}),\max_{i\in I}(x_{i})]$$.

In our problem, $$z_{v}=z_{1,v}-z_{0,v}$$ will play the role of $$x_{i}$$ and a transformation of $$x_{y,v}$$ the role of $$\lambda_{i}$$.

$$\sum_{v\in \mathcal{V}}x_{y,v}=q_{y}\iff \sum_{v\in \mathcal{V}}\bar{x}_{y,v}=1,\ \forall y\in \{0,1\},$$ where $$\bar{x}_{y,v}=x_{y,v}/q_{y}$$. If $$q_{y}=0$$ it suffices to consider $$x_{y,v}=0\ \forall v\in \mathcal{V}$$.

Also we have that

$$$$\begin{split} \sum_{v\in \mathcal{V}}x_{1,v}z_{v}\geq0 \iff& \sum_{v\in \mathcal{V}}\bar{x}_{1,v}(q_{1}z_{v})\geq0\\ \sum_{v\in \mathcal{V}}x_{0,v}z_{v}\leq0 \iff& \sum_{v\in \mathcal{V}}\bar{x}_{0,v}(q_{0}z_{v})\leq0 \end{split}$$$$

$$\sum_{v\in \mathcal{V}}\bar{x}_{1,v}(q_{1}z_{v})\in [\min_{v\in\mathcal{V}}q_{1}z_{v},\max_{v\in\mathcal{V}}q_{1}z_{v}] ,$$ so if $$\max_{v\in\mathcal{V}}(q_{1}z_{v})<0$$ the system doesn't admit a solution. Reversely, suppose that $$\max_{v\in\mathcal{V}}(q_{1}z_{v})\geq0$$ and denote $$v_{max}$$ a element which maximize $$z_{v}$$ (it could be more), then $$\bar{x}_{1,v_{max}}=1 \iff x_{1,v_{max}}=q_{1}$$ and $$\bar{x}_{1,v}=0\iff x_{1,v}=0, \forall v\in\mathcal{V}\setminus\{v_{max}\}$$ satisfies (2).

You can proceed analogously with $$y=0$$ and obtain that it exists a set of $$x_{0,v}$$ that satisfies (3) if and only if $$\min_{v\in\mathcal{V}}(q_{0}z_{v})\leq0$$.

So in conclusion, the problems admits a solution if $$\exists\ v,w\in \mathcal{V}$$ such that $$q_{0}z_{v}\leq 0\leq q_{1}z_{w}$$.

• Thanks. Case 1.: I forgot to mention that $|\mathcal{V}|\geq 2$. Case 2: $q_y\leq |\mathcal{V}|$ is always satisfied as $0\leq q_y\leq 1$. Therefore, in case 2, there is always a solution. Can you rephrase case 1 when $|\mathcal{V}|\geq 2$?
– TEX
Jan 13 at 9:12
• I added a continuation of the proof. Jan 13 at 13:03
• I think there is some typos in the English of "..., then $\tilde{x}_{1,v_{max}}=1 \Leftrightarrow x_{1,v_{max}}=q_1$ and others $\tilde{x}_{1,v}=0$ is satisfied (2)". Also what is $v_{max}$?
– TEX
Jan 13 at 13:31
• You're right, I corrected it. Jan 13 at 14:11