1

One of my homework problem is to prove $(M^*)^*=M$, given $M=(S,\mathcal{I})$ is a matroid, i.e. dual of a dual matroid is itself.

My confusion is what is needed to prove the equality, in general. Is it good enough to say two matroids have same ground sets and their collections of independent sets are equivalent? Or what routine should I follow? Such as two directions of inclusive relation, any base in one matroid is a base in another matroid or something.

For example in this exercise, suppose I can apply the statement that the dual matroid of a matroid is a matroid, i.e. $M^*$ here. So then $(M^*)^*$ is a matroid immediately. Since the dual doesn't change the ground set so I don't need to worry about that. For independent set collection, $\mathcal{I}^*=\{A\subseteq S: S\backslash A\in \mathcal{I}\}$, then I can say $(\mathcal{I}^*)^*=\{A\subseteq S: S\backslash (S\backslash A)\in \mathcal{I}\}=\mathcal{I}$. Thus the two are equal.

adosdeci
  • 165

1 Answers1

2

It is certainly enough to show that the collections of independent sets are the same.

Since a matroid is also determined by its bases you could show they are equal by showing they have exactly the same bases. This may be easier if you know the bases of the dual matroid in terms of those of the original.

A. Brown
  • 36
  • It is necessary to show that ground sets are the same. Let $\mathcal{I} = { \emptyset }$. The matroid with ground set ${1}$ with independent sets $\mathcal{I}$ is not equal to the matroid with the same independent sets on the ground set ${1,2}$. The former has one loop while the latter has two, so they cannot be equal. – Aaron Dall Nov 19 '19 at 07:06