28
(H) H 1C is an integer matrix.
A polynomial-time algorithm for finding U and H can be also found in [8, 13]. Now
let H and U = (tʃɪ, U2) be as in Theorem 6.2, with U1 an n × m1 matrix and U2 an
n × (n — m1) matrix.
Theorem 6.3
(i) Q is nonempty if and only if H~1d ∈ Zml.
(H) IfQ is nonempty, every point x of Q can be written as
x = U1H~1d + U2z, for some z ∈ Zn~ml.
When Q is nonempty, we have
Po = { У ∈ Rn I AU у ≤ b, and CUy = d}
= {y ∈ Rn I AU у ≤ b, and [H, Q]y = d }
= { У ∈ Rn I У = ((B^1d)τ, zγ)∖
and AU(fH~1d)∖zτ)τ <b,zE pn~ml ɪ
= {y ∈ Rn I у = ((H~1d)∖ zτ)τ, and Az <b, z E Rn~ml }.
Let
P = {z ∈ Rn~ml ∖Az<b}.
Doing so leads to an (n — m1)-dimensional polytope P in Rn~mλ. Now the remaining
discussions are the same as in the previous section. Let us demonstrate this by an
example. We are given a polytope
P = { x ∈ R3 I af x ≤ bi, i = 1, 2, 3, and c1x = d1},
where a1 = (—1,0, 0)τ, a2 = (0,-1, 0)τ, a3 = (0,0,—l)τ, c1 = (4,12,2)τ, b1 = 0,
b2 = 0, b3 = 1, and d1 = 2. Then we have
C = [4 12 2],