14
where ɑʃ = (аг1,..., α⅛) is the г-th row of A for i ∈ N, and b = (Z>1,..., δra+1)τ.
A linear transformation U is called a unimodular transformation if U is bijective
on Zn. U is unimodular if and only if the entries of U are integral and the deter-
minant of U is equal to 1 or —1. Let A be the product AU. If U is unimodular,
it is readily seen that given an integral point x and у = Ux, Ay ≤ b if and only if
Ax ≤ b.
One may wonder how to get a unimodular matrix. Clearly, the identity In is
unimodular. In order to obtain a non-trivial unimodular matrix, however, we need
to study some other examples and their effect when they postmultiply a matrix A
and premultiply a vector x:
(г) Interchange: U is equal to In except that the Avth column of U is e(Z) and the
Z-th column of U is e(k^). This transformation switches columns к and I of A
and switches the Avth and Z-th components of x.
(U) Reversal of sign: Z7 is equal to In except that the Avth column of Z7 is equal
to -e(k^). U changes the sign of the entries of the Ат-th column of A and of
the Ат-th component of x.
(ггг) Addition: Z7 is equal to In except that the (A:, Z)-th entry of Z7, к ψ Z, is equal to
one. This transformation replaces the Z-th column of A by the sum of columns
к and Z and replaces the Ат-th component of x by the sum of components к
and I.
The following result can be found in Newman [9].
Theorem 4.1 Every unimodular matrix can be expressed as a finite product of
unimodular matrices of type (г), (гг) and (ггг).
The next basic result says that every simplex can be brought into the standard form
by a unimodular transformation.