If $A$ is an integer matrix in $\mathbb{Z}^{m \times n}$, why is there only a finite number of vectors $x \in [0,1]^n$ such that $Ax$ is a vector of integers?

  • $\begingroup$ $Ax$ is a vector, not an integer... $\endgroup$ – Don Thousand Nov 7 '19 at 7:57
  • $\begingroup$ An integer vector I mean $\endgroup$ – Luna Nov 7 '19 at 7:59
  • $\begingroup$ Then this is not true... Every matrix will satisfy this. $\endgroup$ – Don Thousand Nov 7 '19 at 8:01
  • 1
    $\begingroup$ No, by [0,1] I mean the interval. If A is a 2x2 matrix of all ones and x = [1/3, 1/3], then Ax is not a vector of integers. $\endgroup$ – Luna Nov 7 '19 at 8:06
  • 1
    $\begingroup$ This is not true in general: If $A$ is the zero matrix, $Ax$ is an integer vector for every vector $x$. There has to be some extra condition. $\endgroup$ – Eike Schulte Nov 7 '19 at 8:50

The claim is true if and only if $\ker A=\{0\}$.

Let $\ker A=\{0\}$. Then necessarily $m\ge n$ and there is $B\in \mathbb R^{n,m}$ such that $BA=I_n$.

Since multiplication with $A$ is a linear and bounded map, the image $A([0,1]^n)$ of $[0,1]^n$ is bounded, so $A([0,1]^n) \cap \mathbb Z^m$ is a finite set. Then the set of vectors $x\in [0,1]^n$ with $Ax\in \mathbb Z^m$ is precisely $$ B \left( A([0,1]^n) \cap \mathbb Z^m \right), $$ which is finite as well.

Let now $y \in \ker A$, $y\ne 0$. Since $A$ is an integer matrix, it holds $Ax\in \mathbb Z^m$ for all $x\in \{0,1\}^n$.

Now define $x$ as $$ x_i = \begin{cases} 1 & \text{ if } y_i<0,\\ 0 & \text{ if } y_i\ge0. \end{cases}$$ Then for all $t\ge0$ small enough, $x+ty\in [0,1]^n$ and $A(x+ty)=Ax\in \mathbb Z^m$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.