next | previous | forward | backward | up | top | index | toc | Macaulay2 website
Matroids :: basisIndicatorMatrix

basisIndicatorMatrix -- matrix of basis polytope

Synopsis

Description

The matroid (basis) polytope of a matroid on n elements lives in R^n, and is the convex hull of the indicator vectors of the bases.

For uniform matroids, the basis polytope is precisely the hypersimplex:

i1 : U24 = uniformMatroid(2, 4)

o1 = a "matroid" of rank 2 on 4 elements

o1 : Matroid
i2 : A = basisIndicatorMatrix U24

o2 = | 1 1 0 1 0 0 |
     | 1 0 1 0 1 0 |
     | 0 1 1 0 0 1 |
     | 0 0 0 1 1 1 |

              4        6
o2 : Matrix ZZ  <--- ZZ

In order to obtain an actual polytope object in M2, one must take the convex hull of the columns of the indicator matrix, which is provided by either the Polyhedra or OldPolyhedra package:

i3 : needsPackage "Polyhedra"

o3 = Polyhedra

o3 : Package
i4 : P = convexHull A

o4 = P

o4 : Polyhedron
i5 : vertices P

o5 = | 1 1 0 1 0 0 |
     | 1 0 1 0 1 0 |
     | 0 1 1 0 0 1 |
     | 0 0 0 1 1 1 |

              4        6
o5 : Matrix QQ  <--- QQ

The Gelfand-Goresky-MacPherson-Serganova (GGMS) theorem characterizes which polytopes are basis polytopes for a matroid: namely, each edge is of the form $e_i - e_j$ for some $i, j$, where $e_i$ are the standard basis vectors.

See also

Ways to use basisIndicatorMatrix :

For the programmer

The object basisIndicatorMatrix is a method function.