Results 1 to 2 of 2

Thread: Linear system with binary variables

  1. #1
    Apr 2011

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    May 2010
    Los Angeles, California
    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.
    Last edited by ojones; Apr 19th 2011 at 01:29 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: Sep 16th 2010, 02:25 AM
  2. Replies: 2
    Last Post: Apr 20th 2010, 03:26 PM
  3. Replies: 4
    Last Post: Sep 24th 2009, 01:10 AM
  4. Linear equality system with 5 variables
    Posted in the Algebra Forum
    Replies: 4
    Last Post: Mar 24th 2009, 04:56 PM
  5. What is Base 2 (binary system)?
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Apr 14th 2008, 07:10 PM

Search Tags

/mathhelpforum @mathhelpforum