= Integer-matrix vertex coordinate bound
{title2=$|x_j|\le n!U^n$}
At an <extreme point> of $\{x:Ax\ge b\}$, the active rows span the ambient dimension: otherwise a nonzero direction orthogonal to all active rows permits small feasible moves of both signs. Select $n$ independent active rows to form an integer matrix $B$. Its nonzero determinant has absolute value at least one. <Cramer's rule> and the determinant expansion bound each coordinate by $n!U^n$, where $U$ bounds the entries of $A$ and $b$. The vector $b$ may be real; only the denominator matrix needs to be integer.
Back to article page
