Centre for Discrete and Applicable Mathematics 

CDAM Research Report, LSECDAM200019December 2000 
Gautam Appa and Balázs Kotnyek
Abstract
We define a new class of matrices called binet matrices  B, closely related to network matrices  N. We show that if A belongs to class B, then the polyhedron P(A, b) = { x : Ax <= b, x >= 0 } is integral for all integral b vectors whose common divisor is 2. Starting with the nodeedge incidence matrices of bidirected graphs having elements 0, 1 and 2, binet matrices with elements 0, 1, 2 and 1/2 are derived as their generalization, in parallel with the derivation of network matrices as generalised nodeedge incidence matrices of directed graphs. It is shown that the two well known totally unimodular matrices which are not network matrices are binet matrices, but the transpose of a binet matrix is not necessarily a binet matrix. The most striking result obtained is that class B is closed under pivoting and taking submatrices. Some further theorems on binet matrices are developed, leaving open the problem of an efficient recognition algorithm.
A compressed (gzip) PostScript file (180 kB) with the full contents of this report can be downloaded by clicking here.
Alternatively, if you would like to get a free hard copy of this report, please send the number of this report, LSECDAM200019, together with your name and postal address to:
CDAM Research Reports Series Centre for Discrete and Applicable Mathematics London School of Economics Houghton Street London WC2A 2AE, U.K. 

Phone: +44(0)207955 7732. Fax: +44(0)207955 6877. Email: info@maths.lse.ac.uk 
Introduction to the CDAM Research Report Series.  
CDAM Homepage. 
Last changed: Wed 9 Feb 2005
For comments go to:
http://www.maths.lse.ac.uk/webmaster.html