0
$\begingroup$

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?

$\endgroup$
1
  • 2
    $\begingroup$ Note: Your system of equations consists just of (1), (2), (5). In addition you have (3), (4), (6) as constraints on that system (note that they are not "equations"). (7), (8), (9) (10) are just some facts that the known data happens to satisfy. They may or may not be useful in showing it is possible to not have solutions, but they are not part of the system. I strongly suggest you divide matters up into the equations, the constraints, and the other information, instead of hiding an additional equation and constrains in with the other data. $\endgroup$ Commented Sep 22, 2022 at 15:23

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks for your insightful answer, it was very helpful. Now, I'd like to generalise the claim to $\mathcal{V}$ not finite. I've posted my question here math.stackexchange.com/questions/4539423/… It involves a bit of probability notions, thanks in advance if you can help. $\endgroup$
    – Star
    Commented Sep 26, 2022 at 13:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .