# Thread: Linear system with binary variables

1. ## Linear system with binary variables

A linear system is given, for instance:
$\displaystyle \left\{ \begin{array}{l}2x+y+z=3 \\ x+y=1 \end{array}$.
And there're additional restrictions: $\displaystyle x,y,z\in \{0,1\}$. It is just an example, systems have hundreds equations and twice more variables. This system has an only solution though a number of equations is less than number of variables. Note the variables are binary but it is not suitable to solve the system by using modular arithmetic because in this case it has a few solutions. I see a few ways: 1) to use Gauss' method, then search for rest of solutions exhaustively; 2) to introduce new equations such as $\displaystyle x^2=x$. The former is evidently bad. The latter is awkward and I'm not sure it will actually work. What is a better approach for this problem?

2. Your question seems unnatural. To answer it as stated, just solve the system as if $\displaystyle x, y, z\in \mathbb{R}$. Then choose the free variable (if there is one)to be in $\displaystyle \{ 0, 1\}$ and see if the others lie in this set as well.