application group

Available versions of this document: latest release, release 4.13, release 4.12, 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

The application group provides basic functionality for working with permutation groups. An object of type Group records the abstract properties of the groups that do not depend on any particular representation, such as ORDER, CHARACTER_TABLE and CONJUGACY_CLASS_SIZES. Moreover, it can contain several subobjects of type PermutationAction, PermutationActionOnSets or ImplicitActionOnSets that encode representations of the group. (We use the terms action and representation interchangeably). If the group object is not contained inside a Cone or Polytope, the representation in question is encoded as a PERMUTATION_ACTION, SET_ACTION or IMPLICIT_SET_ACTION, otherwise it may be encoded more specifically as a RAY_ACTION, FACET_ACTION, COORDINATE_ACTION, etc. Different representations of the same group are convertible among each other either via specific rules, or by using the function induced_action, for example.

imports from:

application common

Action:
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
Group:
Object encoding a finite group.
ImplicitActionOnSets:
derived object encoding an action of a permutation group on a collection of sets, but where only one representative of each orbit is stored explicitly
LayeredPermutationAction:
object for encoding the separate actions of a group on a collection of sets, induced by the same generators
MatrixActionOnVectors:
derived object for matrix groups
PermutationAction:
derived objects for permutation representations
PermutationActionOnSets:
derived object for permuting collections of sets

These functions are concerned with orbits in groups.

are_in_same_orbit(PermutationAction a, Vector v1, Vector v2)

Checks whether vectors v1 and v2 are in the same orbit with respect to the (coordinate) action of group.

Parameters:: PermutationAction a: the permutation group acting on coordinates; Vector v1; Vector v2
Returns:: Bool

orbit<action_type>(Array G, Any O)

The orbit of an object O under a group generated by G. The action_type defines how the elements of the group work on O.

Type Parameters:

action_type: controls the on_container the default. The group acts on the elements of a given container, which also could be container. on_elements for this the group will act on the deepest elements inside a given container with respect to the type of the group elements on_rows For this O should be a matrix so that the group can act on the rows of O. on_cols like on_rows this require a matrix so that the group can act on its columns on_nonhomog_cols also require that O is a matrix on whose columns the group generated by G acts. The 0-th column stay fixed.

Parameters:

Array G: Group generators

Any O: (mostly Array, Vector, Matrix or Set)

Returns:

Set<Any>

Example:

 > $permutationgroup = new Array<Array<Int>>([[1,2,3,0]]);
 > $set = new Set<Set<Int>>([[0,1],[2,3]]);
 > print orbit<on_elements>($permutationgroup, $set);
 {{{0 1} {2 3}} {{0 3} {1 2}}}

orbit<action_type>(Group G, Any C)

The orbit of a container C under a group G.

Type Parameters:: action_type: by default on_container can also be on_elements, on_rows, on_cols or on_nonhomog_cols. Call help “<action_type>”; for more information about this.
Parameters:: Group G; Any C
Returns:: Set<Any>

orbit<Scalar>(Array<Matrix<Scalar>> G, Vector<Scalar> V)

The orbit of a vector V under a group generated by G.

Type Parameters:: Scalar: S the number type
Parameters:: Array<Matrix<Scalar>> G: Generators of the group; Vector<Scalar> V
Returns:: Set

orbit_permlib(PermutationAction G, Set S)

The orbit of a set S under a group defined by G.

Parameters:

PermutationAction G

Set S

Returns:

Set

Example:

 > $G=new Group(PERMUTATION_ACTION=>(new PermutationAction(GENERATORS=>[[1,2,0]])));
 > print $G->PERMUTATION_ACTION->ALL_GROUP_ELEMENTS;
 0 1 2
 1 2 0
 2 0 1

 > $S=new Set<Int>(1,2);
 > print orbit_permlib($G->PERMUTATION_ACTION, $S);
 {{0 1} {0 2} {1 2}}

orbit_permlib(PermutationAction G, Set<Set> S)

The orbit of a set S of sets under a group given by G.

Parameters:

PermutationAction G

Set<Set> S

Returns:

Set

Example:

 > $G=new PermutationAction(new PermutationAction(GENERATORS=>[[2,0,1]]));
 > print $G->ALL_GROUP_ELEMENTS;
 0 1 2
 2 0 1
 1 2 0

 > $S=new Set<Set<Int>>(new Set<Int>(1,2), new Set<Int>(0,2));
 > print orbit_permlib($G, $S);
 {{{0 1} {0 2}} {{0 1} {1 2}} {{0 2} {1 2}}}

orbit_representatives(Array<GeneratorType> G)

The indices of one representative for each orbit under the group generated by G.

Parameters:: Array<GeneratorType> G: Group generators
Returns:: Array<Int>

