# Finding integer solutions to a system of linear equations

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.

## 2 Answers

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.

• @holistic: Sure, but I think you can find all the answers in my answer. For the case where $n_1=31,n_2=23$, the only solutions are $(31-k,k,k,23-k,54-4k)$ where $k$ is an integer such that $0\le k\le 13$. And the smallest value of $x$ is $2$ where $a_1=18,a_2=13,b_1=13,b_2=10$ as you wrote. I'll explain with more details if you can show which part of my answer is difficult to understand. – mathlove Oct 2 '16 at 4:40
• @holistic: In short, the only solutions are $(a_1,a_2,b_1,b_2,x)=(n_1-k,k,k,n_2-k,n_1+n_2-4k)$ where $k$ is an integer such that $0\le k\le \min\{n_1,n_2,\lfloor (n_1+n_2)/4\rfloor \}$. And the smallest value of $x$ is $n_1+n_2-4\min\{n_1,n_2,\lfloor (n_1+n_2)/4\rfloor\}$. You can plug the values of $n_1,n_2$ into these. – mathlove Oct 2 '16 at 8:13
• @holistic: By the way, $\lfloor x\rfloor$ represents the largest integer less than or equal to $x$. So, for example, for $n_1=31,n_2=23$, we have $\lfloor (n_1+n_2)/4\rfloor=\lfloor 13.5\rfloor=13$. I hope this helps. – mathlove Oct 2 '16 at 8:22
• @holistic: OK. For 5., since $x=0$ with $n_2=n_1$, we get $x=n_1+n_2-4k=n_1+n_1-4k=0$, i.e. $k=n_1/2$. So, $a_1=n_1-k=n_1/2,a_2=b_1=k=n_1/2,b_2=n_2-k=n_1-k=n_1/2$. I hope this helps. – mathlove Oct 2 '16 at 11:15
• Totally helped!! Thanks, could learn a lot from the way you solved this :). – holistic Oct 2 '16 at 11:38

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

• Thank you! But it seems to me this solution is not with respect to the positive integers. Since a1,a2,b1,b2,n1,n2 are real quantities (amount of people), I'm only interested in those solutions. I researched a bit more into this and a possible approach may be based on the smith normal form, but I couldn't solve it yet. – holistic Sep 30 '16 at 10:03
• @holistic Ah, that's much more complicated: you are having a multiple representation problem [re. e.g. to this work](math.sfsu.edu/beck/papers/frobeasy.slides.pdf), and I do not think you can find an easy way through. In any case it will be interesting if you post the way you found . – G Cab Sep 30 '16 at 11:08
• Yes, it seems pretty difficult. Thanks for the link, I will take a look at it. I found the following documents, which may also be helpful (to anyone who is reading this post and trying to solve it ;)): 1. people.hofstra.edu/raymond_n_greenwell/matrixarticle.pdf 2. math.udel.edu/~lazebnik/papers/dioph2.pdf – holistic Sep 30 '16 at 11:26
• @holistic, the works you indicated are very interesting, thanks indeed. In any case that is a very good step, but to pass from knowing the solutions in $Z$ to those in $N_0$, for $4$ simultaneous equations is a hard step. – G Cab Sep 30 '16 at 15:48
• @holistic, glad to help, example added. Good work. – G Cab Oct 3 '16 at 15:45