The name is absent



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 ZnCx = 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~
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;



More intriguing information

1. What Lessons for Economic Development Can We Draw from the Champagne Fairs?
2. Credit Markets and the Propagation of Monetary Policy Shocks
3. For Whom is MAI? A theoretical Perspective on Multilateral Agreements on Investments
4. Climate Policy under Sustainable Discounted Utilitarianism
5. The name is absent
6. A Theoretical Growth Model for Ireland
7. Spousal Labor Market Effects from Government Health Insurance: Evidence from a Veterans Affairs Expansion
8. The name is absent
9. ADJUSTMENT TO GLOBALISATION: A STUDY OF THE FOOTWEAR INDUSTRY IN EUROPE
10. Evaluation of the Development Potential of Russian Cities