5
$\begingroup$

I have a linear problem that I want to solve but the method is quite different from normal, the problem is still Ax=b. However, in this instant I have A being unknown, apart from the fact that each entry in A can only be zero or 1. Further I have x being known and fixed, the same holds for b.

My question, is it a easy method for getting mathematica to spit out all possible A such that Ax=b given conditions on A.

I tried doing a number of for loops etc, however, I have completely given up after number of hours and the expectation that my effort is incorrect.

$\endgroup$
2
  • $\begingroup$ You should be able to use Tuples[] + Partition[] (after perhaps filtering out nonsingular candidates). $\endgroup$ – J. M.'s ennui Mar 5 '19 at 12:13
  • $\begingroup$ Please post a concrete example. Also note this is essentially the same as this recent MSE question $\endgroup$ – Daniel Lichtblau Mar 5 '19 at 16:13
6
$\begingroup$

Here's a way to code up your problem with Solve automatically:

x = {1, 2, 3};
b = Reverse[x];
sol[x_List, b_List] /; Length[x] === Length[b] := Module[{mat, vars},
   mat = Array[\[FormalM], Length[x]*{1, 1}]; (* construct a matrix of variables*)
   vars = Flatten[mat];
   mat /. 
    Solve[And @@ Thread[mat.x == b] (* Construct the equations *) 
      && vars ∈ Integers && And @@ Thread[0 <= vars <= 1] (* constraints *),
     vars
    ]
   ];
matrixSolutions = sol[x, b]

{{{0, 0, 1}, {0, 1, 0}, {1, 0, 0}}, {{1, 1, 0}, {0, 1, 0}, {1, 0, 0}}}

As you can see, 2 solutions were found. Check that the residuals of the solutions are zero vectors:

#.x - b & /@ matrixSolutions

{{0, 0, 0}, {0, 0, 0}}

It works, but I don't know how scalable this approach is. Instead of Solve, you can also use NSolve and/or FindInstance (you can just replace Solve with any of those two functions in the code above).

$\endgroup$
1
$\begingroup$

Pretty much the same questions as

FrobeniusSolve with solutions only being 0 or 1 being acceptable

Using @Sjoerd's problem

x = {1, 2, 3};
b = Reverse[x];

Can write solution as

res = Tuples@(Select[FrobeniusSolve[x, #], Max@# <= 1 &] & /@ b)

(* {{{0, 0, 1}, {0, 1, 0}, {1, 0, 0}}, 
   {{1, 1, 0}, {0, 1, 0}, {1, 0, 0}}}  *)
$\endgroup$

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.