I am given a $n \times n$ matrix $A$ with real entries and define the inner product $$\langle x,y\rangle = x^T A y.$$

I am also given an integer $k$ and need to find all binary vectors $x$ such that $\langle x,x \rangle = k.$

By binary vector I mean a vector whose entries are in $\{0,1\}.$ For $n$ small it is not hard to solve this problem - simply test all possible $2^n$ vectors. In practice $n$ can be quite large and there is only a small fraction of vectors that satisfy this condition. Hence I am wondering

Is there a more efficient way to compute all binary vectors satisfying $\langle x,x \rangle = k$?

I am pretty sure this problem is hard in general but I am wondering if there is any way to get away with having to test all $2^n$ vectors?

Edit. The matrix $A$ is of the form $(\lambda I-B)^{-1}$ where $\lambda$ is an integer and $B$ is a binary symmetric matrix. $\lambda$ is not an eigenvalue of $B.$

  • $\begingroup$ Is $\lambda$ larger than the largest eigenvalue of $B$ (so that $A$ is positive definite)? $\endgroup$ – Brian Borchers Dec 19 '15 at 17:09

Are the entries in your $A$ matrix actually real or just integer? If they are real numbers, how precisely do you need to satisfy the constraint? Are the entries of $A$ all nonnegative, or could some of the entries be negative?

Your problem is in general NP-Hard, so you shouldn't expect to find a polynomial time algorithm. You may find that you can do better than checking all $2^{n}$ combinations by using back tracking search. I'd suggest looking at constraint programming solvers such as Eclipse to do this backtracking search.

You could also try to approach this using integer linear programming software, but most codes for ILP are not setup to find all solutions but rather stop after finding a single optimal solution even if there may be many more solutions.

| cite | improve this answer | |
  • $\begingroup$ Thank you for your reply. I've made an edit describing the particular structure of $A.$ As for satisfying the constraints, I must make sure all vectors get computed. $\endgroup$ – Jernej Dec 18 '15 at 20:04
  • 2
    $\begingroup$ Let me give an example of what I mean by "how precisely..." Suppose k=27, and $x^{T}Ax=26.9999$. Is x a satisfactory vector? What if $x^{T}Ax=26.97$? $\endgroup$ – Brian Borchers Dec 18 '15 at 20:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.