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 = (| 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 |
o5 : Sequence
|
i6 : halfspaces = H#0
o6 = | 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
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 = | 0 |
| 0 |
| -24 |
| 0 |
| -40 |
| 0 |
| -120 |
| -60 |
| 0 |
| -180 |
| -84 |
| -360 |
| -252 |
| -504 |
| -840 |
| 0 |
| 0 |
| 0 |
| 0 |
| 0 |
20 1
o8 : Matrix ZZ <-- ZZ
|
i9 : inequalityMatrix = transpose submatrix(halfspaces,{1..4},)
o9 = | 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
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 = | 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
o11 : Matrix ZZ <-- ZZ
|
i12 : incidence = matrix table(20,8, (i,j) -> if M_(i,j) == 0 then 1 else 0)
o12 = | 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
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. Ziegler's Lectures on Polytopes, Graduate Texts in Mathematics 152, Springer-Verlag, New York, 1995.