Finite group structures

Elements of finite groups all have a type described by a FiniteGroupType. For example, permutations acting on a certain domain, matrices of a given dimension; direct products of those.

  • FiniteGroupType : A group of elements from which finite subgroups can be constructed.

  • TotalOrder: RepLAB defines a total ordering on any finite group type.

  • FiniteGroup: A group with a finite number of elements, is generated by a finite number of generators.

  • MatrixGroup: A finite group of matrices whose coefficients are in the cyclotomic field (characteristic zero, includes the rational numbers)

FiniteGroupType

class replab.FiniteGroupType

Bases: replab.Group, replab.TotalOrder

Describes a type of finite groups

It is a possibly infinite group, and this object is able to construct finite subgroups of itself.

It also defines a (somewhat arbitrarily chosen) total order used, for example, to define minimal canonical representatives of conjugacy classes and cosets.

Examples of group types include:

  • permutations of a given domain 1..n (the set of such permutations is finite),

  • invertible matrices of a given size with coefficients in the cyclotomic field (the set of such matrices is not finite, but we assume that any explicitly constructed group is finite),

  • direct products of finite group types.

Note

For implementations purposes, there are several families of group types in RepLAB.

  • The first is replab.perm.PermutationGroupType where computational group theory algorithms are implemented and used directly.

  • The second is replab.gen.FiniteGroupType, in which the constructed objects delegate all computations to objects where the algorithms are actually implemented, through a “nice isomorphism”.

For now, those two families are the only ones implemented. Natural extensions would be:

  • Implementing algorithms for solvable groups through the polycyclic presentation as in e.g. GAP System.

  • Implementing black box group algorithms, either through a naive enumeration approach (to validate existing algorithms), or through recent algorithms proposed for black box groups.

  • Implementing matrix groups through a BSGS approach using the action of matrices on vectors; possibly also through recent algorithms based on composition trees.

Own members

groupWithGenerators(self, generators, varargin)

Constructs a group with the given generators

Parameters
  • generators (cell(1,*) of group elements) – Group generators

  • generatorNames – Names of the generators

  • order – Group order

  • relators – Relators

Kwtype generatorNames

cell(1,*) of charstring, optional

Kwtype order

vpi or integer, optional

Kwtype relators

cell(1,*) of charstring or integer(1,*), optional

Returns

Constructed group

Return type

FiniteGroup

isSameTypeAs(self, otherType)

Tests whether this type is the same as another type

Parameters

otherType (FiniteGroupType) – Other type to test with

Returns

True if the types are the same

Return type

logical

subgroupWithGenerators(self, group, generators, varargin)

Constructs a subgroup of a given group with the given parameters

Parameters
  • group (FiniteGroup) – Finite group whose subgroup we are constructing

  • generators (cell(1,*) of group elements) – Subgroup generators

  • generatorNames – Names of the generators

  • order – Group order

  • relators – Relators

Kwtype generatorNames

cell(1,*) of charstring

Kwtype order

vpi or integer

Kwtype relators

cell(1,*) of charstring or integer(1,*)

Returns

Constructed group

Return type

FiniteGroup

TotalOrder

class replab.TotalOrder

Bases: replab.Domain

Describes a domain equipped with a total order

Own members

compare(self, x, y)

Compares two elements of a domain

The method returns:

  • -1 if x < y

  • 0 if x == y

  • 1 if x > y

Parameters
  • x (element) – First element

  • y (element) – Second element

Returns

Result of comparison

Return type

-1,0,1

sort(self, array)

Returns a permutation that sorts the given array

Returns a permutation I such that array(I) is sorted.

Parameters

array (cell(1,*) of elements of this domain) – Array to sort

Returns

Permutation that sorts the array

Return type

integer(1,*)

FiniteGroup

class replab.FiniteGroup

Bases: replab.CompactGroup, replab.FiniteSet

Describes a group with a finite number of elements

A finite group is generated by a finite set of generators.

Groups can be compared for equality using the == operator.

RepLAB implements group algorithms optimized for permutation groups using the BSGS (base and strong generating set) construction.

Generators and equality

The generating set of a group is a property of the group, and is used, for example:

  • to factor a group element as a word in the generators,

  • as the default preimages set for representation/morphism construction,

  • to construct an abstract form of the group (see relatorsWord).

However, groups that differ only by their generators are equal as sets. Thus, two groups that are equal under == can nevertheless return different values for the methods that work with the group generators.

For display purposes, and to describe group elements as words in the generators, the group generators have names generatorNames. Again, groups that differ by the names of their generators are considered mathematically equal.

The exception is AbstractGroup because the generator names are used in the group elements themselves.

