dual(Matroid) -- dual matroid

Synopsis

Function: dual
Usage:

dual M
Inputs:
- M, a matroid,
Outputs:
- a matroid, the dual matroid of M

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{...2...}
             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

If a matroid has a representation stored, then this function will attempt to automatically compute a representation for the dual (whether this works depends on whether reducedRowEchelonForm is implemented for the underlying ring of the matrix).

i12 : F7 = specificMatroid fano

o12 = a "matroid" of rank 3 on 7 elements

o12 : Matroid

i13 : getRepresentation F7

o13 = | 1 1 1 1 0 0 0 |
      | 0 0 1 1 1 1 0 |
      | 0 1 0 1 0 1 1 |

              ZZ 3      ZZ 7
o13 : Matrix (--)  <-- (--)
               2         2

i14 : M = dual F7

o14 = a "matroid" of rank 4 on 7 elements

o14 : Matroid

i15 : getRepresentation M

o15 = | 1 1 1 1 0 0 0 |
      | 1 0 1 0 1 0 0 |
      | 0 1 1 0 0 1 0 |
      | 1 1 0 0 0 0 1 |

              ZZ 4      ZZ 7
o15 : Matrix (--)  <-- (--)
               2         2

Ways to use this method: