documentation:release:4.5:group:action

Available versions of this document: latest release, release 4.11, release 4.10, release 4.9, release 4.8, release 4.7, release 4.6, release 4.5, release 4.4, release 4.3, release 4.2, release 4.1, release 4.0, release 3.6, release 3.5, nightly master

Reference documentation for older polymake versions: release 3.4, release 3.3, release 3.2

BigObject Action

from application group

parametrized object used for encoding group actions (representations).

  • GeneratorType is
    • Array<Int> for permutation groups, or
    • Matrix<Scalar> for matrix groups.
  • DomainType is
    • Int for permutation groups,
    • Vector<Scalar> for matrix groups acting on facets or vertices,
    • Set<Int> or Bitset for groups acting on simplices,
    • IncidenceMatrix for groups acting on (maximal) cones of a fan
  • OrbitGeneratorScalarType is the type of the entries of vectors that generate a geometric orbit; default Rational

These properties capture information of the object that is concerned with the action of permutation groups.


ALL_GROUP_ELEMENTS

All elements of the group, as expressed in the present action Notice that this is a temporary property; it will not be stored in any file.

Type:
Array<GeneratorType>
Example:

The following lists all permutations on 3 elements.

 > print symmetric_group(3)->PERMUTATION_ACTION->ALL_GROUP_ELEMENTS;
 0 1 2
 0 2 1
 1 0 2
 1 2 0
 2 0 1
 2 1 0


CHARACTER

The character of the action. The ordering corresponds to the columns of the CHARACTER_TABLE.

Type:
Example:

The following computes the character of the 3D-cube symmetry group acting on its vertices.

 > $p = cube(3, group=>true);
 > print $p->GROUP->VERTICES_ACTION->CHARACTER;
 8 4 2 0 0 0 0 0 0 0


CONJUGACY_CLASSES

The conjugacy classes themselves.

Type:
Array<Set<GeneratorType>>
Example:

Every conjugacy class of the alternating group on 3 elements is a singleton, since it is abelian.

 > print alternating_group(3)->PERMUTATION_ACTION->CONJUGACY_CLASSES;
 {<0 1 2>}
 {<1 2 0>}
 {<2 0 1>}


CONJUGACY_CLASS_REPRESENTATIVES

A set of representatives for each conjugacy class. The order of these representatives must agree with the implicit order of the columns of the CHARACTER_TABLE.

Type:
Array<GeneratorType>
Example:

The following lists representatives of the 3D-cube symmetry group acting on its facets.

 > $p = cube(3, group=>true);
 > print $p->GROUP->FACETS_ACTION->CONJUGACY_CLASS_REPRESENTATIVES;
 0 1 2 3 4 5
 0 1 4 5 2 3
 4 5 0 1 2 3
 1 0 2 3 4 5
 1 0 4 5 2 3
 3 2 0 1 4 5
 5 4 0 1 2 3
 1 0 3 2 4 5
 1 0 5 4 2 3
 1 0 3 2 5 4


DEGREE

The degree of the representation. For permutation groups, this is the number of permuted indices, for matrix groups it is the dimension of the vector space the group acts on

Type:
Int
Example:

The combinatorial/linear automoprhisms of a 3D-cube can be represented by its vertices or facets. The former has degree 8 (8 vertices), and the latter has degree 6 (6 facets).

 > $p = cube(3, group=>true);
 > print $p->GROUP->VERTICES_ACTION->DEGREE;
 8

print $p→GROUP→FACETS_ACTION→DEGREE;


DOMAIN_NAME

the name of the property that we act on, for example MAX_INTERIOR_SIMPLICES or INTERIOR_RIDGES

Type:
Example:

The following induces the action of the cube symmetry group on the MAX_INTERIOR_SIMPLICES

 > $p = cube(3, group=>true);
 > $a = group::induce_set_action($p, $p->GROUP->VERTICES_ACTION, "MAX_INTERIOR_SIMPLICES");
 > print $a->DOMAIN_NAME;
 MAX_INTERIOR_SIMPLICES