Finite group types

Each finite group has a type (FiniteGroupType), that describes the most general group embedding its elements. The following are finite group types:

  • Permutations acting on 1 .. n (see PermutationGroup)

  • Signed permutations acting on +/- 1 .. n (see SignedPermutationGroup)

  • Cyclotomic matrices of a given size (note: we restrict the corresponding matrix groups to the finite ones)

  • Product groups of the above (direct, semidirect, wreath)

Finite group methods such as contains can be called with arguments from the group type.

Types can be compared with the == operator.

Implementations of finite groups

FiniteGroup has two main subclasses:

  • PermutationGroup, where all the methods are implemented directly using algorithms based on the BSGS construction,

  • replab.gen.FiniteGroup, which delegate the computations to another group type using an isomorphism.

As of July 2021, generic group implementations delegate computations to permutation groups, but this could evolve in the future.

Currently, some delegations of computations assume that the destination group is a permutation group, which is why we have permutationGroup and permutationIsomorphism methods on finite groups.

Own members

generators

Group generators

Type

cell(1,*) of type elements

abelianInvariants(self)

Returns the group abelian invariants

It computes the decomposition of the factor group of this group by its derived subgroup (which is abelian), and returns the primary decomposition of that abelian group.

The abelian invariants are sorted in weakly increasing order.

Example

>>> G = replab.PermutationGroup.cyclic(100);
>>> isequal(G.abelianInvariants, [4 25])
    1
Returns

Group abelian invariants

Return type

integer(1,*)

abstractGroup(self)

Returns an abstract group isomorphic to this finite gorup

The generators of the abstract group must be in one-to-one correspondance with the generators of this group, and their names are taken from generatorNames

Returns

An abstract group isomorphic to this group

Return type

replab.AbstractGroup

abstractIsomorphism(self)

Returns an isomorphism to an abstract group

Example

>>> G = replab.S(3);
>>> f = G.abstractIsomorphism;
>>> f.imageElement([2 3 1])
    'x1'
Returns

Isomorphism to an abstract group

Return type

FiniteIsomorphism

center(self)

Returns the center of this group

Returns

The center

Return type

FiniteGroup

centralizer(self, arg)

Returns the centralizer of the given object in this group

Example

>>> G = replab.S(4);
>>> C = G.centralizer([2 3 1 4]);
>>> C == replab.PermutationGroup.of([2 3 1 4])
  1

Example

>>> G = replab.S(4);
>>> C = G.centralizer(G.subgroup({[2 3 1 4]}));
>>> C == replab.PermutationGroup.of([2 3 1 4])
  1
Parameters

rhs (FiniteGroup or group element) – Element to compute the centralizer of

Returns

The centralizer

Return type

FiniteGroup

characterTable(self)

Alias for complexCharacterTable

Returns

Complex character table

Return type

ComplexCharacterTable

closure(self, varargin)

Computes the group generated by the elements of this group and other elements/groups

Arguments can be either elements of type or FiniteGroup of the same type.

Example

>>> G = replab.PermutationGroup.cyclic(3);
>>> S3 = replab.S(3);
>>> H = S3.subgroup({[2 1 3]});
>>> C = G.closure(H);
>>> C == S3
    1
Returns

The closure

Return type

FiniteGroup

complexCharacterTable(self)

Returns the complex character table of this group

The complex character table is the standard, textbook character table of the group.

Note that randomized techniques are used to find group isomorphisms, and thus the output of this method may not be deterministic.

Raises

An error if the character table cannot be computed.

Returns

Complex character table

Return type

ComplexCharacterTable

conjugacyClass(self, g, varargin)

Returns the conjugacy class corresponding to the given element

Parameters

g (element) – Arbitrary group element

Keywords Args:

isCanonical (logical, optional): Whether the given g is the class canonical representative, default: false centralizer (FiniteGroup, optional): Centralizer of the given element

Returns

The conjugacy class containing the given element

Return type

ConjugacyClass

conjugacyClasses(self)

Returns the conjugacy classes of this group

Returns

Conjugacy classes

Return type

ConjugacyClasses

conjugatingAutomorphism(self, by)

Returns the morphism that corresponds to left conjugation by an element

Parameters

by (element of type) – Element to conjugate the group with

Returns

Conjugating automorphism

Return type

replab.FiniteMorphism

derivedSeries(self)

Returns the derived series of this group

Returns

Return type

cell(1,*) of FiniteGroup

derivedSubgroup(self)

Computes the derived subgroup of this group

Example

>>> S4 = replab.S(4);
>>> S4.order
    24
>>> D = S4.derivedSubgroup;
>>> D == replab.PermutationGroup.alternating(4)
    1
