Macaulay2 » Documentation
Packages » Matroids :: dual(Matroid)
next | previous | forward | backward | up | index | toc

# dual(Matroid) -- dual matroid

- 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:

- dual(Matroid) -- dual matroid

The source of this document is in /build/macaulay2-88fgJW/macaulay2-1.25.11+ds/M2/Macaulay2/packages/Matroids/doc-Matroids.m2:1311:0.