Dimension of circuit space of a matroid

Question

If $G$ is a graph with edge set $E$, let $W$ be the $\mathbb{Z}/2$-vector space generated by the elements of $E$. If $A = \{a_1, \dots, a_n\} \subset E$, let $\bar{A} = a_1 + \dots + a_n \in V$; then $\bar{A}_1 + \bar{A}_2 = \overline{A_1 \Delta A_2}$, where $\Delta$ indicates symmetric difference.

I'll define the cycle space of $G$ to be the subspace of $W$ generated by simple cycles of $G$. More precisely, the cycle space of $G$ is the subspace of $W$ generated by the set $\{\bar{C} \mid C \text{ is a simple cycle of } G\}$. We could also view the cycle space as the first simplicial homology group of $G$ over $\mathbb{Z}/2$. It is not difficult to show that the dimension of the cycle space of $G$ is the corank of the cycle matroid of $G$.

Given any matroid $M$ with ground set $E$, we could define the circuit space of $M$ in a completely analogous way, just using the word "circuit" instead of "simple cycle." My question is: is it always true that the dimension of the circuit space of $M$ is the corank of $M$? If not, for what types of matroids is this true? Finally, can anyone recommend good resources that deal with this sort of thing?

Thanks!

Answer 1

The dimension of the circuit space of a matroid $M$ is the corank of $M$ if and only if $M$ is binary. Here is a proof. Given a basis $B$ and $e \notin B$, we let $C(e,B)$ be the unique circuit contained in $B \cup \{e\}$. We will use the following well-known characterization of binary matroids (Theorem 9.1.2 in Oxley's Matroid Theory text).

Theorem. A matroid $M$ is binary if and only if, for all bases $B$ of $M$ and all circuits $C$ of $M$, $C= \triangle_{e \in C-B} C(e,B)$.

Here, $\triangle$ means symmetric difference, or equivalently $\sum$, if we view sets as vectors over $\mathbb{F}_2$.
Let $\dim(M)$ denote the dimension of the circuit space of $M$ and $r^*(M)$ denote the corank of $M$. We now prove that $\dim(M)=r^*(M)$ if and only if $M$ is binary.

Proof. For each basis $B$ of $M$, let $\mathcal{C}_B:=\{C(e,B) : e \notin B\}$. The circuits in $\mathcal{C}_B$ are linearly independent since for each $e \notin B$, there is a unique circuit in $\mathcal{C}_B$ containing $e$. Thus, $\dim(M) \geq r^*(M)$, for every matroid $M$.

If $M$ is binary, then by the above theorem, $C= \triangle_{e \in C-B} C(e,B)$, for every circuit $C$. Thus, $\dim(M)=r^*(M)$.

If $M$ is not binary, then by the above theorem, there exists a basis $B'$ and a circuit $C'$ such that $C' \neq \triangle_{e \in C-B'} C(e,B')$. In particular, $C'$ is not a sum of the vectors in $\mathcal{C}_{B'}$. Thus, $\dim(M)>r^*(M)$.