Finding integer solutions to a system of linear equations

Question

Given the following system of linear equations:

$$ a_1−a_2−b_1+b_2=x $$ $$ a_1+a_2=n_1 $$ $$ b_1+b_2=n_2 $$ $$ a_1+b_1=n_1 $$ $$ a_2+b_2=n_2 $$

For a given positive non-zero integer value of $n_1$ and $n_2$ , e.g. $n_1=33$,$n_2=27$, find:

1. if the system has any solution in the positive natural numbers including 0

2. if 1. is true, find the values of $x$,$a_1$,$a_2$,$b_1$,$b_2$, for which the system has a solution

3. find the smallest value of $x$ -> $min(x)$ , for which the system has a solution

For example for: $n_1=31$,$n_2=23$ one solution is $x=2=min(x)$,$a_1=18$,$a_2=13$,$b_1=13$,$b_2=10$.

4. is it possible to find a formula that relates $n_1$ and $n_2$ to $x$, i.e. $min(x)=f(n_1,n_2)$

By playing around a bit with different values for $n_1$ and $n_2$, I found that if $n_1$ and $n_2$ are both equal and even numbers, there exist a solution where $x=0$. But I'm not sure if this is true for all even values and combinations of $n_1$ and $n_2$ and I'm not sure how to formally prove this. So

5. prove that for even and equal numbers of $n_1$ and $n_2$, there always exist a solution where $x=0$

I'm no mathematician and my linear algebra is a bit rusty, so I was hoping for some tips how to approach this problem.

Answer 1

We have $$ a_1−a_2−b_1+b_2=x $$ $$ a_1+a_2=n_1 $$ $$ b_1+b_2=n_2 $$ $$ a_1+b_1=n_1 $$ $$ a_2+b_2=n_2 $$

Noting that $$a_2=n_1-a_1=b_1$$ and letting $a_2=k$, we see that we have $$(a_1,a_2,b_1,b_2,x)=(n_1-k,k,k,n_2-k,n_1+n_2-4k)\tag1$$ for some $k$.

For 1., 2. :

The system has a solution in non-negative integers if and only if we have $$n_1-k\ge 0\quad\text{and}\quad k\ge 0\quad\text{and}\quad n_2-k\ge 0\quad\text{and}\quad n_1+n_2-4k\ge 0\quad\text{where}\quad k\in\mathbb Z,$$ i.e. $$0\le k\le \min\left\{n_1,n_2,\left\lfloor\frac{n_1+n_2}{4}\right\rfloor\right\}\quad\text{where}\quad k\in\mathbb Z$$

For 3., 4. :

From 1., 2., $$x_{\text{min}}=n_1+n_2-4\min\left\{n_1,n_2,\left\lfloor\frac{n_1+n_2}{4}\right\rfloor\right\}$$

For 5. :

Since $k=n_1/2$, from $(1)$, $$(a_1,a_2,b_1,b_2,x)=\left(\frac{n_1}{2},\frac{n_1}{2},\frac{n_1}{2},\frac{n_1}{2},0\right)$$ is a solution.

Answer 2

So you are given the system $$ \left( {\begin{array}{*{20}c} 1 & { - 1} & { - 1} & 1 \\ 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ \end{array} } \right)\left( {\begin{array}{*{20}c} {a_{\,1} } \\ {a_{\,2} } \\ {b_{\,1} } \\ {b_{\,2} } \\ \end{array} } \right) = \left( {\begin{array}{*{20}c} x \\ {n_{\,1} } \\ {n_{\,2} } \\ {n_{\,1} } \\ {n_{\,2} } \\ \end{array} } \right) $$ Put 2nd row = 2nd row -4th row, and 3nd row = 3nd row -5th row, you get $$ \left( {\begin{array}{*{20}c} 1 & { - 1} & { - 1} & 1 \\ 0 & 1 & { - 1} & 0 \\ 0 & { - 1} & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ \end{array} } \right)\left( {\begin{array}{*{20}c} {a_{\,1} } \\ {a_{\,2} } \\ {b_{\,1} } \\ {b_{\,2} } \\ \end{array} } \right) = \left( {\begin{array}{*{20}c} x \\ 0 \\ 0 \\ {n_{\,1} } \\ {n_{\,2} } \\ \end{array} } \right) $$ Clearly 2nd and 3rd equation are the same, so one is reduntant and can be deleted. The determinant of the resulting matrix is $4$, so the system can be solved, giving $$ \left( {\begin{array}{*{20}c} {a_{\,1} } \\ {a_{\,2} } \\ {b_{\,1} } \\ {b_{\,2} } \\ \end{array} } \right) = \frac{1} {4}\left( {\begin{array}{*{20}c} 1 & 2 & 3 & { - 1} \\ { - 1} & 2 & 1 & 1 \\ { - 1} & { - 2} & 1 & 1 \\ 1 & { - 2} & { - 1} & 3 \\ \end{array} } \right)\left( {\begin{array}{*{20}c} x \\ 0 \\ {n_{\,1} } \\ {n_{\,2} } \\ \end{array} } \right) $$ And from here I suppose you can continue.

