# On the integer feasibility of polytopes defined by idempotent integer matrices

EDIT: I realized that while writing this question, I was reasoning about orthogonal projections. Thus, I forgot to transpose when forming the projection on to the space orthogonal to the image of $P$. For clarity, it was intended that the L.H.S. is perpendicular to the R.H.S. I have changed the question to reflect this.

Let $P\in\mathbb{Z}^{n \times n}$ with $P^2=P$ and $0<\text{rank}(P)=r<n$. For an arbitrary constant vector $\mathbf{b}\in\mathbb{Z}^n$, consider the polytope defined by:

$$P\mathbf{x}\geq (I-P^T)\mathbf{b}$$

Under what conditions does this posses an integer solution for $x$?

First of all, we can assume without loss of generality that $(I-P^T)\mathbf{b}\neq 0$, and that it has at least one strictly positive and at least one strictly negative coordinate; otherwise the question of feasibility is trivial.

Does anyone know anything about the other cases? This question seems intuitively (perhaps naively) easier than the general integer programming problem, but I can't seem to find an Ansatz.

-