# Permutation groups¶

RepLAB provides ways to work with permutation groups.

Permutation groups are finite groups that are subgroups of the symmetric group acting on n elements.

In particular, the decomposition of $$\{1,...,n\}$$ into orbits, the natural action and representation of the group are all defined.

As a closely related variant, we describe signed permutations. Signed permutations act on the domain $$\{-n,...,-1, 1,...,n\}$$.

## Permutation¶

class replab.Permutation

This class regroups functions that are useful when dealing with permutations.

In RepLAB, permutations are represented using row vectors of integers, those integers being encoded using the type double; so this class does not have any instances.

### Own members

static cycleStructure(perm)

Returns the cycle structure of the given permutation

Example

>>> isequal(replab.Permutation.cycleStructure([2 1 4 3]), [2 2])
1

Parameters

perm (permutation) – Permutation

Returns

Nonincreasing vector of integers containing the sizes of cycles (for sizes > 1)

Return type

integer(1,*)

static cycles(perm)

Returns the cycles of the given permutation

Example

>>> isequal(replab.Permutation.cycleStructure([2 1 4 3]), [2 2])
1

Parameters

perm (permutation) – Permutation

Returns

Nonincreasing vector of integers containing the sizes of cycles (for sizes > 1)

Return type

integer(1,*)

static fromCycles(n, varargin)

Constructs a permutation from a product of cycles.

Each cycle is given as a row vector, and the sequence of cycles is given as variable arguments.

Parameters
• n (integer) – Domain size

• varargin (cell(1,*) of integer(1,*)) – Sequence of cycles as row vectors of indices

Returns

The permutation corresponding to the product of cycles.

Return type

permutation

static fromMatrix(mat)

Returns the permutation corresponding to the given matrix representation

Parameters

mat – A permutation matrix.

Returns

The permutation corresponding to matrix mat.

Raises

Error – if mat is not a permutation matrix, throws an error

static lexCompare(lhs, rhs)

Returns the comparison of two permutations by lexicographic order

Parameters
• lhs (permutation) – First permutation

• rhs (permutation) – Second permutation

Returns

1 if lhs > rhs, 0 if lhs == rhs, -1 if lhs < rhs

Return type

integer

static order(perm)

Returns the order of the permutation

Parameters

perm (permutation) – Permutation

Returns

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

Return type

integer

static shift(n, i)

Returns the cyclic permutation that shifts the domain indices by i.

Parameters
• n (integer) – Domain size

• i (nonnegative integer) – Shift so that j is sent to j + i (wrapping around).

Returns

The constructed cyclic shift

Return type

permutation

static sign(perm)

Returns the sign of a given permutation

Example

>>> replab.Permutation.sign([3 2 1 4])
-1

Parameters

perm (permutation) – Permutation to compute the sign of

Returns

Sign of the permutation

Return type

integer

static sorting(array, greaterFun)

Returns the permutation that sorts a cell array using a custom comparison function

Parameters
• array – A (row or column) vector array containing data of arbitrary type

• greaterFun – A function handle that compares elements such that greaterFun(x, y) == true when x > y and false otherwise

Returns

A permutation p such that sorted = array(p)

static toMatrix(perm)

Returns the permutation matrix corresponding to the given permutation

The returned matrix is such that matrix multiplication is compatible with composition of permutations, i.e. for Sn = replab.S(domainSize) we have replab.permutation.toMatrix(Sn.compose(x, y)) = replab.Permutation.toMatrix(x) * replab.Permutation.toMatrix(y)

Parameters

perm (permutation) – Permutation

Returns

The permutation matrix corresponding to perm.

static toSparseMatrix(perm)

Returns the sparse permutation matrix corresponding to the given permutation

The returned matrix is such that matrix multiplication is compatible with composition of permutations. I.e. for Sn = replab.S(n) we have replab.Permutation.toMatrix(Sn.compose(x, y)) = replab.Permutation.toMatrix(x) * replab.Permutation.toMatrix(y)

Parameters

perm (permutation) – Permutation

Returns

The sparse permutation matrix corresponding to perm.

static transposition(n, i, j)

Returns the transposition permuting i and j.

Parameters
• n (integer) – Domain size

• i (integer) – First domain element to be transposed.

• j (integer) – Second domain element to be transposed.

Returns

The constructed transposition

Return type

permutation

## PermutationGroup¶

class replab.PermutationGroup(domainSize, generators, varargin)

Permutation group over the integer 1, .., domainSize

### Own members

generatorNames_

Generator names

Type

cell(1,*) of charstring

PermutationGroup(domainSize, generators, varargin)

Constructs a permutation group

Parameters
• domainSize (integer) – Domain size of this permutation group

• generators (cell(1,*) of permutation) – Group generators

• chain – BSGS chain describing the group

• generatorNames – Names of the generators

• order – Order of the group

• relators – Relators given either in word or letter format

Kwtype chain

replab.bsgs.Chain

Kwtype generatorNames

cell(1,*) of charstring

Kwtype order

vpi, optional

Kwtype relators

cell(1,*) of charstring

static alternating(n)

Constructs the alternating group

Parameters

n (integer) – Group degree

Returns

The alternating group of degree n

Return type

replab.PermutationGroup

chain(self)

Returns the stabilizer chain corresponding to this permutation group.

Returns

Stabilizer chain

Return type

replab.bsgs.Chain

static cyclic(n)

Constructs the cyclic group of order n acting on n points

Parameters

n (integer) – Cyclic group order and domain size

Returns

The cyclic group of given order/domain size

Return type

replab.PermutationGroup

static dihedral(n)

Constructs the dihedral group of order 2*n

This corresponds to the group of symmetries of the polygon with n vertices

Parameters

n (integer) – Half the dihedral group order

Returns

The dihedral group permuting the vertices of the n-gon

Return type

replab.PermutationGroup

factorization(self)

Returns an object able to compute factorizations in the group generators

Returns

A factorization instance

Return type

replab.mrp.Factorization

static fromChain(chain)

Creates a permutation group from a BSGS chain

This method is mostly used internally.

Parameters

chain (replab.bsgs.Chain) – BSGS chain

Returns

Permutation group

Return type

PermutationGroup

generatorsAsMatrix(self)

Returns the generators of this group concatenated in a matrix

Returns

Matrix whose rows are the group generators

Return type

integer(*,*)

indexRelabelingMorphism(self, indexRange)

Returns the morphism the permutation action of this group on tensor coefficients

The tensor coefficients correspond to R^ir x R^ir ... (domainSize times) where ir = indexRange.

The enumeration of indices is done in the same order as in indexRelabelingPermutation: if I = (i1, ..., id) is a sequence of indices, we increment first id, then i_{d-1} and so on.

Parameters

indexRange (integer) – Dimension of each subindex

Returns

The permutation group homomorphism

Return type

function_handle

indexRelabelingPermutation(self, g, indexRange)

Returns the permutation that acts by permuting tensor coefficients

Let I = (i_1, ..., i_d) be a sequence of indices, where d = self.domainSize and 1 <= i_1,...,i_d <= indexRange

We enumerate elements of I by first incrementing i_d, then i_{d-1}, etc…

We compute the permutation of domain size indexRange^domainSize that acts on the indices of I according to the argument g.

Parameters
• g (permutation) – Permutation of subindices

• indexRange (integer) – Dimension of each subindex

Returns

The permutation on the enumeration of indices

Return type

permutation

indexRelabelingRep(self, indexRange)

Representation that permutes the indices of a tensor

It acts on the tensor space R^ir x R^ir … (domainSize times) where ir = indexRange, by permuting the indices.

The representation returned is real.

Parameters

indexRange (integer) – Dimension of the tensor components/range of the subindices

Returns

The desired permutation representation

Return type

replab.Rep

static kleinFourGroup()

Constructs the Klein Four-Group

This corresponds to the symmetry group of a non-square rectangle, and corresponds to the direct product S2 x S2.

Returns

The Klein four-group as a permutation gorup

Return type

replab.PermutationGroup

lexChain(self)

Returns the reduced stabilizer chain corresponding to this permutation group in lexicographic order

No base points are redundant.

Returns

Stabilizer chain

Return type

replab.bsgs.Chain

matrixAction(self)

Returns the simultaneous action of permutations on both rows and columns of square matrices

Acts on matrices of size self.domainSize x self.domainSize

