0
$\begingroup$

Given a linear inequalities, how can I know the structure of the integer points? An simple example is stated as follows: if \begin{align*} y\geq x\quad \text{and}\quad y\leq2x, \end{align*} then all the integer points in this region can be expressed as \begin{align*} a(1,1)+b(1,2), \end{align*} where $a,b$ are integers satisfying $a\geq0$ and $0\leq b\leq a$. Thus we know the integer solution of this linear inequalities.

I wonder the general answer of this question. Let $A$ be a $m\times n$ integral matrix, and $\alpha$ be an $n$-dimensional vector. What about the structure of the integer solution of $$A\alpha\geq0 .$$
Can all the solutions be expressed as an integer linear combination of finite points like the example above? I also seek for the relative reference.

Any help will be appreciated!:) Thank you!

$\endgroup$
1
$\begingroup$

You are looking for the Integral Volume (somebody calls it Content), of a Polytope defined by its bounding planes. Which may also turn out to be "in-congruent" and thus defining an empty space.

There are some techniques that allow to re-organize / simplify such "set of Diophantine Inequalities /Polytope" and provide some computational simplification, or formulas for the most regular polytopes. But unfortunately not a general "closed" formula (to my knowledge).

You can search on internet: there exist various papers on this topic.

One interesting is e.g. "Computing the Continuous Discretely" - M. Beck, S. Robins.

$\endgroup$

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.