Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
$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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.