Given a group H and an element x belonging to a group K such that H and K are subgroups of the same general linear group, this function returns the set of conjugates of x under the action of H. If H = K, the function returns the conjugacy class of x in H.
Given a group G, construct the conjugacy classes and the class map f for G. For any element x of G, f(x) will be the conjugacy class representative chosen by the Classes function.
WeakLimit: RngIntElt Default: 500
StrongLimit: RngIntElt Default: 5000
Al: MonStgElt Default:
Construct a set of representatives for the conjugacy classes of the matrix group G. The classes are returned as a sequence of triples containing the element order, the class length and a representative element for the class. The parameter Al enables the user to select the algorithm that is to be used.Al := "Action": Create the classes of G by computing the orbits of the set of elements of G under the action of conjugation. This option is only feasible for small groups.
Al := "Random": Construct the conjugacy classes of elements for a matrix group G using an algorithm that searches for representatives of all conjugacy of G by examining a random selection of group elements and their powers. The behaviour of this algorithm is controlled by two associated optional parameters WeakLimit and StrongLimit, whose values are positive integers n1 and n2, say. Before describing the effect of these parameters, some definitions are needed: A mapping f: G -> I is called a class invariant if f(g) = f(gh) for all g, h∈G. In matrix groups, the primary invariant factors are used where possible, or the characteristic or minimal polynomials otherwise. Two matrices g and h are said to be weakly conjugate with respect to the class invariant f if f(g) = f(h). By definition, conjugacy implies weak conjugacy, but the converse is false. The random algorithm first examines n1 random elements and their powers, using a test for weak conjugacy. It then proceeds to examine a further n2 random elements and their powers, using a test for ordinary conjugacy. The idea behind this strategy is that the algorithm should attempt to find as many classes as possible using the very cheap test for weak conjugacy, before employing the more expensive ordinary conjugacy test to recognize the remaining classes.
Al := "Extend": Construct the conjugacy classes of G by first computing classes in a quotient G/N and then extending these classes to successively larger quotients G/H until the classes for G/1 are known. More precisely, a series of subgroups 1 = G0 < G1 < ... < Gr = R < G is computed such that R is the (solvable) radical of G and Gi + 1/Gi is elementary abelian. The radical quotient G/R is computed and its classes and centralizers of their representatives found using the permutation group algorithm, and pulled back to G. The parameters TFAl and ASAl control the algorithm used to compute the classes of G/R. See the GrpPerm chapter for more information on these parameters.
To extend from G/Gi + 1 to the next larger quotient G/Gi, an affine action of each centralizer on a quotient of the elementary abelian layer Gi + 1/Gi is computed. Each distinct orbit in that action gives rise to a new class of the larger quotient (see Mecky and Neubuser [MN89]).
Al := "Lifting": Construct a permutation representation for G, compute the classes of the representation, and lift them back to G through the kernel of the representation. Successful when the kernel is small. Currently uses the permutation action of G on its first basic orbit as the permutation representation.
Al := "Classic": Construct the conjugacy classes by the enumeration of class invariants or by the algorithms described in [Fra20]. This option is available only for the following classical groups.
Default: The Classic algorithm will be used if G is recognised to be one of the groups in the above list and |G| > 100.
- (i)
- groups containing the special linear group;
- (ii)
- the symplectic groups;
- (iii)
- in odd characteristic, the subgroups of the conformal symplectic group that contain the symplectic group;
- (iv)
- the conformal unitary group;
- (v)
- subgroups of the general unitary group that contain the special unitary group;
- (vi)
- the general and special orthogonal groups and the derived groups of the special orthogonal groups;
- (vii)
- the conformal orthogonal groups in odd characteristic.
The action algorithm will be used if |G| ≤2000. If G is soluble, classes are computed in a PC-representation of G.
When |G| > 2000, G is not classical and the base ring of G is a finite field, the Extension algorithm is used.
Otherwise the Lifting algorithm is used, unless the kernel size exceeds 10000. If there is a big kernel and the base ring of the group can be embedded in a field then the extension algorithm is used. If this does not succeed the random algorithm will be applied with the limits given by the parameters WeakLimit and StrongLimit. If that fails to compute all the classes and |G|≤100000, then the action algorithm will be used.
Given a group G for which the conjugacy classes are known, return the designated representative for the conjugacy class of G containing x or the stored representative for conjugacy class i.
The centraliser of the representative element stored for conjugacy class number i in group G. The group computed is stored with the class table for reference by future calls to this function.
Given a group G, for which the classic algorithm for computing conjugacy classes is available, and the class invariants p, h and t, return the standard class representative for the conjugacy class in G with the given invariants. Currently this is available only for the general linear group and the conformal unitary group.
Given a group G and elements g and h belonging to G, return the value true if g and h are conjugate in G. The function returns a second value in the event that the elements are conjugate: an element k which conjugates g into h.
The number of conjugacy classes of elements for the group G.
Given a group G, construct the power map for G. Suppose that the order of G is m and that G has r conjugacy classes. When the classes are determined by Magma, they are numbered from 1 to r. Let C be the set of class indices { 1, ..., r } and let P be the set of integers { 1, ..., m }. The power map f for G is the mapping, f : C x P -> C where the value of f(i, j) for i ∈C and j ∈P is the number of the class which contains xij, where xi is a representative of the i-th conjugacy class.
The preferred method for setting this attribute is G`Classes := Q; and this should be used instead of AssertAttribute.Given a group G, and a sequence Q of k distinct elements of G, one from each conjugacy class, use Q to define the classes attribute of G. The sequence Q may be one of 3 options. The first is a sequence of elements of G. The second is a sequence of pairs <GrpMatElt, RngIntElt> giving class representatives and their class length. In these cases the ordering of the classes may not be preserved.
The third possibility is giving the classes by element order, class length, and class representative as a sequence of triples <RngIntElt, RngIntElt, GrpMatElt>. In this last case the triples must be ordered by element order, then by class length, and then the classes are installed into G in the order given.
> DB := RationalMatrixGroupDatabase();
> G := Group(DB, 12, 3);
> FactoredOrder(G);
[ <2, 17>, <3, 8>, <5, 2> ]
> CompositionFactors(G);
G
| Cyclic(2)
*
| Cyclic(2)
*
| C(2, 3) = S(4, 3)
*
| Cyclic(2)
*
| Cyclic(2)
*
| C(2, 3) = S(4, 3)
*
| Cyclic(2)
1
The conjugacy classes of G are computed as follows:
> time cl := Classes(G); Time: 18.580 > #cl; 1325The group has 1325 conjugacy classes of elements.
According to Kleidman and Liebeck [KL90] a group G is a finite classical group if Ω⊆G⊆A or /line(Ω)⊆G⊆/line(A), where Ω and A are given by the following table and where the symbols /line(Ω) and /line(A) denote the groups Ω and A modulo scalars.
type Omega Delta A ---------------------------------------------- linear SL(n,q) GL(n,q) GammaL*(n,q) symplectic Sp(n,q) CSp(n,q) GammaSp(n,q) unitary SU(n,q) CU(n,q) GamaU(n,q) orthogonal Omega^e(n,q) CO^e(n,q) GammaO^e(n,q) ------------------------------------------------If V is a vector space of dimension n over the field GF(q), then GammaL * (n, q) is the set of all semilinear bijections from V to V together with all semilinear bijections from V to V * . There is a well-defined multiplication (see [Tay92]) which makes this set a group; the group GammaL(n, q) of all semilinear transformations of V is a subgroup of index 2. The other groups in column A are the subgroups of GammaL(n, qd) which preserve an alternating, hermitian or quadratic form up to a scalar multiple, where d is 2 in the case of unitary groups and 1 otherwise.
The groups in the last three rows of column Δ are the so-called conformal groups; they are the groups A∩GL(n, q) which preserve an alternating, hermitian or quadratic form up to a scalar multiple.
Important examples of classical groups, which in general are in neither column Ω nor column Δ, are the general orthogonal groups GOε(n, q), which preserve a quadratic form. In magma these are the groups GO(n,q), GOPlus(n,q) or GOMinus(n,q) where ε is respectively 0, + or -.
As described in the documentation for the ConjugacyClasses intrinsic, magma constructs the classes by computing a complete collection of invariants and then determining a representative matrix for each invariant or by using the algorithms described in [Fra20].
The intention is to implement this for all groups G such that Ω⊆G⊆Δ. Currently this implementation is invoked automatically when constructing the conjugacy classes for G such that SL(n, q)⊆G⊆GL(n, q), the symplectic groups G = Sp(2n, q), the unitary groups SU(n, q)⊆G⊆GU(n, q), the conformal unitary groups CU(n, q) and the orthogonal groups Ωε(n, q), SOε(n, q) and GOε(n, q) where ε is 0, + or -. In addition, when q is odd, it is invoked for the conformal groups symplectic groups CSp(2n, q) and the conformal orthogonal groups COε(n, q)
The implementation is based on Milnor [Mil69] combined with the fundamental work of Wall [Wal63] as interpreted in Gonshaw, Liebeck and O'Brien [GLO17] and the theses of Fulman [Ful97], Britnell [Bri03] and De Franceschi [Fra18], [Fra20].
Class invariants. The conjugacy classes in the group GL(n, q) are parametrised by sequences of pairs < f, μ(f) > where f is an irreducible polynomial and μ(f) is a partition such that
∑fdeg(f)|μ(f)| = n.
In the following description a partition of an integer n will be represented either by a sequence [λ1, λ2, ..., λr] such that λ1≥λ2≥ ... ≥λr and n= ∑i=1rλi or by the sequence of multiplicities [< 1, m1 >, < 2, m2 >, ..., < n, mn >], omitting the terms with mi = 0, where n = ∑i=1n imi.
For the conjugacy classes of the classical groups there are restrictions on the polynomials and partitions that can occur.
If f(t)∈k[t] is a polynomial of degree d (over a field k) such that f(0)≠0, the dual of f(t) is the polynomial f * (t) = f(0) - 1tdf(t - 1).
A polynomial f(t) is *-symmetric if f * (t) = f(t); it is *-irreducible if it has no proper *-symmetric factors.
The dual of the polynomial f.
The sequence of all *-irreducible polynomials of degree d with coefficients in F.Symplectic groups. If g∈Sp(2n, q), then g preserves a non-degenerate alternating form and from this it follows that the minimal polynomial of g is *-symmetric. A symplectic signed partition of an integer n is a sequence [< 1, m1 >, < pm2, m2 >, ..., < n, mn >], such that the unsigned sequence [< 1, m1 >, < 2, m2 >, ..., < n, mn >] is a partition of n, where mi is even for all odd i. Only the terms < i, mi > where i is even are signed.
The conjugacy classes of Sp(2n, q) are in one-to-one correspondence with sequences of pairs < f, μ(f) >, where f is a *-irreducible polynomial and μ(f) is a partition if deg (f) > 1 and a symplectic signed partition if deg(f) = 1. (Note that t - 1 and t + 1 are the only *-irreducible polynomials of odd degree.) When q is a power of 2, more elaborate labels are needed to distinguish the conjugacy classes.
After invoking the command cc := Classes(G); the conjugacy classes for of the group G will be returned as the value of cc and assigned to G`Classes. In addition, the labels for the conjugacy classes will be assigned either to G`Labels_S or G`Labels_A (or both). These labels are used internally.
Conformal symplectic groups. If g belongs to the conformal symplectic group C over the field F there is a non-zero element φ∈F such that gJg^(sevenrm tr) = φ J, where J is the matrix of the alternating form preserved by C. In this case the minimal polynomial of g is φ-symmetric in the sense of the following definition.
Given φ∈F x and a polynomial f(t) of degree d such that f(0)≠0, the φ-dual of f(t) is
f[φ](t) = f(0) - 1td f(φ t - 1).
The polynomial f(t) is φ-symmetric if f[φ](t) = f(t). Thus f(t) is φ-symmetric if and only if td f(φ t - 1) = f(0)f(t). For example t2 - φ and t2 + φ are φ-symmetric and if φ = λ2, then t - λ and t + λ are φ-symmetric.
A polynomial f(t) is φ-irreducible if it is φ-symmetric and has no proper φ-symmetric factors.
The φ-dual of the polynomial f.
The sequence of pairs < φ, pols > where pols is the sequence of all monic polynomials of degree d over the field F with no proper φ-symmetric factor and φ runs through the non-zero elements of F.Each conjugacy class of CSp(2n, q) will be represented by a pair < φ, Ξ >, where φ∈F x and Ξ is an indexed set of pairs < f, μ >, where f is a φ-irreducible polynomial and μ is either a partition or, in the case that f divides t2 - φ, a symplectic signed partition. That is, a conjugacy class invariant has the form < φ, {@ < f1, μ1 >, < f2, μ2 >, ... @} >.
Extended symplectic groups. A group G is an extended symplectic group if Sp(n, q)⊆G ⊆CSp(n, q).
The subgroup of CSp(n, q) that contains Sp(n, q) as a subgroup of index m.
The index of the symplectic group in G. This function fails with a runtime exception if G is not an extended symplectic group.
Unitary groups. If f(t)∈k[t] is a polynomial of degree d (over a field k with an automorphism x |-> /line x where x≠/line(x) and /line(/line(x)) = x) such that f(0)≠0, the twisted dual of f(t) is the polynomial f^~(t) = /line(f(0)) - 1td /line(f)(t - 1).
A polynomial f(t) is tilde-symmetric if f^~(t) = f(t); it is tilde-irreducible if it has no proper tilde-symmetric factors. If g∈GU(n, q), then g preserves a non-degenerate hermitian form and from this it follows that the minimal polynomial of g is tilde-symmetric with respect to the automorphism x |-> xq of GF(q2).
The twisted dual of the polynomial f.
The sequence of all tilde-irreducible polynomials of degree d with coefficients in GF(q2).The conjugacy classes of GU(n, q) are in one-to-one correspondence with sequences of pairs < f, μ(f) >, where f is a tilde-irreducible polynomial and μ(f) is a partition, written as a sequence of multiplicities < i, mi >.
Extended special unitary groups. A group G is an extended special unitary group of index m if SU(n, q)⊆G ⊆GU(n, q) and m = |G : SU(n, q)|.
The subgroup of GU(n, q) that contains SU(n, q) as a subgroup of index m.
The index of the special unitary group in G. This function fails with a runtime exception if G is not an extended special unitary group.
Orthogonal groups. An orthogonal signed partition of an integer n is a sequence
[< ∓ 1, m1 >, < 2, m2 >, ..., < n, mn >],
such that the unsigned sequence [< 1, m1 >, < 2, m2 >, ..., < n, mn >] is a partition of n (in multiplicity format), where mi is even for all even i. Only the terms < i, mi > where i is odd are signed.
The conjugacy classes of GOε(n, q) are in one-to-one correspondence with sequences of pairs < f, μ(f) >, where f is a *-irreducible polynomial and μ(f) is a partition if deg (f) > 1 and an orthogonal signed partition if deg(f) = 1. (Note that t - 1 and t + 1 are the only *-irreducible polynomials of odd degree.) When q is a power of 2, more elaborate labels are needed to distinguish the conjugacy classes.
Standard and natural classical groups.
Here we describe intrinsics to list conjugacy classes, determine centralisers, and decide conjugacy in the classical groups. The classes are listed using algorithms developed and implemented by De Franceschi [Fra18], [Fra20], Gonshaw, Liebeck and O'Brien [GLO17], and Taylor. The algorithms to construct centralisers and decide conjugacy were developed and implemented by De Franceschi [Fra18], [Fra20], and De Franceschi, O'Brien and Liebeck (in preparation). O'Brien and Taylor prepared the final versions of these functions for inclusion in Magma.
The functions listed below with arguments (type, d, q) refer to
the `standard'
classical groups: the groups returned by Magma functions such as
GU(d,q) and so on. The accepted values for the argument (or parameter)
type are the strings
"SL", "GL", "Sp", "SU", "GU",
"Omega+", "Omega-", "Omega",
"SO+", "SO-", "SO", "GO+", "GO-",
and "GO".
The conjugates of these groups within the ambient general linear group are the `natural copy' classical groups. Those functions which accept as argument a group G can be applied to all such conjugates of the standard copy of G. The type of a standard or natural copy of G is returned by ClassicalGroupType.
The sequence of conjugacy classes and the corresponding sequence of labels for the natural classical group G.
The conjugacy classes and their labels for the standard classical group of the supplied type, rank d and field size q.
The centralizer of g in the natural classical group G.
The factored order of the centralizer of g in the natural classical group G.
The size of the conjugacy class of g in the natural classical group G.
If g and h are conjugate in the natural classical group G, return true and a conjugating element, otherwise return false.
> G := OmegaPlus (16, 4); > // some natural copy of the group > G := RandomConjugate (G); > g := Random (G); > z := ClassicalCentraliserOrder (G, g); > C := ClassicalCentraliser (G, g); > FactoredOrder (C) eq z; true > g := Random (G); > m := ClassicalClassSize (G, g); > C := ClassicalCentraliser (G, g); > #G div #C eq m; true > x := Random (G); > flag, c := ClassicalIsConjugate (G, g, g^x); > g^c eq g^x; true
type: MonStgElt Default:
The class map for the natural classical group G. The input parameters C and L are the outputs of ClassicalClasses: C is the sequence of classes and L is the list of corresponding labels. The optional parameter type is the type of the classical group.
Given a semisimple element x in a natural classical group G return representatives and labels of the conjugacy classes in G with semisimple part x.
Return a label for the conjugacy class of the element g of the standard isometry group G determined by type. The labels of the elements of G agree if and only if the elements are conjugate in G. The allowed types are "GU", "Sp", "GO+", "GO-" and "GO".
> G := SOPlus (6, 9);
> g := G.1^G.2;
> Cg := ClassicalCentraliser (G, g);
> #Cg;
728
> C := ClassicalClasses (G);
> phi := ClassicalClassMap (G);
> index := phi (g);
> index;
123
> assert #G div C[index][2] eq #Cg;
> g := C[11][3]^G.1;
> h := C[12][3]^G.1;
> label_g := IsometryGroupClassLabel ("GO+", g);
> label_h := IsometryGroupClassLabel ("GO+", g);
> // are these elements conjugate in GO+?
> label_g eq label_h;
true
> // are these elements conjugate in G?
> ClassicalIsConjugate (G, g, h);
false
>
> C, L := ClassicalClasses ("GO", 7, 9);
> L[4];
{*
<0, $.1 + 1, {* <1, 1>^^5, <1, w> *}>,
<0, $.1 + 2, {* <1, 1> *}>
*}
> G := GO(7, 9);
> phi := ClassicalClassMap (G, C, L);
> phi;
> X := {@ G.i^a * G.j^b: a in [1..Order (G.i)], b in [1..Order (G.j)],
> i, j in [1..Ngens (G)] @};
> x := X[46];
> phi (x);
682
> iseq := function(d,q)
> G := Sp(d,q);
> cc := ConjugacyClasses(G);
> reps := [{ One(G) }];
> labels := [{@ IsometryGroupClassLabel("Sp",One(G)) @}];
> R := {c[3] : c in cc | c[1] eq 2};
> T := &join[ Class(G,x) : x in R ];
> L := {@ IsometryGroupClassLabel("Sp",t) : t in R @};
>
> k := 1;
> total := 1 + #R;
> print "Layer", k, ":", #R;;
>
> repeat
> Append(~reps, R);
> Append(~labels, L);
> if total eq #cc then break; end if;
> R := { };
> L := {@ @};
> k +:= 1;
> for g in reps[k] do
> for t in T do
> h := g*t;
> mu := IsometryGroupClassLabel("Sp",h);
> if mu notin labels[k-1] and mu notin labels[k] and mu notin L then
> Include(~R,h);
> Include(~L, mu);
> if total + #R eq #cc then break g; end if;
> end if;
> end for;
> end for;
> total +:= #R;
> print "Layer", k, ":", #R;;
> until IsEmpty(R);
> return reps;
> end function;
The set T is the set of involutions. Given an element g such that ι(g) = k and an involution t∈T, the function IsometryGroupClassLabel is used to check whether g * t is conjugate to an element already in the sequence of conjugacy class representatives. This is considerably faster than using ClassicalIsConjugate because it avoids computing the conjugating element. (Thanks to Oliver Villa for suggesting this example.)
> reps := iseq(4,3); Layer 1 : 2 Layer 2 : 3 Layer 3 : 7 Layer 4 : 15 Layer 5 : 6
The conjugacy classes of the unipotent elements of the standard classical group of the supplied type, rank d and field F, or field size q.
The conjugacy classes of the semisimple elements of the standard classical group of the supplied type which preserves a form, rank d and field F, or field size q.
Return the number of conjugacy classes of the finite isometry group of given type and degree n as a polynomial in the field size q. The allowed type is one of "GL", "GU", "SpOdd", "SpEven", "GO+Even", "GO+Odd" "GO-Even", "GO-Odd" and "GO". Here "Even" and "Odd" indicate the characteristic of GF(q): the relevant polynomial depends on the characteristic.
> H := SU(12, 9);
> // set up just unipotent classes
> U := UnipotentClasses ("SU", 12, 9);
> #U;
88
> C := ClassicalCentraliser (H, U[4][3]);
> FactoredOrder (C);
[ <2, 2>, <3, 28>, <5, 1> ]
>
> K := Sp (6, 8);
> // set up just semisimple classes
> S := SemisimpleClasses ("Sp", 6, 8);
> // for each semisimple class rep, construct all classes for that rep
> G := Sp(6, 8);
> T := [ClassesForFixedSemisimple (G, S[i][3]): i in [1..#S]];
> // Total number of classes of K
> &+[#x: x in T];
684
>
> // polynomial for number of classes in isometry group of this rank
> f := IsometryGroupNumberOfClasses ("SpEven", 6);
> f;
q^3 + 2*q^2 + 5*q + 4
> Evaluate (f, 8);
684
UseLMGHom: BoolElt Default: false
MatricesOnly: BoolElt Default: false
The conjugacy classes for the standard projective classical group of the given type of dimension d over the field of q elements. The second return value is the projective group P, the third return value is the homomorphism from the classical matrix group G to P and fourth return value is the sequence of preimages of the class representatives of P in G.The accepted values for the argument type are the strings "SL", "GL", "Sp", "SU", "GU", "Omega+", "Omega-", "Omega", "SO+", "SO-", "SO", "GO+", "GO-" and "GO", which describe the corresponding classical matrix group.
If the parameter UseLMGHom is true, the code will use LMGHomomorphism as the homomorphism from the matrix group to the projective group.
If the parameter MatricesOnly is true, matrices in the classical matrix group which represent the conjugacy classes in the projective group will be returned as the first (and only) return value.
> time cc, P, f, mm := ProjectiveClassicalClasses("SL",6,3);
Time: 0.150
> H := sub<Generic(P) | P>;
> time hh := Classes(H);
Time: 3.510
> P eq PSL(6,3);
true
> cc, P, f, mm := ProjectiveClassicalClasses("Sp",4,3);
> mm[4];
<
3,
40,
[1 0 0 0]
[0 1 1 0]
[0 0 1 0]
[0 0 0 1]
>
> cc[4][3] eq f(mm[4][3]);
true