<?xml version="1.0" encoding="utf-8" ?> <!-- for emacs: -*- coding: utf-8 -*- -->
<!-- Apache may like this line in the file .htaccess: AddCharset utf-8 .html -->
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1 plus MathML 2.0 plus SVG 1.1//EN" "http://www.w3.org/2002/04/xhtml-math-svg/xhtml-math-svg-flat.dtd" >
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
<head><title>Finding the facets of the cyclic polytope</title>
<link rel="stylesheet" type="text/css" href="../../../../Macaulay2/Style/doc.css"/>
</head>
<body>
<table class="buttons">
<tr>
<td><div><a href="___Finding_spthe_spfacets_spof_spthe_sppermutahedron.html">next</a> | <a href="___Applications_spto_spmultigraded_sppolynomial_springs.html">previous</a> | <a href="___Finding_spthe_spfacets_spof_spthe_sppermutahedron.html">forward</a> | <a href="___Applications_spto_spmultigraded_sppolynomial_springs.html">backward</a> | up | <a href="index.html">top</a> | <a href="master.html">index</a> | <a href="toc.html">toc</a> | <a href="http://www.math.uiuc.edu/Macaulay2/">Macaulay2 web site</a></div>
</td>
</tr>
</table>
<hr/>
<div><h1>Finding the facets of the cyclic polytope</h1>
<div>The <em>cyclic polytope</em> is the convex hull of distinct points on the moment curve. The function <tt>cyclicPolytope</tt> produces a matrix such that columns generate the cyclic <tt>d</tt>-polytope with <tt>n</tt> vertices.<table class="examples"><tr><td><pre>i1 : cyclicPolytope = (d,n) -> map(ZZ^d, ZZ^n, (i,j) -> j^(i+1));</pre>
</td></tr>
<tr><td><pre>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</pre>
</td></tr>
</table>
<p/>
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).<table class="examples"><tr><td><pre>i3 : homogenizePolytope = V -> (
R := ring V;
n := numgens source V;
map(R^1, R^n, {toList(n:1)}) || V);</pre>
</td></tr>
<tr><td><pre>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</pre>
</td></tr>
<tr><td><pre>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</pre>
</td></tr>
<tr><td><pre>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</pre>
</td></tr>
<tr><td><pre>i7 : numgens source halfspaces
o7 = 20</pre>
</td></tr>
</table>
Since <tt>H#1</tt> is zero, the polyhedral cone spans 5-space. The columns in the matrix <tt>halfspaces</tt> describe a complete minimal system of inequalities for the convex hull of these points. In particular, this polytope has 20 facets.<p/>
To see the combinatorial structure of this polytope, we compute the facet-vertex incidence matrix.<table class="examples"><tr><td><pre>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</pre>
</td></tr>
<tr><td><pre>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</pre>
</td></tr>
<tr><td><pre>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</pre>
</td></tr>
<tr><td><pre>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</pre>
</td></tr>
<tr><td><pre>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</pre>
</td></tr>
</table>
From the rows of the matrix, we see Gale's evenness condition: every segment of consecutive <tt>1</tt>'s is of even length if it is not an initial or a final segment. For more information, see Theorem 0.7 in <a href="http://www.math.tu-berlin.de/~ziegler/">Gunter M. Ziegler's</a> <em>Lectures on Polytopes</em>, Graduate Texts in Mathematics 152, Springer-Verlag, New York, 1995.</div>
</div>
</body>
</html>