Returns

The derived subgroup

Return type

replab.FiniteGroup

doubleCoset(self, element, rightSubgroup, varargin)

Returns a double coset

Returns the set self * element * rightSubgroup.

Parameters
  • element (group element) – Group element

  • rightSubgroup (FiniteGroup) – Finite group

  • group – Group containing both self and element, computed if omitted

  • isCanonical – Whether the given element is canonical w.r.t. to the group ordering

Kwtype group

FiniteGroup, optional

Kwtype isCanonical

logical, optional

Returns

The constructed double coset

Return type

replab.DoubleCoset

doubleCosets(self, leftSubgroup, rightSubgroup)

Returns the set of double cosets in this group by the given groups

Example

>>> n = 5;
>>> G = replab.S(n);
>>> H = G.pointwiseStabilizer(n);
>>> cosets = G.doubleCosets(H, H);
>>> cosets.nElements
    2

Example

>>> G = replab.S(3);
>>> H = replab.PermutationGroup.of([2 1 3]);
>>> K = replab.PermutationGroup.of([3 2 1]);
>>> cosets = G.doubleCosets;
>>> cosets.nElements
    2
Parameters
Returns

The set of double cosets

Return type

replab.DoubleCosets

elementOrder(self, g)

Returns the order of a group element

Parameters

g (element of this group) – Group element

Returns

The order of g, i.e. the smallest o such that g^o == identity

Return type

vpi

exponent(self)

Returns the group exponent

The group exponent is the smallest integer e such that g^e == identity for all g in G.

Returns

The group exponent

Return type

vpi

factorizeFlat(self, elementOrCoset)

Factorizes an element or a coset as a flat sequence in the generators

See imageFlat for the convention.

If a coset is given, this method tries to pick a coset element with a short factorization.

Parameters

elementOrCoset (element or coset of this group) – Element or coset to factorize

Returns

Flat sequence of the word in the generators

Return type

integer(1,*)

factorizeWord(self, elementOrCoset)

Factorizes an element or a coset as a word in the generators

If a coset is given, this method tries to pick a coset element with a short factorization.

Example

>>> G = replab.S(3);
>>> G.factorizeWord([2 3 1])
    'x1'
>>> H = G.withGeneratorNames({'s', 't'});
>>> H.factorizeWord([2 3 1])
    's'
Parameters

elementOrCoset (element or coset of this group) – Element to factorize

Returns

Word representing the element

Return type

charstring

fastRecognize(self)

Attempts to recognize this group in the standard atlas

Returns

A result in case the group is identified; or [] if unrecognized.

Return type

FiniteIsomorphism or []

findIsomorphism(self, to)

Finds an isomorphism from this finite group to another finite group, if it exists

Parameters

to (replab.FiniteGroup) – Target of the isomorphism

Returns

The isomorphism if it exists, or an empty array

Return type

FiniteIsomorphism or []

findIsomorphisms(self, to, varargin)

Finds all the isomorphisms from this finite group to another finite group

Example

>>> G = replab.S(6);
>>> m = G.findIsomorphisms(G, 'upToConjugation', true);
>>> length(m)
    2
Parameters
  • to (replab.FiniteGroup) – Target of the isomorphism

  • upToConjugation – Whether to list morphisms up to conjugation of the image group, default: false

  • single – Whether to return maximum a single result, default: false

Kwtype upToConjugation

logical, optional

Kwtype single

logical, optional

Returns

The isomorphisms

Return type

cell(1,*) of FiniteIsomorphism

findLeftConjugations(self, s, t, varargin)

Returns the set of all elements that left conjugates an element to another element

Let s and t be two elements of this group. This returns the set of all elements b such that t = b s b^-1 or t = leftConjugate(b, s).

When no such b exists, this returns [].

Parameters
  • s (group element) – Source element

  • t (group element) – Target element

  • sCentralizer – Centralizer of s in this group

  • tCentralizer – Centralizer of t in this group

Kwtype sCentralizer

FiniteGroup, optional

Kwtype tCentralizer

FiniteGroup, optional

Returns

Set of all elements of this group that left conjugates s to t if it exists

Return type

replab.LeftCoset or []

findMorphisms(self, to, varargin)

Finds all the morphisms from this finite group to another finite group

Example

>>> S3 = replab.S(3);
>>> S4 = replab.S(4);
>>> m = S4.findMorphisms(S3, 'upToConjugation', true, 'surjective', false);
>>> length(m)
    3
