This package implements permutations (Perms), groups (Groups) and combines them to make permutation groups (PermGroups).
It just depends on the package Combinat. The modules Perms and Groups could be independent packages of their own.
#
PermGroups.Perms — Module.
This package implements permutations and some functions of them. It depends only on the package Combinat.
This package follows the design of permutations in the GAP language. Perms are permutations of the set 1:n, represented internally as a vector of n integers holding the images of 1:n. The integer n is called the degree of the permutation. In this package, as in GAP (and contrary to the philosophy of Magma or the package Permutations.jl), two permutations of different degrees can be multiplied (the result has the larger degree). Two permutations are equal if and only if they move the same points in the same way, so two permutations of different degree can be equal; the degree is thus an implementation detail so usually it should not be used. One should rather use the function last_moved.
This design makes it easy to multiply permutations coming from different groups, like a group and one of its subgroups. It has a negligible overhead compared to the design where the degree is fixed.
The default constructor for a permutation uses the list of images of 1:n, like Perm([2,3,1,5,4,6]). Often it is more convenient to use cycle decompositions: the above permutation has cycle decomposition (1,2,3)(4,5) thus can be written Perm(1,2,3)*Perm(4,5) or perm"(1,2,3)(4,5)" (this last form can parse a permutation coming from GAP or the default printing at the REPL). The list of images of 1:n can be recovered from the permutation by the function perm; note that equal permutations with different degrees will have different perm. Note that the default constructor tests the validity of the input by calling the julia function isperm. To have a faster constructor which does not test the input, use the keyword argument check=false.
The complete type of a permutation is Perm{T} where T<:Integer, where Vector{T} is the type of the vector which holds the image of 1:n. This can be used to save space or time. For instance Perm{UInt8}(1,2,3) can be used for Weyl groups of rank≤8 since they permute at most 240 roots. If T is not specified we take it to be Int16 since this is a good compromise between speed, compactness and possible size of n. One can mix permutations of different integer types; they are promoted to the wider one when multiplying.
Examples of operations with permutations
julia> a=Perm(1,2,3)
(1,2,3)
julia> perm(a)
3-element Vector{Int16}:
2
3
1
julia> a==Perm(perm(a))
true
julia> b=Perm(1,2,3,4)
(1,2,3,4)
julia> a*b # product
(1,3,2,4)
julia> inv(a) # inverse
(1,3,2)
julia> a/b # quotient a*inv(b)
(3,4)
julia> a\b # left quotient inv(a)*b
(1,4)
julia> a^b # conjugation inv(b)*a*b
(2,3,4)
julia> b^2 # square
(1,3)(2,4)
julia> 1^a # image by a of point 1
2
julia> one(a) # trivial permutation
()
julia> sign(a) # signature of permutation
1
julia> order(a) # order (least trivial power) of permutation
3
julia> last_moved(a)
3
julia> first_moved(a)
1
julia> Perm{Int8}(a) # convert a to Perm{Int8}
Perm{Int8}: (1,2,3)
julia> Matrix(b) # permutation matrix of b
4×4 Matrix{Bool}:
0 1 0 0
0 0 1 0
0 0 0 1
1 0 0 0julia> randPerm(10) # random permutation of 1:10
(1,8,4,2,9,7,5,10,3,6)
Perms have methods copy, hash, ==, so they can be keys in hashes or elements of sets; two permutations are equal if they move the same points to the same images. They have methods cmp, isless (lexicographic order on moved points) so they can be sorted. Perms are scalars for broadcasting.
Other methods on permutations are cycles, cycletype, reflection_length, mappingPerm, restricted, support, sortPerm, Perm_rowcol, preimage, randPerm.
No method is given in this package to enumerate Perms; you can use the method permutations from Combinat, iterate Combinat.Permutations or iterate the elements of symmetric_group from PermGroups.
#
PermGroups.Perms.Perm — Type.
struct Perm{T<:Integer}
A Perm represents a permutation of the set 1:n and is implemented by a struct with one field, a Vector{T} holding the images of 1:n. When showing a Perm at the REPL, the cycle decomposition is displayed as well as the type if it is not Int16. The default constructor checks the input, unless the keyword argument check=false is given.
julia> Perms.Perm_(UInt8[1,3,2,4])
Perm{UInt8}: (2,3)#
PermGroups.Perms.Perm — Method.
Perm{T}(x::Integer...)where T<:Integer
returns a cycle. For example Perm{Int8}(1,2,3) constructs the cycle (1,2,3) as a Perm{Int8}. If omitted {T} is taken to be {Int16}.
#
PermGroups.Perms.Perm — Method.
Perm{T}(m::AbstractMatrix) If m is a permutation matrix, returns the corresponding permutation of type T. If omitted, T is taken to be Int16.
julia> Perm([0 1 0;0 0 1;1 0 0])
(1,2,3)#
PermGroups.Perms.Perm — Method.
Perm{T}(l::AbstractVector,l1::AbstractVector)
returns p, a Perm{T}, such that invpermute(l1,p)==l if such a p exists; returns nothing otherwise. If not given {T} is taken to be {Int16}. Needs the eltype of l and l1 to be sortable.
julia> Perm([0,2,4],[4,0,2])
(1,3,2)#
PermGroups.Perms.Perm — Method.
Perm{T}(m::AbstractMatrix,m1::AbstractMatrix;dims=1)
returns p, a Perm{T}, which invpermutes the rows of m1 (the columns of m1 if dims=2, simultaneously the rows and columns if dims=(1,2)) to bring them to those of m, if such a p exists; returns nothing otherwise. If not given {T} is taken to be {Int16}. Needs the elements of m and m1 to be sortable.
julia> Perm([0 1 0;0 0 1;1 0 0],[1 0 0;0 1 0;0 0 1];dims=1)
(1,3,2)
julia> Perm([0 1 0;0 0 1;1 0 0],[1 0 0;0 1 0;0 0 1];dims=2)
(1,2,3)
julia> n=(1:30)'.*(1:30).%15;
julia> m=onmats(n,Perm(1,5,2,8,12,4,7)*Perm(3,9,11,6));
julia> Perm(m,n,dims=(1,2))
(1,5,2,8,12,4,7)(3,9,11,6)#
PermGroups.Perms.@perm_str — Macro.
@perm"..."
makes a Perm{Int16} from a string; allows GAP-style perm"(1,2)(5,6,7)(4,9)". If the cycle decomposition is preceded by "Perm{T}:" the constructed permutation is of type T.
perm"Perm{UInt8}:(1,2)(3,4)"
Perm{UInt8}: (1,2)(3,4)#
PermGroups.Perms.last_moved — Method.
last_moved(a::Perm) is the largest integer moved by a
last_moved(G::PermGroup) the largest moved point by any g∈ G
#
PermGroups.Perms.first_moved — Function.
first_moved(a::Perm) is the smallest integer moved by a
first_moved(G::PermGroup) the smallest moved point by any g∈ G
#
PermGroups.Perms.perm — Function.
perm(p::Perm) returns the data field of a Perm.
julia> perm(Perm(2,3;degree=4))
4-element Vector{Int16}:
1
3
2
4#
PermGroups.Perms.preimage — Function.
preimage(i::Integer,p::Perm) or i/p
the preimage of i by p (same as image of i by inv(p) but does not need computing the inverse)."
#
PermGroups.Perms.invpermute — Function.
invpermute(l::AbstractVector,p::Perm)
returns l invpermuted by p, a vector r of same length as l such that r[i^p]==l[i] for i in eachindex(l). This function corresponds to the GAP function Permuted, but we changed the name to fit the Julia conventions since invpermute(l,p)==invpermute!(copy(l),perm(p)).
julia> invpermute([5,4,6],Perm(1,2,3))
3-element Vector{Int64}:
6
5
4invpermute(m::AbstractMatrix, p1::Perm,p2::Perm)
invpermutes the rows of m by p1 and the columns of m by p2.
julia> m=reshape(1:9,3,3)
3×3 reshape(::UnitRange{Int64}, 3, 3) with eltype Int64:
1 4 7
2 5 8
3 6 9
julia> invpermute(m,Perm(1,2),Perm(2,3))
3×3 Matrix{Int64}:
2 8 5
1 7 4
3 9 6invpermute(m::AbstractMatrix,p::Perm;dims=1)
invpermutes by p the rows, columns or both of the matrix m depending on the value of dims.
julia> m=reshape(1:9,3,3)
3×3 reshape(::UnitRange{Int64}, 3, 3) with eltype Int64:
1 4 7
2 5 8
3 6 9
julia> p=Perm(1,2,3)
(1,2,3)
julia> invpermute(m,p)
3×3 Matrix{Int64}:
3 6 9
1 4 7
2 5 8
julia> invpermute(m,p;dims=2)
3×3 Matrix{Int64}:
7 1 4
8 2 5
9 3 6
julia> invpermute(m,p;dims=(1,2))
3×3 Matrix{Int64}:
9 3 6
7 1 4
8 2 5#
PermGroups.Perms.sortPerm — Function.
for convenience: sortPerm(a)=Perm(sortperm(a))
#
PermGroups.Perms.randPerm — Function.
randPerm([T,]n::Integer) a random permutation of 1:n of type T. If omitted T is taken to be Int16
#
PermGroups.Perms.orbit — Method.
orbit(p::Perm,i::Integer) returns the orbit of p on i.
#
PermGroups.Perms.orbits — Method.
orbits(G::PermGroup) the orbits of G on its moved points.
#
PermGroups.Perms.order — Function.
order(G::Group) the number of elements of G.
order(T<:Integer,G::Group) do the computation with the integer type T (useful when a BigInt is needed to hold the result).
order(a) the smallest integer i≥1 such that isone(a^i)
#
PermGroups.Perms.cycles — Method.
cycles(a::Perm) returns the cycles of a
Example
julia> cycles(Perm(1,2)*Perm(4,5))
2-element Vector{Vector{Int16}}:
[1, 2]
[4, 5]#
PermGroups.Perms.cycletype — Method.
cycletype(a::Perm,domain::AbstractVector{<:Integer};trivial=true)
domain should be a union of orbits of a. Returns the partition of length(domain) associated to the conjugacy class of a in the symmetric group of domain, with ones removed if trivial=false (in which case the partition does not depend on domain but just on support(a))
cycletype(a::Perm)
returns cycletype(a,1:last_moved(a);trivial=false)
Example
julia> cycletype(Perm(1,2)*Perm(4,5))
2-element Vector{Int64}:
2
2
julia> cycletype(Perm(1,2)*Perm(4,5),1:5)
3-element Vector{Int64}:
2
2
1
julia> cycletype(Perm(1,2)*Perm(4,5),1:6)
4-element Vector{Int64}:
2
2
1
1#
PermGroups.Perms.support — Function.
support(a::Perm) is the sorted list of all points moved by a
#
Base.sign — Function.
sign(p::Perm) is the signature of the permutation p
#
Base.Matrix — Method.
Matrix(p::Perm,n=last_moved(p)) the permutation matrix for p operating on n points.
julia> Matrix(Perm(2,3,4),5)
5×5 Matrix{Bool}:
1 0 0 0 0
0 0 1 0 0
0 0 0 1 0
0 1 0 0 0
0 0 0 0 1#
PermGroups.Perms.restricted — Method.
restricted(p::Perm,domain::AbstractVector{<:Integer})
domain should be a union of orbits of p; returns p restricted to domain
julia> restricted(Perm(1,2)*Perm(3,4),3:4)
(3,4)#
PermGroups.Perms.reflection_length — Method.
reflection_length(p::Perm) or reflength
gives the "reflection length" of p (when the symmetric group on n points to which p belongs is interpreted as a reflection group on a space of dimension n), that is, the minimum number of transpositions of which p is the product.
#
PermGroups.Perms.mappingPerm — Function.
mappingPerm([::Type{T},]a::AbstractVector{<:Integer})
given a list of positive integers without repetition a, this function finds a Perm{T} p such that sort(a).^p==a. This can be used to translate between arrangements and Perms. If omitted T is taken to be Int16.
julia> p=mappingPerm([6,7,5])
(5,6,7)
julia> (5:7).^p
3-element Vector{Int64}:
6
7
5mappingPerm([::Type{T},]a,b)
given two lists of positive integers without repetition a and b, this function finds a Perm{T} p such that a.^p==b. If omitted T is taken to be Int16.
julia> mappingPerm([1,2,5,3],[2,3,4,6])
(1,2,3,6,5,4)#
PermGroups.Perms.Perm_rowcol — Function.
Perm_rowcol(m1::AbstractMatrix, m2::AbstractMatrix)
whether m1 can be obtained from m2 by row/col permutations.
m1 and m2 should be rectangular matrices of the same size. The function returns a Tuple of permutations (p1,p2) such that invpermute(m2,p1,p2)==m1 if such permutations exist, nothing otherwise. The eltype of m1 and m2 must be sortable.
julia> a=[1 1 1 -1 -1; 2 0 -2 0 0; 1 -1 1 -1 1; 1 1 1 1 1; 1 -1 1 1 -1]
5×5 Matrix{Int64}:
1 1 1 -1 -1
2 0 -2 0 0
1 -1 1 -1 1
1 1 1 1 1
1 -1 1 1 -1
julia> b=[1 -1 -1 1 1; 1 1 -1 -1 1; 1 -1 1 -1 1; 2 0 0 0 -2; 1 1 1 1 1]
5×5 Matrix{Int64}:
1 -1 -1 1 1
1 1 -1 -1 1
1 -1 1 -1 1
2 0 0 0 -2
1 1 1 1 1
julia> p1,p2=Perm_rowcol(a,b)
((1,3,5,4,2), (3,4,5))
julia> invpermute(b,p1,p2)==a
true#
PermGroups.Groups — Module.
This module gives some basic functionality on groups.
Group is an abstract type, but the following is assumed of a group G of one of its concrete implementations:
- The function
gens(G)returns the list of generators ofG. - The function
one(G)returns the identity element ofG.
Examples
julia> G=Group(Perm(1,2),Perm(1,2,3))
Group((1,2),(1,2,3))
julia> gens(G)
2-element Vector{Perm{Int16}}:
(1,2)
(1,2,3)
julia> ngens(G)
2
julia> minimal_words(G)
OrderedDict{Perm{Int16}, Vector{Int64}} with 6 entries:
() => []
(1,2) => [1]
(1,2,3) => [2]
(1,3) => [1, 2]
(2,3) => [2, 1]
(1,3,2) => [2, 2]There is a constructor of a group with arbitrary type elements, Group(l) where l isa AbstractVector{T} constructs a Groupof{T} which knows only the general methods in this module. The examples above use Group(AbstractVector{<:Perm}) which constructs a PermGroup which has more efficient methods.
for further information on the functions defined in this module, look at the docstrings of Group, gens, ngens, comm, orbit, orbits, transversal, words_transversal, centralizer, stabilizer, center, normalizer, words, minimal_words, word, in, elements, length, order, conjugacy_class, conjugacy_classes, classreps, nconjugacy_classes, fusion_conjugacy_classes, position_class, isabelian, iscyclic, istrivial, rand, transporting_elt, intersect, Hom, kernel, Coset
#
PermGroups.Groups.Group — Type.
(G::Group)(i...)
A Group used as a function takes integer arguments in eachindex(gens(W)). This constructs the element of G product of the generators with the specified indices. An argument can also be negative, then the inverse of the corresponding generator is used.
julia> G=Group(Perm(1,2),Perm(1,2,3))
Group((1,2),(1,2,3))
julia> G(2,1,-2) # returns gens(G)[2]*gens(G)[1]/gens(G)[2]
(1,3)Group(l::AbstractVector{T}[,one]) where T
A group may be constructed from a list of l elements of the same type. These elements must respond to the functions * and inv. If it is not possible to compute one from l (because l[1] does not respond to one, or l is empty and T does not respond to one), then the identity element of the group must be given as a second argument.
julia> G=Group([[-1 -1;1 0]])
Group([[-1 -1; 1 0]])
julia> elements(G)
3-element Vector{Matrix{Int64}}:
[1 0; 0 1]
[-1 -1; 1 0]
[0 1; -1 -1]#
PermGroups.Groups.generators — Function.
gens(G::Group) or generators(G::Group) is the Vector of generators of G.
#
PermGroups.Groups.number_of_generators — Function.
ngens(G::Group) or number_of_generators(G::Group) is the number of generators of G.
#
Base.one — Method.
one(G::Group) returns the identity element of G.
#
PermGroups.Groups.orders_of_generators — Function.
orders_of_generators(G::Group) or ordergens
The list of orders of the generators (this may be expensive to compute so could be worth being cached in G).
#
PermGroups.Groups.ontuples — Function.
ontuples(t,g)
Assume that t is a Vector or a NTuple. ontuples is the action of g given by (t,g)->map(x->x^g,t).
#
PermGroups.Groups.onsets — Function.
onsets(s,g)
Assume that s is a set, represented as a sorted list without repetitions. onsets is the action of g given by (s,g)->sort!(map(x->x^g,s)).
#
PermGroups.Perms.orbit — Method.
orbit(gens::AbstractVector,p,action::Function=^)
orbit(G::Group,p,action::Function=^)
the orbit of point p under repeated action of generators gens. The type of point p should be hashable. The default action of a group element is ^. For example if g is a permutation and p an integer, p^g is the image of p by g; if h and g are group elements, then h^g is the conjugate inv(g)*h*g. If a group is given instead of generators, the orbit under gens(G) is returned.
julia> orbit([Perm(1,2),Perm(2,3)],1)
3-element Vector{Int64}:
1
2
3
julia> orbit([Perm(1,2),Perm(2,3)],[1,3],ontuples)
6-element Vector{Vector{Int64}}:
[1, 3]
[2, 3]
[1, 2]
[3, 2]
[2, 1]
[3, 1]
julia> orbit([Perm(1,2),Perm(2,3)],[1,3],(v,g)->sort(v.^g)) # "OnSets"
3-element Vector{Vector{Int64}}:
[1, 3]
[2, 3]
[1, 2]#
PermGroups.Perms.orbits — Method.
orbits(gens::Vector,v,action=^;trivial=true)
orbits(G,v,action=^;trivial=true)
the orbits on v of the repeated action of gens; the elements of v should be hashable. If a group is given instead of generators, the orbit under gens(G) is returned. If trivial=false the one-element orbits are not returned.
julia> G=Group(Perm(1,2),Perm(2,3));
julia> orbits(G,1:4)
2-element Vector{Vector{Int64}}:
[1, 2, 3]
[4]#
PermGroups.Groups.elements — Method.
elements(G::Group) the list of elements of G
#
PermGroups.Groups.transversal — Function.
transversal(G::Group,p,action::Function=^)
returns an OrderedDict t with keys orbit(G,p,action) and where t[x] is an element of G such that x==action(p,t[x]). Like orbit, it thus requires the type of p to be hashable.
julia> G=Group(Perm(1,2),Perm(2,3));
julia> transversal(G,1)
OrderedDict{Int64, Perm{Int16}} with 3 entries:
1 => ()
2 => (1,2)
3 => (1,3,2)orbit functions can take any action of G as keyword argument
julia> transversal(G,(1,2),ontuples)
OrderedDict{Tuple{Int64, Int64}, Perm{Int16}} with 6 entries:
(1, 2) => ()
(2, 1) => (1,2)
(1, 3) => (2,3)
(3, 1) => (1,3,2)
(2, 3) => (1,2,3)
(3, 2) => (1,3)#
PermGroups.Groups.words_transversal — Function.
words_transversal(gens,p,action::Function=^)
A transversal recording words. returns a Dict t with keys orbit(gens,p,action) and where t[x] is a sequence of integers such that x==action(p,prod(gens[t[x]])), that is for each element x of the orbit of p describes as a word in gens an element bringing p to x.
julia> words_transversal([Perm(1,2),Perm(2,3)],1)
OrderedDict{Int64, Vector{Int64}} with 3 entries:
1 => []
2 => [1]
3 => [1, 2]#
PermGroups.Groups.centralizer — Function.
centralizer(G::Group,p,action=^)
computes the subgroup of elements g of G such that action(p,g)==p.
julia> G=Group(Perm(1,2),Perm(1,2,3));
julia> centralizer(G,1)
Group((2,3))centralizer(G::Group,H::Group) the centralizer in G of the group H
julia> G=Group(Perm(1,2),Perm(1,2,3))
Group((1,2),(1,2,3))
julia> centralizer(G,Group(Perm(1,2)))
Group((1,2))#
PermGroups.Groups.center — Function.
center(G::Group) the center of G
julia> G=Group(Perm(1,2),Perm(3,4),Perm(1,3)*Perm(2,4))
Group((1,2),(3,4),(1,3)(2,4))
julia> center(G)
Group((1,2)(3,4))#
PermGroups.Groups.stabilizer — Function.
stabilizer(G::Group,s,action=^)
computes the subgroup of elements g of G such that action(p,g)==p.
julia> G=Group(Perm(1,2),Perm(1,2,3,4))
Group((1,2),(1,2,3,4))Assume that s is a set, represented as a sorted list without repetitions. onsets is the action of g∈ G given by (g,p)->sort(p.^g).
julia> stabilizer(G,[1,2],onsets)
Group((3,4),(1,2))#
PermGroups.Groups.normalizer — Function.
normalizer(G::Group,H::Group) the normalizer of H in G
#
PermGroups.Groups.word — Method.
word(G::Group,w) a minimal word in gens(G) representing element w of G
#
PermGroups.Groups.comm — Function.
comm(a,b) or commutator(a,b) is a^-1*b^-1*a*b
#
Base.length — Method.
length(G::Group) the number of elements of G.
length(T,G) do the computation with the integer type T.
#
PermGroups.Groups.classreps — Method.
class_representatives(G::Group) or classreps
representatives of conjugacy classes of G. By default queries the attribute G.classreps, and if this attribute is present it will be used by conjugacy_classes.
#
PermGroups.Groups.conjugacy_classes — Function.
conjugacy_classes(G::Group) conjugacy classes of G (as a Vector{ConjugacyClass})
#
PermGroups.Groups.conjugacy_class — Function.
conjugacy_class(G::Group,g) the class of g
#
PermGroups.Groups.number_of_conjugacy_classes — Function.
number_of_conjugacy_classes(G::Group) or nconjugacy_classes
the number of conjugacy classes of G"
#
PermGroups.Groups.position_class — Function.
position_class(G::Group,g) index of conjugacy class to which g belongs
#
PermGroups.Groups.fusion_conjugacy_classes — Function.
fusion_conjugacy_classes(H::Group,G::Group)
A Vector{Int} telling for each conjugacy class of subgroup H of which class of G is is a subset
#
PermGroups.Groups.minimal_words — Function.
minimal_words(G::Group)
returns a Dict giving for each element of G a minimal positive word in the generators representing it.
julia> G=Group(Perm(1,2),Perm(1,2,3));
julia> minimal_words(G)
OrderedDict{Perm{Int16}, Vector{Int64}} with 6 entries:
() => []
(1,2) => [1]
(1,2,3) => [2]
(1,3) => [1, 2]
(2,3) => [2, 1]
(1,3,2) => [2, 2]minimal_words(G::Group,w)
Gives all expressions of w as words in the generators of G of minimal length (uses minimal_words(G)).
julia> G=Group(Perm(1,2),Perm(2,3));
julia> minimal_words(G,Perm(1,3))
2-element Vector{Vector{Int64}}:
[1, 2, 1]
[2, 1, 2]#
PermGroups.Groups.words — Method.
words(G::Group)
returns a Dict giving for each element of G a positive word in the generators representing it. It is faster than minimal_words but the words are not guaranteed minimal.
julia> G=Group(Perm(1,2),Perm(1,2,3));
julia> words(G)
OrderedDict{Perm{Int16}, Vector{Int64}} with 6 entries:
() => []
(1,2) => [1]
(1,2,3) => [2]
(1,3) => [1, 2]
(2,3) => [2, 1]
(1,3,2) => [1, 2, 1]#
PermGroups.Groups.transporting_element — Function.
transporting_elt(G,p,q,action=^) or transporting_element(G,p,q,action=^)
returns an element g∈ G such that p^g==q (or action(p,g)==q if action is given), if such a g exists, and nothing otherwise. The set of possible g forms a right coset of the centralizer of p in G.
julia> g=Group(perm"(1,2,3)(6,7)",perm"(3,4,5)(7,8)")
Group((1,2,3)(6,7),(3,4,5)(7,8))
julia> transporting_elt(g,1,5)
(1,5,4,3,2)
julia> transporting_elt(g,1,6)
julia> transporting_elt(g,[1,2,3,4],[2,3,4,5],(s,g)->sort(s.^g))
(1,2,3,4,5)(6,7,8)
julia> transporting_elt(g,[1,2,3,4],[3,4,5,2],(s,g)->s.^g)#
Base.intersect — Method.
intersect(G::Group, H::Group) the intersection as a group
#
Base.rand — Method.
rand(W::Group) a random element of W
#
PermGroups.Groups.isabelian — Function.
isabelian(G::Group) whether G is abelian
#
PermGroups.Groups.iscyclic — Function.
iscyclic(G::Group) whether G is cyclic
#
PermGroups.Groups.istrivial — Function.
istrivial(G::Group) whether G is trivial
#
PermGroups.Groups.Hom — Type.
Hom(S::Group,T::Group,images)
builds an object representing the homomorphism from S to T which maps gens(S) to images.
julia> S=Group(Perm(1,2),Perm(2,3))
Group((1,2),(2,3))
julia> T=Group(Perm(1,2))
Group((1,2))
julia> h=Hom(S,T,[T(1),T(1)])
Hom(Group((1,2),(2,3))→ Group((1,2));[(1,2), (2,3)]↦ [(1,2), (1,2)]
julia> h(S(1,2)) # the image by h
()#
PermGroups.Groups.kernel — Function.
kernel(h::Hom) the kernel of the homomorphism h
#
PermGroups.Groups.Coset — Type.
Coset(G::Group,phi=one(G)) constructs the (left) coset G.phi where G isa Group{<:T} and phi isa T, as an object of type Cosetof{T}. This general coset knows only the general methods for a coset C=G.phi defined in this module, which are
Group(C)returnsG.isone(C)returnstrueiffphi in Gone(C)returns the trivial cosetG.1length(C)returnslength(G)elements(C)returnselements(G).*Ref(phi)x in Creturnsx/phi in G
#
PermGroups.Groups.NormalCoset — Type.
NormalCoset(G::Group,phi=one(G)) constructs the coset C=G.phi where G isa Group{<:T} and phi isa T, as an object of type NormalCosetof{T}. It is assumed that phi normalizes G. This general coset knows only the general methods defined for normal cosets in the module Groups, which in addition to those defined for cosets (see Coset) are
inv(C)returnG.inv(phi)(assumed equal toinv(phi).G)C*Dgiven another cosetG.psireturnsG.phi*psiC/Dgiven another cosetG.psireturnsG.phi*inv(psi)C^Dgiven another cosetG.psireturnsG.inv(psi)*phi*psiC^nreturnsG.phi^norder(C)the smallestnsuch thatisone(C^n)
The conjugacy classes of a normal coset G.phi are relative to the conjugation action of G on G.phi. We have the functions conjugacy_classes, nconjugacy_classes, classreps, position_class.
Finally the function G/H for two groups constructs the quotient as a group of NormalCosets, and fusion_conjugacy_classes(H::NormalCoset,G::NormalCoset) expresses the fusion of conjugacy classes.
#
PermGroups — Module.
This module is a port of some GAP functionality on permutation groups. A PermGroup is a Group where gens are Perms. It depends on the modules Groups and Perms which could be independent packages on their own.
julia> G=Group([Perm(i,i+1) for i in 1:2])
Group((1,2),(2,3))
julia> collect(G) # PermGroups are iterators over their elements
6-element Vector{Perm{Int16}}:
()
(1,2)
(1,3,2)
(2,3)
(1,2,3)
(1,3)
julia> last_moved(G) # maximum moved point of any element of `G`
3
julia> orbits(G) # the orbits are orbits on points it moves
1-element Vector{Vector{Int16}}:
[1, 2, 3]
julia> Perm(1,2) in G
true
julia> Perm(1,2,4) in G
falseelements, in and other functions are computed on G using Schreier-Sims theory, that is computing the following
julia> get_stabchain(G)
b:1 c:Group((1,2),(2,3))
δ:1=>(),2=>(1,2),3=>(1,3,2)
b:2 c:Group((2,3))
δ:2=>(),3=>(2,3)See the docstring of stabchain for explanations.
There are efficient methods for PermGroups for the functions in, length, elements, position_class. The function on_classes determines the permutation of the conjugacy classes effected by an automorphism. Finally, we give application to the group of simultaneous row and column permutations of a matrix: see stab_onmats, Perm.
finally, benchmarks on julia 1.9
julia> @btime collect(symmetric_group(8));
1.921 ms (50128 allocations: 3.29 MiB)
julia> @btime words(symmetric_group(8));
6.441 ms (80971 allocations: 10.88 MiB)
julia> @btime elements(symmetric_group(8)); # Gap takes 8 ms
1.565 ms (49539 allocations: 3.71 MiB)
julia> rubik_gens=[
perm"(1,3,8,6)(2,5,7,4)(9,33,25,17)(10,34,26,18)(11,35,27,19)",
perm"(9,11,16,14)(10,13,15,12)(1,17,41,40)(4,20,44,37)(6,22,46,35)",
perm"(17,19,24,22)(18,21,23,20)(6,25,43,16)(7,28,42,13)(8,30,41,11)",
perm"(25,27,32,30)(26,29,31,28)(3,38,43,19)(5,36,45,21)(8,33,48,24)",
perm"(33,35,40,38)(34,37,39,36)(3,9,46,32)(2,12,47,29)(1,14,48,27)",
perm"(41,43,48,46)(42,45,47,44)(14,22,30,38)(15,23,31,39)(16,24,32,40)"];
julia> @btime length(Int128,Group(rubik_gens)) # Gap takes 5ms
4.906 ms (104874 allocations: 13.64 MiB)
43252003274489856000
Note the use of Int128 in length: the computation does not fit in an Int64.
#
PermGroups.Perms.last_moved — Method.
last_moved(a::Perm) is the largest integer moved by a
last_moved(G::PermGroup) the largest moved point by any g∈ G
#
Base.in — Method.
x in G for G a group: whether x is an element of G
#
PermGroups.on_classes — Function.
on_classes(G, aut)
aut is an automorphism of the group G (for a permutation group, this could be given as a permutation normalizing G). The result is the permutation of 1:nconjugacy_classes(G) induced by aut.
julia> W=Group(Perm(1,2),Perm(2,3),Perm(4,5),Perm(5,6))
Group((1,2),(2,3),(4,5),(5,6))
julia> on_classes(W,Perm(1,4,2,5,3,6))
(2,4)(3,7)(6,8)#
PermGroups.symmetric_group — Function.
symmetric_group(n::Int) The symmetric group of degree n
#
PermGroups.Perms.onmats — Function.
onmats(m::AbstractMatrix,g::Perm) synonym for invpermute(m,g;dims=(1,2)) or invpermute(m,g,g).
#
PermGroups.stab_onmats — Function.
stab_onmats([G,]M;extra=nothing)
If onmats(m,p)=^(M,p;dims=(1,2)), and the argument G is given (which should be a PermGroup) this is just a fast implementation of centralizer(G,M,onmats). If G is omitted it is taken to be symmetric_group(size(M,1)). The program uses sophisticated algorithms, and can handle matrices up to 80×80. If a list extra is given the result centralizes also extra.
julia> stab_onmats((1:30)'.*(1:30).%15)
Group((1,16),(4,19),(11,26),(14,29),(2,17),(7,22),(8,23),(13,28),(6,21),(9,24),(1,4)(2,8)(3,12)(6,9)(7,13)(11,14)(16,19)(17,23)(18,27)(21,24)(22,28)(26,29),(3,18),(12,27),(1,11)(2,7)(4,14)(5,10)(8,13)(16,26)(17,22)(19,29)(20,25)(23,28),(5,20),(10,25),(15,30))#
PermGroups.Perm_onmats — Function.
Perm_onmats(M, N[, m ,n])
returns p such that onmats(N,p)=M if it exists, nothing otherwise; so is just an efficient version of transporting_elt(symmetric_group(size(M,1)),N,M,onmats) If in addition the vectors m and n are given, p should satisfy invpermute(n,p)=m.
#
PermGroups.ProdIterator — Type.
A ProdIterator([i₁,…,iₙ]) takes a list i₁,…,iₙ of iterators and iterates on all the products i₁[j₁]*…*iₙ[jₙ] (where the inner loop jₙ runs the fastest). It tries to be fast by re-using partial products i₁[j₁]*…*iₖ[jₖ] for k<n.
It is used internally for iterating over a permutation group.