Solve a system of linear equations subject to Boolean constraints

Question

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$?

Answer 1

(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} $$

Answer 2

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}$.