Parameters
  • to (replab.FiniteGroup) – Target of the morphism

  • upToConjugation – Whether to list morphisms up to conjugation of the image group, default: false

  • surjective – Whether to consider only surjective morphisms (or epimorphisms), whose image span to, default: false

  • single – Whether to return maximum a single result, default: false

Kwtype upToConjugation

logical, optional

Kwtype surjective

logical, optional

Kwtype single

logical, optional

Returns

The morphisms

Return type

cell(1,*) of FiniteMorphism

flatToWord(self, letters)

Prints a word described by letters into a string

Parameters

letters (integer(1,*)) – Letters composing the word

Returns

Word in the generators

Return type

charstring

generator(self, i)

Returns the i-th group generator

Parameters

i (integer, charstring) – Generator index or name

Returns

i-th group generator

Return type

element

generatorInverse(self, i)

Returns the inverse of the i-th group generator

Parameters

i (integer, charstring) – Generator index or name

Returns

Inverse of the i-th group generator

Return type

element

generatorNames(self)

Returns the names of the group generators

Returns

Generator names

Return type

cell(1,*) of charstring

imageFlat(self, letters)

Returns the image of a flat word in the group generators

The letters take the values 1...nG which represent the group generators, and also the values -nG...-1 which represent the inverses of those generators.

Parameters

letters (integer(1,*)) – Letters composing the word.

Returns;

element: Element of the group corresponding to the given word

imageWord(self, word)

Computes the image of a word in the group generators

Example

>>> G = replab.S(3);
>>> G.imageWord('x1')
    2 3 1
Parameters

word (charstring) – Word written using mathematical notation

Returns

Element of the group corresponding to the given word

Return type

element

intersection(self, G)

Computes the intersection of two groups

Example

>>> D12 = replab.PermutationGroup.of([1 6 5 4 3 2], [2 1 6 5 4 3]);
>>> G = replab.PermutationGroup.of([2 1 3 4 5 6], [2 3 4 5 1 6]);
>>> I = D12.intersection(G);
>>> I == replab.PermutationGroup.of([5 4 3 2 1 6])
    1
Parameters

G (replab.FiniteGroup) – Group with the same type as this group

Returns

Subgroup representing the intersection

Return type

replab.FiniteGroup

isCommutative(self)

Returns whether this group is commutative

isCyclic(self)

Returns whether this group is a cyclic group

Example

>>> C3 = replab.PermutationGroup.cyclic(3);
>>> C3.isCyclic
    1
>>> C3_C3 = C3.directProduct(C3);
>>> C3_C3.isCommutative
    1
>>> C3_C3.isCyclic
    0
Returns

True if the group is cyclic

Return type

logical

isIsomorphicTo(self, target)

Returns whether this group is isomorphic to another group

Example

>>> h1 = [2 1 3 4];
>>> h2 = [3 4 1 2];
>>> H = replab.PermutationGroup.of(h1, h2);
>>> D = replab.D(4);
>>> H.isIsomorphicTo(D)
    1
Parameters

target (replab.FiniteGroup) – Finite group to test for isomorphism

Returns

Whether this group is isomorphic to the given group

Return type

logical

isMorphismByImages(self, target, varargin)

Checks whether the given images describe a group morphism

The calling convention of this method is the same as morphismByImages, except that nChecks is missing.

Parameters
  • target (replab.Group) – Target group

  • preimages – Preimages of the morphism which generate self, defaults to self.generators

  • images – Images of the given preimages, defaults to target.generators if target is a FiniteGroup

Kwtype preimages

cell(1, *) of self elements

Kwtype images

cell(1, *) of target elements

Returns

True if the given images define a morphism

Return type

logical

isNormalSubgroupOf(self, rhs)

Returns whether this group is a normal subgroup of another group

Example

>>> S3 = replab.S(3);
>>> A3 = replab.PermutationGroup.alternating(3);
>>> A3.isNormalSubgroupOf(S3)
    1

Example

>>> S3 = replab.S(3);
>>> G = S3.subgroup({[2 1 3]});
>>> G.isNormalSubgroupOf(S3)
    0
Parameters

rhs (replab.FiniteGroup) – Other group with the same type as this one

Returns

True if this group is a normal subgroup of rhs

Return type

logical

isNormalizedBy(self, element)

Returns whether a given element/group normalizes this group

This is true when element * group * == group * element.

The same definition when element is a group; then we ask that all this group elements satisfy that property.

Parameters

element (group element or FiniteGroup) – Group element or group

Returns

True if the given element/group normalizes this group

Return type

logical

isSimple(self)

Returns whether this group is simple

Example

>>> S5 = replab.S(5);
>>> S5.isSimple
    0
>>> A5 = S5.derivedSubgroup;
>>> A5.isSimple
    1
Returns

