# Show that a linear system has at least one solution

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.

• 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? Jul 21, 2022 at 17:25
• Thanks. I am looking for an expert advice. I'm not very skilled in linear algebra.
– TEX
Jul 21, 2022 at 20:55

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$$
• 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}$.
• @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}$ Jul 25, 2022 at 9:58