orbits_in_orbit_order(PermutationAction a, Matrix M)

Computes the orbit of the rows of the matrix mat under the permutation action on coordinates action.

Parameters:: PermutationAction a: an action of a group of coordinate permutations; Matrix M: some input vectors
Returns:: List

orbits_of_action(PermutationAction a)

Computes the orbits of the basic set under a.

Parameters:: PermutationAction a: a permutation action of a group
Returns:: Array<Set<Int>>

orbits_of_coordinate_action(PermutationAction a, Matrix<Scalar> M)

Computes the orbits of the vectors (homogenized) of the rows of a matrix M by permuting the coordinates of the vectors (skipping the homogenizing coordinate). The group must act on the set of vectors, and the rows of the matrix must contain the entire orbit.

Parameters:: PermutationAction a: an action of a group acting by permuting the coordinates; Matrix<Scalar> M: a matrix on whose columns the group acts by coordinate permutation
Returns:: Array<Set<Int>>

orbits_of_induced_action(PermutationAction a, IncidenceMatrix I)

Computes the orbits of a set on which an action is induced. The incidences between the domain elements and the elements in the set are given by an incidence matrix inc.

Parameters:: PermutationAction a: an action of a group; IncidenceMatrix I: the incidences between domain elements and elements on which an action is induced
Returns:: Array<Set<Int>>

With these clients you can produce objects of type Group – groups from certain parameterized families, as stabilizers of sets in other groups or from different kinds of cycle notations.

alternating_group(Int d)

Constructs an alternating group of given degree d.

Parameters:: Int d: degree of the alternating group
Returns:: Group

cube_group(Int d)

Constructs the symmetry group of a d-cube, acting on vertices, for 1 ⇐ d ⇐ 6 (for the moment), along with the corresponding character table and conjugacy class representatives.

Parameters:

Int d: the dimension of the cube

Returns:

Group

Example:

The following calculates the orbits of the vertices on a cube.

 > $g = cube_group(3);
 > print $g->PERMUTATION_ACTION->ORBITS;
 {0 1 2 3 4 5 6 7}

cyclic_group(Int d)

Constructs a cyclic group of given degree d.

Parameters:: Int d: degree of the cyclic group
Returns:: Group

dihedral_group(Int o)

Constructs a dihedral group of a given order o. If the order is 2, 4, 6, 8, 10, 12, 16, 20 or 24, the character table is exact, otherwise some entries are mutilated rational approximations of algebraic numbers.

Parameters:: Int o: order of the dihedral group that acts on a regular (o/2)-gon
Returns:: Group

group_from_cyclic_notation0(String generators)

Constructs a group from a string with generators in cyclic notation. All numbers in the string are 0-based. Example: “(0,2)(1,3)”

Parameters:

String generators: the group generators in cyclic notation

Returns:

Group

Example:

The following constructs a group with 2 generators.

 > $g = group_from_cyclic_notation0("(0,2)(1,3),(0,3)");
 > print $g->PERMUTATION_ACTION->GENERATORS;
 2 3 0 1
 3 1 2 0

group_from_cyclic_notation1(String generators)

Constructs a group from a string with generators in cyclic notation. All numbers in the string are 1-based.

Parameters:

String generators: the group generators in cyclic notation

Returns:

Group

Example:

The following constructs a group with 2 generators.

 > $g = group_from_cyclic_notation1("(1,3)(2,4),(1,4)");
 > print $g->PERMUTATION_ACTION->GENERATORS;
 2 3 0 1
 3 1 2 0

group_from_permlib_cyclic_notation(Array<String> gens, Int degree)

Constructs a Group from generators given in permlib cyclic notation, i.e., indices separated by whitespace, generators separated by commas.

Parameters:: Array<String> gens: generators of the permutation group in permlib cyclic notation; Int degree: the degree of the permutation group
Returns:: Group

stabilizer_of_set(PermutationAction a, Set S)

Computes the subgroup of group which stabilizes the given set of indices set.

Parameters:: PermutationAction a: the action of a permutation group; Set S: the set to be stabilized
Returns:: Group

stabilizer_of_vector(PermutationAction a, Vector v)

Computes the subgroup of G which stabilizes the given vector v.

Parameters:: PermutationAction a: the action of a permutation group; Vector v: the vector to be stabilized
Returns:: Group

symmetric_group(Int d)

Constructs a symmetric group of given degree d.

Parameters:: Int d: degree of the symmetric group
Returns:: Group

These functions are dealing with symmetries.

all_group_elements<Scalar>(MatrixActionOnVectors<Scalar> action)

Compute all elements of a given group, expressed as a matrix group action.

Type Parameters:

Scalar: S the underlying number type

Parameters:

MatrixActionOnVectors<Scalar> action: the action of a permutation group

Returns:

Set<Matrix<Scalar>>

Example:

To generate all elements of the regular representation of S_3, type

 > print all_group_elements(symmetric_group(3)->REGULAR_REPRESENTATION);
 <0 0 1
 0 1 0
 1 0 0
 >
 <0 0 1
 1 0 0
 0 1 0
 >
 <0 1 0
 0 0 1
 1 0 0
 >
 <0 1 0
 1 0 0
 0 0 1
 >
 <1 0 0
 0 0 1
 0 1 0
 >
 <1 0 0
 0 1 0
 0 0 1
 >

automorphism_group(GraphAdjacency graph)

Find the automorphism group of the graph.

Parameters:: GraphAdjacency graph
Returns:: Group

automorphism_group(IncidenceMatrix<NonSymmetric> m, Bool on_rows)

Find the automorphism group of the incidence matrix.

Parameters:: IncidenceMatrix<NonSymmetric> m; Bool on_rows: true (default) for row action
Returns:: Group

col_to_row_action(Matrix M, Array<Array> p)

If the action of some permutations on the entries of the rows maps each row of a matrix to another row we obtain an induced action on the set of rows of the matrix. Considering the rows as points this corresponds to the action on the points induced by the action of some permutations on the coordinates.

Parameters:: Matrix M; Array<Array> p: the permutations acting of the rows
Returns:: Array<Array>

conjugacy_class<Element>(Action action, Element e)

Compute the conjugacy class of a group element under a given action

Type Parameters:: Element: E the underlying element type
Parameters:: Action action: the action of the group; Element e: the element to be acted upon
Returns:: Set<Element>

conjugacy_class<Scalar>(MatrixActionOnVectors<Scalar> action, Matrix<Scalar> e)

Compute the conjugacy class of a group element under a given action

Type Parameters:: Scalar: E the underlying number type
Parameters:: MatrixActionOnVectors<Scalar> action: the action of the group; Matrix<Scalar> e: the element to be acted upon
Returns:: Set<Matrix<Scalar>>

group_left_multiplication_table(Group G)

Calculate the left multiplication table of a group action, in which GMT[g][h] = hg

Parameters:: Group G
Options:: String action: which action to take for the calculation; default PERMUTATION_ACTION
Returns:: Array<Array<Int>>

group_right_multiplication_table(Group G)

Calculate the right multiplication table of a group action, in which GMT[g][h] = gh

Parameters:: Group G
Options:: String action: which action to take for the calculation; default PERMUTATION_ACTION
Returns:: Array<Array<Int>>

implicit_character(ImplicitActionOnSets A)

Calculate character of an implicit action

Parameters:: ImplicitActionOnSets A: the given action
Returns:: Array<Int>

induce_implicit_action(PermutationAction original_action, String property)

Construct an implicit action of the action induced on a collection of sets. Only a set of orbit representatives is stored, not the full induced action.

Parameters:

PermutationAction original_action: the action of the group on indices

String property: the name of a property that describes an ordered list of sets on which the group should act

Returns:

ImplicitActionOnSets

Example:

To construct the implicit action of the symmetry group of a cube on its maximal simplices, type:

 > $c=cube(3, group=>1, character_table=>0);
 > group::induce_implicit_action($c, $c->GROUP->VERTICES_ACTION, $c->GROUP->REPRESENTATIVE_MAX_INTERIOR_SIMPLICES, "MAX_INTERIOR_SIMPLICES")->properties();
 name: induced_implicit_action_of_ray_action_on_MAX_INTERIOR_SIMPLICES
 type: ImplicitActionOnSets
 description: induced from ray_action on MAX_INTERIOR_SIMPLICES
 
 DOMAIN_NAME
 MAX_INTERIOR_SIMPLICES
 
 EXPLICIT_ORBIT_REPRESENTATIVES
 {0 1 2 4}
 {0 1 2 5}
 {0 1 2 7}
 {0 3 5 6}
 
 
 GENERATORS
 1 0 3 2 5 4 7 6
 0 2 1 3 4 6 5 7
 0 1 4 5 2 3 6 7

induce_set_action(Cone c, PermutationAction a, String domain)

Construct the induced action of a permutation action on a property that is an ordered collection of sets, such as MAX_INTERIOR_SIMPLICES

Parameters:

Cone c: the cone or polytope

PermutationAction a: a permutation action on, for example, the vertex indices

String domain: the property the induced action should act upon

Returns:

PermutationActionOnSets