True if the group is simple

Return type

logical

isSubgroupOf(self, rhs)

Returns whether this group is a subgroup of another group

Example

>>> S3 = replab.S(3);
>>> G = S3.subgroup({[2 1 3]});
>>> G.isSubgroupOf(S3)
    1
Parameters

rhs (replab.FiniteGroup) – Other group with the same type as this one

Returns

True if this group is a subgroup of rhs

Return type

logical

isTrivial(self)

Tests whether this group is trivial

Returns

True if this group is trivial (i.e. has only one element)

Return type

logical

isomorphismByFunction(self, target, imageElementFun, varargin)

Constructs an isomorphism to a finite group using an image function

Due to the additional structure on target, this method returns a FiniteIsomorphism, and does not need an explicit preimage function.

Parameters
  • target (FiniteGroup or FiniteGroupType) – Finite group isomorphic to the present group

  • imageElementFun (function_handle) – Function that computes the image of a source element

  • preimageElementFun – Function the computes the preimage of a target element

Kwtype preimageElementFun

function_handle, optional

Returns

The constructed isomorphism

Return type

FiniteIsomorphism

isomorphismByImages(self, target, varargin)

Constructs an isomorphism to a group using images of generators

Parameters
  • target (FiniteGroup or FiniteGroupType) – Target of the isomorphism

  • preimages – Preimages of the isomorphism which generate self, defaults to self.generators

  • images – Images of the given preimages, defaults to target.generators

  • imageElementFun – Image function, default: []

  • nChecks – Number of randomized image checks to perform, if inf computes and verifies a presentation of self

Kwtype preimages

cell(1, *) of self elements

Kwtype images

cell(1, *) of target elements

Kwtype imageElementFun

function_handle or [], optional

Kwtype nChecks

integer or inf

knownComplexCharacterTable(self)

Returns whether the complex character table of this group is already known or computed

Returns

Whether the table is already computed

Return type

logical

knownOrder(self)

Returns whether the order of this group has already been computed

Returns

True if the order is known

Return type

logical

knownRealCharacterTable(self)

Returns whether the real character table of this group is already known or computed

Returns

Whether the table is already computed

Return type

logical

knownRelators(self)

Returns whether the relators of this group are known

Returns

True if the relators are known already

Return type

logical

leftConjugateGroup(self, by)

Returns the left conjugate of the current group by the given element

res = self.leftConjugateGroup(by)

In particular, it ensures that res.generator(i) = self.type.leftConjugate(by, self.generator(i))

Parameters

by (element of type) – Element to conjugate the group with

Returns

The conjugated group

Return type

replab.FiniteGroup

leftCoset(self, element, varargin)

Returns a left coset

Returns the set element * self.

Parameters
  • element (group element) – Group element

  • group – Group containing both self and element, computed if omitted

  • isCanonical – Whether the given element is canonical w.r.t. to the group ordering

Kwtype group

FiniteGroup, optional

Kwtype isCanonical

logical, optional

Returns

The constructed right coset

Return type

replab.LeftCoset

leftCosets(self, subgroup)

Returns the set of left cosets of the given subgroup in this group

Parameters

subgroup (replab.FiniteGroup) – Subgroup of this group

Returns

Left cosets

Return type

replab.LeftCosets

mldivide(self, supergroup)

Shorthand for rightCosets

morphismByImages(self, target, varargin)

Constructs a morphism to a group using images of generators

The type of the morphism depends on the type of target:

Example

>>> S4 = replab.S(4);
>>> m = S4.morphismByImages(replab.S(3), 'images', {[1 3 2] [3 2 1]});
>>> m.laws.checkSilent
    1
Parameters
  • target (Group or FiniteGroup) – Target of the morphism, the morphism image is a subgroup of this

  • preimages – Preimages of the morphism which generate self, defaults to self.generators

  • images – Images of the given preimages, defaults to target.generators if target is a FiniteGroup

  • imageElementFun – Image function, default: []

  • nChecks – Number of randomized image checks to perform, if inf computes and verifies a presentation of self

Kwtype preimages

cell(1, *) of self elements

Kwtype images

cell(1, *) of target elements

Kwtype imageElementFun

function_handle or [], optional

Kwtype nChecks

integer or inf

Returns

The constructed morphism

Return type

Morphism or FiniteMorphism

mrdivide(self, subgroup)

Shorthand for leftCosets

nGenerators(self)

Returns the number of group generators

Returns

Number of group generators

Return type

integer

normalClosure(self, obj)

Computes the normal closure of an object in the closure of this group and this object

Example

