The
cyclic polytope is the convex hull of distinct points on the moment curve. We can either use the function
cyclicPolytope to produce the cyclic
d-polytope with
n vertices, or directly construct a matrix whose columns are the vertices of the polytope.
i1 : P = cyclicPolytope(4, 8)
o1 = P
o1 : Polyhedron
|
i2 : vertexList = vertices P
o2 = | 0 1 2 3 4 5 6 7 |
| 0 1 4 9 16 25 36 49 |
| 0 1 8 27 64 125 216 343 |
| 0 1 16 81 256 625 1296 2401 |
4 8
o2 : Matrix QQ <-- QQ
|
i3 : vertexList == map(QQ^4, QQ^8, (i,j) -> j^(i+1))
o3 = true
|
To find the halfspace representation for the convex hull of these points, we first pass from 4-space to 5-space. Specifically, we make the cyclic polytope into a polyhedral cone by placing it a height 1 (we make the extra coordinate the zeroeth coordinate).
i4 : homogenizePolytope = V -> (
R := ring V;
n := numgens source V;
map(R^1, R^n, {toList(n:1)}) || V);
|
i5 : polyCone = homogenizePolytope vertexList
o5 = | 1 1 1 1 1 1 1 1 |
| 0 1 2 3 4 5 6 7 |
| 0 1 4 9 16 25 36 49 |
| 0 1 8 27 64 125 216 343 |
| 0 1 16 81 256 625 1296 2401 |
5 8
o5 : Matrix QQ <-- QQ
|
i6 : H = fourierMotzkin polyCone
o6 = (| 0 0 -24 0 -40 0 -120 -60 0 -180 -84 -360 -252 -504 -840
| 6 12 50 20 78 30 154 112 42 216 152 342 288 450 638
| -11 -19 -35 -29 -49 -41 -71 -65 -55 -91 -83 -119 -113 -145 -179
| 6 8 10 10 12 12 14 14 14 16 16 18 18 20 22
| -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
------------------------------------------------------------------------
0 0 0 0 0 |, 0)
-210 -140 -84 -42 -14 |
107 83 61 41 23 |
-18 -16 -14 -12 -10 |
1 1 1 1 1 |
o6 : Sequence
|
i7 : halfspaceList = H#0
o7 = | 0 0 -24 0 -40 0 -120 -60 0 -180 -84 -360 -252 -504 -840 0
| 6 12 50 20 78 30 154 112 42 216 152 342 288 450 638 -210
| -11 -19 -35 -29 -49 -41 -71 -65 -55 -91 -83 -119 -113 -145 -179 107
| 6 8 10 10 12 12 14 14 14 16 16 18 18 20 22 -18
| -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1
------------------------------------------------------------------------
0 0 0 0 |
-140 -84 -42 -14 |
83 61 41 23 |
-16 -14 -12 -10 |
1 1 1 1 |
5 20
o7 : Matrix QQ <-- QQ
|
i8 : numgens source halfspaceList
o8 = 20
|
Since
H#1 is zero, the polyhedral cone spans 5-space. The columns in the matrix
halfspaceList describe a complete minimal system of inequalities for the convex hull of these points. In particular, this polytope has 20 facets.
To see the combinatorial structure of this polytope, we compute the facet-vertex incidence matrix.
i9 : inequalityVector = transpose submatrix(halfspaceList,{0},)
o9 = | 0 |
| 0 |
| -24 |
| 0 |
| -40 |
| 0 |
| -120 |
| -60 |
| 0 |
| -180 |
| -84 |
| -360 |
| -252 |
| -504 |
| -840 |
| 0 |
| 0 |
| 0 |
| 0 |
| 0 |
20 1
o9 : Matrix QQ <-- QQ
|
i10 : inequalityMatrix = transpose submatrix(halfspaceList,{1..4},)
o10 = | 6 -11 6 -1 |
| 12 -19 8 -1 |
| 50 -35 10 -1 |
| 20 -29 10 -1 |
| 78 -49 12 -1 |
| 30 -41 12 -1 |
| 154 -71 14 -1 |
| 112 -65 14 -1 |
| 42 -55 14 -1 |
| 216 -91 16 -1 |
| 152 -83 16 -1 |
| 342 -119 18 -1 |
| 288 -113 18 -1 |
| 450 -145 20 -1 |
| 638 -179 22 -1 |
| -210 107 -18 1 |
| -140 83 -16 1 |
| -84 61 -14 1 |
| -42 41 -12 1 |
| -14 23 -10 1 |
20 4
o10 : Matrix QQ <-- QQ
|
i11 : ones = map(ZZ^1,ZZ^8,{toList(8:1)})
o11 = | 1 1 1 1 1 1 1 1 |
1 8
o11 : Matrix ZZ <-- ZZ
|
i12 : M = (inequalityMatrix * vertexList) + (ones ** inequalityVector)
o12 = | 0 0 0 0 -24 -120 -360 -840 |
| 0 0 -4 0 0 -40 -180 -504 |
| -24 0 0 0 0 -24 -120 -360 |
| 0 0 -12 -12 0 0 -60 -252 |
| -40 0 0 -4 0 0 -40 -180 |
| 0 0 -24 -36 -24 0 0 -84 |
| -120 -24 0 0 0 0 -24 -120 |
| -60 0 0 -12 -12 0 0 -60 |
| 0 0 -40 -72 -72 -40 0 0 |
| -180 -40 0 0 -4 0 0 -40 |
| -84 0 0 -24 -36 -24 0 0 |
| -360 -120 -24 0 0 0 0 -24 |
| -252 -60 0 0 -12 -12 0 0 |
| -504 -180 -40 0 0 -4 0 0 |
| -840 -360 -120 -24 0 0 0 0 |
| 0 -120 -120 -72 -24 0 0 0 |
| 0 -72 -60 -24 0 0 -12 0 |
| 0 -36 -20 0 0 -20 -36 0 |
| 0 -12 0 0 -24 -60 -72 0 |
| 0 0 0 -24 -72 -120 -120 0 |
20 8
o12 : Matrix QQ <-- QQ
|
i13 : incidence = matrix table(20,8, (i,j) -> if M_(i,j) == 0 then 1 else 0)
o13 = | 1 1 1 1 0 0 0 0 |
| 1 1 0 1 1 0 0 0 |
| 0 1 1 1 1 0 0 0 |
| 1 1 0 0 1 1 0 0 |
| 0 1 1 0 1 1 0 0 |
| 1 1 0 0 0 1 1 0 |
| 0 0 1 1 1 1 0 0 |
| 0 1 1 0 0 1 1 0 |
| 1 1 0 0 0 0 1 1 |
| 0 0 1 1 0 1 1 0 |
| 0 1 1 0 0 0 1 1 |
| 0 0 0 1 1 1 1 0 |
| 0 0 1 1 0 0 1 1 |
| 0 0 0 1 1 0 1 1 |
| 0 0 0 0 1 1 1 1 |
| 1 0 0 0 0 1 1 1 |
| 1 0 0 0 1 1 0 1 |
| 1 0 0 1 1 0 0 1 |
| 1 0 1 1 0 0 0 1 |
| 1 1 1 0 0 0 0 1 |
20 8
o13 : Matrix ZZ <-- ZZ
|
From the rows of the matrix, we see Gale's evenness condition: every segment of consecutive
1's is of even length if it is not an initial or a final segment. For more information, see Theorem 0.7 in
Gunter M. Ziegler's Lectures on Polytopes, Graduate Texts in Mathematics 152, Springer-Verlag, New York, 1995.