In
matroid theory
In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being ...
, 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.
[.][.]
Matroid duals go back to the original paper by
Hassler Whitney
Hassler Whitney (March 23, 1907 – May 10, 1989) was an American mathematician. He was one of the founders of singularity theory, and did foundational work in manifolds, embeddings, immersions, characteristic classes, and geometric integrati ...
defining matroids.
[. Reprinted in , pp. 55–79. See in particular section 11, "Dual matroids", pp. 521–524.] They generalize to matroids the notions of
plane graph duality.
Basic properties
Duality is an
involution
Involution may refer to:
* Involute, a construction in the differential geometry of curves
* ''Agricultural Involution: The Processes of Ecological Change in Indonesia'', a 1963 study of intensification of production through increased labour input ...
: for all
,
.
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.
The
flats of
are complementary to the cyclic sets (unions of circuits) of
, and vice versa.
If
is the
rank function of a matroid
on ground set
, then the rank function of the dual matroid is
.
Minors
A
matroid minor
In the mathematical theory of matroids, a minor of a matroid ''M'' is another matroid ''N'' that is obtained from ''M'' by a sequence of restriction and contraction operations. Matroid minors are closely related to graph minors, and the restricti ...
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.
Self-dual matroids
An individual matroid is self-dual (generalizing e.g. the
self-dual polyhedra
In geometry, every polyhedron is associated with a second dual structure, where the vertices of one correspond to the faces of the other, and the edges between pairs of vertices of one correspond to the edges between pairs of faces of the othe ...
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
In mathematics and computer science, a matroid oracle is a subroutine through which an algorithm may access a matroid, an abstract combinatorial structure that can be used to describe the linear dependencies between vectors in a vector space or th ...
, 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:
*The
binary matroids (matroids representable over
GF(2)
(also denoted \mathbb F_2, or \mathbb Z/2\mathbb Z) is the finite field of two elements (GF is the initialism of ''Galois field'', another name for finite fields). Notations and \mathbb Z_2 may be encountered although they can be confused with ...
), the matroids representable over any other field, and the
regular matroid
In mathematics, a regular matroid is a matroid that can be represented over all fields.
Definition
A matroid is defined to be a family of subsets of a finite set, satisfying certain axioms. The sets in the family are called "independent sets". O ...
s, are all self-dual families.
*The
gammoids form a self-dual family. The strict gammoids are dual to the
transversal matroids.
*The
uniform matroids and
partition matroids are self-dual. The dual to a uniform matroid
is the uniform matroid
.
*The dual of a
graphic matroid
In the mathematical theory of matroids, a graphic matroid (also called a cycle matroid or polygon matroid) is a matroid whose independent sets are the forests in a given finite undirected graph. The dual matroids of graphic matroids are called c ...
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.
*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).
It is an open problem whether the family of
algebraic matroids is self-dual.
If ''V'' is a
vector space
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called '' vectors'', may be added together and multiplied ("scaled") by numbers called '' scalars''. Scalars are often real numbers, but ...
and ''V''* is its
orthogonal complement In the mathematical fields of linear algebra and functional analysis, the orthogonal complement of a subspace ''W'' of a vector space ''V'' equipped with a bilinear form ''B'' is the set ''W''⊥ of all vectors in ''V'' that are orthogonal to every ...
, then the
linear matroid
In the mathematical theory of matroids, a matroid representation is a family of vectors whose linear independence relation is the same as that of a given matroid. Matroid representations are analogous to group representations; both types of repre ...
of ''V'' and the linear matroid of ''V''* are duals. As a corollary, the dual of any linear matroid is a linear matroid.
References
{{reflist
Matroid theory
Matroid
In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being ...