Given linear representations M1 and M2 of matroids over a field F, we consider the problem (denoted by ECLR[F]) of checking if M1and M2 represent the same matroid over F. When F =Z _2, we show that ECLR[Z _2] is complete for $\oplus$L under logspace many-one reductions.

When F=Q, given linear representations M1,M2$\in$Q$^{m\times n}$ as input, any $X\subseteq \{1,\ldots ,n\}$ such that columns corresponding to indexes in $X$ form a minimal linearly dependent set of vectors in one linear representation but the column vectors corresponding to indexes in $X$ are linearly independent in the other linear representation is a witness that M1 and M2 represent different matroids over Q. We show that the decision and the search version of this problem are polynomial time equivalent.

We define the CYCLE MATCHING problem of checking if for a pair of undirected graphs $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ given as input with $V_1=V_2=\{ 1,\ldots ,n\}$ and $n=|V_1|=|V_2|$, whether the set of vertices in $X\subseteq V_1$ form a cycle in $G_1$ if and only if the vertices in $X\subseteq V_2$ form a cycle in $G_2$ also, for all $X\subseteq \{ 1,\ldots ,n\}$. We show that CYCLE MATCHING is complete for L.

Also the problem of counting the number of $X\subseteq \{ 1,\ldots ,n\}$ such that vertices with indexes in $X$ form a cycle in one of the input graphs but not in the other is shown to be #P-complete.

Revision 2 gives the correct proof of many statements claimed in earlier versions. Readability and presentation of the results has also been improved.

Given linear representations $M_1$ and $M_2$ of matroids over a field F, we consider the problem (denoted by ECLR), of checking if M_1 and M_2 represent the same matroid over F. We show that when F=$Z_2$, ECLR{Z_2} is complete for $\parityL$. When F=$Q$, given linear representations $M_1,M_2\in \Q ^{m\times n}$ as input, any set of indexes $X \subseteq \{1,\ldots ,n\}$ such that columns corresponding to these indexes in $X$ are linearly dependent in one linear representation but are linearly independent in the other linear representation is a witness that $M_1$ and $M_2$ represent different matroids over $Q$. We show that the decision and the search version of this problem are polynomial time equivalent.

We consider the CYCLEMATCHING problem of checking if for a pair of undirected graphs $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$ given as input with $n=|V_1|=|V_2|$, we check if the set of vertices having indexes in $X\subseteq {1,...,n}$ form a cycle in $G_1$ if and only if the corresponding set of vertices having indexes in $X\subseteq {1,...,n}$ form a cycle in $G_2$ for all $X\subseteq {1,...,n}$. We show that CYCLEMATCHING is complete for L. Also the problem of counting the number of $X\subseteq {1,...,n}$ such that vertices with indexes in X form a cycle in one of the input graphs but not in the other is shown to be #P-complete.

1). One another reference to J. Edmonds on matroid intersection problem has been added.

2). Base Exchange axiom has been included in Lemma 2.7 referring to Oxley's text on Matroid Theory and some other results that can be obtained from it needed for the results have been included in Section 2.2.

3). Theorem 3.1 has been explicitly stated and proved. It says that given a linear representation of a matroid on $n$ elements it is also represented by any submatrix of itself whose rank is the same as the original linear representation.

4). One another reference of [Braverman-Kulkarni-Roy] in which results showing problems complete for $\parityL$ has been included.

5). Remark 2 has been rewritten based on the comments of the anonymous third referee of STACS 2009 conference.

The manuscript has been rewritten based on the comments of the referees of ISAAC 2008 and STACS 2009 conferences where the previous version (extended abstract) was submitted.

Given linear representations M_1 and M_2 of matroids over a field F, we consider the problem (denoted by ECLR), of checking if M_1 and M_2 represent the same matroid. We show that when F=Z_2, ECLR{Z_2} is complete for $\parityL$. Let M_1,M_2\in Q ^{m\times n} be two matroid linear representations given as input. Then any set of indexes, columns corresponding to which are linearly dependent in one representation but are linearly independent in another is a witness that M_1 and M_2 represent different matroids over Q. We show that the decision and the search version of this problem are polynomial time equivalent. We consider the CYCLEMATCHING problem of checking if for a pair of undirected graphs G_1=(V_1,E_1) and G_2=(V_2,E_2) given as input with |V_1|=|V_2|=n, whether any set of vertices having indexes in X\subseteq {1,...,n} form a cycle in G_1 if and only if the corresponding set of vertices form a cycle in G_2. We show that CYCLEMATCHING is complete for L. Also the problem of counting the number of X\subseteq {1,...,n}$ such that vertices with indexes in X form a cycle in one of the input graphs but not in the other is shown to be $\sharpP$-complete.