1
$\begingroup$

Here is a part of Integer Programming (Graduate Texts in Mathematics, 271) 2014th Edition.

In lemma 5.9, aiming at showing that a finite number of splits ${(\pi, \pi_0)}$ are sufficient to generate the split closure $P^{split}$, the author wish to show that the pointed cone $C_u$ can be generated by a set of extreme rays $r^t$, whose size can be evaluated by the sub-determinants of $A$. However, the detail of the proof is left as an exercise and I get stuck here. Following is the exercise,

Exercise 5.18. Let $C = \{ x\in R^n: Ax=0, x\geq 0\}$ where $A$ be an integral matrix. Let $\Delta$ be the largest among the absolute values of the determinants of the square submatrices of A. Show that the extreme rays $r^1,...,r^q$ of $C$ can be chosen to be integral vectors satisfying $-\Delta 1 \leq r^t \leq \Delta 1, 1\leq t \leq q$.

Could somebody provides some hint or a rough proof? It would be greatly appreciated.

$\endgroup$

0

You must log in to answer this question.

Browse other questions tagged .