Example:

 > $c=cube(3, group=>1, character_table=>0);
 > group::induce_set_action($c, $c->GROUP->VERTICES_ACTION, "MAX_INTERIOR_SIMPLICES")->properties();
 name: induced_set_action_of_ray_action_on_MAX_INTERIOR_SIMPLICES
 type: PermutationActionOnSets
 description: induced from ray_action on MAX_INTERIOR_SIMPLICES
 
 DOMAIN_NAME
 MAX_INTERIOR_SIMPLICES
 
 GENERATORS
 5 4 7 6 1 0 3 2 11 10 9 8 30 29 32 31 38 40 39 41 33 36 35 34 37 43 42 45 44 13 12 15 14 20 23 22 21 24 16 18 17 19 26 25 28 27 49 48 47 46 55 54 57 56 51 50 53 52
 0 2 1 3 12 14 13 15 16 17 18 19 4 6 5 7 8 9 10 11 21 20 22 24 23 25 27 26 28 29 31 30 32 34 33 35 37 36 46 47 48 49 50 52 51 53 38 39 40 41 42 44 43 45 54 56 55 57
 0 4 8 9 1 5 10 11 2 3 6 7 16 20 25 26 12 17 21 27 13 18 22 23 28 14 15 19 24 33 38 42 43 29 34 35 39 44 30 36 40 45 31 32 37 41 50 51 54 55 46 47 52 56 48 49 53 57

induced_action(PermutationAction a, Array<Set<Int>> domain)

Given a permutation action a on some indices and an ordered list domain of sets containing these indices, we ask for the permutation action induced by a on this list of sets.

Parameters:

PermutationAction a: a permutation action that acts on some indices

Array<Set<Int>> domain: a list of sets of indices that a should act on

Returns:

PermutationActionOnSets

Example:

Consider the symmetry group of the 3-cube acting on vertices, and induce from it the action on the facets:

 > $a = cube_group(3)->PERMUTATION_ACTION;
 > $f = new Array<Set>([[0,2,4,6],[1,3,5,7],[0,1,4,5],[2,3,6,7],[0,1,2,3],[4,5,6,7]]);
 > print $a->GENERATORS;
 1 0 3 2 5 4 7 6
 0 2 1 3 4 6 5 7
 0 1 4 5 2 3 6 7

 > print induced_action($a,$f)->GENERATORS;
 1 0 2 3 4 5
 2 3 0 1 4 5
 0 1 4 5 2 3

Example:

To see what the permutation [0,2,1] induces on the array [{0,1},{0,2}], do the following:

 > $a = new Array<Set<Int>>(2);
 > $a->[0] = new Set<Int>(0,1);
 > $a->[1] = new Set<Int>(0,2);
 > $p = new PermutationAction(GENERATORS=>[[0,2,1]]);
 > print induced_action($p,$a)->properties;
 type: PermutationActionOnSets
 
 GENERATORS
 1 0

induced_permutations(Array<Array<Int>> gens, Matrix M)

gives the permutations that are induced on the rows of a matrix M by the action of gens on the columns of M

Parameters:: Array<Array<Int>> gens: a list of permutations; Matrix M: the matrix acted upon
Options:: Bool homogeneous_action: should the generators also act on the homogeneous column? Default False
Returns:: Array<Array<Int>>

induced_permutations(Array<Matrix<Scalar>> gens, Matrix M)

gives the permutations that are induced on the rows of a matrix M by the action of gens on the columns of M. The matrices in gens define the permutations by multiplicate the rows from the right side on it.

Parameters:

Array<Matrix<Scalar>> gens: a list of matrices that act as generators

Matrix M: the matrix acted upon

Options:

Bool homogeneous_action: should the generators also act on the homogeneous column? Default False

Returns:

Array<Array<Int>>

Example:

 > $gens = new Array<Matrix>([new Matrix([[0,1,0],[0,0,1],[1,0,0]]), new Matrix([[0,0,1],[1,0,0],[0,1,0]])]);
 > $M = new Matrix([[1,2,3],[3,1,2],[2,3,1]]);
 > print induced_permutations($gens, $M, homogeneous_action=>1);
 2 0 1
 1 2 0

induced_permutations(Array<Array<Int>> gens, Array<DomainType> S)

gives the permutations that are induced on an ordered collection S by the action of gens on the elements of S

Parameters:: Array<Array<Int>> gens: a list of permutations; Array<DomainType> S: the collection acted upon
Returns:: Array<Array<Int>>

induced_permutations(Array<Array<Int>> a, IncidenceMatrix M)

gives the permutations that are induced on the rows of an incidence matrix M by the action of gens on the columns of M

Parameters:: Array<Array<Int>> a: the permutation action; IncidenceMatrix M: the matrix acted upon
Returns:: Array<Array<Int>>

