A Tutte decomposition for matrices and bimatroids

摘要

We develop a Tutte decomposition theory for matrices and their combinatorial abstractions, bimatroids. As in the graph or matroid case, this theory is based on a deletion-contraction decomposition. The contribution from the deletion, derived by an inclusion-exclusion argument, consists of three terms. With one more term contributed from the contraction, the decomposition has four terms in general. There are universal decomposition invariants, one of them being a corank-nullity polynomial. Under a simple change of variables, the corank-nullity polynomial equals a weighted characteristic polynomial. This gives an analog of an identity of Tutte. Applications to counting and critical problems on matrices and graphs are given. (c) 2005 Elsevier Inc. All rights reserved.