Returns

The matrix action

Return type

replab.Action

matrixFindPermutationsTo(self, S, T, SStabilizer, TStabilizer)

Finds the permutations that send a matrix to another matrix

We return the set of p such that T == S(inverse(p),inverse(p)) or S == T(p,p).

We use this notation as the left action of p on a matrix S is given by S(inverse(p),inverse(p)).

Parameters
• S (double(1,domainSize)) – Source matrix

• T (double(1,domainSize)) – Target matrix

• SStabilizer (PermutationGroup or [], optional) – Stabilizer of S

• TStabilizer (PermutationGroup or [], optional) – Stabilizer of T

Returns

The set of permutations {p} such that T == S(inverse(p),inverse(p)); or [] if no element found

Return type

replab.LeftCoset

matrixStabilizer(self, matrix)

Returns the permutation subgroup that leaves a given matrix invariant by joint permutation of its rows and columns

Example

>>> S4 = replab.S(4);
>>> A = [1 1 0 1; 1 1 1 0; 0 1 1 1; 1 0 1 1]; % adjacency matrix of the square
>>> G = S4.matrixStabilizer(A);
>>> G.order == 8 % is the dihedral group of order 8
1

Parameters

matrix (double(domainSize,domainSize)) – Matrix to stabilize under permutation

Returns

The subgroup of this group such that every element g satisfies matrix(g,g) == matrix

Return type

PermutationGroup

naturalAction(self)

Returns the natural action of elements of this group on its domain

This group natural domain is the set of integers {1..domainSize}

Returns

The natural action

Return type

replab.Action

naturalRep(self)

Returns the natural permutation representation of this permutation group

Returns

The (real) natural permutation representation

Return type

replab.Rep

static of(varargin)

Constructs a nontrivial permutation group from the given generators

Example

>>> G = replab.PermutationGroup.of([2 3 4 1], [4 3 2 1]);
>>> G.order
8


The generators of the group can be named by preceding them all by a charstring:

Example

>>> G = replab.PermutationGroup.of('r', [2 3 4 1], 's', [4 3 2 1]);
>>> G.order
8
>>> G.factorizeWord([3 4 1 2])
'r^2'


This method cannot construct trivial groups without any generators. In that case, use the constructor:

Example

>>> generators = {};
>>> domainSize = 4;
>>> G = replab.PermutationGroup(domainSize, generators);
>>> G.order
1

Parameters

varargin (cell(1,*) of permutation) – Group generators

Returns

The permutation group given as the closure of the generators

Return type

PermutationGroup

orbits(self)

Returns the partition of the domain into orbits under this group

Permutation group orbits are also called domains of transitivity, see https://www.encyclopediaofmath.org/index.php/Transitive_group

Returns

The orbit partition

Return type

Partition

orderedPartitionStabilizer(self, partition)

Computes the subgroup that leaves the given ordered partition invariant

The subgroup maps every block of the partition to itself under permutation of the domain elements.

Example

>>> S4 = replab.S(4);
>>> G = S4.orderedPartitionStabilizer(replab.Partition.fromVector([1 1 2 2]));
>>> G == S4.subgroup({[2 1 3 4] [1 2 4 3]})
1

Parameters

partition (Partition) – Ordered partition to leave invariant

Returns

The subgroup that stabilizes the ordered partition

Return type

PermutationGroup

partialChain(self)

Returns the stabilizer chain corresponding to this permutation group if it can be computed quickly

static permutingGivenPoints(n, points)

Constructs the group that permutes the given points

Essentially constructs the symmetric group of order |points|.

Parameters
• n (integer) – Domain size of the created group

• points (integer(1,*)) – Set of points being permuted

Returns

The permutation group

Return type

PermutationGroup

pointwiseStabilizer(self, set)

Returns the subgroup that stabilizes the given set pointwise

i.e. for this group G, it returns H = {g \in G : g(i) = i, i \in set}.

Example

>>> S4 = replab.S(4);
>>> G = S4.pointwiseStabilizer([1 2]);
>>> G.order == 2
1

Parameters

set (integer(1,*)) – The set to stabilize pointwise

Returns

The subgroup that stabilizes the set pointwise

Return type

replab.PermutationGroup

setwiseStabilizer(self, set)

