1
$\begingroup$

Let $x_i,\ldots,x_n$ and $y_{i,j}$ where $1 \le i \le n$ and $1 \le j \le L$ be a set of variables in the following equations (and inequalities):

$\sum_{i=1}^n x_i y_{i,l} = c_l$ for $1 \le l \le L$

$\sum_{i=1}^n x_i = 1$

$\sum_{i=1}^n y_{i,l} = 1$ for $1 \le l \le L$

$x_i \ge 0, y_{i,l} \ge 0$ for all $1 \le i \le n$ and $1 \le l \le L$

where $c_l$ are non-negative constants.

Is there a solution to these equations if $L$ is large enough? Is the solution unique, and is there an analytic/algorithm way to find it?

Thanks!

(I had a problem finding the right category for this question. I wanted to put it as "algebra" or "equations" but neither exist? since the application is for something related to probability, I decided to use "probability".)

3 Answers 3

0

Consider the $x_i$ as forming an $n$-component row vector $x^T$, and $y_{ij}$ forming an $n \times L$ matrix $Y$. Let $e$ be the $n$-component vector of all 1's. For any $x^T$ with all $x_i \ge 0$ and $x^T e = 1$, the $j$'th column of $Y$ should be a vector $v \ge 0$ such that $x^T v = c_j$ and $e^T v = 1$. Note that the set of $x^T \ge 0$ with $x^T e = 1$ is the simplex with extreme points the unit vectors $u_i^T$ consisting of a single 1 and all other entries 0. The dot product of two members of the simplex can be anything in $[0,1]$. So to get any solution you need $0 \le c_j \le 1$ for all $j$. Moreover, given any such $c$ you get solutions for any $k$ with $x^T = u_k^T$ and $y_{kj} = c_j$ for all $j$. If some $c_j = 1$, $x^T$ must be one of the $u_k^T$. If all $ c_j < 1$, there are infinitely many possibilities for $x^T$.

0

In the case $n=1$ it is easy to construct unsolvable instances for any $L$. We get $x_1=1$ by necessity, and therefore $y_{1,l}=c_l$, but these $y$'s may not sum to $1$.

In general, however, you have $2L+1$ polynomial equations in $n(L+1)$ unknowns, so for $n\ge 2$ if there's a solution at all, it won't be unique (except possibly in degenerate cases).

0

Note that unless $0 \le c_l \le 1$ for every $1\le l\le L$ then there will be no solution as each $x_i\le 1$, so $x_iy_{i,l}\le y_{i,l}$ and so $\sum_i x_iy_{i,l}\le \sum_i y_{i,l}$. If $n\ge 2$ and all of the $c_l$ are in range it is easy to create a solution by letting $x_1=1$, all other $x_i=0$, and $y_{1,l}=c_l$ and the other $y_{i,l}$ chosen arbitrarily to satisfy the $\sum y_{i,l} = 1$ constraint. The solutions will obviously be non unique if $n\ge 3$. If $n=2$ we can create another solution by exchanging $i=1$ and $i=2$.