Prove that if $A$ has integer entries, $|\det A| = 1$, then the polyhedron formed by $A$ does not contain integer points.

161 Views Asked by At

Given $n$ vectors $v_1 , v_2 , v_3 , \dots, v_n \in \mathbb{R}^n$ with integer entries in each vector.

Prove that if $|\det(v_1 , v_2 , \dots , v_n)| = 1$, then the polyhedron $Ov_1v_2\dots v_n$ does not have any points with integer coordinates inside it, except the vertices.


For example,

picture here

My idea

Use determinant to prove that $$\det A = \text{Volume of the paralelipiped spanned by }A $$

and because $\det A$ has integer value, we have $\min|\det A| = 1$. Then conclude that the parallelepiped spanned by $A$ is the smallest. So, if $A$ has any other integer points inside it, it will contain another smaller parallelepiped, which is conflicted with the previous statement. But here we have to consider the polyhedron, which is something I'm stuck with.

1

There are 1 best solutions below

0
On

Let us assume on the contrary that such an integer coordinates point $M$ exists inside the polyhedron.

Being in the (closed) polyhedron means :

$$M=\sum \lambda_k v_k \text{with all} \ \lambda_k \ge 0 \ \text{and} \ \sum \lambda_k=1 \tag{1}$$

(principle of barycentric coordinates).

(1) is equivalent to a linear system with integer entries:

$$\begin{cases}\lambda_1 v_{1,1}+\cdots \lambda_n v_{1,n}&=&m_1\\ \cdots\cdots\cdots \\ \lambda_1 v_{n,1}+\cdots \lambda_n v_{n,n}&=&m_n\\ \end{cases}\tag{2}$$

Let us consider the value of $\lambda_1$ as given by Cramer's formula:

$$\lambda_1=\frac{D_1}{D}=\pm D_1$$

where $D_1$ is itself an integer. Indeed, $D$ is obtained by replacing in main determinant $D$, its first column by the column of the coordinates $m_k$ of $M$.

What we have done for $\lambda_1$ is valid for any $\lambda_k$. Therefore

$$\text{All } \ \lambda_k \in \mathbb{Z}$$

But taking into account the fact (see (1)) that $\sum \lambda_k=1$:

  • either only one of the $\lambda_k$s is non-zero, which implies that this $lambda_k$ is $1$ ; in this case, $M$ coincides with one of the vertices of the polyhedron.

  • or more than one of the $\lambda_k$s is non-zero. In this case, due agein to relationship $\sum \lambda_k = 1$, one of the $\lambda_k$s is negative. But the "theory" of barycentric coordinates implies that such a point $M$ is outside the polyhedron. Contradiction.