circuit and a cocircuit can not have an odd number of common elements.

Question

Here is the question I am trying to solve:

Show that, in a binary matroid, a circuit and a cocircuit can not have an odd number of common elements.

Here are the required definitions:

A binary matroid is one that is representable over $GF(2).$

A cocircuit is a circuit in the dual matroid $M^{*}$ (that is the definition given in James Oxley book "Matroid Theory" second edition).

Also, I found Lemma 6.15 in the file here https://iuuk.mff.cuni.cz/~pangrac/vyuka/matroids/matroid-ch6.pdf is proving the required but I do not quite well understand the idea of the proof. could someone explain the idea for me please in a simple way and maybe with some kind of small drawing if possible?

Specifically, I do not understand these statements of the proof:

1- Since C is a circuit of M, the corresponding columns of $[I_r|D]$ sum to the zero-vector.

Why is this statement correct?

2- Since $x \in C$, there is an odd number of columns of D having non-zero entry in the first row.

Why is this statement correct?

3- However, these columns are precisely the columns corresponding to the elements of $C^∗$ since such non-zero entries correspond to the non-zero entries of the first column of $D^T$.

Why is this statement correct?

And finally, why the following statement is correct?

4- Hence, $C - x$ and $C^{∗} - x$ have an odd number of common elements.

Could anyone help me in understanding this please? probably if someone gave me the matrices of a matroid and its dual and their graphic representations as well, I think this will help me a lot.

Edit:

For example we can consider the matroid and its geometric dual given in the picture below:

Answer 1

1- Since $C$ is a circuit of $M$, the corresponding columns of $[I_r|D]$ sum to the zero-vector.

Why is this statement correct?

$C$ is a cycle of $\mathcal{M}$, so the columns of $C$ must be linearly dependent. So there exist $\alpha_i$ such that $\sum_{e_i\in C}\alpha_iv_i = O$, with $v_i$ the colun corresponding to $e_i$. If one of the $\alpha_i$ is null, by removing $e_i$, the columns are still dependent, so it is not an independent set, contradicting that $C$ s a cycle. So the dependance relation is the sum over all the elements of $C$.

2- Since $x\in C$, there is an odd number of columns of $D$ having non-zero entry in the first row.

Why is this statement correct?

By definition of $GF(2)$, if a sum of values sum to $0$, then there is an even number of ones. The first row of $I_r$ has one $1$, so there must be an odd number of ones in the selected columns of $D$.

3- However, these columns are precisely the columns corresponding to the elements of $C^∗$ since such non-zero entries correspond to the non-zero entries of the first column of $D^T$.

Why is this statement correct?

The first column of $x$ corresponds to the decomposition of $x$ in the base $B^*$. That means that the elements corresponding to these coefficients are the only cycle formed by adding $x$ to $B^*$. $C^*$ must be this cycle, so these elements are exactly the one of $C^*-x$v

4- Hence, $C−x$ and $C^∗−x$ have an odd number of common elements.

Could anyone help me in understanding this please?

We showed that the ones on the first row of $D$ corresponds to elements of $C^*$. If we keep only the ones on the columns of $C$ (that is the elements of the intersection of $C$ and $C^*-x$), there are an odd number of them, as proved in 2).

---

Using you example, let $C = \{1,4,5,6\}$, $C^* = \{2,4,6\}$ and $x = 4$. $C^*-x = \{2,6\}$. This is already a spanning tree, so $B^*= \{2,6\}$, and $B = \{1,3,4,5\}$. We write $\mathcal{M}$ in the base $B$: $$\left(\begin{array}{cccc|cc} 1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 \\ \end{array}\right)$$ The first 4 columns and lines are in order: $4, 1, 3, 5$ ($x$ is the first line). The two last columns are $2, 6$. For $2$, the cycle in $B$ is $\{2, 1, 5,4,3\}$, and for $6$, it is $\{6, 1, 5, 4\}$, hence the corresponding ones in these columns. We can verify that summing columns $1, 4, 5, 6$ gives a zero vector. The only $1$s on the first row of $D$ that belongs to the selected columns is the one of column $6$, and one is indeed an odd number.

We now write the matrix representation of $M^*$ in the base $B^*$ by simply transposing the matrix $D$ and concatenating the identity: $$\left(\begin{array}{cccc|cc} 1 & 1 & 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 & 1 \\ \end{array}\right)$$ The columns in order are still $4,1,3,5$ but the lines in order are now $2,6$. The first column is the cycle containing $4$ in the base $B^*$, we get that $\{4, 2, 6\}$ is a cycle, and by necessity, it is $C^*$. Thus the two ones in this column correspond to the elements of $C^*-x$ (that is $\{2,6\}$) Hence we have $(C-x)\cap (C^*-x)$ = $\{1,5,6\}\cap \{2,6\}$, which is indeed odd. Bringing back $4$, we have an even number of elements (two).