6
$\begingroup$

I'm searching for an algorithm that forms a balanced (or quasi-complete) latin square, in which every element is a horizontal neighbor to every other element exactly twice, and a vertical neighbor to every other element exactly twice.

I've found one example (for n = 5), but am not clear about a couple of steps:

Step 1: Write 1 2 ... n as the first row

12345 

Step 2: For i even in the first row, fill in the diagonal from upper left to lower right starting with i and alternating with i - 1

12345   1 3    2     1 

Step 3: For i odd and less than n in the first row fill in the diagonal from upper right to lower left beginning with i and alternating with i + 1

12345  41 3 3  2     1 

Step 4: Fill in n for the main off diagonal

12345  4153 3 52  5  1 5 

Step 5: For the last column write n n-2 n-1 n-3 ... 1 2

12345  4153 3 524  5  1 5   2 

Step 6: For the even entries of the last column, fill in the diagonal from upper left to lower right beginning with i and alternating with i - 1

? 

Step 7: Complete by symmetry about the main diagonal

? 

For n = 5, the following is obtained:

12345 24153 31524 45231 53412 

Questions...

[RE: Step 5] I was able to fill in that portion of the square, but am not sure what would come after n-3 in a larger sequence, as it would go n n-2 n-1 n-3 ??? ... 1 2

[RE: Step 6] Are even entries even numbers, or does that refer to even positions in the column? Is "i" in this case the number at the upper left or is it the even entry? I don't see how the completed square corresponds to the instructions in this step.

[RE: Step 7] What does "complete by symmetry about the main diagonal" mean?

Otherwise if there's a less involved algorithm for balancing a latin square, I'd like to know how it goes.

1 Answers 1

2

The Latin square L:

12345 24153 31524 45231 53412 

is isomorphic to the Cayley table of the cyclic group of order 5 via the isomorphism (3,5,4). That is, if you permute the rows, columns and symbols of L according to the permutation (3,5,4) you will generate

12345 23451 34512 45123 51234 

The n=7 case gives rise to the Latin square

1234567 2416375 3152746 4627153 5371624 6745231 7563412 

which is isomorphic to the Cayley table of the cyclic group of order 7 via the isomorphism (3,7,5,6,4).

With this in mind, my suspicion is that these Latin squares are special cases of those generated in the constructions described by Rosemary Bailey in Quasi-complete Latin squares: construction and randomization, although I haven't gone into the details.

As for the smaller questions:

  • In papers, by an entry I exclusively refer to a triple $(i,j,l_{ij})$, where $i$ is the row index, $j$ is the column index and $l_{ij}$ is the symbol in the $(i,j)$-th cell. For example (2,3,1) would be an entry of the first Latin square. Importantly, in an entry, the position in the Latin square is important, whereas in a symbol, there is no notion of position (aside from being somewhere in the Latin square). Consequently, I would use the term "even symbol" (although note that the symbols you use make no difference to whether or not you have a quasi-complete Latin square).

  • Latin squares L such that $L^T=L$ are called symmetric Latin squares (just as for symmetric matrices). When giving details of a construction of these types of Latin squares, I find myself writing "...then L admits a unique completion to a symmetric Latin square" or similar. There's no need to identify every entry since some entries are determined by other entries.

  • 0
    It's worth taking a look. Papers that give $c$onstructions for Latin squares with various properties (particularly ones that have applications) tend to be very welcome in combinatorics journals.2010-10-26