Show that a system always admits a solution

Question

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?

Answer 1

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{equation} \begin{split} x_{1,A}=& \ \ q_{1}\\ x_{0,A}=&\ \ q_{0}, \end{split} \end{equation}

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

2. 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}$.

3. $|\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{equation} \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} \end{equation}

$$\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}$.