# How many ${0, 1}$ solutions would this system of underdetermined linear equations have?

The problem:

I have a system of N linear equations, with K unknowns; and K > N. Although the equations are over $\mathbb Z$, the unknowns can only take the values 0 or 1.

Here's an example with N=11 equations and K=15 unknowns:

$1 = x_1 + x_9$
$2 = x_{1} + x_{2} + x_{10}$
$2 = x_{2} + x_{3} + x_{11}$
$2 = x_{3} + x_{12}$
$2 = x_{9} + x_{4} + x_{13}$
$2 = x_{10} + x_{4} + x_{5} + x_{14}$
$2 = x_{11} + x_{5} + x_{6} + x_{15}$
$2 = x_{12} + x_{6}$
$2 = x_{13} + x_{7}$
$2 = x_{14} + x_{7} + x_{8}$
$1 = x_{15} + x_{8}$

Things that will always hold true in the general case:

• Every coefficient is $1$.
• In the entire collection of equations, each $x_i$ appears exactly twice.
• There are exactly two equations of the form $x_i + x_j = 1$.
• All the other equations will have $2$ as the constant.

Some observations:

• If you sum all of the above equations and divide both sides by $2$, you get $\sum_{i=1}^{i=K}x_i=N-1$. In this case,
$x_{1} + x_{2} + x_{3} + x_{4} + x_{5} + x_{6} + x_{7} + x_{8} + x_{9} + x_{10} + x_{11} + x_{12} + x_{13} + x_{14} + x_{15} = 10$.
So, in any solution, there will be exactly N-1 1's and K-(N-1) 0's.

My Questions:

• How many solutions does this general system have?
• Is there a fast way to find these solutions?

FWIW, I encountered this problem when trying to find the longest (hamiltonian) path between two points in a square lattice.

• I think that you have to assume the property in your observation. It seems to me that it is not implied by the other three properties. Maybe you want that any $x_i$ appears twice. – Valerio Capraro Nov 1 '11 at 13:41
• @ValerioCapraro Yes, each $x_i$ appears twice in my problem. Thanks, updated. – Bee San Nov 1 '11 at 13:44
• Have you considered the possibility that your problem may be NP-complete? – Gerry Myerson Nov 2 '11 at 6:04
• @GerryMyerson Yes, that is why I've asked whether there might be a fast way to find the solutions. Hopefully the number of solutions can be found fast enough? – Bee San Nov 2 '11 at 7:28
• Migration is not possible from MSE to MO, as MO is not part of the StackExchange platform. If you want to ask the question there, please go ahead, but please as a courtesy edit your question here to include the MO link and also include this page in your MO version. – Willie Wong Nov 2 '11 at 8:48

Determining whether a Hamiltonian path exists is NP-complete, so a fast solution to your problem applied to all pairs of vertices would prove $P=NP$.