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

basisIndicatorMatrix -- matrix of basis polytope

Synopsis

Description

The matroid (basis) polytope of a matroid on n elements lives in Rn, 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, one must take the convex hull of the columns of the indicator matrix, which is provided by the Polyhedra 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 characterizes which polytopes are basis polytopes for a matroid: namely, each edge is of the form ei - ej for some i, j, where ei are the standard basis vectors.

See also

Ways to use basisIndicatorMatrix :