EQUATIONS_GENERATORS

A set of generators for equations, stored as the rows of a matrix. The list of generators may be redundant and non-canonical.

Type:
Matrix<OrbitGeneratorScalarType,NonSymmetric>

EXPLICIT_ORBIT_REPRESENTATIVES

The representatives of orbits explicitly, not via their indices.

Type:
Array<DomainType>
Example:

Consider the symmetries of a cube. These symmetres act on the cube's maximal interior simplices. Note that there are four orbits, which correspond to the four possible configurations of four vertices in general position up to symmetry. This property then returns four sets of vertices by their indices, each of which represent a single orbit.

 > $c = polytope::cube(3, group=>1);
 > induce_implicit_action($c, $c->GROUP->VERTICES_ACTION, $c->GROUP->REPRESENTATIVE_MAX_INTERIOR_SIMPLICES, "MAX_INTERIOR_SIMPLICES");
 > print $c->GROUP->IMPLICIT_SET_ACTION->EXPLICIT_ORBIT_REPRESENTATIVES;
 {0 1 2 4}
 {0 1 2 5}
 {0 1 2 7}
 {0 3 5 6}


EXPLICIT_ORBIT_REPRESENTATIVE_MATRIX

The representatives of orbits explicitly, not via their indices

Type:
Matrix<OrbitGeneratorScalarType,NonSymmetric>
Example:

We begin with a polyhedral fan. Consider the orbit fan of the original fan, which is the fan defined to be the minimal fan invariant under (in this case) the linear symmetries of the square (in homogenous coordinates), which also contains the rays and maximal cones of the original fan. It is reasonable to ask for the action of the cube on the rays. This property allows us to extract explicit rays which represent the orbits of this action.

 > $f = new PolyhedralFan(RAYS=>[[1,1,1],[1,1,0],[1,1/2,1/4]],MAXIMAL_CONES=>[[0,2],[1,2]]);
 > $of  = orbit_fan($f,polytope::cube(2,group=>1)->GROUP->MATRIX_ACTION);
 > print $of->GROUP->RAYS_ACTION->EXPLICIT_ORBIT_REPRESENTATIVE_MATRIX;
 1 -1 -1
 1 -1 0
 1 -1/2 -1/4


FACETS_GENERATORS

A set of generators for facets, stored as the rows of a matrix. This set of generators together with an action on the facets results in a set of facets, which induce a polyhedron. The list of generators may be redundant and non-canonical.

Type:
Matrix<OrbitGeneratorScalarType,NonSymmetric>
Example:

Consider the generating facets (stored as row vectors) (1,0,3), (-4,5,6), where we allow ourselves to permute the first and second coordinate to create the new facets (5,-4,6) and (0,1,3). This results in an unbounded polyhedron. The creation of the new facets may be done automatically in polymake via

 > $a = new group::PermutationAction(GENERATORS=>[[1,0,2]], FACETS_GENERATORS=>[[1,1,0,3], [1,-4,5,6]]);
 > $g = new group::Group(HOMOGENEOUS_COORDINATE_ACTION=>$a);
 > $p = new polytope::Polytope<Rational>(GROUP=>$g);
 > print $p->FACETS;
 1 0 1 3
 1 1 0 3
 1 -4 5 6
 1 5 -4 6
 > print $p->BOUNDED;
 false


GENERATORS

The generators of the group action.

Type:
Array<GeneratorType>
Example:

Any alternating group of size at least 4 is generated by two elements.

 > print alternating_group(20)->PERMUTATION_ACTION->GENERATORS;
 1 2 0 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
 0 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 1


IMAGES

The images of all domain elements under each group element: [ [ g(x) for x in D ] for g in G ]

Type:
Array<Array<DomainType>>

INDEX_OF

This is populated, when the action was induced by induce_set_action. In this case, the action corresponds to permuations of sets. However, internally (i.e. in the output of other properties) these sets are referred to by their indices in some array. This property stores the map which takes a set which is being permuted, and outputs the corresponding index in the array. This is a temporary property; it will not be stored in any file.

Type:
HashMap<DomainType,Int>
Example:

Consider the induced action on the four interior triangles of a square. The following shows an assigment from each triangle (represented as the set of its vertices) to a number between 0 and 3.

 > $p = cube(2, group=>true);
 > $a = group::induce_set_action($p, $p->GROUP->VERTICES_ACTION, "MAX_INTERIOR_SIMPLICES");
 > print $p->GROUP->SET_ACTION->INDEX_OF;
 {({1 2 3} 3) ({0 1 2} 0) ({0 2 3} 2) ({0 1 3} 1)}


INEQUALITIES_GENERATORS

A set of generators for inequalities, stored as the rows of a matrix. The list of generators may be redundant and non-canonical.

Type:
Matrix<OrbitGeneratorScalarType,NonSymmetric>
Example:

The following constructs a truncated orbit polytope. The inequalites used to generate the polytope can then be recovered by this property.

 > $p = orbit_polytope(new Matrix([ [1,6,0,5,-5,0,-5], [1,1,2,3,4,5,6] ]), group::cyclic_group(6));
 > $p->GROUP->FACETS_ACTION;
 > $tp = truncated_orbit_polytope($p, 1/2);
 > print $tp->GROUP->COORDINATE_ACTION->INEQUALITIES_GENERATORS;
 1 -3/23 -1/23 -1/23 -1/23 -1/23 1/23
 1 -1/21 -1/21 -1/21 -1/21 -1/21 -1/21
 1 -63/313 -29/939 -29/939 -29/939 47/313 -13/313
 1 -101/1651 1919/1651 -1701/1651 109/1651 2029/1651 -1601/1651
 1 1/19 21/19 -1 1/19 21/19 -1
 1 -17/167 -7/167 -7/167 3/167 -17/167 3/167
 1 -103/718 -17/718 -17/718 48/359 16/359 -93/718
 1 43/2157 2363/2157 -2057/2157 683/2157 2143/2157 -2257/2157
 1 109/1651 1769/1651 -1551/1651 529/1651 1549/1651 -1751/1651
 1 -19/219 1/219 -19/219 1/219 -19/219 1/219
 1 16769/5331 -6431/5331 -6331/5331 19189/5331 -4231/5331 -4331/5331
 1 23219/23181 -26681/23181 2339/23181 30919/23181 -19681/23181 3919/23181
 1 3 -1 -1 3 -1 -1
 -1 1 1 1 1 1 1
 111/2 -6 -1 -1 -1 -1 4
 661/2 -31 9 -11 -11 -11 -11


INPUT_LINEALITY_GENERATORS

A set of generators for input lineality, stored as the rows of a matrix. The list of generators may be redundant and non-canonical.

Type:
Matrix<OrbitGeneratorScalarType,NonSymmetric>

INPUT_RAYS_GENERATORS

A set of generators for input rays, stored as the rows of a matrix. The list of generators may be redundant and non-canonical. This may also refer to points, when this stores an action corresponding to a polytope.

Type:
Matrix<OrbitGeneratorScalarType,NonSymmetric>
Example:

Consider the point (2,1), and consider the symmetry group of linear symmetries on the square, where each symmetry is represented as a matrix. The following computes the polytope whose vertices are the image of (2,1) under the matrices corresponding to linear symmetries. You can recover (2,1) (in homogenous coordinates) by asking the underlying symmetry group for its INPUT_RAYS_GENERATORS.

 > $g = orbit_polytope(new Vector([1,1,2]), polytope::cube(2,group=>1)->GROUP->MATRIX_ACTION);
 > print $g->GROUP->MATRIX_ACTION->INPUT_RAYS_GENERATORS;
 1 1 2


IRREDUCIBLE_DECOMPOSITION

The multiplicities of each irreducible representation in this action. The ordering corresponds to the rows of the CHARACTER_TABLE

Type:
Example:

