Balancing a Latin Square

Question

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.

Answer 1

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.