In
matroid theory, the **dual** of a matroid is another matroid that has the same elements as , and in which a set is independent if and only if has a basis set disjoint from it.^{
[1]}^{
[2]}^{
[3]}

Matroid duals go back to the original paper by
Hassler Whitney defining matroids.^{
[4]} They generalize to matroids the notions of
plane graph duality.

Duality is an
involution: for all , .^{
[1]}^{
[3]}^{
[4]}

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

The
flats of are complementary to the cyclic sets (unions of circuits) of , and vice versa.^{
[3]}

If is the
rank function of a matroid on ground set , then the rank function of the dual matroid is .^{
[1]}^{
[3]}^{
[4]}

A
matroid minor is formed from a larger matroid by two operations: the restriction deletes element from without changing the independence or rank of the remaining sets, and the contraction deletes from after subtracting one from the rank of every set it belongs to. These two operations are dual: and . Thus, a minor of a dual is the same thing as a dual of a minor.^{
[5]}

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.^{
[6]}

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:

- The
binary matroids (matroids representable over
GF(2)), the matroids representable over any other field, and the
regular matroids, are all self-dual families.
^{ [7]} - The
gammoids form a self-dual family. The strict gammoids are dual to the
transversal matroids.
^{ [8]} - The
uniform matroids and
partition matroids are self-dual. The dual to a uniform matroid is the uniform matroid .
^{ [9]} - The dual of a
graphic matroid is itself graphic if and only if the underlying graph is planar; the matroid of the dual of a planar graph is the same as the dual of the matroid of the graph. Thus, the family of graphic matroids of planar graphs is self-dual.
^{ [10]} - Among the graphic matroids, and more generally among the binary matroids, the
bipartite matroids (matroids in which every circuit is even) are dual to the
Eulerian matroids (matroids that can be partitioned into disjoint circuits).
^{ [11]}^{ [12]}

It is an open problem whether the family of algebraic matroids is self-dual.

If *V* is a
vector space and *V** is its
orthogonal complement, then the
linear matroid of *V* and the linear matroid of *V** are duals. As a corollary, the dual of any linear matroid is a linear matroid.^{
[13]}

- ^
^{a}^{b}^{c}Schrijver, Alexander (2003),*Combinatorial Optimization: Polyhedra and Efficiency. Vol. B: Matroids, Trees, Stable Sets*, Algorithms and Combinatorics, vol. 24, Berlin: Springer-Verlag, p. 652, ISBN 3-540-44389-4, MR 1956925. **^**Welsh, D. J. A. (2010),*Matroid Theory*, Courier Dover Publications, p. 34, ISBN 9780486474397.- ^
^{a}^{b}^{c}^{d}^{e}Oxley, James G. (2006),*Matroid Theory*, Oxford Graduate Texts in Mathematics, vol. 3, Oxford University Press, pp. 69–70, ISBN 9780199202508. - ^
^{a}^{b}^{c}Whitney, Hassler (1935), "On the abstract properties of linear dependence",*American Journal of Mathematics*, The Johns Hopkins University Press,**57**(3): 509–533, doi: 10.2307/2371182, hdl: 10338.dmlcz/100694, JSTOR 2371182, MR 1507091. Reprinted in Kung (1986), pp. 55–79. See in particular section 11, "Dual matroids", pp. 521–524. **^**Schrijver (2003), p. 653.**^**Jensen, Per M.; Korte, Bernhard (1982), "Complexity of matroid property algorithms",*SIAM Journal on Computing*,**11**(1): 184–190, doi: 10.1137/0211014, MR 0646772.**^**Whitney (1935), Section 13, "Orthogonal hyperplanes and dual matroids".**^**Schrijver (2003), pp. 659–661; Welsh (2010), pp. 222–223.**^**Oxley (2006), pp. 77 & 111.**^**Tutte, W. T. (1965), "Lectures on matroids",*Journal of Research of the National Bureau of Standards*,**69B**: 1–47, doi: 10.6028/jres.069b.001, MR 0179781.**^**Welsh, D. J. A. (1969), "Euler and bipartite matroids",*Journal of Combinatorial Theory*,**6**(4): 375–377, doi: 10.1016/s0021-9800(69)80033-5, MR 0237368.**^**Harary, Frank; Welsh, Dominic (1969), "Matroids versus graphs",*The Many Facets of Graph Theory (Proc. Conf., Western Mich. Univ., Kalamazoo, Mich., 1968)*, Lecture Notes in Mathematics, vol. 110, Berlin: Springer, pp. 155–170, doi: 10.1007/BFb0060114, ISBN 978-3-540-04629-5, MR 0263666.**^**Federico, Ardila (2012). "Matroids Lecture 9".

- Kung, Joseph P. S.v, ed. (1986),
*A Source Book in Matroid Theory*, Boston: Birkhäuser, doi: 10.1007/978-1-4684-9199-9, ISBN 978-0-8176-3173-4, MR 0890330.