Solve a system of linear equations subject to Boolean constraints Say I have an equation on the form
$$c_1^{\top} = c_2^{\top} X$$
where $c_1, c_2 \in \mathbb N^n$ and $X \in \{0,1\}^{n \times n}$ is a square matrix. How do I solve for $X$?
 A: (let's call $c_1 = a$ and $c_2 = b$ for the rest of the question)
Let's say $x \in \mathbb{R}^{n\times x}$ (with $x_{ij}\in \{0,1\}$) and $a,b\in\mathbb{R}^n$. This makes:
$$ \begin{bmatrix} a_1 \\ a_2 \\ \vdots \\ a_n \end{bmatrix}^T = \begin{bmatrix} b_1 \\ b_2 \\ \vdots \\ b_n \end{bmatrix}^T \begin{bmatrix} x_{11} & x_{12} & \cdots & x_{1n} \\
x_{21} & x_{22} & \cdots & x_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
x_{n1} & x_{n2} & \cdots & x_{nn} \end{bmatrix} $$
Thus
$$ \begin{array}{rcl}
a_1 & = & b_1 x_{11} + b_2 x_{21} + \cdots + b_n x_{n1} \\
a_2 & = & b_1 x_{12} + b_2 x_{22} + \cdots + b_n x_{n2} \\
&\vdots& \\
a_n & = & b_1 x_{1n} + b_2 x_{2n} + \cdots + b_n x_{nn}
\end{array}$$
It is easy to show that no unique sollution exists. Let's give a counter example:
take $a = \begin{bmatrix}4 & 1 & 3\end{bmatrix}$ and $b = \begin{bmatrix} 1 & 2 & 1 \end{bmatrix}$. This gives us:
$$ \begin{array}{rcl}
4 & = & 1 x_{11} + 2 x_{21} + 1 x_{31} \\
1 & = & 1 x_{12} + 2 x_{22} + 1 x_{32} \\
3 & = & 1 x_{13} + 2 x_{23} + 1 x_{33}
\end{array}$$
Do you see that different solutions are:
$$ \begin{bmatrix} 4 & 1 & 3 \end{bmatrix} = \begin{bmatrix} 1 & 2 & 1 \end{bmatrix}  
\begin{bmatrix} 1 & 1 & 0 \\
1 & 0 & 1 \\
1 & 0 & 1 \end{bmatrix} $$
As well as:
$$ \begin{bmatrix} 4 & 1 & 3 \end{bmatrix} = \begin{bmatrix} 1 & 2 & 1 \end{bmatrix}  
\begin{bmatrix} 1 & 0 & 1 \\
1 & 0 & 1 \\
1 & 1 & 0 \end{bmatrix} $$
A: We have the following matrix equation in $\mathrm X \in \{0,1\}^{n \times n}$
$$\rm a^{\top} X = b^{\top}$$
where $\mathrm a, \mathrm b \in \mathbb N^n$ are given. If $\rm a \neq 0_n$, and if there were no Boolean constraints, then one solution would be the following rank-$1$ matrix
$$\rm X = \frac{\mathrm a \mathrm b^{\top}}{\| \mathrm a \|_2^2}$$
Given the Boolean constraints, the following binary integer program (IP) produces one solution
$$\begin{array}{ll} \text{minimize} & \langle \mathrm O_n, \mathrm X \rangle\\ \text{subject to} & \mathrm a^{\top} \mathrm X = \mathrm b^{\top}\\ & \mathrm O_n \leq \mathrm X \leq \mathrm 1_n \mathrm 1_n^{\top}\\ & \mathrm X \in \mathbb Z^{n \times n}\end{array}$$
If this integer program is infeasible, then the original matrix equation has no solution over $\{0,1\}^{n \times n}$.
