<?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 permutahedron</title>
<link rel="stylesheet" type="text/css" href="../../../../Macaulay2/Style/doc.css"/>
</head>
<body>
<table class="buttons">
<tr>
<td><div><a href="_fourier__Motzkin.html">next</a> | <a href="___Finding_spthe_spfacets_spof_spthe_spcyclic_sppolytope.html">previous</a> | <a href="_fourier__Motzkin.html">forward</a> | <a href="___Finding_spthe_spfacets_spof_spthe_spcyclic_sppolytope.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 permutahedron</h1>
<div>The <em>permutahedron</em> is the convex hull of all vectors that are obtained by permuting the coordinates of the vector <tt>(1,2, ..., d)</tt>. The function <tt>permutahedron</tt> produces a matrix such that columns generate the cyclic <tt>d</tt> permutahedron in <tt>(d+1)</tt>-space.<table class="examples"><tr><td><pre>i1 : permutahedron = d -> transpose matrix permutations toList(1..d+1);</pre>
</td></tr>
<tr><td><pre>i2 : vertices = permutahedron 3
o2 = | 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 4 |
| 2 2 3 3 4 4 1 1 3 3 4 4 1 1 2 2 4 4 1 1 2 2 3 3 |
| 3 4 2 4 2 3 3 4 1 4 1 3 2 4 1 4 1 2 2 3 1 3 1 2 |
| 4 3 4 2 3 2 4 3 4 1 3 1 4 2 4 1 2 1 3 2 3 1 2 1 |
4 24
o2 : Matrix ZZ <--- ZZ</pre>
</td></tr>
</table>
<p/>
To find the halfspace representation for permutahedron, we first pass from 4-space to 5-space. Specifically, we make the permutahedron 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 : H = fourierMotzkin homogenizePolytope vertices
o4 = (| 0 0 0 0 0 0 0 0 0 0 0 0 0 0 |, | 10 |)
| 1 3 3 -7 3 -2 -2 1 1 -9 3 -7 -2 -7 | | -1 |
| 1 3 -7 3 -2 3 -2 1 -9 1 -7 3 -2 -7 | | -1 |
| 1 -7 3 3 -2 -2 3 -9 1 1 -7 -7 -2 3 | | -1 |
| -9 -7 -7 -7 -2 -2 -2 1 1 1 3 3 3 3 | | -1 |
o4 : Sequence</pre>
</td></tr>
<tr><td><pre>i5 : transpose H#1
o5 = | 10 -1 -1 -1 -1 |
1 5
o5 : Matrix ZZ <--- ZZ</pre>
</td></tr>
<tr><td><pre>i6 : halfspaces = H#0;
5 14
o6 : Matrix ZZ <--- ZZ</pre>
</td></tr>
<tr><td><pre>i7 : numgens source halfspaces
o7 = 14</pre>
</td></tr>
</table>
Since <tt>H#1</tt> has one column vector, the polyhedral cone spans a 4-dimensional subspace of 5-space. Indeed, the sum of the components for each vertex is 10. The columns in the matrix <tt>halfspaces</tt> describe a complete minimal system of inequalities for permutahedron. In particular, this polytope has 14 facets.<p/>
To see the combinatorial structure of this polytope, we compute the facet-vertex incidence matrix.<table class="examples"><tr><td><pre>i8 : inequalityMatrix = transpose submatrix(halfspaces,{1..4},)
o8 = | 1 1 1 -9 |
| 3 3 -7 -7 |
| 3 -7 3 -7 |
| -7 3 3 -7 |
| 3 -2 -2 -2 |
| -2 3 -2 -2 |
| -2 -2 3 -2 |
| 1 1 -9 1 |
| 1 -9 1 1 |
| -9 1 1 1 |
| 3 -7 -7 3 |
| -7 3 -7 3 |
| -2 -2 -2 3 |
| -7 -7 3 3 |
14 4
o8 : Matrix ZZ <--- ZZ</pre>
</td></tr>
<tr><td><pre>i9 : M = inequalityMatrix * vertices
o9 = | -30 -20 -30 -10 -20 -10 -30 -20 -30 0 -20 0 -30 -10 -30 0 -10
| -40 -40 -30 -30 -20 -20 -40 -40 -20 -20 -10 -10 -30 -30 -20 -20 0
| -30 -20 -40 -20 -40 -30 -20 -10 -40 -10 -40 -20 -20 0 -30 0 -30
| -20 -10 -20 0 -10 0 -30 -20 -30 0 -20 0 -40 -20 -40 -10 -20
| -15 -15 -15 -15 -15 -15 -10 -10 -10 -10 -10 -10 -5 -5 -5 -5 -5
| -10 -10 -5 -5 0 0 -15 -15 -5 -5 0 0 -15 -15 -10 -10 0
| -5 0 -10 0 -10 -5 -5 0 -15 0 -15 -5 -10 0 -15 0 -15
| -20 -30 -10 -30 -10 -20 -20 -30 0 -30 0 -20 -10 -30 0 -30 0
| -10 -10 -20 -20 -30 -30 0 0 -20 -20 -30 -30 0 0 -10 -10 -30
| 0 0 0 0 0 0 -10 -10 -10 -10 -10 -10 -20 -20 -20 -20 -20
| -20 -30 -20 -40 -30 -40 -10 -20 -10 -40 -20 -40 0 -20 0 -30 -20
| -10 -20 0 -20 0 -10 -20 -30 0 -30 0 -20 -20 -40 -10 -40 -10
| 0 -5 0 -10 -5 -10 0 -5 0 -15 -5 -15 0 -10 0 -15 -10
| 0 0 -10 -10 -20 -20 0 0 -20 -20 -30 -30 -10 -10 -20 -20 -40
------------------------------------------------------------------------
0 -20 -10 -20 0 -10 0 |
0 -20 -20 -10 -10 0 0 |
-20 -10 0 -20 0 -20 -10 |
-10 -40 -30 -40 -20 -30 -20 |
-5 0 0 0 0 0 0 |
0 -15 -15 -10 -10 -5 -5 |
-10 -10 -5 -15 -5 -15 -10 |
-10 -10 -20 0 -20 0 -10 |
-30 0 0 -10 -10 -20 -20 |
-20 -30 -30 -30 -30 -30 -30 |
-30 0 -10 0 -20 -10 -20 |
-20 -30 -40 -20 -40 -20 -30 |
-15 -5 -10 -5 -15 -10 -15 |
-40 -20 -20 -30 -30 -40 -40 |
14 24
o9 : Matrix ZZ <--- ZZ</pre>
</td></tr>
<tr><td><pre>i10 : incidence = matrix table(14,24, (i,j) -> if M_(i,j) == 0 then 1 else 0)
o10 = | 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 |
| 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 |
| 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 |
| 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 |
| 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 |
| 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 |
| 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 |
| 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 |
| 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 |
| 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 |
| 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 |
| 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 |
| 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 |
| 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 |
14 24
o10 : Matrix ZZ <--- ZZ</pre>
</td></tr>
<tr><td><pre>i11 : vertexDegree = map(ZZ^1,ZZ^14,{toList(14:1)}) * incidence
o11 = | 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 |
1 24
o11 : Matrix ZZ <--- ZZ</pre>
</td></tr>
<tr><td><pre>i12 : facets = transpose(incidence * transpose map(ZZ^1,ZZ^24,{toList(24:1)}))
o12 = | 6 4 4 4 6 6 6 6 6 6 4 4 6 4 |
1 14
o12 : Matrix ZZ <--- ZZ</pre>
</td></tr>
</table>
We see that each vertex has degree 3. Moreover, there are 8 hexagonal facets and 6 quadrilateral facets. For pictures, see pages 17-18 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>
