next | previous | forward | backward | up | top | index | toc | Macaulay2 website
Matroids :: dual(Matroid)

dual(Matroid) -- dual matroid

Synopsis

Description

The dual matroid of a matroid M has the same ground set as M, and bases equal to the complements of bases of M.

Duality is a fundamental operation in matroid theory: for nearly any property/operation of matroids, there is a corresponding dual version, usually denoted with the prefix "co-". For instance, coloops are loops of the dual, and contraction is dual to deletion.

In this package, every dual matroid is created as a matroid-dual matroid pair, and each is cached as the dual of the other. Often the ideal of the dual matroid has a significantly different number of generators, so many algorithms in this package will use an equivalent check for the ideal with fewer generators.

i1 : M = matroid({a,b,c,d},{{a,b},{a,c}})

o1 = a matroid of rank 2 on 4 elements

o1 : Matroid
i2 : D = dual M

o2 = a matroid of rank 2 on 4 elements

o2 : Matroid
i3 : peek D

o3 = Matroid{bases => {set {2, 3}, set {1, 3}}}
             cache => CacheTable{...3...}
             groundSet => set {0, 1, 2, 3}
             rank => 2
i4 : M == dual D

o4 = true
i5 : loops D == coloops M

o5 = true
i6 : hyperplanes M === apply(circuits D, C -> D.groundSet - C)

o6 = true

A matroid that is isomorphic to its dual is called self-dual; and a matroid that is equal to its dual is called identically self-dual.

i7 : V8plus = specificMatroid "V8+"

o7 = a matroid of rank 4 on 8 elements

o7 : Matroid
i8 : V8plus == dual V8plus

o8 = true
i9 : V = relaxation(V8plus, set{4,5,6,7})

o9 = a matroid of rank 4 on 8 elements

o9 : Matroid
i10 : V == dual V

o10 = false
i11 : areIsomorphic(V, dual V)

o11 = true