Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision | |||
user_guide:tutorials:apps_group [2019/01/25 13:40] – ↷ Links adapted because of a move operation oroehrig | user_guide:tutorials:apps_group [2019/02/04 22:55] (current) – external edit 127.0.0.1 | ||
---|---|---|---|
Line 1: | Line 1: | ||
- | ====== Groups in polymake ====== | + | {{page> |
- | + | ||
- | '' | + | |
- | + | ||
- | Some functionality builds on '' | + | |
- | + | ||
- | + | ||
- | ===== General properties of groups ===== | + | |
- | + | ||
- | We start with the description of permutation groups in '' | + | |
- | + | ||
- | In order to access the complete set of functions dealing with groups, you should switch to the corresponding [[user_guide: | + | |
- | < | + | |
- | > application " | + | |
- | </ | + | |
- | + | ||
- | ====Conjugacy classes and character tables==== | + | |
- | + | ||
- | As we mentioned before, the only properties that are stored directly in the '' | + | |
- | + | ||
- | For the symmetric groups, we currently include the '' | + | |
- | < | + | |
- | group > print dihedral_group(20)-> | + | |
- | 1 1 1 1 1 1 1 1 | + | |
- | 1 1 1 1 1 1 -1 -1 | + | |
- | 1 -1 1 -1 1 -1 1 -1 | + | |
- | 1 -1 1 -1 1 -1 -1 1 | + | |
- | 2 1/2+1/2r5 -1/2+1/2r5 1/2-1/2r5 -1/2-1/2r5 -2 0 0 | + | |
- | 2 -1/2+1/2r5 -1/2-1/2r5 -1/2-1/2r5 -1/2+1/2r5 2 0 0 | + | |
- | 2 1/2-1/2r5 -1/2-1/2r5 1/2+1/2r5 -1/2+1/2r5 -2 0 0 | + | |
- | 2 -1/2-1/2r5 -1/2+1/2r5 -1/2+1/2r5 -1/2-1/2r5 2 0 0 | + | |
- | + | ||
- | group > print dihedral_group(22)-> | + | |
- | 1 1 1 1 1 1 1 | + | |
- | 1 1 1 1 1 1 -1 | + | |
- | 2 3788669096982621/ | + | |
- | 2 3741725795518811/ | + | |
- | 2 -2563716210467435/ | + | |
- | 2 -2949230557375555/ | + | |
- | 2 -8642344396869719/ | + | |
- | </ | + | |
- | + | ||
- | ====Important notice==== | + | |
- | + | ||
- | For internal consistency, | + | |
- | + | ||
- | =====Permutation groups===== | + | |
- | + | ||
- | An instance of a group action is created by specifying its property '' | + | |
- | < | + | |
- | group > $p = new PermutationAction(GENERATORS => [[1, | + | |
- | group > $g = new Group(PERMUTATION_ACTION => $p); | + | |
- | group > print $g-> | + | |
- | polymake: used package permlib | + | |
- | A callable C++ library for permutation computations. | + | |
- | Written by Thomas Rehn. | + | |
- | http:// | + | |
- | + | ||
- | 6 | + | |
- | </ | + | |
- | + | ||
- | Of course, there is a user function for creating symmetric groups given the degree, as well as for several other standard constructions. See the [[https:// | + | |
- | < | + | |
- | group > $h = symmetric_group(3); | + | |
- | group > print $h-> | + | |
- | 1 0 2 | + | |
- | 0 2 1 | + | |
- | </ | + | |
- | + | ||
- | + | ||
- | ====Properties of permutation actions==== | + | |
- | + | ||
- | We can compute some interesting properties of a PermutationAction: | + | |
- | < | + | |
- | group > $p = new PermutationAction(GENERATORS => [[1, | + | |
- | group > print all_group_elements($p); | + | |
- | 0 1 2 | + | |
- | 0 2 1 | + | |
- | 1 0 2 | + | |
- | 1 2 0 | + | |
- | 2 0 1 | + | |
- | 2 1 0 | + | |
- | </ | + | |
- | + | ||
- | There also exist basic functions to compute orbits and stabilizers, | + | |
- | < | + | |
- | group > $p = new PermutationAction(GENERATORS => [[1, | + | |
- | group > $s = stabilizer_of_set($p, | + | |
- | group > print $s-> | + | |
- | 0 2 1 | + | |
- | group > print $s-> | + | |
- | {0} | + | |
- | {2 1} | + | |
- | </code> | + | |
- | + | ||
- | ====A note on permutations in polymake==== | + | |
- | '' | + | |
- | < | + | |
- | 0 1 2 | + | |
- | 1 0 2 | + | |
- | </ | + | |
- | which is equal to (0 1) ∈ S< | + | |
- | < | + | |
- | group > $p = new PermutationAction(GENERATORS=> | + | |
- | group > print action_to_cyclic_notation($p); | + | |
- | (1,2), | + | |
- | (2,3) | + | |
- | group > $AGL_1_5 = group_from_cyclic_notation1(" | + | |
- | group > print $AGL_1_5-> | + | |
- | 0 2 3 4 1 | + | |
- | 1 2 4 0 3 | + | |
- | </ | + | |
- | + | ||
- | ===== Symmetry groups of polymake objects ===== | + | |
- | We switch to the polytope application for the following section: | + | |
- | < | + | |
- | group > application ' | + | |
- | </ | + | |
- | + | ||
- | ==== Polytopes ==== | + | |
- | There is more than one way to associate a group with any given polytope, depending on which kind of structural information you want to preserve. You can find some functions concerning symmetry groups of polytopes [[https:// | + | |
- | + | ||
- | One interesting group is the group of // | + | |
- | < | + | |
- | polytope > $c = cube(3); | + | |
- | polytope > $aut = automorphisms($c-> | + | |
- | polytope > print $aut; | + | |
- | (<0 1 4 5 2 3> <0 1 4 5 2 3 6 7>) | + | |
- | (<2 3 0 1 4 5> <0 2 1 3 4 6 5 7>) | + | |
- | (<1 0 2 3 4 5> <1 0 3 2 5 4 7 6>) | + | |
- | </ | + | |
- | This says that the combinatorial automorphisms are generated by three elements, one per line in the output. | + | |
- | + | ||
- | Let's wrap some of this information up in a Group object: | + | |
- | < | + | |
- | polytope > @g = map { $_-> | + | |
- | polytope > $fperm = new group:: | + | |
- | polytope > $g = new group:: | + | |
- | polytope > $g->name = " | + | |
- | polytope > $c-> | + | |
- | </ | + | |
- | + | ||
- | Now we can, e.g., compute the generators of the action on the vertices from the action on the facets: | + | |
- | < | + | |
- | polytope > print $c-> | + | |
- | 0 1 4 5 2 3 6 7 | + | |
- | 0 2 1 3 4 6 5 7 | + | |
- | 1 0 3 2 5 4 7 6 | + | |
- | </ | + | |
- | + | ||
- | Many standard constructions of polytopes come with an option to compute the canonical symmetry group during construction in a more efficient way than computing the face lattice and then solving the graph automorphism problem. If you type the name of the function you want to execute and then hit F1 twice, the available options will be displayed. You will find a description of the action that will be computed too. For example, the following creates a cube, but with the action on the facets already attached: | + | |
- | < | + | |
- | polytope > $cg = cube(3, | + | |
- | polytope > print $cg-> | + | |
- | 1 0 2 3 4 5 | + | |
- | 2 3 0 1 4 5 | + | |
- | 0 1 4 5 2 3 | + | |
- | </ | + | |
- | + | ||
- | ===Orbit polytopes=== | + | |
- | + | ||
- | Given a group with either a '' | + | |
- | < | + | |
- | polytope > $cg = cube(3, | + | |
- | polytope > print orbit_polytope(new Matrix([[1, | + | |
- | 48 | + | |
- | </ | + | |
- | See [[https:// | + | |
- | + | ||
- | ==== Quotient spaces ==== | + | |
- | + | ||
- | One way of constructing interesting topological spaces is by identifying points on the boundary of a fundamental region. Polymake can do this in the case where the fundamental region is a convex polytope. For example, a cylinder is obtained by identifying opposite sides of a square, and the [[https:// | + | |
- | + | ||
- | For example, to obtain a topological space homeomorphic to a cylinder, type | + | |
- | < | + | |
- | polytope > print $p-> | + | |
- | 2 3 0 1 | + | |
- | polytope > print $p-> | + | |
- | {0 2} | + | |
- | {1 3} | + | |
- | polytope > print $p-> | + | |
- | {{0} {1}} | + | |
- | {{0 1} {0 2} {1 3}} | + | |
- | {{0 1 2 3}} | + | |
- | polytope > print $p-> | + | |
- | 2 3 1 | + | |
- | </ | + | |
- | Thus, vertices 0,2 and vertices 1,3 of a square (a 2-dimensional cube) are identified, and after identification two vertices, three edges, and one two-dimensional face remain. In order to get a simplicial complex without identifications among the vertices, you can calculate the second barycentric subdivision by asking for the property SIMPLICIAL_COMPLEX: | + | |
- | < | + | |
- | 26 72 48 | + | |
- | polytope > print $p-> | + | |
- | ({} 0) | + | |
- | ({} 0) | + | |
- | ({} 1) | + | |
- | </ | + | |
- | + | ||
- | An easy way to make projective spaces is to identify opposite faces in a centrally symmetric polytope, using the function [[https:// | + | |
- | < | + | |
- | polytope > print $m-> | + | |
- | ({} 0) | + | |
- | ({(2 1)} 0) | + | |
- | ({} 0) | + | |
- | ({} 1) | + | |
- | </ | + | |
- | + | ||
- | As another example, the [[https:// | + | |
- | < | + | |
- | polytope > print $m-> | + | |
- | 300 600 360 60 1 | + | |
- | </ | + | |
- | Calculating the homology takes a little bit longer: | + | |
- | + | ||
- | | + | |
- | 94321 1146960 3644640 4320000 1728000 | + | |
- | | + | |
- | ({} 0) | + | |
- | ({(2 1)} 0) | + | |
- | ({} 0) | + | |
- | ({(2 1)} 0) | + | |
- | ({} 0) | + | |
- | + | ||
- | + | ||
- | ===== Matrix groups ===== | + | |
- | + | ||
- | Let's switch back to '' | + | |
- | < | + | |
- | polytope > application ' | + | |
- | </ | + | |
- | + | ||
- | Polymake can also deal with groups given by matrices that act on the ambient space. They are stored in the property '' | + | |
- | < | + | |
- | group > $d = polytope:: | + | |
- | group > $d-> | + | |
- | type: Group as Polytope< | + | |
- | + | ||
- | VERTICES_ACTION | + | |
- | type: PermutationAction< | + | |
- | + | ||
- | group > $d-> | + | |
- | + | ||
- | group > print $d-> | + | |
- | <1 0 0 0 | + | |
- | 0 -1 0 0 | + | |
- | 0 0 1 0 | + | |
- | 0 0 0 1 | + | |
- | > | + | |
- | <1 0 0 0 | + | |
- | 0 1/4-1/4r5 1/2 -1/ | + | |
- | 0 1/2 1/4+1/4r5 -1/ | + | |
- | 0 -1/4-1/4r5 -1/4+1/4r5 1/2 | + | |
- | > | + | |
- | <1 0 0 0 | + | |
- | 0 1 0 0 | + | |
- | 0 0 1 0 | + | |
- | 0 0 0 -1 | + | |
- | > | + | |
- | </ | + | |
- | As we can see, the property '' | + | |
- | + | ||
- | Of course, not every combinatorial symmetry group of a concrete point configuration has a realization as a matrix group, in which case the above computation will fail. A sure-fire way to get a matrix group is to calculate the '' | + | |
- | + | ||
- | ====Orbits==== | + | |
- | + | ||
- | Once you have a matrix group, you may calculate the orbit of an arbitrary vector under it: | + | |
- | < | + | |
- | group > $s = symmetric_group(3); | + | |
- | + | ||
- | group > $a = $s-> | + | |
- | + | ||
- | group > print orbit($a-> | + | |
- | {<3 2 1> <1 2 3> <2 1 3> <1 3 2> <3 1 2> <2 3 1>} | + | |
- | </ | + | |
- | + | ||
- | ====Invariant polynomials==== | + | |
- | + | ||
- | Or you can regard the matrices as acting on polynomials, | + | |
- | + | ||
- | [ 1 1 ] | + | |
- | [ 1 -1 ] . ( x^2 - y^2 ) = ( x + y )^2 - ( x - y )^2. | + | |
- | + | ||
- | You can calculate the polynomials left invariant by the matrices sending the vertices of a dodecahedron into each other as follows: | + | |
- | < | + | |
- | group > $d = polytope:: | + | |
- | + | ||
- | group > $d-> | + | |
- | + | ||
- | group > print join " | + | |
- | x_0^2 + x_1^2 + x_2^2 | + | |
- | x_0^4 + 2*x_0^2*x_1^2 + 2*x_0^2*x_2^2 + x_1^4 + 2*x_1^2*x_2^2 + x_2^4 | + | |
- | </ | + | |
- | This is consistent with the Molien series of this action starting out as 1 + x^2 + x^4 + 2x^6 + ..., so in particular no invariant of degree exactly 5 is found. See [[http:// | + | |
- | + | ||
- | =====Decomposition into irreps, and bases of isotypic components===== | + | |
- | + | ||
- | You can calculate | + | |
- | + | ||
- | * the character of a permutation action or matrix action, | + | |
- | * the decomposition of the action into irreducible representations, | + | |
- | * the projection operators to (and vector space bases of) the isotypic components. | + | |
- | + | ||
- | For '' | + | |
- | < | + | |
- | group > print $d-> | + | |
- | -2 0 2 1 4 1 1/2-1/2r5 3/2-1/2r5 1/2+1/2r5 3/2+1/2r5 | + | |
- | + | ||
- | group > print irreducible_decomposition($d-> | + | |
- | polymake: | + | |
- | </ | + | |
- | This didn't work, because the dodecahedron doesn' | + | |
- | + | ||
- | It does work, for instance, for the symmetric group of order 5! (in fact, up to order 7!): | + | |
- | < | + | |
- | group > $s=symmetric_group(5); | + | |
- | + | ||
- | group > print $s-> | + | |
- | 1 -1 1 1 -1 -1 1 | + | |
- | 4 -2 0 1 1 0 -1 | + | |
- | 5 -1 1 -1 -1 1 0 | + | |
- | 6 0 -2 0 0 0 1 | + | |
- | 5 1 1 -1 1 -1 0 | + | |
- | 4 2 0 1 -1 0 -1 | + | |
- | 1 1 1 1 1 1 1 | + | |
- | + | ||
- | group > $s-> | + | |
- | + | ||
- | group > print $s-> | + | |
- | 5 3 1 2 0 1 0 | + | |
- | + | ||
- | group > print irreducible_decomposition($s-> | + | |
- | 0 0 0 0 0 1 1 | + | |
- | </ | + | |
- | So the regular (permutation) representation decomposes into one copy each of the invariant subspaces associated to the characters in the last two lines of the character table. The first entries there, 4 and 1, say that these components should have dimensions 4 and 1, respectively: | + | |
- | < | + | |
- | group > print isotypic_basis($s, | + | |
- | 4/5 -1/5 -1/5 -1/5 -1/5 | + | |
- | -1/5 4/5 -1/5 -1/5 -1/5 | + | |
- | -1/5 -1/5 4/5 -1/5 -1/5 | + | |
- | -1/5 -1/5 -1/5 4/5 -1/5 | + | |
- | + | ||
- | group > print isotypic_basis($s, | + | |
- | 1/5 1/5 1/5 1/5 1/5 | + | |
- | </ | + | |