The following computes the irreducible decomposistion of the 3D-cube symmetry group acting on its vertices.

 > $p = cube(3, group=>true);
 > print $p->GROUP->VERTICES_ACTION->IRREDUCIBLE_DECOMPOSITION;
 1 0 0 1 0 0 0 0 1 1


LINEALITY_SPACE_GENERATORS

A set of generators for input lineality, stored as the rows of a matrix. The list of generators may be redundant and non-canonical.

Type:
Matrix<OrbitGeneratorScalarType,NonSymmetric>

MAXIMAL_CONES_GENERATORS

A set of generators for the maximal cones of a fan, stored in terms of indices of vertex generators. The list of generators may be redundant and non-canonical.

Type:
Example:

Consider a PolyhedralFan where we know what the rays are, and we know the symmetries of this polyhedral fan with respect to its rays and its maximal cones. We can fully describe the action on the rays, but we only know a few of the maximal cones. By applying the symmetries on the rays, we may deduce the PolyhedralFan with the least amount of maximal cones which respect the action of the symmetry group on its maximal cones.

 > $ra = new group::PermutationAction(GENERATORS=>[[0,3,2,1]]);
 > $a = new group::PermutationAction(MAXIMAL_CONES_GENERATORS=>[[0,1],[1,2]]);
 > $g = new group::Group(MAXIMAL_CONES_ACTION=>$a, RAYS_ACTION=>$ra);
 > $f = new PolyhedralFan(GROUP=>$g, RAYS=>[[1,1],[1,0],[-1,-1],[0,1]]);
 > print $f->MAXIMAL_CONES;
 {2 3}
 {1 2}
 {0 1}
 {0 3}


N_EQUATIONS_GENERATORS

The number of generators for orbits.

Type:
Int

N_FACETS_GENERATORS

The number of generators for orbits.

Type:
Int

N_INEQUALITIES_GENERATORS

The number of generators for orbits. See INEQUALITIES_GENERATORS

Type:
Int
Example:

As in the example for INEQUALITIES_GENERATORS, constructs a truncated orbit polytope. The number of inequalities used to generate the polytope may be recovered by this property.

 > $p = orbit_polytope(new Matrix([ [1,6,0,5,-5,0,-5], [1,1,2,3,4,5,6] ]), group::cyclic_group(6));
 > $p->GROUP->FACETS_ACTION;
 > $tp = truncated_orbit_polytope($p, 1/2);
 > print $tp->GROUP->COORDINATE_ACTION->N_INEQUALITIES_GENERATORS;
 16


N_INPUT_LINEALITY_GENERATORS

The number of generators for orbits.

Type:
Int

N_INPUT_RAYS_GENERATORS

The number of input ray generators, see INPUT_RAYS_GENERATORS.

Type:
Int
Example:

Consider the point (1,2,3), where we may permute the coordinates as we wish. Taking the convex hull, we arrive at a polytope. Since we permuted (1,2,3) to get the vertices, we naturally have a group associated with the polytope. This has one input ray generator (in this case a point), namely (1,2,3).

 > $g = polytope::orbit_polytope(new Vector([1,1,2,3]), group::symmetric_group(3));
 > print $g->GROUP->COORDINATE_ACTION->N_INPUT_RAYS_GENERATORS;
 1


N_LINEALITY_SPACE_GENERATORS

The number of generators for orbits.

Type:
Int

N_MAXIMAL_CONES_GENERATORS

The number of generators for orbits.

Type:
Int

N_ORBITS

The number of orbits in the domain under the group action.

Type:
Int
Example:

Under the action of the symmetric group any element may be moved to any other element.

 > print symmetric_group(20)->PERMUTATION_ACTION->N_ORBITS;
 1


N_ORBIT_REPRESENTATIVES

the number of representatives of orbits

Type:
Int

N_RAYS_GENERATORS

The number of generators for orbits. See RAYS_GENERATORS.

Type:
Int
Example:

Consider a polyhedral fan. We may the coordinates of the rays to obtain new rays. We define a new polyhedral by the rays we obtain in this way. This property lets us recover the number of generators we gave in this construction.

 > $f = new PolyhedralFan(RAYS=>[[1,1],[1,0],[-1,-1]], MAXIMAL_CONES=>[[0,1],[1,2]]);
 > $of = orbit_fan($f,[[1,0]]);
 > print $of->GROUP->HOMOGENEOUS_COORDINATE_ACTION->N_RAYS_GENERATORS;
 3


ORBITS

The orbits of the domain, represented via their indices.

Type:
Example:

Consider the linear symmetries over an Egyptian pyramid (pyramid with a square base) acting on the vertices. All four of the vertices of the base may be exchanged by 90/180-degree rotations. However, the apex vertex is a fixed point under any symmetry. This means that there should be two orbits - one of size 4, one of size 1.

 > $c = cube(2);
 > $p = pyramid($c);
 > linear_symmetries($p);
 > print $p->GROUP->VERTICES_ACTION->ORBITS;
 {0 1 2 3}
 {4}


ORBIT_REPRESENTATIVES

A collection of representatives for each orbit, represented via their indices

Type:
Example:

Consider the linear symmetries over an Egyptian pyramid (pyramid with a square base). There are two orbits - one orbit consisting of the four vertices of the base square, and one consisting of the apex vertex. This returns a vertex of the square, and the apex vertex (by their indices).

 > $s = cube(2);
 > $p = pyramid($s);
 > linear_symmetries($p);
 > print $p->GROUP->VERTICES_ACTION->ORBIT_REPRESENTATIVES;
 0 4


ORBIT_REPRESENTATIVE_LABELS

Labels for the orbit representatives

Type:

ORBIT_SIZES

The cardinality of each orbit

Type:

PERMUTATION_TO_ORBIT_ORDER

A permutation that orders the domain elements by orbits. After permutation, the first elements will be the ones in the first orbit (as ordered in ORBITS), and the ones after will be in the second orbit, and so on.

Type:
Example:

Begin with a polyhedral fan, and consider its orbit fan with respect to the linear symmetries of a square in homogenous coordinates. Then the following returns a permutation on the orbit fan's maximal cones, which encodes the sequence 0 3 4 5 1 6 7 8 2 9 10 11 12 13 14 15, which is a sequence respecting the orbit order.

 > $f = new PolyhedralFan(RAYS=>[[1,1,1],[1,1,0],[1,1/2,1/4]],MAXIMAL_CONES=>[[0,2],[1,2]]);
 > $of = orbit_fan($f,polytope::cube(2,group=>1)->GROUP->MATRIX_ACTION);
 > $of->GROUP->RAYS_ACTION;
 > print $of->GROUP->MAXIMAL_CONES_ACTION->ORBITS;
 {0 3 4 5}
 {1 6 7 8}
 {2 9 10 11 12 13 14 15}
 > print $of->GROUP->MAXIMAL_CONES_ACTION->PERMUTATION_TO_ORBIT_ORDER;
 0 4 8 1 2 3 5 6 7 9 10 11 12 13 14 15


RAYS_GENERATORS

A set of generators for rays, stored as the rows of a matrix. The list of generators may be redundant and non-canonical.

Type:
Matrix<OrbitGeneratorScalarType,NonSymmetric>
Example:

Consider a polyhedral fan. We consider the orbit fan of this fan - i.e. we consider the rays, upon which we may apply elements of a finite matrix group. This will result in new rays, and this collection of rays defines a new a new polyhedral fan. The original rays we had may be recovered using this property.

 > $f = new PolyhedralFan(RAYS=>[[1,1],[1,0],[-1,-1]], MAXIMAL_CONES=>[[0,1],[1,2]]);
 > $of = orbit_fan($f,polytope::cube(2,group=>1)->GROUP->MATRIX_ACTION);
 > print $of->GROUP->MATRIX_ACTION->RAYS_GENERATORS;
 1 1
 1 0
 -1 -1


  • documentation/release/4.5/group/action.txt
  • Last modified: 2021/09/24 09:02
  • by 127.0.0.1