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$
4
  • $\begingroup$ It would be useful to have a small example, in Mathematica input form. $\endgroup$ Dec 16, 2015 at 23:39
  • $\begingroup$ Where is your b1? $\endgroup$ Dec 17, 2015 at 1:55
  • $\begingroup$ @belisariushassettled:For this case, it can be taken to be 1. $\endgroup$
    – kodlu
    Dec 17, 2015 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$ Dec 17, 2015 at 17:21

2 Answers 2

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$
4
  • $\begingroup$ Thank you, your MapThread and Thread commands show me how to do this. $\endgroup$
    – kodlu
    Dec 17, 2015 at 5:00
  • $\begingroup$ No, no, no. This is not going to scale. $\endgroup$ Dec 17, 2015 at 17:26
  • $\begingroup$ @DanielLichtblau I know. But n will be large doesn't set a scale either $\endgroup$ Dec 17, 2015 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$ Dec 17, 2015 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$
1
  • $\begingroup$ Veggy nice ... :) $\endgroup$ Dec 17, 2015 at 17:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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