# Dual matroid

Matroid duals go back to the original paper by Hassler Whitney defining matroids. They generalize to matroids the notions of planar graph duality and of dual spaces in linear algebra.

## Basic properties

An alternative definition of the dual matroid is that its basis sets are the complements of the basis sets of $M$ . The basis exchange axiom, used to define matroids from their bases, is self-complementary, so the dual of a matroid is necessarily a matroid.

## Self-dual matroids

An individual matroid is self-dual (generalizing e.g. the self-dual polyhedra for graphic matroids) if it is isomorphic to its own dual. The isomorphism may, but is not required to, leave the elements of the matroid fixed. Any algorithm that tests whether a given matroid is self-dual, given access to the matroid via an independence oracle, must perform an exponential number of oracle queries, and therefore cannot take polynomial time.

## Matroid families

Many important matroid families are self-dual, meaning that a matroid belongs to the family if and only if its dual does. Many other matroid families come in dual pairs. Examples of this phenomenon include: