Editing Matroid (section)

== Basic constructions ==
There are some standard ways to make new matroids out of old ones.

===Duality===
If <math> M </math> is a finite matroid, we can define the ''orthogonal'' or ''[[dual matroid]]'' <math>M^*</math> by taking the same underlying set and calling a set a ''basis'' in <math> M^* </math> if and only if its complement is a basis in <math> M</math>. It is not difficult to verify that <math> M^* </math> is a matroid and that the dual of <math> M^* </math> is <math> M</math>.<ref name=Whi8632>{{harvp|White|1986|p=32}}</ref>

The dual can be described equally well in terms of other ways to define a matroid. For instance:

* A set is independent in <math>M^*</math> if and only if its complement spans <math>M</math>. 

* A set is a circuit of <math>M^*</math> if and only if its complement is a coatom in <math>M</math>. 

* The rank function of the dual is <math> r^*(S) = |S| - r(M) + r\left(E\smallsetminus S\right)</math>. 

According to a matroid version of [[Kuratowski's theorem]], the dual of a graphic matroid <math> M </math> is a graphic matroid if and only if <math> M </math> is the matroid of a [[planar graph]]. In this case, the dual of <math> M </math> is the matroid of the [[dual graph]] of <math> G</math>.<ref name=Whi86105>{{harvp|White|1986|p=105}}</ref> The dual of a vector matroid representable over a particular field <math> F </math> is also representable over <math> F</math>. The dual of a transversal matroid is a strict gammoid and vice versa.

;Example: The cycle matroid of a graph is the dual matroid of its bond matroid.

===Minors===
{{main|Matroid minor}}
If ''M'' is a matroid with element set ''E'', and ''S'' is a subset of ''E'', the ''restriction'' of ''M'' to ''S'', written ''M''&nbsp;|''S'', is the matroid on the set ''S'' whose independent sets are the independent sets of ''M'' that are contained in ''S''.  Its circuits are the circuits of ''M'' that are contained in ''S'' and its rank function is that of ''M'' restricted to subsets of ''S''.

In linear algebra, this corresponds to restricting to the subspace generated by the vectors in ''S''.  Equivalently if ''T'' = ''M''−''S'' this may be termed the ''deletion'' of ''T'', written ''M''\''T'' or ''M''−''T''. The submatroids of ''M'' are precisely the results of a sequence of deletions: the order is irrelevant.<ref name=Whi86131>{{harvp|White|1986|p=131}}</ref><ref name=Whi86224>{{harvp|White|1986|p=224}}</ref>

The dual operation of restriction is contraction.<ref name=Whi866139>{{harvp|White|1986|p=139}}</ref> If ''T'' is a subset of ''E'', the ''contraction'' of ''M'' by ''T'', written ''M''/''T'', is the matroid on the underlying set ''E &minus; T'' whose rank function is <math>r'(A) = r(A \cup T) - r(T)</math>.<ref name=Whi86140>{{harvp|White|1986|p=140}}</ref>  In linear algebra, this corresponds to looking at the quotient space by the linear space generated by the vectors in ''T'', together with the images of the vectors in ''E - T''.

A matroid ''N'' that is obtained from ''M'' by a sequence of restriction and contraction operations is called a [[matroid minor|minor]] of ''M''.<ref name=Whi86224/><ref name=Whi86150>{{harvp|White|1986|p=150}}</ref>  We say ''M'' ''contains'' ''N'' ''as a minor''. Many important families of matroids may be characterized by the [[minimal element|minor-minimal]] matroids that do not belong to the family; these are called ''forbidden'' or ''excluded minors''.<ref name=Whi861467>{{harvp|White|1986|pp=146–147}}</ref>

===Sums and unions===
Let ''M'' be a matroid with an underlying set of elements ''E'', and let ''N'' be another matroid on an underlying set ''F''.
The ''direct sum'' of matroids ''M'' and ''N'' is the matroid whose underlying set is the [[disjoint union]] of ''E'' and ''F'', and whose independent sets are the disjoint unions of an independent set of ''M'' with an independent set of ''N''.

The ''union'' of ''M'' and ''N'' is the matroid whose underlying set is the union (not the disjoint union) of ''E'' and ''F'', and whose independent sets are those subsets that are the union of an independent set in ''M'' and one in ''N''. Usually the term "union" is applied when ''E'' = ''F'', but that assumption is not essential.  If ''E'' and ''F'' are disjoint, the union is the direct sum.