How to dualize polytopes using Sage, polymake, or 4ti2 by Dave Swinarski First version: Sep. 3, 2010 Most recent update: May 3, 2012 Two relevant Sage pages: The Polyhedra class: http://www.sagemath.org/doc/reference/sage/geometry/polyhedra.html?highlight=polytope#sage.geometry.polyhedra.Polytopes The lattice polytope class: http://www.sagemath.org/doc/reference/sage/geometry/lattice_polytope.html?highlight=polytope#sage.geometry.lattice_polytope.LatticePolytopeClass polymake homepage/wiki: http://www.opt.tu-darmstadt.de/polymake/doku.php/start 4ti2 homepage: http://www.4ti2.de/ ------------------------------------------------------------------------------ Example: Let P be the cone in R^3 whose extremal rays are spanned by the vectors v1 = (7,1,-3) v2 = (1, -5,3) v3 = (1,7,3) This is known as a V-representation of a polyhedron ("V" for "vertices"). We can easily compute by hand that the plane containing v1 and v2 is x+2y+3z=0, the plane containing v1 and v3 is x-y+2z=0, and the plane containing v2 and v3 is 3x-z=0. Moreover, we see that x+2y+3z evaluated on v3 is positive, x-y+2z evaluated on v2 is positive, and 3x-z evaluated on v1 is positive. Thus our cone can be represented by the inequalities x+2y+3z>=0 x-y+2z>=0 3x-z>=0. This is known as an H-representation of a polyhedron ("H" for "half space"). Often one wants to change between V-representations and H-representations of a polyhedron. (Example: given a cone sigma in the fan of a toric variety, compute sigma^{\vee}.) Here's how to do this using different software packages. ------------------------------------------------------------------------------ METHOD 1: Sage See http://www.sagenb.org/home/pub/2417 The commands to define P in terms of the V-representation and compute an H-representation are P = Polyhedron(rays=[[7,1,-3],[1,-5,3],[1,7,3]]) P.Hrepresentation() The commands to define Q in terms of the H-representation and compute a V-representation are Q=Polyhedron(ieqs = [[0,1,2,3],[0,1,-1,2],[0,3,0,-1]]) Q.Vrepresentation() ------------------------------------------------------------------------------ METHOD 2: polymake, from the command line (very old-fashioned) Make a file called "3dconeV.poly" that contains the following four lines: POINTS 0 7 1 -3 0 1 -5 3 0 1 7 3 The 0 at the front of each line tells polymake we are thinking of these as rays, not points. (Enter a "1" instead of a "0" if you want points instead.) Also, I used the command POINTS instead of VERTICES because I am not telling polymake that I have checked that these rays are actually all extremal; I'm just specifying my cone as the convex hull of these. Then from the command line run > polymake 3dconeV.poly FACETS and the output will appear: polymake: used package cddlib Implementation of the double description method of Motzkin et al. Copyright by Komei Fukuda. http://www.ifor.math.ethz.ch/~fukuda/cdd_home/cdd.html FACETS 0 1 -1 2 0 3 0 -1 0 1 2 3 The way to read this output is: A0 A1 A2 A3 denotes the inequality A0 + A1*x1+A2*x2 +A3*x3 >= 0. Now, suppose you wanted to go the other way. Starting with the inequalities x+2*y+3*z >=0 x-y+2z >=0 3x-z >= 0 you could make a file called "3dconeH.poly" with the four lines INEQUALITIES 0 1 2 3 0 1 -1 2 0 3 0 -1 Once again, by using the command INEQUALITIES instead of FACETS I am telling polymake that my polyhedron is specified by these inequalities, but I am not asserting to polymake that I have checked that this is in fact an irredundant list of facets. Then, from the command line, run > polymake 3dconeH.poly VERTICES and it will produce VERTICES 0 1 -5 3 0 1 7 3 0 1 1/7 -3/7 1 0 0 0 which up to scaling is v1, v2, v3, and (0,0,0) (the apex of the cone). ------------------------------------------------------------------------------ METHOD 3: polymake, interactive The newest versions of polymake have an interactive environment. Here's how to do the same calculation in the interactive shell: Start polymake > polymake Welcome to polymake version 2.9.5, released on December 25, 2008 Copyright (c) 1997-2008 Ewgenij Gawrilow (TU Berlin), Michael Joswig (TU Darmstadt) http://www.math.tu-berlin.de/polymake, mailto:polymake@math.tu-berlin.de This is free software licensed under GPL; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. Type 'help;' for basic instructions. Application polytope uses following third-party software (for details: help 'credits';) cddlib, lrslib, nauty polytope > $p=new Polytope; polytope > $p->POINTS=<<"."; polytope (2)> 0 7 1 -3 polytope (3)> 0 1 -5 3 polytope (4)> 0 1 7 3 polytope (5)> . polytope > print $p->FACETS; 0 1 -1 2 0 3 0 -1 0 1 2 3 Personally, I find this notation very confusing. ------------------------------------------------------------------------------ METHOD 4: 4ti2 To convert between an H-representation and a V-representation, make 3 files: Make a file called "3dH.mat" 1st row: the number of rows and columns then enter the inequalities as rows of a matrix For instance, put the following 4 lines in "3dH.mat": 3 3 1 2 3 1 -1 2 3 0 -1 Then, in "3dH.rel" we need to tell 4ti2 what kind of relations we have (>=, =, or <=). 1st row: the number of lines to follow, and the number of symbols that will be entered in that line For instance, put the following two lines in "3dH.rel": 1 3 > > > Finally, we need to tell 4ti2 the signs allowed in our answers. If you do not want to enter any condition, enter "0". This goes in "3dH.sign" as the following two lines: 1 3 0 0 0 Then from the command line run > ./rays 3dH and in the output file "3dH.ray" you will see 3 3 1 -5 3 1 7 3 7 1 -3 All this can be reversed to get an H-representation from a V-representation. For instance, if we make three files: "3dV.mat" 3 3 1 -5 3 1 7 3 7 1 -3 "3dV.rel" 1 3 > > > "3dV.sign" 1 3 0 0 0 then run > ./rays 3dV and in "3dV.ray" we get 3 3 1 -1 2 1 2 3 3 0 -1