A (0, 1) matrix A is said to be ideal if all the vertices of the polytope Q (A) = (x \ Ax greater than or equal to 1, 0 less than or equal to x less than or equal to 1) are integral. The issue of finding a satisfactory characterization of those matrices which are minimally non-ideal is a well known open problem. An outstanding result toward the solution of this problem, due to Alfred Lehman, is the description of crucial properties of minimally non-ideal matrices. In this paper we consider the extension of the notion of ideality to (0, +/-1) matrices. By means of a standard transformation, we associate with any (0, +/-1) matrix A a suitable (0, 1) matrix D(A). Then we introduce the concept of disjoint completion A(+) of a (0, +/-1) matrix A and we show that A is ideal if and only if D(A(+)) is ideal. Moreover, we introduce a suitable concept of a minimally non-ideal (0, +/-1) matrix and we prove a Lehman-type characterization of minimally non-ideal (0, +/-1) matrices.
(0, +-1) Ideal Matrices
NOBILI, Paolo;
1998-01-01
Abstract
A (0, 1) matrix A is said to be ideal if all the vertices of the polytope Q (A) = (x \ Ax greater than or equal to 1, 0 less than or equal to x less than or equal to 1) are integral. The issue of finding a satisfactory characterization of those matrices which are minimally non-ideal is a well known open problem. An outstanding result toward the solution of this problem, due to Alfred Lehman, is the description of crucial properties of minimally non-ideal matrices. In this paper we consider the extension of the notion of ideality to (0, +/-1) matrices. By means of a standard transformation, we associate with any (0, +/-1) matrix A a suitable (0, 1) matrix D(A). Then we introduce the concept of disjoint completion A(+) of a (0, +/-1) matrix A and we show that A is ideal if and only if D(A(+)) is ideal. Moreover, we introduce a suitable concept of a minimally non-ideal (0, +/-1) matrix and we prove a Lehman-type characterization of minimally non-ideal (0, +/-1) matrices.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
