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. Olive Tree Farming in Jaen: Situation With the New Cap and Comparison With the Province Income Per Capita.
2. ANTI-COMPETITIVE FINANCIAL CONTRACTING: THE DESIGN OF FINANCIAL CLAIMS.
3. Barriers and Limitations in the Development of Industrial Innovation in the Region
4. INTERPERSONAL RELATIONS AND GROUP PROCESSES
5. Midwest prospects and the new economy
6. Standards behaviours face to innovation of the entrepreneurships of Beira Interior
7. ROBUST CLASSIFICATION WITH CONTEXT-SENSITIVE FEATURES
8. The name is absent
9. Accurate, fast and stable denoising source separation algorithms
10. The name is absent
11. The name is absent
12. Macro-regional evaluation of the Structural Funds using the HERMIN modelling framework
13. The name is absent
14. he Virtual Playground: an Educational Virtual Reality Environment for Evaluating Interactivity and Conceptual Learning
15. Integration, Regional Specialization and Growth Differentials in EU Acceding Countries: Evidence from Hungary
16. Julkinen T&K-rahoitus ja sen vaikutus yrityksiin - Analyysi metalli- ja elektroniikkateollisuudesta
17. The name is absent
18. Nurses' retention and hospital characteristics in New South Wales, CHERE Discussion Paper No 52
19. Learning and Endogenous Business Cycles in a Standard Growth Model
20. Computational Batik Motif Generation Innovation of Traditi onal Heritage by Fracta l Computation