A system of equations is
$$x_1+x_2+x_3+x_4=b_1$$
$$x_1+x_5+x_6+x_7=b_2$$
$$x_2+x_5+x_7+x_8=b_3$$
$$x_3+x_6+x_8+x_{10}=b_4$$
$$x_4+x_7+x_9+x_{10}=b_5$$
$b_1,…,b_5$ and $x_1,…,x_{10}$ are positive integers or zero. How can I determine all possible solutions from this additional information. There are necessarily finite solutions as there are only finite positive integers for each x that are smaller than b. It is impossible to solve it by trying every possibility as the original system is way bigger (around 40 equations and 900 variables). I would appreciate every hint in the right direction.
Best Answer
There is a theory to solve systems of linear Diophantine equations over $\mathbb{Z}$, e.g., see here. Then one could select the nonneggative solutions.
In this particualr case, I find it helpful to first solve the system over the field of rational numbers. Then, by linear algebra, the system is equivalent to \begin{align*} x_1 & =\frac{b_1 + b_2 - b_3 - b_4 - b_5 + 2x_{10} + x_7 + 2x_8 + x_9}{2}, \\ x_2 & = \frac{b_1 - b_2 + b_3 - b_4 - b_5 + 2x_{10} + 2x_6 + x_7 + x_9}{2},\\ x_3 & = b_4 - x_{10} - x_6 - x_8, \\ x_4 & = b_5 - x_{10} - x_7 - x_9, \\ x_5 & = \frac{- b_1 + b_2 + b_3 + b_4 + b_5 - 2x_{10} - 2x_6 - 3x_7 - 2x_8 - x_9}{2}, \end{align*} where we can choose the variables on the LHS (namely $x_6,x_7,x_8,x_9,x_{10}$) as arbitrary rational numbers.
Now we can restrict the domain to nonnegative integers, and obtain the additional conditions on $x_6,\ldots ,x_{10}$: the expressions in the nominator for $x_1,x_2,x_5$ need to be even, and all expressions need to be nonnegative. There is still some work to do, however, but it seems easier to me than before. For example, if $b_4=b_5=0$, then necessarily $x_6=\ldots =x_{10}=0$.