>>> S5 = replab.S(5);
>>> S4 = S5.subgroup({[2 3 4 1 5] [2 1 3 4 5]});
>>> nc = S4.normalClosure([1 2 4 5 3]); % demonstrates both syntaxes
>>> nc = S4.normalClosure(S5.subgroup({[1 2 4 5 3]}));
>>> nc == S5.subgroup({[1 2 4 5 3] [5 2 3 1 4] [2 5 3 4 1]})
    1

Example

>>> S4 = replab.S(4);
>>> nc = S4.normalClosure(S4.subgroup({[2 3 1 4]}));
>>> nc == S4.subgroup({[2 3 1 4] [1 3 4 2]})
    1
Parameters

obj (FiniteGroup or element of type) – Group or element to compute the normal closure of

Returns

The normal closure of obj in this group

Return type

replab.FiniteGroup

normalCoset(self, element, varargin)

Returns a normal coset

Returns the set element * self == self * element.

Parameters
  • element (group element) – Group element

  • group – Group containing both self and element, computed if omitted

  • isCanonical – Whether the given element is canonical w.r.t. to the group ordering

Kwtype group

FiniteGroup, optional

Kwtype isCanonical

logical, optional

Returns

The constructed normal coset

Return type

replab.NormalCoset

normalCosets(self, subgroup)

Returns the set of normal cosets of the given subgroup in this group

Parameters

subgroup (replab.FiniteGroup) – Normal subgroup of this group

Returns

The set of normal cosets

Return type

NormalCosets

order(self)

Returns the group order

Returns

The group order

Return type

vpi

orderPreservingPermutationIsomorphism(self)

Returns an isomorphism from this group to a permutation group, which preserves element order

Returns

Isomorphism with replab.FiniteIsomorphism.preservesTypeOrder set

Return type

replab.FiniteIsomorphism

permutationGroup(self)

Returns the permutation group isomorphic to this finite group

The generators of the permutation group are in one-to-one correspondance with the generators of this group.

This is the image of permutationIsomorphism.

Returns

A permutation group isomorphic to this group

Return type

replab.PermutationGroup

permutationIsomorphism(self)

Returns an isomorphism from this group to a permutation group

Compared to orderPreservingPermutationIsomorphism, this isomorphism may be more efficient to compute or use.

Returns

Isomorphism

Return type

replab.FiniteIsomorphism

permutationRep(self, dimension, varargin)

Constructs a permutation representation of this group

The returned representation is real. Use replab.Rep.complexification to obtain a complex representation.

Example

>>> C3 = replab.PermutationGroup.cyclic(3);
>>> rep = C3.permutationRep(3, 'preimages', {[2 3 1]}, 'images', {[3 1 2]});
>>> rep.dimension
    3
Parameters
  • dimension (integer) – Dimension of the representation

  • preimages – Preimages of the representation map which generate self, defaults to self.generators

  • images – Images of the generators as permutations of size dimension

Kwtype preimages

cell(1,n) of self elements, optional

Kwtype images

cell(1,*) of permutations

Returns

The constructed group representation

Return type

replab.Rep

presentation(self)

Returns a presentation of this group as a string

Returns

Presentation

Return type

charstring

randomProperSubgroup(self, nSteps)

Constructs a random proper subgroup of this group

The call fails if no proper subgroup exists.

Parameters

nSteps (integer, optional) – How many steps of reduction to perform, default 1

Returns

A proper subgroup

Return type

FiniteGroup

randomSubgroup(self)

Constructs a random subgroup of this group

Compared to randomProperSubgroup, this method can return the trivial group or self. This method never fails.

Returns

A subgroup

Return type

FiniteGroup

realCharacterTable(self)

Returns the real character table of this group

Note that randomized techniques are used to find group isomorphisms, and thus the output of this method may not be deterministic.

Raises

An error if the character table cannot be computed.

Returns

Real character table

Return type

RealCharacterTable

recognize(self)

Attempts to recognize this group in the standard atlas

Returns

A result in case the group is identified; or [] if unrecognized.

Return type

FiniteIsomorphism or []

regularIsomorphism(self)

Returns an isomorphism from this group to a permutation group whose degree matches the order of this group

Returns

Isomorphism

Return type

replab.FiniteIsomorphism

regularRep(self)

Returns the left regular representation of this group

Returns

The left regular representation as a real permutation representation

Return type

Rep

relatorsFlat(self)

Returns the relators of a presentation of this finite group in the flat format

See AbstractGroup for a description of the presentation of a finite group

Returns

Relators in flat form

Return type

cell(1,*) of integer(1,*)

relatorsWord(self)

Returns the relators of a presentation of this finite group

Returns

Relators in word form

Return type

cell(1,*) of charstring

