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

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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11587/107185
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? 8
social impact