Returns the subgroup that stabilizes the given set as a set

i.e. for this group G, it returns H = {g \in G : g(set) = set}

Example

>>> G = replab.PermutationGroup.of([3 1 2 4], [1 4 2 3]);
>>> H = G.setwiseStabilizer([1 2]);
>>> H == replab.PermutationGroup.of([2 1 4 3])
1


Example

>>> G = replab.PermutationGroup.of([1,3,2,10,9,8,6,5,7,4], [1,4,3,2,5,6,7,8,9,10]);
>>> H = G.setwiseStabilizer([2 3]);
>>> H.order
10

Parameters

set (integer(1,*)) – The set to stabilize

Returns

The subgroup that stabilizes the set

Return type

replab.PermutationGroup

signRep(self)

Returns the sign representation of this permutation group

Returns

One dimensional sign representation of this group

Return type

replab.Rep

stabilizer(self, p)

Returns the subgroup that stabilizes a given point

standardRep(self)

Returns the standard representation of this permutation group

It is an abuse of terminology as the “standard representation” is the faithful $$n-1$$ dimensional representation of the symmetric group acting on $$n$$ elements; but we can reuse that subrepresentation on subgroups of the symmetric group.

It corresponds to the representation complementary to the trivial representation with basis [1, 1, ..., 1]'

Returns

The (real) standard representation

Return type

replab.SubRep

static symmetric(n)

Returns the symmetric group acting on a certain domain size

Parameters

domainSize (integer) – Domain size, must be >= 0

Returns

Symmetric group

Return type

replab.PermutationGroup

static trivial(n)

Constructs the trivial permutation group acting on n points

Example

>>> G = replab.PermutationGroup.trivial(4);
>>> G.order
1

Parameters

n (integer) – Domain size

Returns

Trivial group

Return type

replab.PermutationGroup

unorderedPartitionStabilizer(self, partition)

Computes the subgroup that leaves the given unordered partition invariant

Example

>>> S4 = replab.S(4);
>>> G = S4.unorderedPartitionStabilizer(replab.Partition.fromVector([1 1 2 2]));
>>> G == S4.subgroup({[2 1 3 4] [3 4 1 2]})
1

Parameters

partition (Partition) – Unordered partition to leave invariant

Returns

The subgroup that stabilizes the unordered partition

Return type

PermutationGroup

vectorAction(self)

Returns the action of permutations on column vectors

Acts on vectors of size domainSize by permuting their coefficients

Returns

The vector action

Return type

replab.Action

vectorFindLexMinimal(self, s, sStabilizer)

Finds the lexicographic minimal vector under permutation of its coefficients by this group

Example

>>> n = 10;
>>> s = randi([-3 3], 1, n);
>>> G = replab.S(n);
>>> [sml, P] = G.vectorFindLexMinimal(s);
>>> all(sml == sort(s)) % lexmin using the symmetric group is simply a sort
1
>>> all(sml(P.representative) == s)
1

Parameters
• s (double(1,domainSize)) – Vector to permute

• sStabilizer (PermutationGroup or [], optional) – Stabilzier of s

Returns

• sMinLex (double(1,domainSize):) – Minimal lexicographic representative of s under permutation by this group

• P (LeftCoset) – Set of permutations p such that sMinLex == s(inverse(p)) or s == sMinLex(p)

vectorFindPermutationsTo(self, s, t, sStabilizer, tStabilizer)

Finds the permutations that send a vector to another vector

We return the set of p such that t == s(inverse(p)) or s == t(p).

We use this notation as the left action of p on a list s is given by s(inverse(p)).

Parameters
• s (double(1,domainSize)) – Source vector

• t (double(1,domainSize)) – Target vector

• sStabilizer (PermutationGroup or [], optional) – Stabilizer of s

• tStabilizer (PermutationGroup or [], optional) – Stabilizer of t

Returns

The set of permutations {p} such that t == s(inverse(p)); or [] if no element found

Return type

replab.LeftCoset

vectorStabilizer(self, vector)

Returns the permutation subgroup that leaves a given vector invariant

Parameters

vector (double(1,domainSize)) – Vector to stabilize under permutation

Returns

The subgroup of this group leaving vector invariant

Return type

