In matroid theory, the dual of a matroid ${\displaystyle M}$ is another matroid ${\displaystyle M^{\ast }}$ that has the same elements as ${\displaystyle M}$, and in which a set is independent if and only if ${\displaystyle M}$ has a basis set disjoint from it.

Matroid duals go back to the original paper by Hassler Whitney defining matroids. They generalize to matroids the notions of plane graph duality.

Duality is an involution: for all ${\displaystyle M}$, ${\displaystyle (M^{\ast })^{\ast }=M}$.

An alternative definition of the dual matroid is that its basis sets are the complements of the basis sets of ${\displaystyle 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.

The flats of ${\displaystyle M}$ are complementary to the cyclic sets (unions of circuits) of ${\displaystyle M^{\ast }}$, and vice versa.

If ${\displaystyle r}$ is the rank function of a matroid ${\displaystyle M}$ on ground set ${\displaystyle E}$, then the rank function of the dual matroid is ${\displaystyle r^{\ast }(S)=r(E\setminus S)+|S|-r(E)}$.

A matroid minor is formed from a larger matroid ${\displaystyle M}$ by two operations: the restriction ${\displaystyle M\setminus x}$ deletes element ${\displaystyle x}$ from ${\displaystyle M}$ without changing the independence or rank of the remaining sets, and the contraction ${\displaystyle M/x}$ deletes ${\displaystyle x}$ from ${\displaystyle M}$ after subtracting one from the rank of every set it belongs to. These two operations are dual: ${\displaystyle M\setminus x=(M^{\ast }/x)^{\ast }}$ and ${\displaystyle M/x=(M^{\ast }\setminus x)^{\ast }}$. Thus, a minor of a dual is the same thing as a dual of a minor.

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.