2
$\begingroup$

Let $E$, a $\mathbb{Q}$-affine space of arbitrary dimension included in $\mathbb{Q}^n$. Is it possible to check efficiently if $E \cap \mathbb{Z}^n$ is empty or not?

If is an hard problem could give me the reduction to a well-known hard-problem (or a source that attest the fact: it is a well-known hard problem).

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Does this help? If $E$ is given as $\{ v + Aw : w \in \mathbb Q^m \}$, $A \in M_{n, m}(\mathbb Q)$, $m \leq n$, and $B$ is a left-inverse for $A$, then $E \cap \mathbb Z^n \neq \varnothing$ is equivalent to $(1-AB) v \in \mathbb Z^n + A \mathbb Z^m$. We can find a basis of this full rank $\mathbb Z$-module and check if the coordinates of $(1-AB) v$ in that basis are integers. $\endgroup$
    – Bart Michels
    Commented Nov 29, 2019 at 13:47
  • $\begingroup$ Thx to answer so fastly; How do you find a base for a module? Is $B$ not right-inverse? $\endgroup$
    – Ievgeni
    Commented Nov 29, 2019 at 13:54

1 Answer 1

Reset to default
6
$\begingroup$

If $E$ is given as $\{ v + Aw : w \in \mathbb Q^m \}$ where $v \in \mathbb Q^n$ and $A \in M_{n, m}(\mathbb Q)$, then if $B$ is a left-inverse for $A$ we have $E \cap \mathbb Z^n \neq \varnothing \iff (1-AB)v \in (1-AB) \mathbb Z^n$. We can find a basis of this $\mathbb Z$-module and check if the coordinates of $(1-AB) v$ in that basis are integers.

For $\iff$: If we can write $(1-AB)v = (1-AB)x$, then $v + AB(x-v) = x \in E \cap \mathbb Z^n$. Conversely, if $v + Aw = x \in \mathbb Z^n$, then $Bv+w = Bx$. Hence $x = v + Aw = v + A(Bx-Bv)$ so that $(1-AB)v = (1-AB)x$.

So, first find a left inverse $B$ for $A$ (through Gaussian elimination). Take an integer $N$ such that $N(1-AB)$ has integer entries. Then find the Smith normal form for $N(1-AB)$, and keep track of the transformation matrices. Say $1-AB = P D Q$ with $D$ diagonal and $P, Q \in GL(n, \mathbb Z)$. Now $(1-AB)v \in (1-AB) \mathbb Z^n$ is equivalent to $ P^{-1}(1-AB)v \in D \mathbb Z^n$. Because $D$ is diagonal, this is easy to check.

As remarked by Emil Jeřábek supports Monica in the comments, this is a polynomial time algorithm.

Improve this answer
$\endgroup$
5
  • $\begingroup$ If $B$ is a left-inverse, why do you write $AB$? $\endgroup$
    – Ievgeni
    Commented Nov 29, 2019 at 14:50
  • $\begingroup$ I want a left inverse because that allows me to cancel the $A$ in the proof of the equivalence: $BAw = w$. It just so happens that $AB$ appears in the end. $\endgroup$
    – Bart Michels
    Commented Nov 29, 2019 at 15:01
  • $\begingroup$ I think it might be worth explicitly stating that this gives a polynomial-time algorithm. $\endgroup$
    – Emil Jeřábek
    Commented Nov 29, 2019 at 15:49
  • 1
    $\begingroup$ @EmilJeřábeksupportsMonica I'm not confident enough to make a precise statement; the complexity of the Euclidean algorithm part will depend on the denominators and numerators of $AB$. $\endgroup$
    – Bart Michels
    Commented Nov 29, 2019 at 16:13
  • 1
    $\begingroup$ math.tamu.edu/~rojas/kannanbachemhermitesmith79.pdf $\endgroup$
    – Emil Jeřábek
    Commented Nov 29, 2019 at 16:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .