# Finding all binary vectors with given A-length

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

• Is $\lambda$ larger than the largest eigenvalue of $B$ (so that $A$ is positive definite)? – 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.
• 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. – Jernej Dec 18 '15 at 20:04
• 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$? – Brian Borchers Dec 18 '15 at 20:16