Positive solutions to a system of linear Diophantine equations

Question

A system of equations is

\begin{align} 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 \end{align}

where $b_1$, $\ldots$, $b_5$ and $x_1$, $\ldots$, $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.

Answer 1

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$.