# Integral Farkas Lemma

The context of this question is commutative algebra, however the question itself is more related to convex geometry. All necessary information is given.

In the proof of Lemma 3.1.1 in the book "Monomial Ideals" by Herzog and Hibi, the following situation arises: Let $i=1,\dots,m$ and for every $i$ let $a_i, b_i \in \mathbb{N}^n$. For the purpose of the proof, we want to find a $w \in \mathbb{N}^n$ such that the standard inner product $\langle a_i - b_i, w \rangle >0, \forall i$. Then the proof continues: "suppose no such $w$ exists. Then by the Farkas Lemma there exist $c_i \in \mathbb{Z}_+$ with $c_i >0$ for at least one $i$, such that the vector $\sum_{i=1}^m c_i (a_i-b_i)$ has non-positive entries."

The proof refers to a book by Schrijver on Linear and Integer Programming for the Farkas Lemma. I checked the reference and not only i could not find a discrete version of the Farkas Lemma, but the continuous versions (i.e. all vectors are in $\mathbb{R}^n$) that i found, do not seem to match the argument of the proof. So i wonder if anyone familiar with the various versions of the Farkas Lemma could explain to me which version is used and provide a reference or proof for it.

## 1 Answer

I might be a little late with the answer but here it is : Let $Ax = b$ be a rational system. Then there exists an integral solution $x$ iff $y^Tb$ is integer for each rational $y$ such that $y^T A$ is integral. I hope this helps.