repByImages(self, field, dimension, varargin)

Constructs a finite dimensional representation of this group from preimages/images pairs

The preimages need to generate this group. If the preimages are omitted, they default to the generators of this group.

The images can either be exact, in which case they should be provided as cyclotomic matrices, or as double matrices – the latter only if they have integer entries. In the case of exact images, the keyword argument imagesErrorBound can be omitted. When images are exact, RepLAB has the freedom of performing matrix products containing an arbitrary number of factors without loss of precision, and thus a wider range of algorithm can be used. Also, the constructed representation can return exact images using rep.image(g, 'exact')

Otherwise, the provided images will be considered inexact. In that case, RepLAB uses a factorization algorithm to decompose group elements as short words in the preimages. The keyword argument imagesErrorBound should be given as well; it corresponds to an upper bound on the error of the matrix images in the Frobenius norm. Either a single number can be provided, as an upper bound on all images in the provided set; or an individual bound for each image. However, this error bound will be ignored for each image provided as an interval matrix. If inexact floating-point images are provided but imagesErrorBound is omitted, an ad-hoc error is estimated and a warning is emitted.

If the images are exact, the isUnitary keyword parameter can be omitted.

Example

>>> S4 = replab.S(4);
>>> m = S4.repByImages('R', 1, 'images', {-1 -1});
>>> m.laws.checkSilent
    1
Parameters
  • field ({'R', 'C'}) – Whether the representation is real (R) or complex (C)

  • dimension (integer) – Representation dimension

  • preimages – Preimages of the representation map which generate self, defaults to self.generators

  • images – Images of the given preimages

  • imagesErrorBound – Error

  • isUnitary – Value of the constructed Rep.isUnitary; a “true” value accelerates computations

  • isIrreducible – Value of the constructed Rep.isIrreducible

  • trivialDimension – Value of the constructed Rep.trivialDimension

  • frobeniusSchurIndicator – Value of the constructed Rep.frobeniusSchurIndicator

  • 'H->R (divisionAlgebraName % ('R->C', 'C->R', 'H->C',) – rep’, ‘’, optional): Name of the division algebra encoding this representation respects, default ''

Kwtype preimages

cell(1,n) of self elements, optional

Kwtype images

cell(1,n) of double(d,d) or cyclotomic(d,d), may be sparse

Kwtype imagesErrorBound

double or double(1,d) or []

Kwtype isUnitary

logical or [], optional

Kwtype isIrreducible

logical or [], optional

Kwtype trivialDimension

integer or [], optional

Kwtype frobeniusSchurIndicator

integer or [], optional

Returns

The constructed group representation

Return type

replab.RepByImages

rightCoset(self, element, varargin)

Returns a right coset

Returns the set self * element.

Parameters
  • element (group element) – Group element

  • group – Group containing both self and element, computed if omitted

  • isCanonical – Whether the given element is canonical w.r.t. to the group ordering

Kwtype group

FiniteGroup, optional

Kwtype isCanonical

logical, optional

Returns

The constructed right coset

Return type

replab.RightCoset

rightCosets(self, subgroup)

Returns the set of right cosets of the given subgroup in this group

Parameters

subgroup (replab.FiniteGroup) – Subgroup of this group

Returns

Right cosets

Return type

replab.RightCosets

setComplexCharacterTable(self, table)

Sets the complex character table of this group

Throws an error if this method or complexCharacterTable has already been called before.

Parameters

table (ComplexCharacterTable) – Complex character table

setConjugacyClasses(self, classes)

Sets the conjugacy classes of this group

Throws an error if this method or conjugacyClasses has already been called before.

Parameters

classes (ConjugacyClasses) – Conjugacy classes

setRealCharacterTable(self, table)

Sets the real character table of this group

Throws an error if this method or realCharacterTable has already been called before.

Parameters

table (RealCharacterTable) – Complex character table

signedPermutationRep(self, dimension, varargin)

Returns a real signed permutation representation of this group

The returned representation is real. Use rep.complexification to obtain a complex representation.

>>> S2 = replab.S(2);
>>> rep = S2.signedPermutationRep(1, 'preimages', {[2 1]}, 'images', {[-1]});
>>> rep.image([2 1])
    -1
Parameters
  • dimension – Dimension of the representation

  • preimages – Preimages of the representation map which generate self, defaults to self.generators

  • images – Images of the generators as signed permutations of size dimension

Kwtype preimages

cell(1,n) of self elements, optional

Kwtype images

cell(1,*) of signed permutations

Returns

The constructed group representation

Return type

replab.Rep

smallGeneratingSet(self)

Returns a small set of elements generating the group

Returns

