A Discrete Farkas Lemma

摘要

Given A ∈ Z~(m * n) and b ∈ Z~m, we consider the issue of existence of a nonnegative integral solution x ∈ N~n to the system of linear equations Ax = b. We provide a discrete and explicit analogue of the celebrated Farkas lemma for linear systems in R~n and prove that checking existence of integral solutions reduces to solving an explicit linear programming problem of fixed dimension, known in advance.