  Basic path-matchings, introduced by Cunningham and Geelen (FOCS 1996), are a
common generalization of matroid intersection and non-bipartite matching. The
main results of this paper are a new algebraic characterization of basic
path-matching problems and an algorithm for constructing basic path-matchings
in O(n^w) time, where n is the number of vertices and w is the exponent for
matrix multiplication. Our algorithms are randomized, and our approach assumes
that the given matroids are linear and can be represented over the same field.
  Our main results have interesting consequences for several special cases of
path-matching problems. For matroid intersection, we obtain an algorithm with
running time O(nr^(w-1))=O(nr^1.38), where the matroids have n elements and
rank r. This improves the long-standing bound of O(nr^1.62) due to Gabow and Xu
(FOCS 1989). Also, we obtain a simple, purely algebraic algorithm for
non-bipartite matching with running time O(n^w). This resolves the central open
problem of Mucha and Sankowski (FOCS 2004).
