Suppose I have the two matrix equations: $$A_1 M = C_1$$ $$A_2 M = C_2$$ where $A_1, A_2, C_1,C_2$ are given. I want to know if there is a matrix $M$ with entries in $\{0,1\}$ that satisfies the system. What are good algorithms I can use to solve this efficiently?
A related question is what happens when $A_2 M = C_2$ is replaced with: $$A_2M^2 + A_3M = C_2$$ How can I find solutions to these systems efficiently. I've heard Grobner bases can be used for the second problem, but I'm not sure about the technique. Can someone point out references?
The first problem can be solved via integer linear programming. The second one can be solved via quadratically constrained integer programming or linearized as follows. Replace $(M^2)_{i,j}=\sum_k M_{i,k} M_{k,j}$ with $\sum_k N_{i,k,j}$, with additional linear constraints \begin{align} N_{i,k,j} &\le M_{i,j} \\ N_{i,k,j} &\le M_{k,j} \\ N_{i,k,j} &\ge M_{i,j} + M_{k,j} - 1 \\ N_{i,k,j} &\ge 0 \end{align}