The name is absent

14

where ɑʃ = (а_г1,..., α⅛) is the г-th row of A for i ∈ N, and b = (Z>₁,..., δ_ra+1)^τ.

A linear transformation U is called a unimodular transformation if U is bijective
on Zⁿ. 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 I_n 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 I_n 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 I_n 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 I_n 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.

<<   13   14   15   16   17   18   19   >>

More intriguing information