Goto Chapter: Top 1 2 3 4 5 6 Bib Ind
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 

5 Examples
 5.1 Example 1 -- Constructing groups
 5.2 Example 2 -- Dual polar spaces and their graphs
 5.3 Example 3 -- Codes
 5.4 Example 4 -- Using the library
 5.5 Example 5 -- Constructing HS (advanced example)

5 Examples

5.1 Example 1 -- Constructing groups

In this example, we show how we can use coherent configurations to construct an entriely different almost simple permutation group from another one. We first show how \(PSU(4,3)\) can be made out of its subgroup \(PSL(3,4)\).

gap> psl34 := PSL(3,4);;
gap> sylow3 := SylowSubgroup(psl34, 3);;
gap> normaliser := Normaliser(psl34, sylow3);;
gap> G := Image( FactorCosetAction(psl34, normaliser) );;

At this stage, we have constructed the unique permutation representation of degree 280, for \(PSL(3,4)\).

gap> A := HomogeneousCoherentConfigurationByOrbitals(G);
7-class homogeneous coherent configuration of order 280
gap> mat := RelationMatrix(A);;
gap> P := MatrixOfEigenvalues(A);;
gap> Print(P);
[ [ 1, 18, 18, 18, 72, 72, 72, 9 ], [ 1, 4, 4, 4, 16, -12, -12, -5 ],
 [ 1, -2, -2, 10, -8, 0, 0, 1 ], [ 1, -2, 10, -2, -8, 0, 0, 1 ], 
 [ 1, 10, -2, -2, -8, 0, 0, 1 ],
 [ 1, -2, -2, -2, 0, -8*E(7)^3-8*E(7)^5-8*E(7)^6, -8*E(7)-8*E(7)^2-8*E(7)^4, -3 ], 
 [ 1, -2, -2, -2, 0, -8*E(7)-8*E(7)^2-8*E(7)^4, -8*E(7)^3-8*E(7)^5-8*E(7)^6, -3 ],
 [ 1, -2, -2, -2, 7, -3, -3, 4 ] ]

We now take a particular fusion of this coherent configuration to obtain a 2-class association scheme.

gap> valency18 := Filtered([1..7], j -> Number(mat[1], i -> i = j) = 18);
[1,2,3]
gap> fusions := List(Combinations(valency18,2), t -> 
> 		FusionOfHomogeneousCoherentConfiguration(A, [[0], t, 
> 			Difference([1..7],t)]) );;

Any of these three fusions will do:

gap> autgroup := AutomorphismGroup( fusions[1] );;
gap> DisplayCompositionSeries( autgroup );
G (11 gens, size 26127360)
 | Z(2)
S (4 gens, size 13063680)
 | Z(2)
S (3 gens, size 6531840)
 | Z(2)
S (2 gens, size 3265920)
 | 2A(3,3) = U(4,3) ~ 2D(3,3) = O-(6,3)
1 (0 gens, size 1)
gap> socle := Socle(autgroup);;
gap> StructureDescription(socle);
"PSU(4,3)"

5.2 Example 2 -- Dual polar spaces and their graphs

For this example, we also use the package FinInG [BBDB+18]. We will construct a metric association scheme coming from a dual polar space.

gap> LoadPackage("FinInG", false);;
gap> quadric := EllipticQuadric(7, 2);
Q-(7, 2)
gap> points := AsList( Planes(quadric) );;
gap> mat := NullMat(Length(points), Length(points));;
gap> for i in [1..Length(points)] do
> 	for j in [i+1..Length(points)] do
> 		intersection := Meet( points{[i,j]} );
gap> 		mat[i][j] := 2 - ProjectiveDimension( intersection );
gap> 		mat[j][i] := mat[i][j];
gap> 	od;
gap> od;

So far we have constructed the relation matrix arising from the dual polar space.

gap> a := HomogeneousCoherentConfiguration( mat );
3-class association scheme of order 765
gap> P := MatrixOfEigenvalues(a);;
gap> Q := MatrixOfDualEigenvalues(a);;
gap> Display(P);
[ [    1,   28,  224,  512 ],
  [    1,   11,   20,  -32 ],
  [    1,   -7,   14,   -8 ],
  [    1,    1,  -10,    8 ] ]
gap> Display(Q);
[ [       1,      84,     204,     476 ],
  [       1,      33,     -51,      17 ],
  [       1,    15/2,    51/4,   -85/4 ],
  [       1,   -21/4,  -51/16,  119/16 ] ]
gap> IsPPolynomial(a);
true
gap> IsQPolynomial(a);
true 

A simpler way (perhaps) uses the automorphism group of the ambient polar space:

gap> cgroup := CollineationGroup(quadric);
PGO(-1,8,2)
gap> G := Action(cgroup, points);
<permutation group with 3 generators>
gap> a := SchurianAssociationScheme(G);
3-class homogeneous coherent configuration of order 765
gap> IsPPolynomial(a);
true

The automorphism group of the association scheme should be the same:

gap> autgroup := AutomorphismGroup(a);;
gap> autgroup = G;
true

