####################### latinsquares ##### 20.1.2003 ########## ##################################################################### # This is a collection of GAP4-programs used in the paper # # Diagonal-complete latin squares # # by Olaf Krafft, Herbert Pahlings and Martin Schaefer (RWTH-Aachen) # # European J. of Combinatorics, 24 (2003), p.229-237 # # # Questions or suggestions are welcome and should be sent to # Herbert.Pahlings@math.rwth-aachen.de # ####################################################################### ####################################################################### ### Definitions # # Let N = {1,...,n}. # A latin square A = [a_{i,j}] is "right-diagonal-complete" (r-complete) # if { ( a_{i,j} , a_{i+1,j+1} ) | i,j in N } = { (i,j) | i,j in N } . # and "left-diagonal-complete" (l-complete) # if { ( a_{i,j} , a_{i-1,j-1} ) | i,j in N } = { (i,j) | i,j in N } . # Here all indices have to be taken mod n . # # For the purpose of the programmes below these definitions have been # extended to latin rectangles [a_{i,j}] in N^{m x n} with m < n # which are called r-complete if # | { ( a_{i,j} , a_{i+1,j+1} ) | i = 1..m-1 , j = 1..n } | = (m-1)*n , # where again indices have to be taken mod n . Similarly for l-completeness. # # The rows of a latin square A can be considered as permutations: # [a_1,...,a_n] is 'identified' with p = ( i -> a_i ) in S_n . # They generate a transitive subgroup G(A) of S_n . If they form a # subgroup (in other words, if G(A) is regular) then A is said to be # "based on a group". A latin square based on a group G can be given # by listing generators of (the regular permutation group) G and by # by listing the first column, which may be an arbitrary permutation # in S_n . # # We call a latin square "normalized" if its first row is [1.,,,.n] . # We call a latin square based on a group "in normal form" if # the first column is [1,...,n]^T . # ######################################################################## ### Examples ### ### In the following examples lines beginning with # are GAP command-lines ## are GAP output ### are comments. ### Of course, the commands in the examples work only, when (the collection ### of functions of) this file has been read in in a GAP-session. ### ### ### Example 1 (r-complete latin squares of degree 4,5,6,7) ### # n := 4;; # li := Derangements( [1..n] );; # res := latRcomplete( [[1..n]] , li );; # Display( res ); ### computes all (four) r-complete latin squares with first row ### [1,2,3,4] and displays the first one as ## [ [ 1, 2, 3, 4 ], ## [ 2, 1, 4, 3 ], ## [ 4, 3, 2, 1 ], ## [ 3, 4, 1, 2 ] ] # # Set ( List (res , groupLQ ) ); ## [ Group([ (), (1,2)(3,4), (1,4)(2,3), (1,3)(2,4) ]) ] ### All four r-complete latin squares are based on the Klein 4-group # ma := List( Elements( groupLQ(res) ), ListPerm );; ma:=[1..n];; # groupbasedlatRcomplete(ma,); ## [ [ 1, 2, 4, 3 ], [ 1, 3, 2, 4 ], [ 1, 3, 4, 2 ], [ 1, 4, 2, 3 ] ] ### These are the first columns of the four r-complete latin squares with ### first row [1,2,3,4] based on the above group. ### Remark: For n = 5,6,7 the same computations show that no r-complete ### latin square of these sizes exist. For n = 7 this computation already ### takes a long time and should be sped up by considering ### representatives of the orbits under the n-cycle p = (1,...,n). # n := 7;; # p := (1,2,3,4,5,6,7);; # li := Derangements( [1..n] );; # lis := ShallowCopy ( li );; # orbreps := [];; # while lis <> [] do # y := orbitofvector( lis, p ) ; Add( orbreps , y); # SubtractSet( lis , y); # od; ### orbreps is now a set of representatives of the orbits of < p > ### on the set of derangements. Since < p > acts on the set of ### normalized r-complete latin squares (by conjugation) it suffices to ### consider elements of orbreps as second rows of the normalized ### latin squares to be tested: # rcomplete7 := [];; # for x in orbreps do # Append( rcomplete7 , latRcomplete( [ [1..n] , x ] , li ) ); # od; # rcomplete7; ## [] ### Example 2 (r-complete latin squares of degree 8) ### # n := 8;; # ma := [ [ 1, 2, 3, 4, 5, 6, 7, 8 ], # [ 2, 1, 4, 3, 6, 5, 8, 7 ] ];; # li := Derangements([1..8]) ;; # res := latRcomplete(ma,li) ;; ## this takes a few hours # Length( res ); ## 16 # List ( res , isLcomplete ) ; ## [ true, true, false, false, false, true, false, true, true, false, true, ## true, true, false, false, false ] # List ( res, x -> IdGroup( groupLQ (x) ) ); ## [ [ 8, 3 ], [ 8, 3 ], [ 128, 928 ], [ 128, 928 ], [ 128, 928 ], [ 8, 3 ], ## [ 128, 928 ], [ 8, 3 ], [ 8, 3 ], [ 128, 928 ], [ 8, 3 ], [ 8, 3 ], ## [ 8, 3 ], [ 128, 928 ], [ 128, 928 ], [ 128, 928 ] ] ## ### So there are 16 extensions of 'ma' to r-complete latin squares of which ### 8 also l-complete. The latter ones are exactly those which are ### based on a group, the dihedral group of order 8 (computed by 'groupLQ'), ### which has GAP-identifier [ 8, 3 ] (returned by IdGroup( ) ), ### the other 8 latin squares all generate (when the rows are considered as ### permutations as above) a group of order 128 with number 928 in the ### library (of groups of order 2^7). In fact the 16 latin squares above ### generate just 2 different groups: # # Set ( List ( res , groupLQ ) ); ## ## [ Group([ (), (1,2)(3,4)(5,6)(7,8), (1,4)(2,7,6,3)(5,8), (1,3,8,6)(2,5,7,4), ## (1,5)(2,6)(3,7)(4,8), (1,7,5,3)(2,8)(4,6), (1,8)(2,3,6,7)(4,5), ## (1,6,8,3,5,2,4,7) ]), ### has Order 128 ## Group([ (), (1,2)(3,4)(5,6)(7,8), (1,3,5,7)(2,8,6,4), (1,6)(2,5)(3,8)(4,7), ## (1,4)(2,7)(3,6)(5,8), (1,8)(2,3)(4,5)(6,7), (1,7,5,3)(2,4,6,8), ## (1,5)(2,6)(3,7)(4,8) ]) ] ### the dihedral group # Display ( res ); ## [ [ 1, 2, 3, 4, 5, 6, 7, 8 ], ## [ 2, 1, 4, 3, 6, 5, 8, 7 ], ## [ 3, 8, 5, 2, 7, 4, 1, 6 ], ## [ 6, 5, 8, 7, 2, 1, 4, 3 ], ## [ 4, 7, 6, 1, 8, 3, 2, 5 ], ## [ 8, 3, 2, 5, 4, 7, 6, 1 ], ## [ 7, 4, 1, 6, 3, 8, 5, 2 ], ## [ 5, 6, 7, 8, 1, 2, 3, 4 ] ] ### ### Example 3 (r-complete latin squares based on D_8) ### ### Instead of continuing with the last example, we start anew (at the same ### point) and want to find all r-complete latin squares based on the ### dihedral group (in its regular representation found in the last example). # G := Group([(1,2)(3,4)(5,6)(7,8), (1,3,5,7)(2,8,6,4)]) ;; # IdGroup(G); ## [ 8, 3 ] # ma := List( Elements(G) , ListPerm);; ma := [1 .. 8];; # Display (ma); ## [ [ 1, 2, 3, 4, 5, 6, 7, 8 ], ## [ 2, 1, 4, 3, 6, 5, 8, 7 ], ## [ 3, 8, 5, 2, 7, 4, 1, 6 ], ## [ 4, 7, 6, 1, 8, 3, 2, 5 ], ## [ 5, 6, 7, 8, 1, 2, 3, 4 ], ## [ 6, 5, 8, 7, 2, 1, 4, 3 ], ## [ 7, 4, 1, 6, 3, 8, 5, 2 ], ## [ 8, 3, 2, 5, 4, 7, 6, 1 ] ] # 1cols := groupbasedlatRcomplete( ma ,  );; # Length( 1cols ); ## 64 # ForAll( 1cols , x -> isLcomplete( ma{x}) ); ## true ## ### Thus there are 64 normalized r-complete latin squares based on G , ### which you obtain as matrices as { ma{x} | x in 1cols} , or in ### GAP-notation List( 1cols , x -> ma{x} ); . The example ### displayed in the end of Example 2 is ma{ 1cols } . ### All these 64 latin squares are also l-complete. ### ### Example 4 (r-complete latin squares based on C_3 x C_3) ### # der:=Derangements([1..9]);; # li:=Filtered( der , x-> Order( PermList(x)) = 3 );; # Length(li); ## 2240 # p:=(1,2,3,4,5,6,7,8,9);; orbreps := [];; lis :=ShallowCopy(li);; # while lis <> [] do # Add(orbreps, lis); # y := orbitofvector( lis, p ) ; SubtractSet( lis , y); # od; # Length(orbreps); ## 256 ### As in Example 1 we calculated a set of representatives 'orbreps' ### of the orbits of

