2
$\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 below. The vector of unknowns is $(x_{y,v}: y\in \mathcal{Y}, v\in \mathcal{V})$. The vectors $(w_v: v\in \mathcal{V})$ and $(q_y: y\in \mathcal{Y})$ and the sets $\mathcal{V},\mathcal{Y}$ are known. $$ (*) \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} *v \geq 0,\\ &(4) \quad\sum_{v\in \mathcal{V}} x_{0,v} *v \leq 0,\\ &--------------------\\ &(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 $(*)$ has at least one solution.

Note: The claim seems to me correct. For example, let $\mathcal{V}\equiv \{-1,1\}$. The system $(*)$ reduces to $$ \begin{cases} (a)\quad x_{0,1}+x_{1,1}=w_1,\\ (b)\quad x_{0,-1}+x_{1,-1}=1-w_1,\\ (c)\quad x_{0,1}+x_{0,-1}=q_0,\\ (d)\quad x_{1,1}+x_{1,-1}=1-q_0,\\ (e)\quad x_{1,1}-x_{1,-1}\geq 0,\\ (f)\quad x_{0,1}-x_{0,-1}\leq 0, \end{cases} $$ which I think has many solutions. I would like to show the claim in a general way.

$\endgroup$
2
  • $\begingroup$ from what I see, (7) and (9) are redundant because (1) (2) and (5) together give them. Everything else I would just characterize as row-sums and column-sums together with dot product are known. As far as showing a solution, I think a bounded sub-space argument could be made, is that what you might be looiking for? $\endgroup$
    – adam W
    Jul 21, 2022 at 17:25
  • $\begingroup$ Thanks. I am looking for an expert advice. I'm not very skilled in linear algebra. $\endgroup$
    – TEX
    Jul 21, 2022 at 20:55

1 Answer 1

Reset to default
1
+50
$\begingroup$

Let $\mathcal{V}\equiv \{-1,1\}$ and $q_1 = 1/10 = w_{-1}$, $q_0=9/10 = w_{1}$. In this case the problem has no solution since (4) cannot hold: $$ x_{0,1} - x_{0,-1} = q_0 - 2 x_{0,-1} \ge q_0 - 2 w_{-1} = 7/10 >0 $$

$\endgroup$
2
  • $\begingroup$ Thanks. Looking at my example, the first step comes from (c): $x_{0,1}+x_{0,-1}-2 x_{0,-1}=q_0-2 x_{0,-1}$ which becomes $x_{0,1}-x_{0,-1}=q_0-2 x_{0,-1}$. I don't understand where the next inequality comes from, could you add more details? From (b), $x_{0,-1}=w_{-1}-x_{1,-1}$. Hence, $q_0-2 x_{0,-1}=q_0-2 w_{-1}-2 x_{1,-1}$ and, so, $q_0-2 x_{0,-1}\leq q_0-2 w_{-1}$. $\endgroup$
    – TEX
    Jul 25, 2022 at 8:44
  • 1
    $\begingroup$ @TEX you have a wrong sign in your derivation. $x_{0,-1}=w_{-1}-x_{1,-1}\implies q_0-2 x_{0,-1}=q_0-2 w_{-1} \color{red}{+} 2 x_{1,-1}$ $\endgroup$
    – Exodd
    Jul 25, 2022 at 9:58

You must log in to answer this question.

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