The name is absent

27

dimensional nonempty polytope in Rⁿ we may assume under the same conditions
that P can be expressed as

P = { x ∈ Rⁿ I ajx ≤ b_i, i = 1, ∙ ∙ ∙ , m, and eʃæ = ⅛, г = 1, ∙ ∙ ∙ , m¹ },

where diτnP = n — mɪ, for some mɪ, 0 ≤ m¹ ≤ n. As usual we assume that α₁,...,
α_m, C₁,..., c_mι are integral vectors of Rⁿ, and δ₁, ∙ ∙ ∙, δ_m, d₁,...,d_mι are integers. Let
A denote an m × n matrix whose rows are ɑʃ, ∙ ∙ ∙, ɑɪ, and let b = (δ₁, ∙ ∙ ∙ , δ_m)^τ.
Moreover, let C be an m¹ × n matrix whose rows are eʃ, ∙ ∙ ∙, c^v_{m 1}, and let d =
(d₁, ∙ ∙ ∙ , d_mι)^τ. We define a set Q by

Q = {x E Zⁿ∖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 Rⁿ~^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 m¹ × m¹ nonsingular integer matrix H is called in Hermite
normal form if it satisfies the following conditions:

(1) H is lower triangular and hi_j = 0 for i < j;

(2) h_ii > 0 for ι = 1, ∙ ∙ -, m¹;

(3) hi_j ≤ 0 and ∖hij∖ < ha for i > j.

The following two results can be found in [8, 13].

Theorem 6.2 Given an m¹ × n matrix C with rank{C') = m¹, there exists an
n × n unimodular matrix U such that the following holds:

(i) CU = (Lf, 0) where H is an m¹ × m¹ matrix in Hermite normal form and 0
is an m¹ × (n — m¹) zero matrix;

<<   26   27   28   29   30   31   32   >>

More intriguing information