Finding all binary vectors with given A-length

Question

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

Answer 1

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.