Latin squares have long been a staple object of study of combinatorics and recreational mathematics. A Latin square of size n is an array of elements of some set of n symbols such that each symbol appears exactly once in each row and in each column. For our purposes, it will be important to have the set of indices for the rows and columns and the set of symbols be the same set. For some finite index. The “obvious” choice for the index sets will be or , but we could use any finite set. Whenever I display a Latin square here, I will use one of these sets, with row numbers increasing from left to right and column numbers increasing from top to bottom.
It’s illustrative to move from the graphical definition of a Latin square to something more symbolic. A Latin square on an index set I is a function f assigning each element of an element such that for each fixed , and realize each value in exactly once. Blurring the distinction between and , we can recast the above definition in the following way.
Definition. A Latin square on a (finite) index set I is a subset S of such that, for any fixed , each of the incomplete triples can be completed to an element of in exactly one way. (That is, a subset of with size whose projection onto any pair of coordinates is exactly .)
Notice that “function-ness” and the conditions on the rows and columns are absorbed into one pleasantly symmetric condition. This explains the mysterious fourth paragraph of this Not About Apples post. (This definition also generalizes gracefully to orthogonal Latin squares; a list of k orthogonal squares corresponds naturally to a subset of with size whose projection onto any pair of coordinates is exactly .) This symmetry also means that acts naturally on the set of Latin squares on a particular index set by permuting the coordinates. This led me to think about the following definition.
Definition. A supersymmetric Latin square (ssLs) is a Latin square which (viewed a subset of ) is closed under permutation of coordinates.
That is, a supersymmetric Latin square is in an orbit by itself under the -action.
Example.
There are three supersymmetric Latin squares on {0,1,2}.
021 102 210 210 021 102 102 210 021
For ordinary Latin squares, there is another kind of symmetry. Rows can be permuted, columns can be permuted, and the symbols themselves can be permuted. That is, the symmetric group on the index set acts naturally on the set of Latin squares in three ways, by acting on the first, second, or third coordinate of the triples. This justifies the common convention of assuming without loss of generality that a Latin square has the symbols listed in order across the first row and down the first column; since each of these actions is free (though the composite action of is not), we have an instant proof that divides the number of Latin squares on a set of n (and if you are a little careful, you can improve this to for almost no extra work).
This doesn’t work for supersymmetric Latin squares, though; these actions of are not compatible with the action of in the definition of supersymmetry. There does, however, exist a natural action of on the set of supersymmetric Latin squares on , where a permutation of acts on all permutation . In further contrast with the ordinary case, this action is not free; it’s not even faithful.
Example.
The first ssLs listed above is stabilized by all of . The latter two are stabilized by the even permutations; odd permutations interchange them.
I call two supersymmetric Latin squares on I equivalent if they are in the same orbit of this -action. Likewise, ssls on I is equivalent to an ssls on J if the latter is the image of the former under some bijection acting on every component of every triple. I’m interested in classifying supersymmetric Latin squares of size n, up to equivalence.
For , it’s not hard to check that there are no examples. (Edit: as noted in the comments, that’s just plain not true.) For there are the two already given. Call them in the order they are listed in the first example.
There are infinitely many supersymmetric Latin squares. Let me briefly explain the construction of all the ones I know.
There is a natural product on Latin squares. If S (resp. S’) is a Latin square on I (resp. I’), then we define , a Latin square on , by . I leave to the reader the verification that this is fact a Latin square, and that it is supersymmetric if S and S’ are.
Since we have two ssLs’s of size 3, we can construct ssLs’s of size 9. There are four possibilities to consider: . All will be supersymmetric, of course, but they cannot all be inequivalent. The middle two are certainly equivalent, since the product operation is commutative up to equivalence. Now we can just write out . (In order to write the squares in my preferred way, I have to choose a bijection between and ; here I use the one provided by base 3 notation.)
021687354 102768435 435102768 210876543 021687354 354021687 102768435 210876543 543210876 687354021 768435102 102768435 876543210 687354021 021687354 768435102 876543210 210876543 354021687 435102768 768435102 543210876 354021687 687354021 435102768 543210876 876543210
It’s not obvious, but the second and third squares are actually equivalent under e.g. the permutation .
The same approach enables us to construct two supersymmetric Latin squares and of size for . Any mixed product of ‘s and ‘s is equivalent to , so we have found all the ssLs’s which arise as products of the ones we know. These two are inequivalent, because contains all triples of the form and contains no such triples.
Questions.
- Do supersymmetric Latin squares exist of any size which is not a power of 3?
- For size any positive power of 3, we have found two inequivalent ssLs’s. Is this a complete list?
- We could also consider less strict symmetry conditions, requiring only that the Latin square be invariant under some subgroup of . If the subgroup is generated by a transposition, then this boils down to considering Latin squares which are symmetric (in the sense of symmetric matrices). But what about requiring only -symmetry, that the square be invariant under cyclic shifts. (I haven’t really thought about this yet, but it seems potentially interesting.)