How to solve simultaneous linear equations with only two possible values per variable?

Question

I am trying to solve a system of simultaneous linear equations whose unknowns have only two possible values. How do I approach this, or what area of mathematics do I employ inorder to arrive at the exact solution. e.g. \begin{align} a+b+c+d+f+g+h+i &= 12, \tag{1} \\ b+c+d &= 6, \tag{2} \\ f+g &= 2, \tag{3} \end{align} where possible values for $a,b,c,d,f,g,h,i$ can only be $2$ or $0$.

NB The example above is just an illustration of what I am trying to solve which is a nested Venn diagram problem with about $10$ equations of $14$ unknowns ($a,b,c,\dotsc,n$) whose values can only be $4$ or $6$.

Answer 1

You may consider it a problem of discrete structure or number theory.

You have $$a+b+c+d+f+g+h+i = 12$$

From

$$b+c+d = 6$$ and the assumption that your variables are only either $0$ or $2$ we get $$b=c=d=2$$

Thus $$a+f+g+h+i = 6$$

From

$$f+g = 2$$ we get $$a+h+i =4$$

That gives us different cases for $f$ and $g$ and $a,h,i$

Answer 2

Generally this would be considered an integer linear programming problem.

Unfortunately even finding out whether a system of this shape has any solution or not is NP-complete, so you should not hope to find a provably efficient algorithm. There are various heuristics, though; see the linked Wikipedia article.

(Of course if you only have $14$ variables, there are less than 17,000 combinations to check; with a bit of programming you can brute-force that faster than it would be to come up with something clever).

Answer 3

One possible algorithm is given by Groebner: it turns any set of polynomial equations into a set of equivalent equations as simple as possible given a priority order on the variables.

Pros:

• if the solution is unique, you will know it and you will know what it is.

• if there are no solutions, you will know it.

Cons:

• if there is more than one solution, the output will not necessarily be very helpful. It will just look like another set of equations, with very simple ones and very complicated ones.

In your case, if you want to use that, you need to add polynomials that encode the fact that each variable can be only $4$ or $6$. For instance, to say that $a\in\{4,6\}$ you use the polynomial $$(a-4)(a-6)$$ since this is $0$ exactly when $a$ lies in the desired set.

Answer 4

You have linear system $Ax = b$ and want to know if there is a solution such that all coordinates of $x$ are either $4$ or $6$. Instead of that, consider system $Ay = b/2$ where all coordinates of $y$ have to be either $2$ or $3$. If there exists a solution to that system, there must be a solution to the same system modulo $2$.

Thus, reduce the system modulo $2$ and solve it as a linear system over $\mathbb Z/2\mathbb Z$ (linear algebra applies!) This will give you a finite number of possible solutions to the original system - it is easy to reconstruct them since $2$ is even and $3$ is odd.

This will be very efficient in your case, since $10$ equations with $14$ unknowns means the solution space is $4$-dimensional. Over $\mathbb Z/2\mathbb Z$ it means $16$ solutions to check.