Generating set

Return type

cell(1,*) of group elements

subgroup(self, elements, varargin)

Constructs a subgroup of the current group from elements

The generators of the result are the given elements with the identity filtered out.

Example

>>> S5 = replab.S(5);
>>> G = S5.subgroup({[1 2 3 4 5]});
>>> isempty(G.generators)
    1
Parameters
  • elements (cell(1,*) of elements of this group) – List of elements

  • generatorNames – Names of the generators

  • order – Group order

  • relators – Relators

Kwtype generatorNames

cell(1,*) of charstring, optional

Kwtype order

vpi or integer, optional

Kwtype relators

cell(1,*) of charstring or integer(1,*), optional

Returns

The subgroup generated by generators

Return type

replab.FiniteGroup

subgroupWithGenerators(self, generators, varargin)

Constructs a subgroup of the current group from generators

Guarantees that the constructed subgroup preserves the order of the generators. However, the given generators cannot contain the identity element.

Example

>>> S5 = replab.S(5);
>>> G = S5.subgroupWithGenerators({[2 3 4 5 1]});
>>> isequal(G.generators{1}, [2 3 4 5 1])
    1
Parameters
  • generators (cell(1,*) of elements of this group) – List of generators, does not contain the identity

  • generatorNames – Names of the generators

  • order – Group order

  • relators – Relators

Kwtype generatorNames

cell(1,*) of charstring, optional

Kwtype order

vpi or integer, optional

Kwtype relators

cell(1,*) of charstring or integer(1,*), optional

Returns

The subgroup generated by generators

Return type

replab.FiniteGroup

trivialSubgroup(self)

Returns the trivial subgroup of this group

Returns

The trivial subgroup

Return type

replab.FiniteGroup

withGeneratorNames(self, newNames)

Returns a modified copy of this finite group with renamed generators

Parameters

newNames (cell(1,*) of charstring) – New generator names

Returns

Updated copy

Return type

FiniteGroup

wordToFlat(self, word)

Parses a word into generator letters

Parameters

word (charstring) – Word written using mathematical notation

Returns

Letters of the word

Return type

integer(1,*)

MatrixGroup

class replab.MatrixGroup(matrixSize, generators, varargin)

Bases: replab.gen.FiniteGroup

Finite group of matrices with coefficients in the cyclotomic field

The cyclotomic field includes the rational numbers, square roots of rational numbers, cosines and sines of fractions of pi and complex roots of unity.

The use of MatrixGroup requires the availability of the Java Virtual Machine, as computations are done in exact precision using a Scala/Java library.

RepLAB implements matrix groups by enumerating all their elements explicitly, which is adequate for groups with a few hundred elements.

Matrix groups are constructed by calling the constructor of MatrixGroup as below, specifying the dimension and the matrix generators. Note that generators are specified in any way that could be passed to the cyclotomic constructor, which includes a string representation. However, one should not pass a floating-point inexact matrix such as [1/sqrt(2), 1/sqrt(2); -1/sqrt(2), 1/sqrt(2)], because RepLAB is not able to guess the exact representation of 0.7071... then.

Example

>>> m1 = [0 1; 1 0]; % doctest: +cyclotomic
>>> m2 = '[1/sqrt(2), 1/sqrt(2); -1/sqrt(2), 1/sqrt(2)]';
>>> M = replab.MatrixGroup(2, {m1, m2});
>>> M.order
    16

The natural representation of a matrix group is given by the matrix itself, see naturalRep .

Own members

MatrixGroup(matrixSize, generators, varargin)

Constructs a finite matrix group

Additional keyword arguments (type, nice and niceIsomorphism) are used internally but are not part of the public API.

Parameters
  • matrixSize (integer) – Siye of the matrices

  • generators (cell(1,*) of replab.cyclotomic(matrixSize,matrixSize)) – Group generators

  • generatorNames – Names of the generators

  • order – Order of the group

  • relators – Relators given either in word or letter format

Kwtype generatorNames

cell(1,*) of charstring

Kwtype order

vpi, optional

Kwtype relators

cell(1,*) of charstring

naturalRep(self, varargin)

Returns the natural representation of this matrix group

The natural representation rho has images rho(g) = g.

Example

>>> M = replab.MatrixGroup(2, {[0 1; 1 0], '[1/sqrt(2), 1/sqrt(2); -1/sqrt(2), 1/sqrt(2)]'}); % doctest: +cyclotomic
>>> M.naturalRep.isIrreducible
    1
Parameters

field – Field over which to define the representation, default: ‘C’

Kwtype field

{‘R’ or ‘C’}

Returns

The natural representation of this group

Return type

Rep