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 group::PermutationAction, group::PermutationActionOnSets or group::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::Cone, 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 group::induced_action, for example.

imports from: common

Objects

User Functions

  •  
    induced_action ()

    UNDOCUMENTED

  •  

    These functions are concerned with orbits in groups.

    •  
      are_in_same_orbit (action, vec1, vec2) → Bool

      Checks whether vector vec1 and vec2 are in the same orbit with respect to the (coordinate) action of group.

      Parameters
      PermutationActionaction
      the permutation group acting on coordinates
      Vectorvec1
      Vectorvec2
      Returns
      Bool
    •  
      orbit <action_type> (G, O) → Set<Object>

      The orbit of an object O under a group generated by G.

      Type Parameters
      action_type
      Parameters
      ArrayG
      Group generators
      ObjectO
      Returns
      Set<Object>
    •  
      orbit (G, C) → Set<container>

      The orbit of an container C under a groupG.

      Parameters
      GroupG
      AnyC
      Returns
      Set<container>
    •  
      orbits_in_orbit_order (action, mat) → List

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

      Parameters
      PermutationActionaction
      an action of a group of coordinate permutations
      Matrix<Scalar>mat
      some input vectors
      Returns
      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.

      Parameters
      PermutationActiona
      a permutation action of a group
      Returns
      Array<Set<Int>>
    •  
      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
      PermutationActiona
      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>>
      an array of the orbits under the action on the coordinates
    •  
      orbits_of_induced_action (action, inc) → 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
      PermutationActionaction
      an action of group
      IncidenceMatrixinc
      the incidences between domain elements and elements on which an action is induced
      Returns
      Array<Set<Int>>
      an array of the orbits of the induced action
    •  
      orbit_permlib (G, S) → Set

      The orbit of a set S under a group G.

      Parameters
      GroupG
      SetS
      Returns
      Set
    •  
      orbit_permlib (G, S) → Set

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

      Parameters
      GroupG
      Set<Set>S
      Returns
      Set
    •  
      orbit_representatives (G) → Array<Int>

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

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

    Special purpose functions.

  •  

    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 (degree) → Group

      Constructs an alternating group of given degree.

      Parameters
      Intdegree
      of the alternating group
      Returns
      Group
    •  
      cube_group (dimension) → Group

      Constructs the symmetry group of a d-cube, 3 <= d <= 6 (for the moment) with the corresponding character table and conjugacy class representatives.

      Parameters
      Intdimension
      of the cube
      Returns
      Group
    •  
      cyclic_group (degree) → Group

      Constructs a cyclic group of given degree.

      Parameters
      Intdegree
      of the cyclic group
      Returns
      Group
    •  
      dihedral_group (order) → Group

      Constructs a dihedral group of a given order. 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
      Intorder
      of the dihedral group (acts on a regular (order/2)-gon
      Returns
      Group
    •  
      group_from_cyclic_notation0 (group) → Group

      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
      Stringgroup
      generators in cyclic notation
      Returns
      Group
    •  
      group_from_cyclic_notation1 (group) → Group

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

      Parameters
      Stringgroup
      generators in cyclic notation
      Returns
      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 notation
      Intdegree
      the degree of the permutation group
      Returns
      Group
      the group generated by gens
    •  
      stabilizer_of_set (action, set) → Group

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

      Parameters
      PermutationActionaction
      the action of a permutation group
      Setset
      the set to be stabilized
      Returns
      Group
      the stabilizer of set w.r.t. group
    •  
      stabilizer_of_vector (group, vec) → Group

      Computes the subgroup of group which stabilizes the given vector vec.

      Parameters
      Groupgroup
      a permutation group
      Vectorvec
      the vector to be stabilized
      Returns
      Group
      the stabilizer of vec w.r.t. group
    •  
      symmetric_group (degree) → Group

      Constructs a symmetric group of given degree.

      Parameters
      Intdegree
      of the symmetric group
      Returns
      Group
  •  

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

    •  
      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.

      Parameters
      MatrixM
      Arrayof
      permutations
      Returns
      Array
      of permutations
    •  
      group_left_multiplication_table (G) → Array<Array<Int>>

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

      Parameters
      GroupG
      Options
      Stringaction
      which action to take for the calculation; default PERMUTATION_ACTION
      Returns
      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
      GroupG
      Options
      Stringaction
      which action to take for the calculation; default PERMUTATION_ACTION
      Returns
      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 (the) → Array<Int>

      Calculate character of an implicit action

      Parameters
      ImplicitActionOnSetsthe
      given action
      Returns
      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<Array<Int>>gens
      a list of permutations
      MatrixM
      the matrix acted upon
      Options
      Boolhomogeneous_action
      should the generators also act on the homogeneous column? Default False
      Returns
      Array<Array<Int>>
    •  
      induced_permutations (gens, the) → Array<Array<Int>>

      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
      Array<DomainType>the
      collection acted upon
      Returns
      Array<Array<Int>>
    •  
      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 action
      IncidenceMatrixM
      the matrix acted upon
      Returns
      Array<Array<Int>>
    •  
      lex_min_representative (G, S) → Set

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

      Parameters
      GroupG
      a symmetry group
      SetS
      a set
      Returns
      Set
      the lex-min representative of S
    •  
      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 action
      Set<Int>S
      a set
      Returns
      Array<Int>
    •  
      spans_invariant_subspace (a, S) → Bool

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

      Parameters
      group::ImplicitActionOnSetsa
      the given action
      Array<HashMap<Bitset, Rational>>S
      the sparsely given generating vectors of the subspace
      Options
      Boolverbose
      give a certificate if the answer is False
      Returns
      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 subspace
      Array<HashMap<SetType, Rational>>S2
      the sparse generating vectors of the second subspace
      Returns
      Bool
    •  
      sparse_isotypic_basis (the, the) → 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
      PermutationActionOnSetsthe
      given representation
      Intthe
      index of the irrep that defines the isotypic component
      Options
      Booluse_double
      use inexact arithmetic for reducing the basis; default 0
      Stringfilename
      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 (the, the) → 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
      PermutationActionOnSetsthe
      given representation
      Intthe
      index of the irrep that defines the isotypic component
      Options
      Stringfilename
      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 (the, the) → HashSet<Bitset>

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

      Parameters
      PermutationActionOnSetsthe
      given representation
      Intthe
      index of the irrep that defines the isotypic component
      Options
      Stringfilename
      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>
      Support.
  •  

    Miscellaneous functions.

Property Types

  •  
    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

  •  
    on_rows

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