induced_permutations_set_set(Array<Array<Int>> gens, Array<Set<Set>> domain)

gives the permutations that are induced on an Array<Set<Set» by permuting the elements of the inner set

Parameters:: Array<Array<Int>> gens: the generators of permutation action; Array<Set<Set>> domain: the domain acted upon
Returns:: Array<Array<Int>>

induced_rep(Cone C, PermutationActionOnSets A, Array<Int> g)

Calculate the representation of a group element

Parameters:: Cone C: the cone or polytope containing the sets acted upon; PermutationActionOnSets A: the action in question; Array<Int> g: the group element, acting on vertices
Returns:: SparseMatrix

invariant_polynomials(MatrixActionOnVectors a, Int d)

Given a matrix action a of a group G on some n-dimensional vector space and a total degree d, calculate the G-invariant polynomials of total degree 0 < deg ≤ d in n variables. This is done by calculating the a-orbit of all monomials of total degree at most d. By a theorem of Noether, for d = the order of G the output is guaranteed to generate the entire ring of G-invariant polynomials. No effort is made to calculate a basis of the ideal generated by these invariants.

Parameters:

MatrixActionOnVectors a: the matrix action

Int d: the maximal degree of the sought invariants

Options:

Bool action_is_affine: is the action a affine, ie., ignore the first row and column of the generating matrices? Default yes

Example:

To calculate the invariants of degree at most six of the matrix action of the symmetry group of the 3-cube, type

 > $c = cube(3, group=>1);
 > print join "\n", @{group::invariant_polynomials($c->GROUP->MATRIX_ACTION, 6)};
 x_0^2 + x_1^2 + x_2^2
 x_0^2*x_1^2 + x_0^2*x_2^2 + x_1^2*x_2^2
 x_0^2*x_1^2*x_2^2
 x_0^4 + x_1^4 + x_2^4
 x_0^4*x_1^2 + x_0^4*x_2^2 + x_0^2*x_1^4 + x_0^2*x_2^4 + x_1^4*x_2^2 + x_1^2*x_2^4
 x_0^6 + x_1^6 + x_2^6

irreducible_decomposition<Scalar>(Vector<Scalar> character, Group G)

Calculate the decomposition into irreducible components of a given representation

Type Parameters:

Scalar: the number type of the character

Parameters:

Vector<Scalar> character: the character of the given representation

Group G: the given group; it needs to know its CHARACTER_TABLE and CONJUGACY_CLASS_SIZES.

Returns:

Vector<Int>

Example:

Remember that in polymake, we use the terms action and representation interchangeably. To calculate the irreducible decomposition of the vertex action of the symmetry group of the 3-cube, type

 > $g = cube_group(3); $a = $g->PERMUTATION_ACTION;
 > print irreducible_decomposition($a->CHARACTER, $g);
 1 0 0 1 0 0 0 0 1 1

Thus, the action of the symmetry group on the vertices decomposes into one copy of each of the irreducible representations corresponding to the rows 0,3,8,9 of the character table:

 > print $g->CHARACTER_TABLE->minor([0,3,8,9],All);
 1 1 1 1 1 1 1 1 1 1
 1 1 1 -1 -1 -1 -1 1 1 -1
 3 1 0 -1 1 -1 0 -1 -1 3
 3 1 0 1 -1 1 0 -1 -1 -3

The first entries of these rows say that a decomposes into two 1-dimensional irreps and two 3-dimensional ones. This correctly brings the dimension of the representation a to 8, the number of vertices of the 3-cube.

isotypic_basis(Group G, PermutationActionOnSets A, Int i)

Calculate a basis of the isotypic component given by the i-th irrep

Parameters:

Group G: the acting group, which needs to know its CHARACTER_TABLE

PermutationActionOnSets A: the representation in question, which needs to know its corresponding CONJUGACY_CLASSES

Int i: the index of the sought irrep

Options:

Bool permute_to_orbit_order: Should the rows and columns be ordered by orbits? Default 1

Returns:

SparseMatrix

Example:

Consider the action of the symmetry group of the 3-cube on the set of facets:

 > $g = cube_group(3);
 > $f = new Array<Set>([[0,2,4,6],[1,3,5,7],[0,1,4,5],[2,3,6,7],[0,1,2,3],[4,5,6,7]]);
 > $a = induced_action($g->PERMUTATION_ACTION, $f);
 > print irreducible_decomposition($a->CHARACTER, $g)
 1 0 0 0 0 1 0 0 0 1

Now we can calculate a basis of the 5th irrep:

 > print isotypic_basis($g, $a, 5);
 -1/6 -1/6 1/3 1/3 -1/6 -1/6
 1/3 1/3 -1/6 -1/6 -1/6 -1/6

