24
for all к, I E N. Now it immediately follows from (4.2) that
λkh3k = 0
for all h and k. Hence xk = x0 and l(xk) = 0. It is a contradiction. We complete
the proof. □
Theorem 2.4 is a straightforward result of the above results.
5 Extension to general п-dimensional polytopes
Let M denote the set of integers { 1, ∙ ∙ ∙ , m }. The problem is to test the integral
property of a general n-dimensional polytope P given by
P = { x ∈ Rn I Ax ≤ b },
where ¾τ = (аг1, ...,c⅛n) is the г-th row of the m by n matrix A for i = 1, ..., m,
and b = (δι, ∙ ∙ ∙ , δm)τ is a vector of Rm. It is clear that m ≥ n ⅛ 1. As usual we
may assume that ɑɪ,..., am are integral vectors of Rn, and b = (b1, , bm)τ is an
integral vector of Rm. Finally we assume that none of the constraints ɑʃæ ≤ bi,
i ∈ M ,is redundant, and that there is a subset J, with cardinality n ⅛ 1, of M such
that
{ x ∈ Rn I ɑɪx ≤ bi, i ∈ ,J }
is an п-dimensional simplex. In the sequel we take J = N for simplicity of notation.
Compared with the labeling rule in Section 2, we have the following generalized
labeling rule.
Generalized Labeling Rule: If there is an index i E M for which ajx — bi > 0,
we assign x E Zn with the label
/(æ) = min{ j E N ∖ aj x — bj = max{ ɑɪæ — ∕y} }.