Prove that if A has integer entries, A does not contain any lattice point except it's vertices, then |det(A)| = 1

98 Views Asked by At

This is an extension of this question

That question stated that if A is a matrix with $n$ integer vectors $v_i$, $|det(A)| = 1$ then the polyhedron formed by $v_i$ does not contain any lattice point inside it.

So what about the backward preposition : if A has $n$ independent integer vectors, the polyhedron does not contain any lattice point inside it, can we show that then $|det(A)| = 1$ ?

My idea is using the affine combination, we can prove if vector $w$ lies inside the polyhedron formed by $A$, specify $B_i$ as matrix A with vector $w$ replacing $v_i$ . Then $\det(A) \geq \det (B_i)$ but again, I'm stuck here.

1

There are 1 best solutions below

0
On

Notice it's not enough to know just that no lattice points are in the interior; consider rectangle $(1,0), (0,2)$ which has no lattice points strictly inside but does have extra lattice points on its edges, and has determinant 2. What we can actually prove:

Given a non-singular $n \times n$ matrix $A$ with integer entries, call its column vectors $v_1, \ldots, v_n$. If the closed $n$-parallelepiped having $v_i$ as edges includes no lattice points other than its $2^n$ vertices, then $|\det A| = 1$.

The closed parallelepiped is the set of points $$x = \sum_{i=1}^n \lambda_i v_i$$ where each coefficient $\lambda_i$ is a real number $0 \leq \lambda_i \leq 1$. The vertices are the points where all the $\lambda_i$ values are either $0$ or $1$.

Now consider any integer vector $x = (x_1, \ldots, x_n) \in \mathbb{Z}^n$. Since $A$ is non-singular, we can define $y \in \mathbb{R}^n$ as $y = (y_1,\ldots, y_n) = A^{-1} x$. Writing the matrix equation $A y = x$ in terms of the vectors $v_i$ gives

$$\sum_{i=1}^n y_i v_i = x$$

Replace the coefficients $y_i$ with their integer parts to define

$$ z = \sum_{i=1}^n \lfloor y_i \rfloor v_i $$ $$ x-z = \sum_{i=1}^n (y_i - \lfloor y_i\rfloor) v_i $$

Since every $\lfloor y_i \rfloor$ and all coordinates of every $v_i$ are integers, $z$ is another integer vector, and so is $x-z$. For any real $y_i$ we have $0 \leq y_i - \lfloor y_i \rfloor < 1$, so $x-z$ satisfies the description of a point in the closed parallelepiped. But the only integer vector / lattice points in the closed parallelepiped are its vertices, so $y_i - \lfloor y_i \rfloor \in \{0,1\}$. The only remaining possibility is that every $y_i = \lfloor y_i \rfloor$, so $y = A^{-1} x$ is also an integer vector.

So $A^{-1} x$ has integer coordinates whenever $x$ does. Then in particular this is true for the basis vectors $x = (0,\ldots,0,1,0,\ldots,0)$. This shows the column vectors of $A^{-1}$ have integer coordinates, so $A^{-1}$ has all integer entries. Finally, we know that $\det A$ and $\det A^{-1}$ are non-zero integers, and $$(\det A)(\det A^{-1}) = \det(A A^{-1}) = \det I = 1 $$ This requires $|\det A| = |\det A^{-1}| = 1$.