Now (for the purist!) we see if there are interesting subsets. Take a nondegenerate hyperplane section defining a parabolic quadric.

gap> hyperplane := First(Hyperplanes(PG(7,2)), h -> 
> 		TypeOfSubspace(quadric, h) = "parabolic");
<a proj. 6-space in ProjectiveSpace(7, 2)>
gap> insidehyp := Filtered(points, t -> t * hyperplane);;
gap> vector := CharacteristicVector(points, insidehyp);;
gap> dist := InnerDistribution(a, vector);
[ 1, 56, 64, 14 ]
gap> macw := MacWilliamsTransform(a, dist);
[ 135, 630, 0, 0 ]

Therefore, a hyperplane section gives rise to a design that is not a code, in this association scheme. Now we produce the dual polar graph.

gap> P := MatrixOfEigenvalues(a);;
gap> Display(P);
[ [    1,  224,  512,   28 ],
  [    1,   20,  -32,   11 ],
  [    1,   14,   -8,   -7 ],
  [    1,  -10,    8,    1 ] ]
gap> position := Position(P[1], 28);
4
gap> M := AdjacencyMatrices(a)[ position ];;
gap> graph := Graph(G, [1..Order(a)], OnPoints, {x,y} -> M[x][y] = 1);;
gap> IsDistanceRegular(graph);
true
gap> GlobalParameters(graph);
[ [ 0, 0, 28 ], [ 1, 3, 24 ], [ 3, 9, 16 ], [ 7, 21, 0 ] ]

5.3 Example 3 -- Codes

For this example, we use the package Guava[BBC+18] for its facility with block codes. We will see that the inner distribution vector of a subset coincides with the weight enumerator of a code when the association scheme is a Hamming scheme.

gap> hammingscheme := HammingScheme(7,2);
7-class homogeneous coherent configuration of order 128
gap> LoadPackage("Guava", false);;
gap> hammingcode := HammingCode(3, GF(2));
a linear [7,4,3]1 Hamming (3,2) code over GF(2)

We now use an operation from Guava:

gap> InnerDistribution(hammingcode);
[ 1, 0, 0, 7, 7, 0, 0, 1 ]

From the association scheme perspective ...

gap> codewords := List( hammingcode, VectorCodeword );;
gap> vector := CharacteristicVector( AsList(GF(2)^7), codewords );;
gap> Collected(vector);
[ [ 0, 112 ], [ 1, 16 ] ]
gap> inndist := InnerDistribution( hammingscheme, vector);
[ 1, 0, 0, 7, 7, 0, 0, 1 ]

The MacWilliams transform coincides with the distribution vector of the dual code:

gap> 1/16 * MacWilliamsTransform( hammingscheme, inndist);
[ 1, 0, 0, 0, 7, 0, 0, 0 ]
gap> dualcode := DualCode( hammingcode );
a linear [7,3,4]2..3 dual code
gap> InnerDistribution( dualcode );
[ 1, 0, 0, 0, 7, 0, 0, 0 ]

5.4 Example 4 -- Using the library

In this package, we also have a library of all small homogeneous coherent configurations, of order at most 38 (except 31, ,35, 36, 37), corresponding to [HM].

gap> for i in [5..20] do
> 	Print(i,"    ",NumberOfHomogeneousCoherentConfigurations(i),"\n");
gap> od;
5    2
6    6
7    3
8    16
9    10
10    11
11    3
12    54
13    5
14    14
15    24
16    208
17    4
18    90
19    6
20    90
gap> order7 := List([1..3], i -> HomogeneousCoherentConfiguration(7, i));
 1-class homogeneous coherent configuration of order 7, 
 2-class homogeneous coherent configuration of order 7, 
 3-class homogeneous coherent configuration of order 7 ]

The first of these is trivial, so we look at the other two. The first arises from the Paley graph of order 7.

gap> a1 := order7[2];
2-class homogeneous coherent configuration of order 7
gap> autgroup := AutomorphismGroup(a1);
Group([ (2,3,4)(5,7,6), (1,2,3,5,4,6,7) ])
gap> StructureDescription(autgroup);
"C7 : C3"

The last one is a 3-class association scheme:

gap> a2 := order7[3];
3-class homogeneous coherent configuration of order 7
gap> IsAssociationScheme(a2);
true
gap> IsPPolynomial( a2 );
true
gap> IsPrimitive(a2);
rue
gap> Valencies(a2);
[ 1, 2, 2, 2 ]
gap> autgroup := AutomorphismGroup(a2);
Group([ (2,3)(4,5)(6,7), (1,2)(3,4)(5,6) ])
gap> StructureDescription(autgroup);
"D14"
gap> P := MatrixOfEigenvalues(a2);;
gap> Display(P);
[ [              1,              2,              2,              2 ],
  [              1,  E(7)^3+E(7)^4,    E(7)+E(7)^6,  E(7)^2+E(7)^5 ],
  [              1,  E(7)^2+E(7)^5,  E(7)^3+E(7)^4,    E(7)+E(7)^6 ],
  [              1,    E(7)+E(7)^6,  E(7)^2+E(7)^5,  E(7)^3+E(7)^4 ] ]
gap> AllPPolynomialOrderings(a2);
[ [ 0, 1, 2, 3 ], [ 0, 2, 3, 1 ], [ 0, 3, 1, 2 ] ]
gap> AdmitsQPolynomialOrdering(a2);
true
gap> AllQPolynomialOrderings(a2);
[ [ 0, 1, 3, 2 ], [ 0, 2, 1, 3 ], [ 0, 3, 2, 1 ] ]

5.5 Example 5 -- Constructing HS (advanced example)

We redo an example that appears in Section 3.6 of Peter Cameron's "Permutation Groups" book [Cam99] and construct the Higman-Sims group.

First we construct the Hoffman-Singleton graph from the alternating group of degree 7.

gap> A7 := AlternatingGroup(7);;
gap> Pi := [ [ 1, 2, 4 ], [ 1, 3, 7 ], [ 1, 5, 6 ], 
>  [ 2, 3, 5 ], [ 2, 6, 7 ], [ 3, 4, 6 ], [ 4, 5, 7 ] ];;
gap> OnSetsRecursive := function(x,g) 
> 	if not IsSet(x) then
> 		return x^g; 
gap> 	else 
> 		return Set(x,y->OnSetsRecursive(y,g));
gap> 	fi;
gap> end;;
gap> triples := Combinations([1..7], 3);;
gap> allFanos := Orbit(A7, Pi, OnSetsSets);;
gap> fifty := Concatenation(triples, allFanos);;
gap> A7action := Action(A7, fifty, OnSetsRecursive);
<permutation group with 2 generators>
gap> orbitals := Orbits(A7action, Combinations([1..50],2), OnSets);;
gap> List(orbitals, Size);
[ 210, 315, 70, 420, 105, 105 ]

We will now make a homogeneous coherent configuration from scratch, from these orbitals.

gap> mat := NullMat(50,50);;
gap> for i in [1..50] do
> 	for j in [i+1..50] do
> 		pos := First([1..Length(orbitals)], k -> [i,j] in orbitals[k]);
gap> 		mat[i][j] := pos;
gap> 		mat[j][i] := pos;
gap> 	od;
gap> od;

This is not a CC yet. We will fuse the relations of valency 3 and 4:

gap> l := Collected(mat[1]);
[ [ 0, 1 ], [ 1, 12 ], [ 2, 18 ], [ 3, 4 ], [ 4, 12 ], [ 5, 3 ] ]
gap> to_fuse := Filtered([1..Length(l)], t -> l[t][2] in [3,4])-1;
[ 3, 5 ]
gap> to_fuse2 := Difference([1..6],to_fuse);
[ 1, 2, 4, 6 ]
gap> poly := InterpolatedPolynomial(Rationals, Concatenation([0], to_fuse, 
> 	to_fuse2), [0,1,1,2,2,2,2] );;
gap> newmat := List(mat, row -> List(row, x -> Value(poly,x)));;
gap> Collected(newmat[1]);
[ [ 0, 1 ], [ 1, 7 ], [ 2, 42 ] ]

This now leads us directly to the Hoffman-Singleton graph:

gap> cc := HomogeneousCoherentConfiguration( newmat ); 
2-class association scheme of order 50
gap> autHoffSing := AutomorphismGroup( cc );
<permutation group with 7 generators>
gap> StructureDescription( autHoffSing );
"PSU(3,5) : C2"

We will now construct the Mesner-Higman-Sims graph

gap> vals := Valencies(cc);
[ 1, 7, 42 ]
gap> adjmat := AdjacencyMatrices(cc)[ Position(vals, 42) ];;
gap> graph := Graph(autHoffSing, [1..50], OnPoints, {x,y} -> adjmat[x][y]=1);;
gap> one_coclique := CompleteSubgraphsOfGivenSize(graph, 15)[1];;
gap> all_cocliques := Orbit(autHoffSing, 
> 	Set(VertexNames(graph){one_coclique}), OnSets);;
gap> Size(all_cocliques);
100
gap> G := Action(autHoffSing, all_cocliques, OnSets);;
gap> a := SchurianAssociationScheme(G);
4-class homogeneous coherent configuration of order 100

Now fuse the relations with valencies 7 and 15 (and the complement)

gap> vals := Valencies(a);
[ 1, 35, 42, 15, 7 ]
gap> to_fuse := Filtered([1..Length(vals)], t -> vals[t] in [7,15])-1;;
gap> to_fuse2 := Difference([1..4], to_fuse);;
gap> fusion := FusionOfHomogeneousCoherentConfiguration(a, [[0], to_fuse,
> 	to_fuse2]);
2-class association scheme of order 100
gap> autgroup2 := AutomorphismGroup(fusion);
<permutation group with 10 generators>
gap> StructureDescription(autgroup2);
"HS : C2"
 [Top of Book]  [Contents]   [Previous Chapter]   [Next Chapter] 
Goto Chapter: Top 1 2 3 4 5 6 Bib Ind

generated by GAPDoc2HTML