Exercise 46 Given the integer set S Z Axb where A is a tot

Exercise 4.6. Given the integer set S :-{ Z : Ax-b}, where A is a totally unimodular matrix and b is a vector that may have fractional components, show that conv(S)-(a E R : Ax } components, show that conv(S)ER : A b)

Solution

Since S is the set of n dimensional integer entried points. All the basis vectors of Rⁿ₊ are in Zⁿ_+.

i.e. {(1,0,0,...,0),(0,1,...,0),...,(0,0,...,1)}.

Convex set made by the points of set S will be the whole space Rⁿ₊.

Since, b is the vector that may have fractional components, in Conv(S), Ax <= [b].