# Integer solution for sets of linear equations

I'm searching for an integer solution to an arbitrary set of linear equations with binary coefficients. It is given that the rank of the Matrix is not maximal. The right hand side is the 0-vector.

So let $A \in \{0,1\}^{(d+k)\cdot (d+1)}$ with last column fixed to 1: $A_{i,d+1}=1\forall i\in \{1,..,d+k\}$, with $k \in \mathbb{N} \cup\{0\}$

Let $x\in \mathbb{Z}^{d+1}$ and $r = (0,...,0)^t \in \mathbb{N}^{d+k}$.

It is given that $rank(A) =d$ and there are no conflicting linear equations, thus there are infinitively many solutions.

I now want to search only for non-trivial integer solutions of $A \cdot x =r$, preferably, the integers should be small.

Let's put that in the way that $x^* = argmin_x (max_i |x_i|)$ s.t. $Ax=r$ and $x\neq 0$. If it's easier for the task, the use of maximum-norm is not necessary, but the requirement that the integers of the solution should be near 0 (in the common sense, i.e. all above 10 would be odd to my kind of problem), is non-optional.

Are there fast/efficient algorithms to achieve this?

-
$x \in N^{d+1} or Z^{d+1}$ ? or is the addition mod 2 ? – tulasi Jun 15 '12 at 15:17
your right, should be $\mathbb{Z}$, just corrected it. Thank you! – stefan Jun 15 '12 at 15:20
actually, in the case of my matrices, I currently think that x is in ${-1,0,1}^{d+1}$, but since i'm not sure about that, I asked that more general problem. – stefan Jun 15 '12 at 15:22
als, what is the purpose of $x_{*}$ you just defined it and didnt do anything wih it – tulasi Jun 15 '12 at 15:23
$x^*$ is short for "optimal solution" – stefan Jun 15 '12 at 15:24