Results 1 to 2 of 2

Math Help - Linear system with binary variables

  1. #1
    Newbie
    Joined
    Apr 2011
    Posts
    1

    Linear system with binary variables

    A linear system is given, for instance:
     \left\{ \begin{array}{l}2x+y+z=3 \\ x+y=1 \end{array} .
    And there're additional restrictions:  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 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
    Joined
    May 2010
    From
    Los Angeles, California
    Posts
    274
    Thanks
    1
    Your question seems unnatural. To answer it as stated, just solve the system as if x, y, z\in \mathbb{R}. Then choose the free variable (if there is one)to be in \{ 0, 1\} and see if the others lie in this set as well.
    Last edited by ojones; April 19th 2011 at 02:29 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

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

Search Tags


/mathhelpforum @mathhelpforum