This tutorial describes the construction of a specific rational cone in six dimensions which is due to:
The rows of this matrix describe a cone C:
> $M = new Matrix<Rational>([[0,1,0,0,0,0], > [0,0,1,0,0,0], > [0,0,0,1,0,0], > [0,0,0,0,1,0], > [0,0,0,0,0,1], > [1,0,2,1,1,2], > [1,2,0,2,1,1], > [1,1,2,0,2,1], > [1,1,1,2,0,2], > [1,2,1,1,2,0]]); > $C=new Polytope<Rational>(POINTS=>$M);
From
> print $C->HILBERT_BASIS; 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 2 1 1 2 1 1 1 2 0 2 1 1 2 0 2 1 1 2 0 2 1 1 1 2 1 1 2 0
one can see that the given generators of C form a Hilbert basis. Now we consider one particular point x. The output of the second command (all coefficients positive) shows that x is contained in the interior of C.
> $x=new Vector<Rational>([9,13,13,13,13,13]); > print $C->FACETS * $x; 17 13 13 17 13 15/7 19/8 17 13 13 17 15/7 19/8 9 4 4 4 4 4 17 19/8 15/7 19/8 15/7 19/8 11/6 15/7
The following loop iterates over all invertible 6×6 submatrices of M and computes the unique representation of x as a linear combination of the rows of the submatrix. The output (suppressed as it is too long) shows that each such linear combination requires at least one negative or one non-integral coefficient.
> foreach (@{all_subsets_of_k(range(0,9),6)}) { > $B = $M->minor($_,All); > if (det($B)) { > print lin_solve(transpose($B),$x), "\n"; > } > } 13 -5 4 4 -5 9 -5 13 -5 4 4 9 4 -5 13 -5 4 9 4 4 -5 13 -5 9 -5 4 4 -5 13 9 3 5 -1 4 4 5 8 -5 9 -1 4 5 8 -5/2 4 3/2 13/2 5/2 -1 9 -5 8 5 4 -5 17 -9 8 13 -4 4 -1 5 3 5 4 8 -9 17 -5 13 -4 3/2 4 -5/2 8 13/2 5/2 9 -5 8 -1 5 4 17 -9 8 -5 13 -4 5 -1 4 3 5 4 -1 5 3 4 5 4 -9 17 -5 8 13 -4 -5 9 -1 8 5 4 4 -5/2 8 3/2 13/2 5/2 -5/2 4 3/2 8 5/2 13/2 7 -3 7 4 1 4 7 1 3 8 5 -4 11 -7 7 8 -3 4 7 -4 8 3 5 1 8 -4 7 5 3 1 19/2 -4 11/2 8 -3/2 5/2 7 -7 11 -3 8 4 3 1 7 5 8 -4 11/2 -4 19/2 8 5/2 -3/2 5 3 4 -1 5 4 17 -5 8 -9 13 -4 9 -1 8 -5 5 4 -5/2 8 3/2 4 13/2 5/2 -5 8 -1 9 4 5 4 3/2 8 -5/2 5/2 13/2 -9 8 -5 17 -4 13 -1 4 3 5 4 5 7/2 4 7/2 4 9/2 1/2 4 4 3 5 5 -1 4 7/2 7/2 9/2 4 1/2 -1 4 8 -5 5 9 8 -1/2 7/2 17/2 -4 9/2 4 3/2 11/2 5/2 4 5/2 3/2 4 11/2 5/2 5/2 4 -1/2 8 7/2 17/2 9/2 -4 4 -1 8 -5 9 5 7/3 7/3 19/3 5/3 17/3 5/3 -7 11 7 -3 8 4 1 7 3 5 8 -4 -3 7 7 1 4 4 1 3 7 5 -4 8 -7 7 11 -3 4 8 -4 19/2 11/2 8 5/2 -3/2 -4 8 7 5 1 3 -4 7 8 3 1 5 -4 11/2 19/2 -3/2 5/2 8 7 4 11 8 -3 -7 4 7 8 11 -7 -3 15 -4 19 -11 -7 8 -4 15 19 8 -7 -11 8 3/2 4 -5/2 13/2 5/2 8 -1 9 -5 4 5 3 4 -1 5 4 5 3/2 8 -5/2 4 5/2 13/2 8 -5 17 -9 -4 13 -5 8 -9 17 -4 13 4 3 5 -1 4 5 -1 8 -5 9 4 5 11/2 4 3/2 4 5/2 5/2 8 4 -1 9 5 -5 19/3 7/3 7/3 17/3 5/3 5/3 3 4 4 -1 5 5 8 -1 4 9 -5 5 11/2 3/2 4 4 5/2 5/2 7/2 4 7/2 1/2 9/2 4 7/2 8 -1/2 9/2 17/2 -4 7/2 -1/2 8 -4 17/2 9/2 7/2 7/2 4 4 9/2 1/2 4 11/2 3/2 5/2 5/2 4 8 7/2 -1/2 17/2 9/2 -4 4 7/2 7/2 9/2 1/2 4 -1 8 4 -5 9 5 4 3 4 5 -1 5 7/2 7/2 4 4 1/2 9/2 7/3 19/3 7/3 5/3 17/3 5/3 4 8 -1 5 9 -5 -1/2 7/2 8 -4 9/2 17/2 3/2 11/2 4 4 5/2 5/2 7 4 7 4 1 -3 4 7 1 4 7 -3 15/2 7/2 8 4 -7/2 1/2 7/2 15/2 4 8 1/2 -7/2 19/2 11/2 -4 8 5/2 -3/2 8 7 -4 5 1 3 11 7 -7 8 4 -3 7 8 -4 3 1 5 7 3 1 8 -4 5 7 7 -3 4 4 1 11/2 19/2 -4 -3/2 5/2 8 3 7 1 -4 8 5 7 11 -7 4 8 -3 15/2 7/2 8 1/2 -7/2 4 4 7 1 -3 7 4 7 4 7 -3 1 4 7/2 15/2 -7/2 1/2 8 4 15 -4 19 8 -7 -11 4 7 8 -3 -7 11 7 4 11 -7 -3 8 -4 15 -11 -7 8 19 11 15 4 -7 -7 4 8 -5/2 4 3/2 5/2 13/2 -5 17 -9 8 -4 13 8 -9 17 -5 -4 13 3/2 4 -5/2 8 5/2 13/2 3 5 -1 4 4 5 8 -5 9 -1 4 5 -1 9 -5 8 5 4 4 -1 5 3 5 4 11 -7 7 4 8 -3 8 -4 7 1 5 3 19/2 -4 11/2 5/2 8 -3/2 3 1 7 -4 5 8 11/2 -4 19/2 -3/2 8 5/2 7 -3 7 4 1 4 7 1 3 8 5 -4 7 -4 8 3 5 1 7 -7 11 -3 8 4 4 7/2 7/2 1/2 9/2 4 8 -1/2 7/2 9/2 17/2 -4 4 3/2 11/2 5/2 5/2 4 -1/2 8 7/2 -4 17/2 9/2 4 -1 8 5 -5 9 7/3 7/3 19/3 5/3 5/3 17/3 7/2 4 7/2 4 9/2 1/2 4 4 3 5 5 -1 -1 4 8 -5 5 9 3/2 4 11/2 5/2 5/2 4 4 7 -3 8 11 -7 15 -4 8 19 -11 -7 -4 15 -11 19 8 -7 7 4 11 8 -3 -7 19/3 7/3 7/3 5/3 17/3 5/3 8 -1 4 5 9 -5 11/2 3/2 4 5/2 4 5/2 7/2 8 -1/2 -4 9/2 17/2 7/2 -1/2 8 9/2 -4 17/2 7/2 7/2 4 1/2 4 9/2 11/2 4 3/2 4 5/2 5/2 8 4 -1 9 5 -5 3 4 4 -1 5 5 7/2 4 7/2 1/2 9/2 4 4 7 -3 1 4 7 15/2 7/2 1/2 8 4 -7/2 7/2 15/2 -7/2 4 8 1/2 7 4 7 4 1 -3 15/2 7/2 4 8 1/2 -7/2 4 7 4 1 -3 7 7 4 4 7 -3 1 7/2 15/2 4 -7/2 1/2 8 11 4 15 4 -7 -7 19/2 -4 11/2 -3/2 5/2 8 11/2 -4 19/2 5/2 -3/2 8 7 1 3 -4 8 5 7 -4 8 1 3 5 7 -7 11 4 -3 8 11 -7 7 4 8 -3 8 -4 7 1 5 3 3 1 7 -4 5 8 7 -3 7 4 1 4 4 7 -7 -3 8 11 15 -4 -7 8 19 -11 -4 15 -7 -11 19 8 7 4 -7 11 8 -3 15/2 7/2 -7/2 1/2 8 4 7/2 15/2 1/2 -7/2 4 8 7 4 -3 7 4 1 4 7 -3 1 4 7 11 -7 4 15 4 -7 15 -4 -11 -7 8 19 -4 15 8 -7 -11 19 7 4 -3 -7 11 8 4 7 -7 -3 8 11 11 -7 -7 4 15 4 11 4 -7 -7 4 15
This means that x cannot be represented as a non-negative linear combination of any six of the given generators of C.
The following is taken from
polymake and lattice polytopes. In Christian Krattenthaler, Volker Strehl and Manuel Kauers (eds.), Proceedings of the 21th International Conference on Formal Power Series and Algebraic Combinatoric, Hagenberg, Austria, 2009, pp. 493-504.
> print $C->N_VERTICES, " ", $C->DIM; > print rows_labeled($C->VERTICES_IN_FACETS); 10 50:1 3 4 5 7 1:1 2 3 4 5 2:0 1 2 3 9 3:0 1 3 7 9 4:0 1 3 4 7 5:3 5 6 7 9 6:3 4 5 6 7 7:0 2 3 6 9 8:0 2 3 4 6 9:0 1 2 4 8 10:0 2 4 6 8 11:2 5 6 8 9 12:2 3 5 6 9 13:0 1 2 3 4 14:1 2 3 5 7 9 15:0 3 4 6 7 9 16:0 1 2 6 8 9 17:2 3 4 5 6 8 18:0 1 4 5 7 8 19:1 2 4 5 8 20:0 1 7 8 9 21:1 5 7 8 9 22:1 2 5 8 9 23:0 6 7 8 9 24:0 4 6 7 8 25:5 6 7 8 9 26:4 5 6 7 8
There are two disjoint facets covering all the vertices. Beware the numbering of facets depends on the convex hull algorithm employed.
> print $C->VERTICES_IN_FACETS->[8]; > print $C->VERTICES_IN_FACETS->[22]; {0 2 3 4 6}{1 2 5 8 9} > print rows_labeled($M); 0:0 1 0 0 0 0 1:0 0 1 0 0 0 2:0 0 0 1 0 0 3:0 0 0 0 1 0 4:0 0 0 0 0 1 5:1 0 2 1 1 2 6:1 2 0 2 1 1 7:1 1 2 0 2 1 8:1 1 1 2 0 2 9:1 2 1 1 2 0
Here is another polytope which is somewhat similar but not quite the same.
> $cross5=cross(5); > print isomorphic($C,$cross5); > print isomorphic($C->GRAPH->ADJACENCY,$cross5->GRAPH->ADJACENCY); falsetrue > print $cross5->F_VECTOR - $C->F_VECTOR; 0 0 0 5 5
Look at two facets of the five-dimensional cross polytope and their positions in the dual graph.
> print $cross5->VERTICES_IN_FACETS->[12]; > print $cross5->VERTICES_IN_FACETS->[13]; > print rows_labeled($cross5->DUAL_GRAPH->ADJACENCY); {0 2 5 7 8}{1 2 5 7 8}0:1 2 4 8 16 1:0 3 5 9 17 2:0 3 6 10 18 3:1 2 7 11 19 4:0 5 6 12 20 5:1 4 7 13 21 6:2 4 7 14 22 7:3 5 6 15 23 8:0 9 10 12 24 9:1 8 11 13 25 10:2 8 11 14 26 11:3 9 10 15 27 12:4 8 13 14 28 13:5 9 12 15 29 14:6 10 12 15 30 15:7 11 13 14 31 16:0 17 18 20 24 17:1 16 19 21 25 18:2 16 19 22 26 19:3 17 18 23 27 20:4 16 21 22 28 21:5 17 20 23 29 22:6 18 20 23 30 23:7 19 21 22 31 24:8 16 25 26 28 25:9 17 24 27 29 26:10 18 24 27 30 27:11 19 25 26 31 28:12 20 24 29 30 29:13 21 25 28 31 30:14 22 26 28 31 31:15 23 27 29 30
Now we construct a new graph by manipulating the dual graph of the cross polytope by contracting a perfect matching.
> $g=new GraphAdjacency($cross5->DUAL_GRAPH->ADJACENCY); > $g->contract_edge(12,13); > $g->contract_edge(24,26); > $g->contract_edge(17,21); > $g->contract_edge(3,11); > $g->contract_edge(6,22); > $g->squeeze;
The last command renumbers the nodes sequentially, starting from 0. This is necessary to render the graph a valid object.
> print isomorphic($C->DUAL_GRAPH->ADJACENCY,$g); true
This finally reveals the combinatorial structure: The cone C is a cone over a 5-polytope which can be obtained from the 5-dimensional cross polytope by straightening five pairs of adjacent (simplex) facets into bipyramids over 3-simplices.