The
cyclic polytope is the convex hull of distinct points on the moment curve. The function
cyclicPolytope produces a matrix such that columns generate the cyclic
d-polytope with
n vertices.
i1 : cyclicPolytope = (d,n) -> map(ZZ^d, ZZ^n, (i,j) -> j^(i+1));
|
i2 : vertices = cyclicPolytope(4,8)
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 ZZ <--- ZZ
|
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).
i3 : homogenizePolytope = V -> (
R := ring V;
n := numgens source V;
map(R^1, R^n, {toList(n:1)}) || V);
|
i4 : polyCone = homogenizePolytope vertices
o4 = | 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
o4 : Matrix ZZ <--- ZZ
|
i5 : H = fourierMotzkin polyCone
o5 = (| -840 -504 -252 -84 0 0 0 0 0 0 -360 -180 -60 0 -120
| 638 450 288 152 -210 42 -140 -84 -42 -14 342 216 112 30 154
| -179 -145 -113 -83 107 -55 83 61 41 23 -119 -91 -65 -41 -71
| 22 20 18 16 -18 14 -16 -14 -12 -10 18 16 14 12 14
| -1 -1 -1 -1 1 -1 1 1 1 1 -1 -1 -1 -1 -1
------------------------------------------------------------------------
-40 0 -24 0 0 |, 0)
78 20 50 12 6 |
-49 -29 -35 -19 -11 |
12 10 10 8 6 |
-1 -1 -1 -1 -1 |
o5 : Sequence
|
i6 : halfspaces = H#0
o6 = | -840 -504 -252 -84 0 0 0 0 0 0 -360 -180 -60 0 -120
| 638 450 288 152 -210 42 -140 -84 -42 -14 342 216 112 30 154
| -179 -145 -113 -83 107 -55 83 61 41 23 -119 -91 -65 -41 -71
| 22 20 18 16 -18 14 -16 -14 -12 -10 18 16 14 12 14
| -1 -1 -1 -1 1 -1 1 1 1 1 -1 -1 -1 -1 -1
------------------------------------------------------------------------
-40 0 -24 0 0 |
78 20 50 12 6 |
-49 -29 -35 -19 -11 |
12 10 10 8 6 |
-1 -1 -1 -1 -1 |
5 20
o6 : Matrix ZZ <--- ZZ
|
i7 : numgens source halfspaces
o7 = 20
|
Since
H#1 is zero, the polyhedral cone spans 5-space. The columns in the matrix
halfspaces 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.
i8 : inequalityVector = transpose submatrix(halfspaces,{0},)
o8 = | -840 |
| -504 |
| -252 |
| -84 |
| 0 |
| 0 |
| 0 |
| 0 |
| 0 |
| 0 |
| -360 |
| -180 |
| -60 |
| 0 |
| -120 |
| -40 |
| 0 |
| -24 |
| 0 |
| 0 |
20 1
o8 : Matrix ZZ <--- ZZ
|
i9 : inequalityMatrix = transpose submatrix(halfspaces,{1..4},)
o9 = | 638 -179 22 -1 |
| 450 -145 20 -1 |
| 288 -113 18 -1 |
| 152 -83 16 -1 |
| -210 107 -18 1 |
| 42 -55 14 -1 |
| -140 83 -16 1 |
| -84 61 -14 1 |
| -42 41 -12 1 |
| -14 23 -10 1 |
| 342 -119 18 -1 |
| 216 -91 16 -1 |
| 112 -65 14 -1 |
| 30 -41 12 -1 |
| 154 -71 14 -1 |
| 78 -49 12 -1 |
| 20 -29 10 -1 |
| 50 -35 10 -1 |
| 12 -19 8 -1 |
| 6 -11 6 -1 |
20 4
o9 : Matrix ZZ <--- ZZ
|
i10 : ones = map(ZZ^1,ZZ^8,{toList(8:1)})
o10 = | 1 1 1 1 1 1 1 1 |
1 8
o10 : Matrix ZZ <--- ZZ
|
i11 : M = (inequalityMatrix * vertices) + (ones ** inequalityVector)
o11 = | -840 -360 -120 -24 0 0 0 0 |
| -504 -180 -40 0 0 -4 0 0 |
| -252 -60 0 0 -12 -12 0 0 |
| -84 0 0 -24 -36 -24 0 0 |
| 0 -120 -120 -72 -24 0 0 0 |
| 0 0 -40 -72 -72 -40 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 |
| -360 -120 -24 0 0 0 0 -24 |
| -180 -40 0 0 -4 0 0 -40 |
| -60 0 0 -12 -12 0 0 -60 |
| 0 0 -24 -36 -24 0 0 -84 |
| -120 -24 0 0 0 0 -24 -120 |
| -40 0 0 -4 0 0 -40 -180 |
| 0 0 -12 -12 0 0 -60 -252 |
| -24 0 0 0 0 -24 -120 -360 |
| 0 0 -4 0 0 -40 -180 -504 |
| 0 0 0 0 -24 -120 -360 -840 |
20 8
o11 : Matrix ZZ <--- ZZ
|
i12 : incidence = matrix table(20,8, (i,j) -> if M_(i,j) == 0 then 1 else 0)
o12 = | 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 0 0 0 0 1 1 1 |
| 1 1 0 0 0 0 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 |
| 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 0 |
| 0 0 1 1 1 1 0 0 |
| 0 1 1 0 1 1 0 0 |
| 1 1 0 0 1 1 0 0 |
| 0 1 1 1 1 0 0 0 |
| 1 1 0 1 1 0 0 0 |
| 1 1 1 1 0 0 0 0 |
20 8
o12 : 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. Zielger's Lectures on Polytopes, Graduate Texts in Mathematics 152, Springer-Verlag, New York, 1995.