  We study the complexity of testing if two given matroids are isomorphic. The
problem is easily seen to be in $\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 $\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. We give a polynomial time Turing reduction
from graphic matroid isomorphism problem to the graph isomorphism problem.
Using this, we are able to show that graphic matroid isomorphism testing for
planar graphs can be done in deterministic polynomial time. We then give a
polynomial time many-one reduction from bounded rank matroid isomorphism
problem to graphic matroid isomorphism, thus showing that all the above
problems are polynomial time equivalent. Further, for linear and graphic
matroids, we prove that the automorphism problem is polynomial time equivalent
to the corresponding isomorphism problems. In addition, we give a polynomial
time membership test algorithm for the automorphism group of a graphic matroid.

Computational Complexity