----- Addendum -----
Note that, apart from the general approach discussed in the comments, in your particular case some simplifications may be done.
The last equation above can in fact be reduced to
$a_{\,2} = b_{\,1}$ , and $$ \begin{gathered} \left( {\begin{array}{*{20}c} {a_{\,1} } \\ {b_{\,1} } \\ {b_{\,2} } \\ \end{array} } \right) = \frac{1} {4}\left( {\begin{array}{*{20}c} 1 & 3 & { - 1} \\ { - 1} & 1 & 1 \\ 1 & { - 1} & 3 \\ \end{array} } \right)\left( {\begin{array}{*{20}c} x \\ {n_{\,1} } \\ {n_{\,2} } \\ \end{array} } \right)\quad \Leftrightarrow \quad \left( {\begin{array}{*{20}c} x \\ {n_{\,1} } \\ {n_{\,2} } \\ \end{array} } \right) = \left( {\begin{array}{*{20}c} 1 & { - 2} & 1 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \\ \end{array} } \right)\left( {\begin{array}{*{20}c} {a_{\,1} } \\ {b_{\,1} } \\ {b_{\,2} } \\ \end{array} } \right) \hfill \\ \end{gathered} $$ From here, imposing that all the parameters shall be non-negative integers, we obtain $$ \begin{gathered} \left\{ \begin{gathered} 0 \leqslant b_{\,1} \leqslant b_{\,1} + a_{\,1} = n_{\,1} \hfill \\ 0 \leqslant b_{\,1} \leqslant b_{\,1} + b_{\,2} = n_{\,2} \hfill \\ 0 \leqslant b_{\,1} = \frac{1} {4}\left( {n_{\,1} + n_{\,2} - x} \right) = \text{integer} \hfill \\ \end{gathered} \right.\quad \Rightarrow \quad \left\{ \begin{gathered} 0 \leqslant y = n_{\,1} + n_{\,2} - x \hfill \\ 0 \equiv y\quad \left( {\bmod 4} \right) \hfill \\ y \leqslant 4n_{\,1} \hfill \\ y \leqslant 4n_{\,2} \hfill \\ \end{gathered} \right.\quad \Rightarrow \hfill \\ \Rightarrow \quad \left\{ \begin{gathered} 0 \leqslant k \hfill \\ k \leqslant n_{\,1} \hfill \\ k \leqslant n_{\,2} \hfill \\ 4k \leqslant n_{\,1} + n_{\,2} \hfill \\ 4k + x = n_{\,1} + n_{\,2} \hfill \\ \end{gathered} \right.\quad \Rightarrow \quad \left\{ \begin{gathered} 0 \leqslant k \hfill \\ 0 \leqslant \left( {n_{\,1} - k} \right) \hfill \\ 0 \leqslant \left( {n_{\,2} - k} \right) \hfill \\ 2k \leqslant \left( {n_{\,1} - k} \right) + \left( {n_{\,2} - k} \right) \hfill \\ 2k + x = \left( {n_{\,1} - k} \right) + \left( {n_{\,2} - k} \right) \hfill \\ \end{gathered} \right. \hfill \\ \end{gathered} $$ which gives you the requested conditions on the parameters $x,n_1,n_2$.
Finally we can collect the whole and put it under, for instance, this form $$ \left( {\begin{array}{*{20}c} x \\ {n_{\,1} } \\ {n_{\,2} } \\ {a_{\,2} } \\ \end{array} } \right) = \left( {\begin{array}{*{20}c} { - 2} & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \\ 1 & 0 & 0 \\ \end{array} } \right)\;\left( {\begin{array}{*{20}c} {b_{\,1} } \\ {a_{\,1} } \\ {b_{\,2} } \\ \end{array} } \right)\quad \left| \begin{gathered} \;0 \leqslant a_{\,1} ,b_{\,2} \hfill \\ \;0 \leqslant b_{\,1} \leqslant \left\lfloor {\frac{{a_{\,1} + b_{\,2} }} {2}} \right\rfloor \hfill \\ \end{gathered} \right. $$ with $a_1,b_2$ as free non-negative parameters, and $b_1$ also free non-negative but upper limited.

----- example -----
For example, with $n_1=31,n_2=23$ we get $$ \begin{gathered} \left\{ \begin{gathered} 0 \leqslant k \hfill \\ k \leqslant n_{\,1} \hfill \\ k \leqslant n_{\,2} \hfill \\ 4k \leqslant n_{\,1} + n_{\,2} \hfill \\ 4k + x = n_{\,1} + n_{\,2} \hfill \\ \end{gathered} \right.\quad \mathop \Rightarrow \limits_{\begin{array}{*{20}c} {n_{\,1} = 31} \\ {n_{\,2} = 23} \\ \end{array} } \quad \left\{ \begin{gathered} \left. \begin{gathered} 0 \leqslant k \hfill \\ k \leqslant 31 \hfill \\ k \leqslant 23 \hfill \\ 4k \leqslant 54 \hfill \\ \end{gathered} \right\}0 \leqslant k \leqslant 13 \hfill \\ x = 54 - 4k \hfill \\ \end{gathered} \right.\quad \Rightarrow \hfill \\ \Rightarrow \quad \left( \begin{gathered} a_{\,1} \hfill \\ a_{\,2} = b_{\,1} \hfill \\ b_{\,2} \hfill \\ \end{gathered} \right) = \frac{1} {4}\left( {\begin{array}{*{20}c} 1 & 3 & { - 1} \\ { - 1} & 1 & 1 \\ 1 & { - 1} & 3 \\ \end{array} } \right)\left( {\begin{array}{*{20}c} x \\ {n_{\,1} } \\ {n_{\,2} } \\ \end{array} } \right) = \hfill \\ = \frac{1} {4}\left( {\begin{array}{*{20}c} 1 & 3 & { - 1} \\ { - 1} & 1 & 1 \\ 1 & { - 1} & 3 \\ \end{array} } \right)\left( {\begin{array}{*{20}c} {54 - 4k} \\ {31} \\ {23} \\ \end{array} } \right)\quad \left| {\;0 \leqslant k \leqslant 13} \right. \hfill \\ \end{gathered} $$