3
$\begingroup$

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.

  • 0
    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.2011-11-01
  • 0
    @ValerioCapraro Yes, each $x_i$ appears twice in my problem. Thanks, updated.2011-11-01
  • 0
    Have you considered the possibility that your problem may be NP-complete?2011-11-02
  • 0
    @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?2011-11-02
  • 0
    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.2011-11-02
  • 0
    Also posted to MO, http://mathoverflow.net/questions/79811/ where it is getting some answers, so I vote to close here.2011-11-02

2 Answers 2