Let $n$ be a positive integer and $\mathbf{A}$ an $n$-by-$n$ matrix with integer entries. Suppose that $k:=\big|\det(\mathbf{A})\big|$ is nonzero. How many $n$-by-$1$ column vectors $\mathbf{x}\in\mathbb{Q}^n$ each of whose entries lies within the interval $[0,1)$ are there with the property that $\mathbf{A}\,\mathbf{x}=\mathbf{b}$ for some $n$-by-$1$ column vector $\mathbf{b}\in\mathbb{Z}^n$?

When $n=1$, the answer is trivially $k$. According to this thread, when $n=2$, the answer is also $k$. I believe that, in general, the answer is $k$. Geometrically, the image of $\mathbf{x}\mapsto \mathbf{A}\,\mathbf{x}$ for $\mathbf{x}\in[0,1)^n$ is an $n$-dimensional hyper-parallelipiped $H\subseteq \mathbb{R}^n$ with integral vertices and with volume $k$. However, I am not certain how to calculate the number of integral points inside and on the boundary of $H$. I remember that there may be a theorem relating the volume and the number of integral points within and on the boundary of a convex polytope whose vertices are integral points. What I do not remember is the name of the theorem and what it states exactly.

I found out what I was referring to, and it was the Ehrhart Polynomial Theorem. The answer is indeed $k$. However, I will still greatly appreciate a number-theoretic or algebraic solution.


You are basically asking for the number of (standard) lattice points inside the fundamental parallelepiped $F$ of the lattice generated by the matrix $A$. Since the vertices of $F$ are on the standard lattice, the number of lattice points in $F$ is the same as the number of points in $F+x$ for any translate of $F$ by an integer vector $x$. Therefore, if you multiply (scale) $F$ by an integer $r$, then the number of points in $rF$ is $r^n$ times the number of points in $F$.

On the other hand, for any convex body $K\subset \mathbb{R}^n$, $$ \lim_{r\to\infty} \frac{\#\{ rK \cap \mathbb{Z}^n \}}{r^n} = \rm{Vol}(K).$$

| cite | improve this answer | |

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.