On the Complexity of Matroid Isomorphism Problem

We study the complexity of testing if two given matroids are isomorphic. The problem is easily seen to be in S₂^p\Sigma_{2}^{p}. In the case of linear matroids, which are represented over polynomially growing fields, we note that the problem is unlikely to be S₂^p\Sigma_{2}^{p}-complete and is co NP-hard. We show that when the rank of the matroid is bounded by a constant, linear matroid isomorphism, and matroid isomorphism are both polynomial time many-one equivalent to graph isomorphism.