## Archive for the ‘Misc. Combinatorics’ Category

### Supersymmetric Latin squares

July 4, 2011

Latin squares have long been a staple object of study of combinatorics and recreational mathematics.  A Latin square of size n is an $n\times n$ 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 $\{1,2,3,\ldots,n\}$ or $\{0,1,2,\ldots,n-1\}$, 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 $I \times I$ an element $I$ such that for each fixed $a\in I$, $f(a,-)$ and $f(-,a)$ realize each value in $I$ exactly once.  Blurring the distinction between $(I \times I) \times I)$ and $I \times I \times I$, 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 $I\times I\times I$ such that, for any fixed $a,b\in I$, each of the incomplete triples $(a,b, - ), (a, - , b), (-, a, b)$ can be completed to an element of $S$ in exactly one way.  (That is, a subset of $I\times I\times I$ with size $|I|^2$ whose projection onto any pair of coordinates is exactly $I\times I$.)

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 $I^{k+2}$ with size $|I|^2$ whose projection onto any pair of coordinates is exactly $I\times I$.)  This symmetry also means that $S_3$ 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 $I\times I\times I$) is closed under permutation of coordinates.

That is, a supersymmetric Latin square is in an orbit by itself under the $S_3$-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 $S_I\times S_I \times S_I$ is not), we have an instant proof that $n!$ divides the number of Latin squares on a set of n (and if you are a little careful, you can improve this to $n!(n-1)!$ for almost no extra work).

This doesn’t work for supersymmetric Latin squares, though; these actions of $S_I$ are not compatible with the action of $S_3$ in the definition of supersymmetry.  There does, however, exist a natural action of $S_I$ on the set of supersymmetric Latin squares on $I$, where a permutation of $I$ 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 $S_3$.  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 $S_I$-action.  Likewise, ssls on I is equivalent to an ssls on J if the latter is the image of the former under some bijection $I\to J$ acting on every component of every triple.  I’m interested in classifying supersymmetric Latin squares of size n, up to equivalence.

For $n=1,2,4,5$, it’s not hard to check that there are no examples.  (Edit: as noted in the comments, that’s just plain not true.)  For $n=3$ there are the two already given.  Call them $\alpha, \beta$ 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 $S\times S'$, a Latin square on $I\times I'$, by $\left\{((a,a'),(b,b'),(c,c'))\in (I\times I')^3~:~(a,b,c)\in S , (a',b',c')\in S'\right\}$.  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: $\alpha\times \alpha, \alpha\times\beta, \beta\times\alpha, \beta\times\beta$.  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  $\alpha\times \alpha, \alpha\times\beta, \beta\times\beta$.  (In order to write the squares in my preferred way, I have to choose a bijection between $\{0,1,2\}^2$ and $\{0,1,2,3,4,5,6,7,8\}$; 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 $(0)(14562873)$.

The same approach enables us to construct two supersymmetric Latin squares $\alpha^k=\alpha\times\cdots \times \alpha$ and $\beta^k=\beta\times\cdots \times \beta$ of size $3^k$ for $k=1,2,3,\ldots$.  Any mixed product of $\alpha$‘s and $\beta$‘s is equivalent to $\beta^k$, so we have found all the ssLs’s which arise as products of the ones we know.  These two are inequivalent, because $\alpha^k$ contains all triples of the form $(a,a,a)$ and $\beta^k$ contains no such triples.

Questions.

1. Do supersymmetric Latin squares exist of any size which is not a power of 3?
2. For size any positive power of 3, we have found two inequivalent ssLs’s.  Is this a complete list?
3. We could also consider less strict symmetry conditions, requiring only that the Latin square be invariant under some subgroup of $S_3$.  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 $A_3$-symmetry, that the square be invariant under cyclic shifts.  (I haven’t really thought about this yet, but it seems potentially interesting.)