MATROID MATCHING VIA MIXED SKEW-SYMMETRIC MATRICES

Tutte associates a V by V skew-symmetric matrix T, having indeterminate entries, with a graph G=(V,E). This matrix, called the Tutte matrix, has rank exactly twice the size of a maximum cardinality matching of G. Thus, to find the size of a maximum matching it suffices to compute the rank of T. We consider the more general problem of computing the rank of T +K where K is a real V by V skew-symmetric matrix. This modest gen-eralization of the matching problem contains the linear matroid matching problem and, more generally, the linear delta-matroid parity problem. We present a tight upper bound on the rank of T +K by decomposing T+K into a sum of matrices whose ranks are easy to compute