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

Finding the facets of the cyclic polytope

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.