27
dimensional nonempty polytope in Rn we may assume under the same conditions
that P can be expressed as
P = { x ∈ Rn I ajx ≤ bi, i = 1, ∙ ∙ ∙ , m, and eʃæ = ⅛, г = 1, ∙ ∙ ∙ , m1 },
where diτnP = n — mɪ, for some mɪ, 0 ≤ m1 ≤ n. As usual we assume that α1,...,
αm, C1,..., cmι are integral vectors of Rn, and δ1, ∙ ∙ ∙, δm, d1,...,dmι are integers. Let
A denote an m × n matrix whose rows are ɑʃ, ∙ ∙ ∙, ɑɪ, and let b = (δ1, ∙ ∙ ∙ , δm)τ.
Moreover, let C be an m1 × n matrix whose rows are eʃ, ∙ ∙ ∙, cvm 1, and let d =
(d1, ∙ ∙ ∙ , dmι)τ. We define a set Q by
Q = {x E Zn∖Cx = d}.
It is clear that if Q is empty, then P has no integral point.
Now we can transform the polytope into a full-dimensional polytope in Rn~mλ
by reducing the number of variables in polynomial time. To do so, we first introduce
matrices in Hermite normal form.
Definition 6.1 An m1 × m1 nonsingular integer matrix H is called in Hermite
normal form if it satisfies the following conditions:
(1) H is lower triangular and hij = 0 for i < j;
(2) hii > 0 for ι = 1, ∙ ∙ -, m1;
(3) hij ≤ 0 and ∖hij∖ < ha for i > j.
The following two results can be found in [8, 13].
Theorem 6.2 Given an m1 × n matrix C with rank{C') = m1, there exists an
n × n unimodular matrix U such that the following holds:
(i) CU = (Lf, 0) where H is an m1 × m1 matrix in Hermite normal form and 0
is an m1 × (n — m1) zero matrix;