All possible A of Ax=b with constraints on A

Question

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.

Answer 1

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).

Answer 2

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}}}  *)