on the set of derangements of order 3, which are ### candidates for the second row x of a latin square based on C_3 x C_3. ### All other rows y must commute (when considered as a permutation) ### with x and in addition y^-1 * x must be a derangement. Using ### these restrictions makes the backtrack search feasible: # res3x3 :=[];; x:=[];; # for x in orbreps do # lis := Filtered( li , y -> PermList(x) * PermList(y) = # PermList(y) * PermList(x) and # ListPerm( PermList(y)^-1 * PermList(x) ) in li ) ; # res:= latRcomplete( [ [1..9] , x ] , lis); # Append( res3x3 , res ); # od; # Length( res3x3 ); ## 0 ### So no r-complete latin squares based on C_3 x C_3 exist . ### ### Example 5 (r-complete latin squares based on C_9) ### # p := (1,2,3,4,5,6,7,8,9) ;; # cl := ConjugacyClassSubgroups( SymmetricGroup(9), Group( p ) ) ;; # cl := AsList(cl) ;; Length(cl); ## 6720 # lc9 := [];; ma:= [];; grouplist := [];; # for x in cl do # ma := List(Elements(x),ListPerm ); ma := [1..9]; # 1cols := groupbasedlatRcomplete( ma ,  ); # if 1cols <> [] then # Append (lc9 , List ( 1cols , y -> ma{y} ) ); # Add ( grouplist , x); # fi; # od; # Length( lc9 ); ## 648 ### This is the total number of normalized l-complete latin squares of ### order 9 based on a cyclic group. The corresponding groups were ### collected in the list 'grouplist'. # Length( grouplist ); ## 56 # grli := Set( ShallowCopy( grouplist ) );; grouporb := [];; # while grli <> [] do # Add( grouporb, grli ); # orb := Set( List([ 1 .. Order( p )], i-> grli^(p ^ i) )); # SubtractSet( grli, orb); Print( Length(orb),",\c"); # od; ## 9,9,9,9,9,9,1,1, ### 'cl' is the list of all (6720) cyclic subgroups of order 9 of S_9. ### Of these 56 yield r-complete latin squares. Under the action of

