Paper detail

On the representability of totally unimodular matrices on bidirected graphs

Seymour's famous decomposition theorem for regular matroids states that any totally unimodular (TU) matrix can be constructed through a series of composition operations called $k$-sums starting from network matrices and their transposes and two compact representation matrices $B_{1}, B_{2}$ of a certain ten element matroid. Given that $B_{1}, B_{2}$ are binet matrices we examine the $k$-sums of network and binet matrices. It is shown that the $k$-sum of a network and a binet matrix is a binet matrix, but binet matrices are not closed under this operation for $k=2,3$. A new class of matrices is introduced the so called {\em tour matrices}, which generalises network, binet and totally unimodular matrices. For any such matrix there exists a bidirected graph such that the columns represent a collection of closed tours in the graph. It is shown that tour matrices are closed under $k$-sums, as well as under pivoting and other elementary operations on its rows and columns. Given the constructive proofs of the above results regarding the $k$-sum operation and existing recognition algorithms for network and binet matrices, an algorithm is presented which constructs a bidirected graph for any TU matrix.