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. Apprenticeships in the UK: from the industrial-relation via market-led and social inclusion models
2. A Duality Approach to Testing the Economic Behaviour of Dairy-Marketing Co-operatives: The Case of Ireland
3. Tissue Tracking Imaging for Identifying the Origin of Idiopathic Ventricular Arrhythmias: A New Role of Cardiac Ultrasound in Electrophysiology
4. Herman Melville and the Problem of Evil
5. Design and investigation of scalable multicast recursive protocols for wired and wireless ad hoc networks
6. Wounds and reinscriptions: schools, sexualities and performative subjects
7. The name is absent
8. Applications of Evolutionary Economic Geography
9. Poverty transition through targeted programme: the case of Bangladesh Poultry Model
10. POWER LAW SIGNATURE IN INDONESIAN LEGISLATIVE ELECTION 1999-2004