### these groups form 6 orbits of length 9 and two of length 1. We ### compute the number of normalized r-complete latin squares these ### groups provide: # for g in grouporb do # ma := List( Elements(g), ListPerm); ma := [1..9]; # Print(Length(groupbasedlatRcomplete( ma ,  ) ),",\c"); # od; ## 6,6,6,6,6,6,162,162, ### Thus exactly half of the 648 normalized l-complete latin squares ### are based on one of the two groups invariant under p . ### ### Example 6 (r-complete latin squares based on C_n (n = q^2 , q odd) ### # n := 25;; q := 5;; # l := List( [1..n] , i -> RemInt( (q+1) * i + 1 , n) );; # l[ Position(l,0) ] := n;; # g := Elements( Group( PermList(l) ) );; Size(g) ; ## 25 # ma := List( g , ListPerm) ;; ma := [1..n];; # li := [1, 6, 2, 7, 8, 13, 19, 24, 10, 15, 12, 11];; # cols := groupbasedlatLRcomplete( ma , li ); ## [ [ 1, 6, 2, 7, 8, 13, 19, 24, 10, 15, 12, 11, 14, 3, 16, 20, 22, 5, 21, 4, ## 23, 25, 17, 9, 18 ], ## [ 1, 6, 2, 7, 8, 13, 19, 24, 10, 15, 12, 11, 14, 23, 25, 17, 9, 3, 16, 20, ## 22, 5, 21, 4, 18 ], ## [ 1, 6, 2, 7, 8, 13, 19, 24, 10, 15, 12, 11, 18, 16, 20, 4, 17, 9, 23, 25, ## 3, 22, 5, 21, 14 ] ] ### Thus we have found 3 l-r-complete latin squares based on our group ### (with the first 12 rows prescribed by 'li' ). There are a lot more ### squares based on our group which are r-complete but not l-complete. ### ### Example 7 (r-complete latin squares based on C_7.C_3) ### # n := 21;; # a := ( 1, 2,18)( 3,7,8)(4,5,21)(6,10,11)(9,13,14)(12,16,17)(15,19,20);; # b := ( 1, 4, 7,10,13,16,19)(2,8,14,20,5,11,17)(3,15,6,18,9,21,12);; # G := Group( a, b );; # Order(G); ## 21 # IsAbelian(G); ## false # ma := List( Elements(Group(a,b)) , ListPerm );; ma := [1..n];; # res := groupbasedlatLRcomplete( ma , [ 1, 2, 4, 5, 8, 10, 15] ); ## [ [ 1, 2, 4, 5, 8, 10, 15, 16, 9, 11, 6, 21, 3, 18, 14, 17, 12, 19, ## 20, 7, 13 ] ] ### So there is just one l-r-complete latin square based on G with ### the first 7 rows as given. On the other hand, the number of ### such squares which are just r-complete is very large. #################################################################### # Functions : #################################################################### groupLQ := function(ma) # computes the group generated by the rows of 'ma' considered as # permutations of n = Length(ma) return(Group(List(ma , x -> PermList(x) ) )); end; orbitofvector := function ( x, p ) # Input: 'x' = [s(1),...,s(n)] for s in S_n # 'p' in S_n # Output: Orbit { [t(1),...,t(n)] | t = p^{-i}*s*p^i , i = 0,1,... } local res, i; res := [ x ]; for i in [ 1 .. Order( p ) - 1 ] do Add( res, ListPerm( PermList( x ) ^ (p ^ i) ) ); od; return Set( res ); end; orbitLQ := function ( ma, p ) # Input: 'ma' = latin square of size n # 'p' in S_n # Output: Orbit of 'ma' und operation (by conjugation) of