= Normalized integer Farkas infeasibility gap
{title2=$b^T\lambda\geq[(n+1)U]^{-(n+1)}$}
Suppose $A,b$ have integer entries of absolute value at most $U\geq1$, $A$ has $n$ columns, and $Ax\geq b$ is infeasible. A <Farkas certificate for linear inequalities> can be chosen with $\lambda\geq0$, $A^T\lambda=0$, $\mathbf1^T\lambda=1$ and the displayed lower bound. Normalize an infeasibility certificate to obtain the last equality, then maximize $b^T\lambda$ over the resulting compact <linear polyhedron>. A maximizing <extreme point> has at most $n+1$ positive entries: otherwise the augmented columns $(A_i^T,1)$ on its support would be dependent, allowing feasible perturbations in both directions. For its $k\leq n+1$ independent supported columns, select $k$ independent equations. <Cramer's rule> expresses the supported entries with a common nonzero integer determinant denominator. That determinant has absolute value at most $k!U^k\leq[(n+1)U]^{n+1}$. The positive value $b^T\lambda$ therefore has a positive integer numerator over a denominator of at most this size, proving the bound.
Back to article page