isotypic_basis(Group G, PermutationAction A, Int i)

Calculate a basis of the isotypic component given by the i-th irrep

Parameters:

Group G: the acting group, which needs to know its CHARACTER_TABLE

PermutationAction A: the action in question, which needs to know its corresponding CONJUGACY_CLASSES

Int i: the index of the sought irrep

Options:

Bool permute_to_orbit_order: Should the rows and columns be ordered by orbits? Default 1

Returns:

SparseMatrix

Example:

Consider the action of the symmetry group of the 3-cube on its vertices. We first calculate its decomposition into irreducible representations via

 > $g = cube_group(3); $a = $g->PERMUTATION_ACTION;
 > print irreducible_decomposition($a->CHARACTER, $g);
 1 0 0 1 0 0 0 0 1 1

We now calculate a basis of the 3rd irrep:

 > print isotypic_basis($g,$a,3);
 1/8 -1/8 -1/8 1/8 -1/8 1/8 1/8 -1/8

isotypic_basis<Scalar>(Group G, MatrixActionOnVectors<Scalar> A, Int i)

Calculate a basis of the isotypic component given by the i-th irrep

Type Parameters:: Scalar: S the underlying number type
Parameters:: Group G: the acting group, which needs to know its CHARACTER_TABLE; MatrixActionOnVectors<Scalar> A: the matrix action in question, which needs to know its corresponding CONJUGACY_CLASSES; Int i: the index of the sought irrep
Returns:: SparseMatrix

isotypic_projector(Group G, PermutationAction A, Int i)

Calculate the projection map into the isotypic component given by the i-th irrep. The map is given by a block matrix, the rows and columns of which are indexed by the domain elements; by default, these are ordered by orbits.

Parameters:

Group G: the acting group

PermutationAction A: the action in question

Int i: the index of the sought irrep

Options:

Bool permute_to_orbit_order: Should the rows and columns be ordered by orbits? Default 1

Returns:

SparseMatrix<QuadraticExtension>

Example:

Consider the action of the symmetry group of the 3-cube on its vertices. We first calculate its decomposition into irreducible representations via

 > $g = cube_group(3); $a = $g->PERMUTATION_ACTION;
 > print irreducible_decomposition($a->CHARACTER, $g);
 1 0 0 1 0 0 0 0 1 1

We now calculate the projection matrices to the irreps number 3 and 8:

 > $p3 = isotypic_projector($g,$a,3); print $p3, "\n", rank($p3);
 1/8 -1/8 -1/8 1/8 -1/8 1/8 1/8 -1/8
 -1/8 1/8 1/8 -1/8 1/8 -1/8 -1/8 1/8
 -1/8 1/8 1/8 -1/8 1/8 -1/8 -1/8 1/8
 1/8 -1/8 -1/8 1/8 -1/8 1/8 1/8 -1/8
 -1/8 1/8 1/8 -1/8 1/8 -1/8 -1/8 1/8
 1/8 -1/8 -1/8 1/8 -1/8 1/8 1/8 -1/8
 1/8 -1/8 -1/8 1/8 -1/8 1/8 1/8 -1/8
 -1/8 1/8 1/8 -1/8 1/8 -1/8 -1/8 1/8
 
 1

 > $p8 = isotypic_projector($g,$a,8); print $p8, "\n", rank($p8);
 3/8 -1/8 -1/8 -1/8 -1/8 -1/8 -1/8 3/8
 -1/8 3/8 -1/8 -1/8 -1/8 -1/8 3/8 -1/8
 -1/8 -1/8 3/8 -1/8 -1/8 3/8 -1/8 -1/8
 -1/8 -1/8 -1/8 3/8 3/8 -1/8 -1/8 -1/8
 -1/8 -1/8 -1/8 3/8 3/8 -1/8 -1/8 -1/8
 -1/8 -1/8 3/8 -1/8 -1/8 3/8 -1/8 -1/8
 -1/8 3/8 -1/8 -1/8 -1/8 -1/8 3/8 -1/8
 3/8 -1/8 -1/8 -1/8 -1/8 -1/8 -1/8 3/8
 
 3

From this we deduce that the irrep indexed 3 has dimension 1, and the one indexed 8 has dimension 3. This is consistent with the information collected in the character table:

 > print $g->CHARACTER_TABLE->minor([3,8],All);
 1 1 1 -1 -1 -1 -1 1 1 -1
 3 1 0 -1 1 -1 0 -1 -1 3

In effect, the first entries in these rows are 1 and 3, respectively.

isotypic_projector<Scalar>(Group G, MatrixActionOnVectors<Scalar> A, Int i)

Calculate the projection map into the isotypic component given by the i-th irrep. Note that the option permute_to_orbit_order makes no sense for matrix actions, so it is always set to 0.

