The automorphism group A of an incidence structure D is always presented as a permutation group G acting on the standard support. The reasons for this include the fact that the support chosen when computing the automorphism group is often quite complicated. Further, if the group is represented as acting on a set of objects relating to the incidence structure, printed permutations are often unreadable. The support used when constructing the automorphism group of an incidence structure D is either the point set of D (when D is simple), or the disjoint union of the point set with the block set (when D has repeated blocks).
The automorphism group G of D does not act directly on D. Instead, G-sets are used to transfer the action of G to various sets associated with D. The two most important G-sets, corresponding to action of G on the point set and on the block set, are returned by each of the functions provided for constructing automorphism group or some specified subgroup of it.
In some circumstances, rather than viewing automorphisms as group elements, it is desirable to view them is as mappings of D into itself. Associated with each incidence structure is a mapping structure, Aut(D), which denotes the set of automorphisms of D. Note that Aut(D) is the parent of the automorphisms of G so that the function Aut(D) simply creates a shell structure rather than the actual automorphism group of D. A transfer map is provided to convert a permutation of the automorphism group G into a mapping belonging to Aut(D).
Construct the automorphism group G of the incidence structure D. The set on which G acts depends upon whether or not the design is simple. Suppose D has v points and b blocks. If the incidence structure D is simple, the automorphism group is constructed in its action on the points of D. It is returned acting on the standard support { 1, ..., v }, where i corresponds to the i-th point of D. If D is not simple, it is constructed in its action of the disjoint union of the point set and block set of D. Again, it is returned acting on the standard support { 1, ..., v+b }, where 1 ≤i ≤v corresponds to the i-th point of D and v + 1 ≤i ≤v + b corresponds to the (i - v)-th point of D. The function returns:Given a permutation g of G, t(g) is the mapping of D into itself that corresponds to the automorphism group element g. The G-sets Y and W should be used whenever it is necessary to have G act on the points or lines of D.
- (i)
- The automorphism group G of D as described above;
- (ii)
- A G-set Y corresponding to the action of G on the point set of D.
- (iii)
- A G-set W corresponding to the action of G on the block set of D.
- (iv)
- The Aut structure S for D; and
- (v)
- A transfer map t : G -> S.
A cyclic subgroup H of the automorphism group G of the incidence structure D. The purpose of this function is to terminate the search for automorphisms of D as soon as a non--trivial automorphism is found. The function returns:Given a permutation g of H, t(g) is the mapping of D into itself that corresponds to the automorphism group element g.
- (i)
- The automorphism group H of D as described above;
- (ii)
- The Aut structure S for D; and
- (iii)
- A transfer map t : G -> S.
The subgroup H of the automorphism group G of the incidence structure D, which stabilizes the first k base points of G. This function is provided so as to return a subgroup of G that is sometimes easier to compute than all of G. The function returns:Given a permutation g of H, t(g) is the mapping of D into itself that corresponds to the automorphism group element g.
- (i)
- The automorphism group H of D as described above;
- (ii)
- The Aut structure S for D; and
- (iii)
- A transfer map t : G -> S.
The automorphism group of the incidence structure D given in its action on the point set of D, together with the points G-set.
The automorphism group of the incidence structure D given in its action on the block set of D.
The power structure A of all automorphisms of the incidence structure D, together with the transfer map t : Sym(n) -> A, where the points of Sym(n) are assumed to be in one--to--one correspondence with the natural support for the automorphism group of D.
> R := MatrixRing(Integers(), 4);
> H := R ! [1,1,1,-1, 1,1,-1,1, 1,-1,1,1, -1,1,1,1];
> L := TensorProduct(H, -H);
> D, P, B := HadamardRowDesign(L, 1);
> D;
3-(16, 8, 3) Design with 30 blocks
> G, pg, bg, A, t := AutomorphismGroup(D);
> G;
Permutation group G acting on a set of cardinality 16
Order = 322560 = 2^10 * 3^2 * 5 * 7
(9, 15)(10, 16)(11, 13)(12, 14)
(5, 11, 7, 9)(6, 12, 8, 10)(13, 15)(14, 16)
(5, 9, 14)(6, 10, 13)(7, 11, 16)(8, 12, 15)
(1, 2)(7, 8)(9, 13, 10, 14)(11, 16, 12, 15)
(2, 5)(4, 7)(10, 13)(12, 15)
(3, 9)(4, 10)(7, 13)(8, 14)
(3, 8, 15, 12)(4, 7, 16, 11)(5, 9)(6, 10)
(5, 6)(7, 8)(13, 14)(15, 16)
(3, 12, 4, 11)(7, 16, 8, 15)(9, 10)(13, 14)
(3, 7)(4, 8)(11, 15)(12, 16)
(3, 8)(4, 7)(9, 10)(11, 15)(12, 16)(13, 14)
(9, 10)(11, 12)(13, 14)(15, 16)
(9, 13)(10, 14)(11, 15)(12, 16)
> CompositionFactors(G);
G
| Alternating(8)
*
| Cyclic(2)
*
| Cyclic(2)
*
| Cyclic(2)
*
| Cyclic(2)
1
As noted at the beginning of the section, the automorphism group G of an incidence structure D is given in its action on the standard support and it does not act directly on D. The action of G on D is obtained using the G-set mechanism. The two basic G-sets associated with D correspond to the action of G on the set of points P and the set of blocks B of D. These two G-sets are given as return values of the function AutomorphismGroup or may be constructed directly. Additional G-sets associated with D may be built using the G-set constructors. Given a G-set Y for G, the action of G on Y may be studied using the permutation group functions that allow a G-set as an argument. In this section, only a few of the available functions are described: see the section on G-sets for a complete list.
Let G be a subgroup of the automorphism group for the incidence structure D and let Y be a G-set for G. Given an element y belonging either to Y or to a G-set derived from Y, find the image of y under G.
Let G be a subgroup of the automorphism group for the incidence structure D and let Y be a G-set for G. Given an element y belonging either to Y or to a G-set derived from Y, construct the orbit of y under G.
Let G be a subgroup of the automorphism group for the incidence structure D and let Y be a G-set for G. This function constructs the orbits of the action of G on Y.
Let G be a subgroup of the automorphism group for the incidence structure D and let Y be a G-set for G. Given an element y belonging either to Y or to a G-set derived from Y, construct the stabilizer of y in G.
Given a subgroup G of the automorphism group of the incidence structure D, and a G-set Y for G, construct the homomorphism φ: G -> L, where the permutation group L gives the action of G on the set Y. The function returns:
- (a)
- The natural homomorphism φ: G -> L;
- (b)
- The induced group L;
- (c)
- The kernel of the action (a subgroup of G).
Given a subgroup G of the automorphism group of the incidence structure D, and a G-set Y for G, construct the permutation group L giving the action of G on the set Y.
Given a subgroup G of the automorphism group of the incidence structure D, and a G-set Y for G, construct the kernel of the action of G on the set Y.
Returns true iff the automorphism group of the incidence structure D acts transitively on the point set of D.
Returns true iff the automorphism group of the incidence structure D acts transitively on the block set of D.
> D, P, B := WittDesign(12);
> A, PY, BY := AutomorphismGroup(D);
> A;
Permutation group Aut acting on a set of cardinality 12
Order = 95040 = 2^6 * 3^3 * 5 * 11
(1, 2)(5, 8)(6, 11)(10, 12)
(2, 3)(5, 12)(6, 8)(10, 11)
(3, 4)(5, 10)(6, 11)(8, 12)
(4, 7)(5, 8)(6, 12)(10, 11)
(5, 11, 12, 6)(7, 8, 9, 10)
(5, 9, 12, 7)(6, 10, 11, 8)
(5, 12)(6, 11)(7, 9)(8, 10)
> a := A!(1, 2, 3, 4)(5, 6, 12, 11);
> 4^a;
1
> {1, 2, 3}^a;
{ 2, 3, 4 }
> Image(a, BY, Block(D, 3));
{1, 2, 3, 8, 11, 12}
> S2 := SylowSubgroup(A, 2);
> S2;
Permutation group S2 acting on a set of cardinality 12
Order = 64 = 2^6
(1, 11, 9, 4)(6, 10, 12, 7)
(1, 9)(2, 12)(3, 7)(4, 11)(5, 10)(6, 8)
(1, 4)(3, 5)(7, 10)(9, 11)
> Stabilizer(S2, BY, Block(D, 4));
Permutation group acting on a set of cardinality 12
Order = 2
(1, 9)(3, 5)(6, 7)(10, 12)
> Stabilizer(S2, 6);
Permutation group acting on a set of cardinality 12
Order = 8 = 2^3
(1, 4)(3, 5)(7, 10)(9, 11)
(1, 4, 9, 11)(2, 5, 8, 3)
> 3^S2;
GSet{ 2, 3, 5, 6, 7, 8, 10, 12 }
> IsPointTransitive(D);
true
> IsBlockTransitive(D);
true
We calculate the action of the automorphism group of the design on
its blocks.
> H := ActionImage(A, BY); > #H; 95040 > H; Permutation group H acting on a set of cardinality 132 Order = 95040 = 2^6 * 3^3 * 5 * 11