Show that a linear system may have no solutions

Question

I would like your help to show that the system below has at least one solution.

Let $\mathcal{Y}\equiv \{0,1\}$. Let $\mathcal{V}$ be a finite set containing positive and negative numbers.

Consider the system of equations/inqualities below. The vector of unknowns is $(x_{y,v}: y\in \mathcal{Y}, v\in \mathcal{V})$. We know the vectors $(w_v: v\in \mathcal{V})$, $(q_y: y\in \mathcal{Y})$, and $(z_{y,v}: y\in \mathcal{Y}, v\in \mathcal{V})$, and the sets $\mathcal{V},\mathcal{Y}$. $$ (*) \quad \begin{cases} &(1) \quad \sum_{y\in \mathcal{Y}}x_{y,v} =w_v \quad \forall v \in \mathcal{V},\\ &(2) \quad \sum_{v\in \mathcal{V}} x_{y,v}=q_y\quad \forall y\in \mathcal{Y},\\ & -----------------------\\ &(3) \quad \sum_{v\in \mathcal{V}} x_{1,v} *z_{1,v} \geq \sum_{v\in \mathcal{V}} x_{1,v} *z_{0,v},\\ &(4) \quad\sum_{v\in \mathcal{V}} x_{0,v} *z_{0,v} \geq \sum_{v\in \mathcal{V}} x_{0,v} *z_{1,v} ,\\ &--------------------\\ &(5) \quad \sum_{y\in \mathcal{Y},v\in \mathcal{V}} x_{y,v}=1,\\ &(6) \quad 0\leq x_{y,v}\leq 1 \quad \forall y\in \mathcal{Y}, v\in \mathcal{V},\\ &(7) \quad \sum_{v\in \mathcal{V} } w_v=1,\\ &(8) \quad 0\leq w_v\leq 1 \quad \forall v\in \mathcal{V},\\ &(9) \quad \sum_{y\in \mathcal{Y} } q_y=1,\\ &(10) \quad 0\leq q_y\leq 1 \quad \forall y\in \mathcal{Y}.\\ \end{cases} $$

Question: Show that $(*)$ may not have a solution.

Note: I've posed a similar question here for the case where $z_{y,v}\equiv y*v$ (hence, constraints (3) and (4) look simpler there). Can the same counterexample be extended to this more general setting?

Answer 1

Let $\mathcal{Y}\equiv \{0,1\}$. Let $\mathcal{V}$ be a finite set containing positive and negative numbers.

Since the elements of $\cal Y, V$ are not used as anything other than indices, it doesn't matter what they are, only that $|\mathcal Y| = 2$ and $n = |\mathcal V|$ is finite.

We can define vectors in $\Bbb R^n$: $$x_0 = (x_{0,v})_{v\in\cal V}\\x_1 = (x_{1,v})_{v\in\cal V}\\z_0 = (z_{0,v})_{v\in\cal V}\\z_1 = (z_{1,v})_{v\in\cal V}\\z = z_1 - z_0\\w = (w_v)_{v\in\cal V}\\c=(1)_{v\in\cal V}$$

Your system of equations is $$x_0 + x_1 = w \tag{1}$$ $$x_0 \cdot c = q_0\tag {2a}$$ $$x_1 \cdot c = q_1\tag {2b}$$ $$x_0 \cdot c + x_1 \cdot c = 1\tag 5$$ with constraints $$x_1 \cdot z \ge 0\tag 3$$ $$x_0 \cdot z \le 0\tag 4$$ $$0 \le x_0, 0 \le x_1\tag 6$$

Where $(6)$ is meant to hold coordinate-wise. The upper bound of $1$ on the coordinates of $x_0,x_1$ follows from $(6)$ and $(5)$, and thus does not need to be enforced separately. But since we also know that $q_0 + q_1 = 1$, equation $(5)$ follows from equations $(2)$, and thus can also be dropped from the list.

If we simplify the notation by letting $x = x_0$, and substitute $w - x$ for $x_1$, we can reduce the problem further: $$ x\cdot c = q_0\\x\cdot c = w\cdot c - q_1\\ x\cdot z \le w \cdot z \\x\cdot z \le 0\\0 \le x, 0 \le w - x$$

But we also know that $w\cdot c = 1 = q_0 + q_1$, so the two equations are the same. we can reduce it further to just $$x \cdot c = q_0\\x\cdot z \le \min\{0,w\cdot z\}\\0\le x\le w$$

But when $0 < z$ and $q_0 > 0$, this is impossible.