Type Parameters:

Scalar: S the underlying number type

Parameters:

Group G: the acting group

MatrixActionOnVectors<Scalar> A: the action in question

Int i: the index of the sought irrep

Returns:

SparseMatrix<QuadraticExtension>

Example:

We first construct a matrix action:

 > $s = symmetric_group(3); $a = $s->REGULAR_REPRESENTATION;
 > print irreducible_decomposition($a->CHARACTER, $s);
 0 1 1

Since we now know that the irreps indexed 1 and 2 appear in the regular representation, we project to one of them:

 > print isotypic_projector($s, $a, 1);
 2/3 -1/3 -1/3
 -1/3 2/3 -1/3
 -1/3 -1/3 2/3

isotypic_supports(PermutationActionOnSets a, Array<Set> A)

For each isotypic component of a representation a, which of a given array A of sets are supported on it?

Parameters:: PermutationActionOnSets a: the representation in question; Array<Set> A: the given array of sets
Options:: Bool permute_to_orbit_order: Should the columns be ordered by orbits? Default 1
Returns:: IncidenceMatrix

isotypic_supports(PermutationActionOnSets a, SparseMatrix M)

For each row of a given SparseMatrix M, to which isotypic components of a representation a does it have a non-zero projection? The columns of the SparseMatrix correspond, in order, to the sets of the representation.

Parameters:: PermutationActionOnSets a: the representation in question; SparseMatrix M: the given matrix
Options:: Bool permute_to_orbit_order: Should the columns be ordered by orbits? Default 1
Returns:: IncidenceMatrix

lex_min_representative(Group G, Set S)

Computes the lexicographically smallest representative of a given set with respect to a group

Parameters:

Group G: a symmetry group

Set S: a set

Returns:

Set

Example:

To calculate the lex-min representative of the triangle [2,5,7] under the symmetry group of the 3-cube, type

 > print lex_min_representative(cube_group(3)->PERMUTATION_ACTION, new Set([2,5,7]));
 {0 1 6}

orbit_reps_and_sizes<Container>(Array<Array<Int>> generators, Container S)

Computes the lexicographically smallest representatives of a given array of sets with respect to a group, along with the corresponding orbit sizes

Type Parameters:

Container: a container of sets, for example Array<Set> or IncidenceMatrix

Parameters:

Array<Array<Int>> generators: the generators of a symmetry group

Container S: a container of sets, for example Array<Set> or IncidenceMatrix

Returns:

Pair<Array<Set<Int>>,Array<Int>>

Example:

To calculate the orbits and orbit sizes of an icosidodecahedron, type

 > $q=polytope::icosidodecahedron();
 > print orbit_reps_and_sizes($q->GROUP->VERTICES_ACTION->GENERATORS,$q->VERTICES_IN_FACETS);
 <{0 1 2 4 6}
 {0 1 3}
 >
 12 20

partition_representatives(Array<Array<Int>> gens, Set<Int> S)

Partition a group into translates of a set stabilizer

Parameters:: Array<Array<Int>> gens: the generators of a given group action; Set<Int> S: a set
Returns:: Array<Int>

regular_representation(PermutationAction a)

Calculate the regular representation of a permutation action

Parameters:

PermutationAction a: a permutation action

Returns:

MatrixActionOnVectors

Example:

To calculate the regular representation of the symmetric group S_3, type

 > $s = symmetric_group(3); $s->REGULAR_REPRESENTATION;
 > print $s->REGULAR_REPRESENTATION->properties();
 type: MatrixActionOnVectors<Rational>
 
 CONJUGACY_CLASS_REPRESENTATIVES
 <1 0 0
 0 1 0
 0 0 1
 >
 <0 1 0
 1 0 0
 0 0 1
 >
 <0 0 1
 1 0 0
 0 1 0
 >
 
 
 GENERATORS
 <0 1 0
 1 0 0
 0 0 1
 >
 <1 0 0
 0 0 1
 0 1 0
 >

row_support_sizes(SparseMatrix M)

How many non-zero entries are there in each row of a SparseMatrix?

Parameters:: SparseMatrix M: the given matrix
Returns:: Array<Int>

span_same_subspace(Array<HashMap<SetType,Rational>> S1, Array<HashMap<SetType,Rational>> S2)

Do two collections S1, S2 of sparse vectors span the same subspace?

Parameters:: Array<HashMap<SetType,Rational>> S1: the sparse generating vectors of the first subspace; Array<HashMap<SetType,Rational>> S2: the sparse generating vectors of the second subspace
Returns:: Bool

spans_invariant_subspace(ImplicitActionOnSets a, Array<HashMap<Bitset,Rational>> S)

