Macaulay2 » Documentation
Packages » FourierMotzkin :: Finding the facets of the permutahedron
next | previous | forward | backward | up | index | toc

Finding the facets of the permutahedron

The permutahedron is the convex hull of all vectors that are obtained by permuting the coordinates of the vector (1,2, ..., d). The function permutahedron produces a matrix such that columns generate the cyclic d permutahedron in (d+1)-space.
i1 : permutahedron = d -> transpose matrix permutations toList(1..d+1);
i2 : vertices = permutahedron 3

o2 = | 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 4 |
     | 2 2 3 3 4 4 1 1 3 3 4 4 1 1 2 2 4 4 1 1 2 2 3 3 |
     | 3 4 2 4 2 3 3 4 1 4 1 3 2 4 1 4 1 2 2 3 1 3 1 2 |
     | 4 3 4 2 3 2 4 3 4 1 3 1 4 2 4 1 2 1 3 2 3 1 2 1 |

              4       24
o2 : Matrix ZZ  <-- ZZ

To find the halfspace representation for permutahedron, we first pass from 4-space to 5-space. Specifically, we make the permutahedron into a polyhedral cone by placing it a height 1 (we make the extra coordinate the zeroeth coordinate).
i3 : homogenizePolytope = V -> (
          R := ring V;
          n := numgens source V;
          map(R^1, R^n, {toList(n:1)}) || V);
i4 : H = fourierMotzkin homogenizePolytope vertices

o4 = (| 0  0  0  0  0  0  0  0  0  0  0  0  0  0  |, | 10 |)
      | 1  3  3  -7 3  -2 -2 1  1  -9 3  -7 -2 -7 |  | -1 |
      | 1  3  -7 3  -2 3  -2 1  -9 1  -7 3  -2 -7 |  | -1 |
      | 1  -7 3  3  -2 -2 3  -9 1  1  -7 -7 -2 3  |  | -1 |
      | -9 -7 -7 -7 -2 -2 -2 1  1  1  3  3  3  3  |  | -1 |

o4 : Sequence
i5 : transpose H#1

o5 = | 10 -1 -1 -1 -1 |

              1       5
o5 : Matrix ZZ  <-- ZZ
i6 : halfspaces = H#0;

              5       14
o6 : Matrix ZZ  <-- ZZ
i7 : numgens source halfspaces

o7 = 14
Since H#1 has one column vector, the polyhedral cone spans a 4-dimensional subspace of 5-space. Indeed, the sum of the components for each vertex is 10. The columns in the matrix halfspaces describe a complete minimal system of inequalities for permutahedron. In particular, this polytope has 14 facets.

To see the combinatorial structure of this polytope, we compute the facet-vertex incidence matrix.
i8 : inequalityMatrix = transpose submatrix(halfspaces,{1..4},)

o8 = | 1  1  1  -9 |
     | 3  3  -7 -7 |
     | 3  -7 3  -7 |
     | -7 3  3  -7 |
     | 3  -2 -2 -2 |
     | -2 3  -2 -2 |
     | -2 -2 3  -2 |
     | 1  1  -9 1  |
     | 1  -9 1  1  |
     | -9 1  1  1  |
     | 3  -7 -7 3  |
     | -7 3  -7 3  |
     | -2 -2 -2 3  |
     | -7 -7 3  3  |

              14       4
o8 : Matrix ZZ   <-- ZZ
i9 : M = inequalityMatrix * vertices

o9 = | -30 -20 -30 -10 -20 -10 -30 -20 -30 0   -20 0   -30 -10 -30 0   -10
     | -40 -40 -30 -30 -20 -20 -40 -40 -20 -20 -10 -10 -30 -30 -20 -20 0  
     | -30 -20 -40 -20 -40 -30 -20 -10 -40 -10 -40 -20 -20 0   -30 0   -30
     | -20 -10 -20 0   -10 0   -30 -20 -30 0   -20 0   -40 -20 -40 -10 -20
     | -15 -15 -15 -15 -15 -15 -10 -10 -10 -10 -10 -10 -5  -5  -5  -5  -5 
     | -10 -10 -5  -5  0   0   -15 -15 -5  -5  0   0   -15 -15 -10 -10 0  
     | -5  0   -10 0   -10 -5  -5  0   -15 0   -15 -5  -10 0   -15 0   -15
     | -20 -30 -10 -30 -10 -20 -20 -30 0   -30 0   -20 -10 -30 0   -30 0  
     | -10 -10 -20 -20 -30 -30 0   0   -20 -20 -30 -30 0   0   -10 -10 -30
     | 0   0   0   0   0   0   -10 -10 -10 -10 -10 -10 -20 -20 -20 -20 -20
     | -20 -30 -20 -40 -30 -40 -10 -20 -10 -40 -20 -40 0   -20 0   -30 -20
     | -10 -20 0   -20 0   -10 -20 -30 0   -30 0   -20 -20 -40 -10 -40 -10
     | 0   -5  0   -10 -5  -10 0   -5  0   -15 -5  -15 0   -10 0   -15 -10
     | 0   0   -10 -10 -20 -20 0   0   -20 -20 -30 -30 -10 -10 -20 -20 -40
     ------------------------------------------------------------------------
     0   -20 -10 -20 0   -10 0   |
     0   -20 -20 -10 -10 0   0   |
     -20 -10 0   -20 0   -20 -10 |
     -10 -40 -30 -40 -20 -30 -20 |
     -5  0   0   0   0   0   0   |
     0   -15 -15 -10 -10 -5  -5  |
     -10 -10 -5  -15 -5  -15 -10 |
     -10 -10 -20 0   -20 0   -10 |
     -30 0   0   -10 -10 -20 -20 |
     -20 -30 -30 -30 -30 -30 -30 |
     -30 0   -10 0   -20 -10 -20 |
     -20 -30 -40 -20 -40 -20 -30 |
     -15 -5  -10 -5  -15 -10 -15 |
     -40 -20 -20 -30 -30 -40 -40 |

              14       24
o9 : Matrix ZZ   <-- ZZ
i10 : incidence = matrix table(14,24, (i,j) -> if M_(i,j) == 0 then 1 else 0)

o10 = | 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 |
      | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 |
      | 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 |
      | 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 |
      | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 |
      | 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 |
      | 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 |
      | 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 |
      | 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 |
      | 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 |
      | 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 |
      | 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 |
      | 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 |
      | 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 |

               14       24
o10 : Matrix ZZ   <-- ZZ
i11 : vertexDegree = map(ZZ^1,ZZ^14,{toList(14:1)}) * incidence

o11 = | 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 |

               1       24
o11 : Matrix ZZ  <-- ZZ
i12 : facets = transpose(incidence * transpose map(ZZ^1,ZZ^24,{toList(24:1)}))

o12 = | 6 4 4 4 6 6 6 6 6 6 4 4 6 4 |

               1       14
o12 : Matrix ZZ  <-- ZZ
We see that each vertex has degree 3. Moreover, there are 8 hexagonal facets and 6 quadrilateral facets. For pictures, see pages 17-18 in Gunter M. Ziegler's Lectures on Polytopes, Graduate Texts in Mathematics 152, Springer-Verlag, New York, 1995.