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.