Does a set S of sparse vectors span an invariant subspace under an implicit group action a?

Parameters:: ImplicitActionOnSets a: the given action; Array<HashMap<Bitset,Rational>> S: the sparsely given generating vectors of the subspace
Options:: Bool verbose: give a certificate if the answer is False
Returns:: Bool

sparse_isotypic_basis(PermutationActionOnSets rep, Int i)

Calculate a sparse representation of a basis for an isotypic component. For this, the sets in the representation are listed in order by orbit. In this basis, the projection matrix to the isotypic component decomposes into blocks, one for each orbit.

Parameters:: PermutationActionOnSets rep: the given representation; Int i: the index of the irrep that defines the isotypic component
Options:: Bool use_double: use inexact arithmetic for reducing the basis; default 0; String filename: if defined, the basis will be written to a file with this name, but not returned. Use this option if you expect very large output.
Returns:: Array<HashMap<Bitset,Rational>>

sparse_isotypic_spanning_set(PermutationActionOnSets rep, Int i)

Calculate a sparse representation of a spanning set for an isotypic component. For this, the sets in the representation are listed in order by orbit. In this basis, the projection matrix to the isotypic component decomposes into blocks, one for each orbit.

Parameters:: PermutationActionOnSets rep: the given representation; Int i: the index of the irrep that defines the isotypic component
Options:: String filename: if defined, the basis will be written to a file with this name, but not returned. Use this option if you expect very large output.
Returns:: Array<HashMap<Bitset,Rational>>

sparse_isotypic_support(PermutationActionOnSets rep, Int i)

Calculate the support of a sparse representation of a spanning set for an isotypic component.

Parameters:: PermutationActionOnSets rep: the given representation; Int i: the index of the irrep that defines the isotypic component
Options:: String filename: if defined, the basis will be written to a file with this name, but not returned. Use this option if you expect very large output.; Bool equivalence_class_only only report representatives of simplices, default true

Bool index_only only output the indices of the representatives to filename, default true

Returns:: HashSet<Bitset>

Miscellaneous functions.

action<action_type>(Any g, Any O)

The image of an object O under a group element g. The action_type defines how g acts on O. For more informations see the help function on the action types.

Type Parameters:

action_type: must be compatible with O by default on_container can also be on_elements, on_rows, on_cols, on_nonhomog_cols

Parameters:

Any g: Group element

Any O: Container type like Array, Set, Matrix or Vector

Returns:

Any

Example:

 > $g = new Array<Int>([1,2,0]);
 > $O = new Matrix<Int>([[0,0],[1,1],[2,2]]);
 > print $O;
 0 0
 1 1
 2 2

 > print action<on_rows>($g, $O);
 1 1
 2 2
 0 0

action_from_generators(Array<Array<Int>> gens, Group action)

Computes groups with a permutation action with the basic properties BASE, STRONG_GENERATORS, and TRANSVERSALS.

Parameters:: Array<Array<Int>> gens: some generators of the group; Group action: the generated action

action_inv<action_type>(Array<Int> p, Any O)

The image of an object O under the inverse of a permutation p. The way it acts on O is given by the action_type.

Type Parameters:

action_type: must be compatible with O, by default on_container can also be on_elements, on_rows, on_cols or on_nonhomog_cols

Parameters:

Array<Int> p: permutation

Any O: Container type like Array, Set, Matrix or Vector

Returns:

Any

Example:

 > $p = new Array<Int>([1,2,0]);
 > $O = new Array<Int>([2,3,1]);
 > print action_inv($p,$O);
 1 2 3

action_to_cyclic_notation(PermutationAction a)

Returns group generators in 1-based cyclic notation (GAP like, not permlib like notation)

Parameters:: PermutationAction a: the action of the permutation group
Returns:: String

all_group_elements(PermutationAction a)

Compute all elements of a given group, expressed as a permutation action.

Parameters:: PermutationAction a: the action of a permutation group
Returns:: Array<Array<Int>>

SwitchTable: UNDOCUMENTED

on_cols: A template parameter used by action and orbit specifying that the permutation acts on the columns of a matrix.

on_container: A template parameter used by action and orbit specifying that the permutation acts on the given container. It will permute the order of the elements

on_elements: A template parameter used by action and orbit specifying that the permutation acts on the deepest elements inside a given container, which should be of type Int.

on_nonhomog_cols: A template parameter used by action and orbit specifying that the permutation acts on all columns of a matrix, except the '0'-th one, and adjusting the indices of the permutation

on_nonhomog_container: A template parameter used by action and orbit specifying that the permutation acts on the given container. It will permute the order of the elements, leaving the '0'-th one fixed and adjusting the indices of the permutation