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;
More intriguing information
1. L'organisation en réseau comme forme « indéterminée »2. Gerontocracy in Motion? – European Cross-Country Evidence on the Labor Market Consequences of Population Ageing
3. Mergers and the changing landscape of commercial banking (Part II)
4. The name is absent
5. LIMITS OF PUBLIC POLICY EDUCATION
6. EMU: some unanswered questions
7. The Response of Ethiopian Grain Markets to Liberalization
8. The InnoRegio-program: a new way to promote regional innovation networks - empirical results of the complementary research -
9. The name is absent
10. Response speeds of direct and securitized real estate to shocks in the fundamentals