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

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.

$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.
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}$$
• @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