# What is this *redundant cycle* “thing”? Why is it a matroid?

I found the following definition in an introductory exposition about matroids.

Let $G=(V,E)$ be a given (finite) graph. Let $\mathcal{C, D}$ be arbitrary collections of cycles in $G$.

$\mathcal{C}$ is redundant, if every edge in $G$ appears in an even number of cycles of $\mathcal{C}$. $\mathcal{D}$ is independent, if there is no subset of $\mathcal{D}$ which is redundant.

I am supposed to be showing that the set of independent sets of cycles form a matroid.

I do not know how to proceed here, or what this notion of redundancy is actually referring to. It took me a while to come up with a graph and a redundant cycle set, but I didn't get any intuition of what this is about.

What is the intuition behind these objects? How do I proceed to show that these indeed form a matroid?

Think of a cycle (or in general any subgraph of $G$) as an element of $\mathbb F_2^{|E|}$. That is, if we order the edges of $G$ as $E = \{e_1, e_2, \dots, e_m\}$, then a cycle $C$ corresponds to a vector $x \in \mathbb F_2^m$ such that $$x_i = \begin{cases} 1 & e_i \in C, \\ 0 & e_i \notin C.\end{cases}$$ Then a collection of cycles $\mathcal C$ is redundant precisely when the corresponding vectors sum to $0$ (that is, the zero element of $\mathbb F_2^m$), and a redundant subset of $\mathcal D$ is a linear dependency.
(Over $\mathbb F_2$, a subset that sums to $0$ is the only kind of linear dependency you can have, since coefficients are always either $0$ or $1$.)
As a result, a collection of cycles $\mathcal D$ is independent, by this definition, precisely when it corresponds to a linearly independent collection of vectors in $\mathbb F_2^m$. It's easy to check that linearly independent sets over any vector space satisfy the properties of a matroid. Clearly it looks as though a ladder graph with $n$ rungs is made of $n-1$ cycles glued together. However, if you count all possible cycles, you find $\binom n2$ of them (choose any two rungs and take the rectangle between them). The notion of independent cycles formalizes the former intuition; all independent sets of cycles have $n-1$ elements.