What is the computationally most efficient way to find integer solutions $\mathbf {X}$ for the following linear system
$$\mathbf {Xa = c}$$
given the following constraints?
- $\mathbf a$ is of dimension $n \times 1$,
- $\mathbf c$ is of dimension $m \times 1$,
- $\mathbf X$ is of dimension $m \times n$,
- $n >= m$
- $\mathbf {X}$ can only have 1 or 0 as elements
- $\mathbf {a}$ and $\mathbf {c}$ only have
finite decimal numbersintegers as elements - Sum of elements in $\mathbf {a}$ equals to the sum of elements in $\mathbf {c}$
- There must be one and only one 1 in every column of $\mathbf {X}$
The practical problem I am trying to solve is to find all the many-to-1 maps (functions) between two finite list of numbers such that y is the sum of all its preimages. For example:
- list_A: 1, 2, 3, 4, 6
- list_B: 5, 5', 6 (adding a prime sign to the second 5 to distinguish it from the first 5)
Then there will be two solutions:
- f(1) = 5, f(2) = 5', f(3) = 5', f(4) = 5, f(6) = 6
- f(1) = 5', f(2) = 5, f(3) = 5, f(4) = 5', f(6) = 6
To put this example in the language of the above problem, $\mathbf a$ and $\mathbf c$ are: \begin{align*} \mathbf a = \begin{pmatrix} 1 \\ 2 \\ 3 \\ 4 \\ 6 \\ \end{pmatrix}, \mathbf c = \begin{pmatrix} 5 \\ 5 \\ 6 \\ \end{pmatrix} \end{align*}
And there are two solutions: \begin{align*} \mathbf X_1 = \begin{pmatrix} 1&0&0&1&0 \\ 0&1&1&0&0 \\ 0&0&0&0&1 \\ \end{pmatrix}, \mathbf X_2 = \begin{pmatrix} 0&1&1&0&0 \\ 1&0&0&1&0 \\ 0&0&0&0&1 \\ \end{pmatrix}, \end{align*}
And of course there are cases where there exists no solution. For example:
- list_A: 1, 2, 3, 4
- list_B: 1, 2, 3, 5
\begin{align*} \mathbf a = \begin{pmatrix} 1 \\ 2 \\ 3 \\ 4 \\ \end{pmatrix}, \mathbf c = \begin{pmatrix} 1 \\ 2 \\ 3 \\ 5 \\ \end{pmatrix} \end{align*}