4
$\begingroup$

Given two vectors $u=(x_1,\ldots,x_n,a_1,\ldots,a_s) \in \{-1,1\}^{n+s}$ and $v=(x_1,\ldots,x_n) \in \{-1,1\}^n$ and a bunch of fixed vectors $c_1,\ldots,c_k \in \{-1,1\}^{n+s}$ and $b_1,\ldots,b_k \in \{-1,1\}^{n}$ and I want to find an instance when all the following (inner product) equations are satisfied: $$c_i \cdot u + 1 = b_i \cdot v,\quad i=1,\ldots,s$$

In general $n$ will be large. So I want to specify the condition that I am only interested in solutions in, say, $\{-1,1\}^{n+s}$ by using the membership of $u$ in Tuples[{-1,1},n+s] instead of putting numerous componentwise integer inequalities into play after specifying Integers as a condition. I will want to do this for varying $n$ and $s.$

Edit: A small example, done componentwise is below. I want to abstract out the equations by using inner products since they will get messy for larger cases. Here $n=s=1$ and I ask for 4 instances. ff allows me to specify +1 and -1 by using ff[x,1].

ff[x_, a_] := (x^2 == a); 
FindInstance[
      x1*xn + 1 == a1*(x1 + xn) &&  ff[x1, 1] && ff[xn, 1] && 
      ff[a1, 1], {x1, xn, a1}, Integers, 4]
$\endgroup$
  • $\begingroup$ It would be useful to have a small example, in Mathematica input form. $\endgroup$ – Daniel Lichtblau Dec 16 '15 at 23:39
  • $\begingroup$ Where is your b1? $\endgroup$ – Dr. belisarius Dec 17 '15 at 1:55
  • $\begingroup$ @belisariushassettled:For this case, it can be taken to be 1. $\endgroup$ – kodlu Dec 17 '15 at 2:15
  • $\begingroup$ This example is nonlinear (it has products of variable a1 by variables x1 and xn). The description c_i.u+1==b_i.v is of a linear problem. $\endgroup$ – Daniel Lichtblau Dec 17 '15 at 17:21
4
$\begingroup$

Perhaps

e = {-1, 1};
SeedRandom[42];
n = 3;
s = 3;
k = 2;
aa = Array[a, s];
vv = Array[x, n];
uu = Join[vv, aa];
c = RandomChoice[e, {k, n + s}];
b = RandomChoice[e, {k, n}];

FindInstance[And @@ MapThread[#1.uu + 1 == #2.vv &, {c, b}] && 
            (And @@    Thread[Abs[uu] == 1]), uu, Integers]

(*{{x[1] -> 1, x[2] -> 1, x[3] -> -1, a[1] -> 1, a[2] -> 1, a[3] -> 1}} *)
$\endgroup$
  • $\begingroup$ Thank you, your MapThread and Thread commands show me how to do this. $\endgroup$ – kodlu Dec 17 '15 at 5:00
  • $\begingroup$ No, no, no. This is not going to scale. $\endgroup$ – Daniel Lichtblau Dec 17 '15 at 17:26
  • $\begingroup$ @DanielLichtblau I know. But n will be large doesn't set a scale either $\endgroup$ – Dr. belisarius Dec 17 '15 at 17:33
  • $\begingroup$ What I meant by "to scale" was not "to the scale of the original question" but rather "to scale well on larger problems". I basically cribbed all your work, and made a minor tweak at the end, to get a method that will scale better. $\endgroup$ – Daniel Lichtblau Dec 17 '15 at 17:41
2
$\begingroup$

Here is a slight adjustment to the method proposed by @Dr.belisarius. I'll show with a larger set of variables though.

e = {-1, 1};
SeedRandom[42];
n = 11;
s = 11;
k = 2;
aa = Array[a, s];
vv = Array[x, n];
uu = Join[vv, aa];
c = RandomChoice[e, {k, n + s}];
b = RandomChoice[e, {k, n}];

Now just adjust so these are 0-1 variables, multiply each by 2 and subtract 1 to get the effect of being +-1.

soln = 
 FindInstance[
  And @@ MapThread[#1.(2*uu - 1) + 1 == #2.(2*vv - 1) &, {c, 
      b}] && (And @@ Thread[0 <= uu <= 1]), uu, Integers]

(* Out[285]= {{x[1] -> 1, x[2] -> 0, x[3] -> 0, x[4] -> 0, x[5] -> 1, 
  x[6] -> 0, x[7] -> 0, x[8] -> 1, x[9] -> 0, x[10] -> 1, x[11] -> 1, 
  a[1] -> 0, a[2] -> 0, a[3] -> 1, a[4] -> 0, a[5] -> 1, a[6] -> 1, 
  a[7] -> 0, a[8] -> 0, a[9] -> 0, a[10] -> 1, a[11] -> 0}} *)

Now undo the transformation to get the results in the desired set.

2*uu - 1 /. soln

(* Out[263]= {{1, -1, -1, -1, 1, -1, -1, 1, -1, 1, 1, -1, -1, 1, -1, 1, 
  1, -1, -1, -1, 1, -1}} *)
$\endgroup$
  • $\begingroup$ Veggy nice ... :) $\endgroup$ – Dr. belisarius Dec 17 '15 at 17:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.