Is there any way to solve a system of linear equations with both the coefficients and variables coming from {0,1} but where addition is considered over the non-negative integers, not F2?

Question

Davion Fletcher · Accepted Answer

The unknowns   (      x    i        )          i      ≤      n       are in   {  0  ,  1  }; then the number of solutions is finite...If I understand correctly your question, then one has a system   A  x  =  b where   A  =  [      a          i      ,      j        ]  ∈      M          p      ,      n        (  {  0  ,  1  }  ),   b  =  [      b    i    ] with       b    i    ∈  {  0  ,  1  } are given,   x is as   b but is unknown.We solve the system in       Z        /    2      Z   (with Gauss) ; we assume that there is more than one solution. Then the result is in the form : for every   i  ≤  k,       x    i    =      f    i    (      x          k      +      1        ,  ⋯  ,      x    n    ) where       f    i   is an affine function and       x          k      +      1        ,  ⋯  ,      x    n   are arbitrary, that is, we obtain       2          n      −      k       candidates. If       2          n      −      k       is not a too great number, then we can conclude by brute force. Else we use the following fact: for every   i  ≤  p,   c  a  r  d  i  n  a  l  i  t  y  (  {  j  ;      a          i      ,      j            x    j    ≠  0  }  ) is   0 or   1.

Is there any way to solve a system of linear equations with both the coefficients and variables coming from {0,1} but where addition is considered over the non-negative integers, not F2?

Answered question

Answer & Explanation

New Questions in Algebra I