application: group
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 polytope::Cone or polytope::Polytope, the representation in question is encoded as a Group::PERMUTATION_ACTION, Group::SET_ACTION or Group::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.
Objects
-
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
Properties of Action
-
These properties capture information of the object that is concerned with the action of permutation groups.
-
ALL_GROUP_ELEMENTS: common::Array
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.
-
CHARACTER: common::Vector<QuadraticExtension<Rational>>
The character of the action. The ordering corresponds to the columns of the CHARACTER_TABLE
-
-
CONJUGACY_CLASS_REPRESENTATIVES: common::Array
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.
-
DEGREE: common::Int
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
-
DOMAIN_NAME: common::String
the name of the property that we act on, for example MAX_INTERIOR_SIMPLICES or INTERIOR_RIDGES
-
EQUATIONS_GENERATORS: common::Matrix
A set of generators for equations, stored as the rows of a matrix. The list of generators may be redundant and non-canonical.
-
EXPLICIT_ORBIT_REPRESENTATIVES: common::Array
the representatives of orbits explicitly, not via their indices
-
EXPLICIT_ORBIT_REPRESENTATIVE_MATRIX: common::Matrix
the representatives of orbits explicitly, not via their indices
-
FACETS_GENERATORS: common::Matrix
A set of generators for facets, stored as the rows of a matrix. The list of generators may be redundant and non-canonical.
-
-
IMAGES: common::Array
The images of all domain elements under each group element: [ [ g(x) for x in D ] for g in G ]
-
INDEX_OF: common::HashMap
The map giving the index of each group element This is a temporary property; it will not be stored in any file.
-
-
INEQUALITIES_GENERATORS: common::Matrix
A set of generators for inequalities, stored as the rows of a matrix. The list of generators may be redundant and non-canonical.
-
INPUT_LINEALITY_GENERATORS: common::Matrix
A set of generators for input lineality, stored as the rows of a matrix. The list of generators may be redundant and non-canonical.
-
INPUT_RAYS_GENERATORS: common::Matrix
A set of generators for input rays, stored as the rows of a matrix. The list of generators may be redundant and non-canonical.
-
IRREDUCIBLE_DECOMPOSITION: common::Vector<Int>
The multiplicities of each irreducible representation in this action. The ordering corresponds to the rows of the CHARACTER_TABLE
-
LINEALITY_SPACE_GENERATORS: common::Matrix
A set of generators for input lineality, stored as the rows of a matrix. The list of generators may be redundant and non-canonical.
-
MAXIMAL_CONES_GENERATORS: common::IncidenceMatrix<NonSymmetric>
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.
-
-
-
-
-
-
-
-
-
-
-
-
ORBIT_REPRESENTATIVES: common::Array<Int>
A collection of representatives for each orbit, represented via their indices
-
-
-
PERMUTATION_TO_ORBIT_ORDER: common::Array<Int>
A permutation that orders the domain elements by orbits
-
RAYS_GENERATORS: common::Matrix
A set of generators for rays, stored as the rows of a matrix. The list of generators may be redundant and non-canonical.
-
-
-
Object encoding a finite group.
Properties of Group
-
These properties capture information of the object that is concerned with the action of permutation groups.
-
CHARACTER_TABLE: common::Matrix<QuadraticExtension<Rational>, NonSymmetric>
The character table. NOTE: We do not support complex characters, but for the moment only real ones.
-
-
-
-
HOMOGENEOUS_COORDINATE_ACTION: PermutationAction<Int, Rational>
operates on indices, including the '0'-th homogeneous coordinate
-
IMPLICIT_SET_ACTION: ImplicitActionOnSets
an action on sets where only one representative for each orbit is stored
-
-
-
-
MAXIMAL_CONES_ACTION: PermutationAction<Int, Rational> as Group::MAXIMAL_CONES_ACTION
operates on indices
-
-
-
-
-
SET_ACTION: PermutationAction<Set<Int>, Rational>
a permutation action on a collection of sets of integers
-
-
-
-
-
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
-
object for encoding the separate actions of a group on a collection of sets, induced by the same generators
-
derived object for matrix groups
Properties of MatrixActionOnVectors
-
These properties capture information of the object that is concerned with the action of permutation groups.
-
-
-
derived objects for permutation representations
Properties of PermutationAction
-
-
-
-
-
-
Dealing with orbits under permutation groups.
-
SWITCH_TABLE: SwitchTable
A switch table is a tool for finding lex-maximal or -minimal in orbits under the action of a permutation group. Its main ingredient is an upper-left triangular matrix with group elements as entries. See https://arxiv.org/abs/1709.04746
The output contains the support at every level, i.e. a number and a Set<Int>, the number is the size of the support and and the Set<Int> are the indices of those entries that can be permuted to the index of the current level while keeping previous level indices fixed. I.e. entry [i,j] will keep the first i entries of a vector fixed, while moving the j-th entry to position i. Note that we start counting at 0!
Example:-
> $P = new PermutationAction(GENERATORS=>[[1,2,0,4,5,3],[2,1,0,5,4,3]]);
> print $P->SWITCH_TABLE;
Supports: (size, content)
Level 0: 3 {0 1 2}
Level 1: 2 {1 2}
Entries:
[0,0]: 0 1 2 3 4 5
[0,1]: 1 0 2 4 3 5
[0,2]: 1 2 0 4 5 3
[1,1]: 0 1 2 3 4 5
[1,2]: 0 2 1 3 5 4
-
-
User Methods of PermutationAction
-
Dealing with orbits under permutation groups.
-
lex_maximal ()
Assume the group acts on a vector by permuting its entries. Then this method gives the lex-maximal vector from the orbit of the input vector under the group action. See https://arxiv.org/abs/1709.04746
-
lex_minimal ()
Similar to lex_maximal.
-
-
-
derived object for permuting collections of sets
User Functions
-
These functions are concerned with orbits in groups.
-
are_in_same_orbit (a, v1, v2) → Bool
Checks whether vectors v1 and v2 are in the same orbit with respect to the (coordinate) action of group.
-
orbit <action_type> (G, O) → Set<Core::Object>
The orbit of an object O under a group generated by G.
-
orbit <Scalar> (G, V) → Set
The orbit of a vector V under a group generated by G.
Type Parameters
Scalar S the number typeParameters
Array<Matrix<Scalar>> G Generators of the groupVector<Scalar> V Returns
Set -
orbits_in_orbit_order (a, M) → List
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 permutationsMatrix M some input vectorsReturns
List ( Matrix generated vectors in orbit order, Array orbits of generated vectors) -
orbits_of_action (a) → Array<Set<Int>>
Computes the orbits of the basic set under a.
-
orbits_of_coordinate_action (a, M) → Array<Set<Int>>
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 coordinatesMatrix<Scalar> M a matrix on whose columns the group acts by coordinate permutationReturns
Array<Set<Int>> an array of the orbits under the action on the coordinates -
orbits_of_induced_action (a, I) → Array<Set<Int>>
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 groupIncidenceMatrix I the incidences between domain elements and elements on which an action is inducedReturns
Array<Set<Int>> an array of the orbits of the induced action -
orbit_permlib (G, S) → Set
-
orbit_permlib (G, S) → Set
-
orbit_representatives (G) → Array<Int>
The indices of one representative for each orbit under the group generated by G.
-
-
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 (d) → Group
-
cube_group (d) → Group
-
cyclic_group (d) → Group
-
dihedral_group (o) → Group
-
group_from_cyclic_notation0 (generators) → Group
-
group_from_cyclic_notation1 (generators) → Group
-
group_from_permlib_cyclic_notation (gens, degree) → Group
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 notationInt degree the degree of the permutation groupReturns
Group the group generated by gens -
stabilizer_of_set (a, S) → Group
Computes the subgroup of group which stabilizes the given set of indices set.
Parameters
PermutationAction a the action of a permutation groupSet S the set to be stabilizedReturns
Group the stabilizer of S w.r.t. a -
stabilizer_of_vector (a, v) → Group
Computes the subgroup of G which stabilizes the given vector v.
Parameters
PermutationAction a the action of a permutation groupVector v the vector to be stabilizedReturns
Group the stabilizer of v w.r.t. a -
symmetric_group (d) → Group
-
-
These functions capture information of the object that is concerned with the action of permutation groups.
-
all_group_elements <Scalar> (action) → Set<Matrix<Scalar>>
Compute all elements of a given group, expressed as a matrix group action.
Type Parameters
Scalar S the underlying number typeParameters
MatrixActionOnVectors<Scalar> action the action of a permutation groupReturns
Set<Matrix<Scalar>> G a set containing all group elementsExample:- 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
>
-
col_to_row_action (M, of) → Array
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.
-
conjugacy_class <Element> (action, e) → Set<Element>
Compute the conjugacy class of a group element under a given action
Type Parameters
Element E the underlying element typeParameters
Action action the action of the groupElement e the element to be acted uponReturns
Set<Element> S a set containing the conjugacy class of the element -
conjugacy_class <Scalar> (action, e) → Set<Matrix<Scalar>>
Compute the conjugacy class of a group element under a given action
Type Parameters
Scalar E the underlying number typeParameters
MatrixActionOnVectors<Scalar> action the action of the groupMatrix<Scalar> e the element to be acted uponReturns
Set<Matrix<Scalar>> S a set containing the conjugacy class of the element -
group_left_multiplication_table (G) → Array<Array<Int>>
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_ACTIONReturns
Array<Array<Int>> GMT the multiplication table, where the elements of G are ordered by conjugacy classes (if available), else in generated order -
group_right_multiplication_table (G) → Array<Array<Int>>
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_ACTIONReturns
Array<Array<Int>> GMT the multiplication table, where the elements of G are ordered by conjugacy classes (if available), else in generated order -
implicit_character (A) → Array<Int>
Calculate character of an implicit action
-
induced_action (a, domain) → PermutationActionOnSets
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 indicesArray<Set<Int>> domain a list of sets of indices that a should act onReturns
PermutationActionOnSets Examples:- 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
- 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 (gens, M) → Array<Array<Int>>
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 permutationsMatrix M the matrix acted uponOptions
Bool homogeneous_action should the generators also act on the homogeneous column? Default FalseReturns
Array<Array<Int>> -
induced_permutations (gens, M) → Array<Array<Int>>
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<Matrix<Scalar>> gens a list of matrices that act as generatorsMatrix M the matrix acted uponOptions
Bool homogeneous_action should the generators also act on the homogeneous column? Default FalseReturns
Array<Array<Int>> -
induced_permutations (gens, S) → Array<Array<Int>>
gives the permutations that are induced on an ordered collection S by the action of gens on the elements of S
-
induced_permutations (a, M) → Array<Array<Int>>
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 actionIncidenceMatrix M the matrix acted uponReturns
Array<Array<Int>> -
induced_permutations_set_set (gens, domain) → Array<Array<Int>>
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 actionArray<Set<Set>> domain the domain acted uponReturns
Array<Array<Int>> -
induced_rep (C, A, g) → SparseMatrix
Calculate the representation of a group element
Parameters
polytope::Cone C the cone or polytope containing the sets acted uponPermutationActionOnSets A the action in questionArray<Int> g the group element, acting on verticesReturns
SparseMatrix -
induce_implicit_action (original_action, property) → ImplicitActionOnSets
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 indicesString property the name of a property that describes an ordered list of sets on which the group should actReturns
ImplicitActionOnSets the action of the group on the given property, such that only representatives are storedExample:- 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
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
DOMAIN_NAME
MAX_INTERIOR_SIMPLICES
EXPLICIT_ORBIT_REPRESENTATIVES
{0 1 2 4}
{0 1 2 5}
{0 1 2 7}
{0 3 5 6}
-
induce_set_action (c, a, domain) → PermutationActionOnSets
Construct the induced action of a permutation action on a property that is an ordered collection of sets, such as MAX_INTERIOR_SIMPLICES
Parameters
polytope::Cone c the cone or polytopePermutationAction a a permutation action on, for example, the vertex indicesString domain the property the induced action should act uponReturns
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
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
DOMAIN_NAME
MAX_INTERIOR_SIMPLICES
-
invariant_polynomials (a, 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 actionInt d the maximal degree of the sought invariantsOptions
Bool action_is_affine is the action a affine, ie., ignore the first row and column of the generating matrices? Default yesExample:- 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> (character, G) → Vector<Int>
Calculate the decomposition into irreducible components of a given representation
Type Parameters
Scalar the number type of the characterParameters
Vector<Scalar> character the character of the given representationGroup 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 (G, A, i) → SparseMatrix
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_TABLEPermutationActionOnSets A the representation in question, which needs to know its corresponding CONJUGACY_CLASSESInt i the index of the sought irrepOptions
Bool permute_to_orbit_order Should the rows and columns be ordered by orbits? Default 1Returns
SparseMatrix a matrix whose rows form a basis of the i-th irrepExample:- 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 (G, A, i) → SparseMatrix
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_TABLEPermutationAction A the action in question, which needs to know its corresponding CONJUGACY_CLASSESInt i the index of the sought irrepOptions
Bool permute_to_orbit_order Should the rows and columns be ordered by orbits? Default 1Returns
SparseMatrix a matrix whose rows form a basis of the i-th irrepExample:- 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> (G, A, i) → SparseMatrix
Calculate a basis of the isotypic component given by the i-th irrep
Type Parameters
Scalar S the underlying number typeParameters
Group G the acting group, which needs to know its CHARACTER_TABLEMatrixActionOnVectors<Scalar> A the matrix action in question, which needs to know its corresponding CONJUGACY_CLASSESInt i the index of the sought irrepReturns
SparseMatrix a matrix whose rows form a basis of the i-th irrep > $s = symmetric_group(3); $a = $s->REGULAR_REPRESENTATION; > print irreducible_decomposition($a->CHARACTER, $s); | 0 1 1 We now calculate a basis of the 1st irrep: > print isotypic_basis($s, $a, 1); | 2/3 -1/3 -1/3 | -1/3 2/3 -1/3 This is consistent with the information collected in the character table: > print $g->CHARACTER_TABLE->row(1); | 2 0 1 In effect, the first entry in this rows says that the dimension of this irrep is 2. -
isotypic_projector (G, A, i) → SparseMatrix<QuadraticExtension>
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 groupPermutationAction A the action in questionInt i the index of the sought irrepOptions
Bool permute_to_orbit_order Should the rows and columns be ordered by orbits? Default 1Returns
SparseMatrix<QuadraticExtension> pi the matrix of the projection, the rows and columns of which are indexed by the domain elements; by default; these are ordered by orbits.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> (G, A, i) → SparseMatrix<QuadraticExtension>
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 typeParameters
Group G the acting groupMatrixActionOnVectors<Scalar> A the action in questionInt i the index of the sought irrepReturns
SparseMatrix<QuadraticExtension> pi the matrix of the projectionExample:- 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 (a, A) → IncidenceMatrix
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 questionArray<Set> A the given array of setsOptions
Bool permute_to_orbit_order Should the columns be ordered by orbits? Default 1Returns
IncidenceMatrix -
isotypic_supports (a, M) → IncidenceMatrix
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 questionSparseMatrix M the given matrixOptions
Bool permute_to_orbit_order Should the columns be ordered by orbits? Default 1Returns
IncidenceMatrix -
lex_min_representative (G, S) → Set
Computes the lexicographically smallest representative of a given set with respect to a group
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> (generators, S) → Pair<Array<Set<Int>>,Array<Int>>
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 IncidenceMatrixParameters
Array<Array<Int>> generators the generators of a symmetry groupContainer S a container of sets, for example Array<Set> or IncidenceMatrixReturns
Pair<Array<Set<Int>>,Array<Int>> the lex-min representatives of S, and the sizes of the corresponding orbitsExample:- 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 (gens, S) → Array<Int>
Partition a group into translates of a set stabilizer
Parameters
Array<Array<Int>> gens the generators of a given group actionSet<Int> S a setReturns
Array<Int> -
regular_representation (a) → MatrixActionOnVectors
Calculate the regular representation of a permutation action
Parameters
PermutationAction a a permutation actionReturns
MatrixActionOnVectors g the regular representation of a by permutation matricesExample:- 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>
GENERATORS
<0 1 0
1 0 0
0 0 1
>
<1 0 0
0 0 1
0 1 0
>
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
>
-
row_support_sizes (M) → Array<Int>
How many non-zero entries are there in each row of a SparseMatrix?
-
spans_invariant_subspace (a, S) → Bool
Does a set S of sparse vectors span an invariant subspace under an implicit group action a?
Parameters
ImplicitActionOnSets a the given actionArray<HashMap<Bitset, Rational>> S the sparsely given generating vectors of the subspaceOptions
Bool verbose give a certificate if the answer is FalseReturns
Bool -
span_same_subspace (S1, S2) → Bool
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 subspaceArray<HashMap<SetType, Rational>> S2 the sparse generating vectors of the second subspaceReturns
Bool -
sparse_isotypic_basis (rep, i) → Array<HashMap<Bitset,Rational>>
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 representationInt i the index of the irrep that defines the isotypic componentOptions
Bool use_double use inexact arithmetic for reducing the basis; default 0String 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>> Basis. Each entry tells the coefficient for each orbit representative. -
sparse_isotypic_spanning_set (rep, i) → Array<HashMap<Bitset,Rational>>
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 representationInt i the index of the irrep that defines the isotypic componentOptions
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>> SpanningSet. Each entry tells the coefficient for each orbit representative. -
sparse_isotypic_support (rep, i) → HashSet<Bitset>
Calculate the support of a sparse representation of a spanning set for an isotypic component.
Parameters
PermutationActionOnSets rep the given representationInt i the index of the irrep that defines the isotypic componentOptions
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 trueBool index_only only output the indices of the representatives to filename, default trueReturns
HashSet<Bitset> Support.
-
-
Miscellaneous functions.
-
action <action_type> (g, O) → Core::Object
The image of an object O under a group element g.
-
action_from_generators (gens, 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 groupGroup action the generated action -
action_inv <action_type> (p, O) → Core::Object
The image of an object O under the inverse of a permutation p.
-
action_to_cyclic_notation (a) → String
Returns group generators in 1-based cyclic notation (GAP like, not permlib like notation)
Parameters
PermutationAction a the action of the permutation groupReturns
String group generators, separated by newline and comma -
all_group_elements (a) → Array<Array<Int>>
Compute all elements of a given group, expressed as a permutation action.
Parameters
PermutationAction a the action of a permutation groupReturns
Array<Array<Int>> all group elements
-