PermutationGroup

wreathProduct(self, A)

Returns the wreath product of a compact group by this permutation group

Note that our notation is reversed compared to the Wikipedia page, the permutation group is on the left hand side, as our convention for semidirect product places the group acted upon on the right.

Note that the return type depends on the argument type: if A is a FiniteGroup, the result will be a finite group too.

Parameters

A (CompactGroup) – The group whose copies are acted upon

Returns

A wreath product group

Return type

replab.WreathProductGroup

## SignedPermutation¶

class replab.SignedPermutation

This class regroups functions that are useful when dealing with signed permutations.

### Own members

static fromMatrix(mat)

Returns the signed permutation corresponding to the given matrix representation or throws an error

static fromPermutation(perm)

Returns the signed permutation corresponding to the given permutation encoding

static isSignedPermutationMatrix(mat)

Returns true when “mat” is a signed permutation matrix, i.e. a monomial matrix with nonzero entries equal to +1 or -1

static toMatrix(signedPerm)

Returns the signed permutation matrix corresponding to the given signed permutation

Such that matrix multiplication is compatible with composition of permutations, i.e. S.toMatrix(S.compose(x, y)) = S.toMatrix(x) * S.toMatrix(y) where S = SignedPermutations(domainSize)

static toPermutation(signedPerm)

Returns the permutation corresponding to the given signed permutation where the permutation acts on the list [-d,..,-1,1,..,d]

## SignedPermutationGroup¶

class replab.SignedPermutationGroup(domainSize, generators, varargin)

Bases: replab.gen.FiniteGroup

A base class for all signed permutation groups

### Own members

domainSize

The integer $$d$$ when this group acts on $$\{-d, .., -1, 1, .., d\}$$

Type

integer

SignedPermutationGroup(domainSize, generators, varargin)

Constructs a signed permutation group

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

Parameters
• domainSize (integer) – Domain size of this permutation group

• generators (cell(1,*) of integer(1,*)) – 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

elementPermutationPart(self, g)

Returns the permutation part of a signed permutation, by taking image absolute values

Computes the permutation p that acts on 1…domainSize as p(i) = abs(g(i))

Parameters

g (signed permutation) – Signed permutation

Returns

The permutation part of g

Return type

permutation

matrixAction(self)

Returns the action of elements of this group on d x d matrices

Note that d = self.domainSize, and this acts by simultaneous permutations of their rows and columns and flipping their signs

naturalAction(self)

Returns the action of elements of this group on {-d..-1 1..d}

Here, d is self.domainSize

naturalRep(self)

Natural representation on R^d of signed permutations on integers -d..-1, 1..d

static of(varargin)

Constructs a nontrivial signed permutation group from the given generators

Example

>>> s = [-1 -2 -3 -4];
>>> i = [2 -1 4 -3];
>>> j = [3 -4 -1 2];
>>> Q = replab.SignedPermutationGroup.of(s, i, j);
>>> Q.order == 8
1


The generators of the group can be named by preceding them all by a charstring:

Example

>>> s = [-1 -2 -3 -4];
>>> i = [2 -1 4 -3];
>>> j = [3 -4 -1 2];
>>> Q = replab.SignedPermutationGroup.of('s', s, 'i', i, 'j', j);
>>> Q.order == 8
1


This method cannot construct trivial groups without any generators. In that case, use the constructor:

Example

>>> generators = {};
>>> domainSize = 4;
>>> G = replab.SignedPermutationGroup(domainSize, generators);
>>> G.order
1

Parameters

varargin (cell(1,*) of signed permutations) – Group generators, pos

Returns

The signed permutation group given as the closure of the generators

Return type

SignedPermutationGroup

permutationPart(self)

Returns the permutation part of the current group

Corresponds to the group image under the homomorphism elementPermutationPart.

Returns

The corresponding permutation group

Return type

replab.PermutationGroup

static signedSymmetric(n)

Creates the signed symmetric group of a given degree

Parameters

n (integer) – Degree of the signed symmetric group

Returns

The signed symmetric group of degree n

Return type

SignedPermutationGroup

vectorAction(self)

Returns the action of elements of this group on vectors

Vectors are (self.domainSize)-dimensional vectors, and this permutes their coefficients and flips their signs