4

First off, my apologies for the long and convoluted title. I am no mathematician so I don't know the "proper" terms to use... which is exactly my problem:

I want to find a/any/one Latin square of order 8 in which each pair of numbers in each row only occurs once in the complete square, i.e. I am looking for a latin square $L\in\mathbb{N}^{n\times n}$ in which each pair $(l_{i,j},l_{i,j+1}), i\in[1,n],j\in[1,n)$ is unique.

Here is an example for an order-4 square:

A "regular" Latin square that does not have the property I am looking for: $$ A= \begin{bmatrix} 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \\ 3 & 4 & 1 & 2 \\ 4 & 1 & 2 & 3 \\ \end{bmatrix} $$

A Latin square that has the property I am looking for: $$ B= \begin{bmatrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 1 & 3 \\ 3 & 1 & 4 & 2 \\ 4 & 3 & 2 & 1 \\ \end{bmatrix} $$

For example, in $A$ the pair $(a_{1,2},a_{1,3})=(2,3)$ is repeated in the the rows 2 and 3 as $(a_{2,1},a_{2,2})$ and $(a_{3,3},a_{3,4})$, respectively. In $B$, however, that same pair $(b_{1,2},b_{1,3})=(2,3)$ is not repeated. Is there a name for this property?

To be honest, I don't even know if such a Latin square exist for order 8, but so far I haven't been able to find some related information, mainly as I don't know what to google for :(.

Any answer that gives me some searchable terms would greatly help me. Of course, a direct example of a Latin square of order 8 with the property I am after would be even more appreciated. Thanks in advance for spending your time responding.

PS:In case somebody is wondering why I am looking for this: I am trying to set up a full factorial experiment with 3 factors at 2 levels each, i.e. $2^3=8$ cases. I would like to use the Latin square I am after to find sequences of the individual experiments in which two experiments never follow each other more than once so that I can exclude any training or learning effects from one to the other.

Edit: While further looking onto this I noticed that my given example square $B$ shows additional properties that I actually don't really care for: I neither need $B$ to be in reduced form (first row and first column are in natural order), nor do I need $B$ to be symmetric ($B=B^T$).

hcc23
  • 141
  • Dear @hcc23, you just require that the pairs do not repeat horizontally, am I right ? You also don't need to exclude circular pairs (seeing the latin square as a cylinder or a torus) ? – ogerard Oct 27 '14 at 18:55
  • @ogerard: Yes, you are correct: no "wrap around" and no comparison between rows (i.e. the pair $(a_{i,j},a_{i+1,j})$ can repeat). Order also matters, i.e. $(x,y)$ is different from $(y,x)$. My apologies if my notation isn't as concise as it should/could be. – hcc23 Oct 28 '14 at 13:41

2 Answers2

3

Hi I believe that the name of the property you are describing is row complete. See here for more information http://personal.maths.surrey.ac.uk/st/H.Bruin/MMath/LatinSquares.html

  • 1
    Thanks for not only providing the name but also a very easy to read reference. A quick MATLAB script based on the method outlined in your reference (https://gist.github.com/hcc23/274b76edc3dd82d5de1a) instantly provided what I needed :) Thanks! – hcc23 Oct 28 '14 at 14:44
  • @hcc23 I'm glad that it was useful to you! –  Oct 28 '14 at 15:24
  • An archive version is at https://web.archive.org/web/20170708014237/http://personal.maths.surrey.ac.uk/st/H.Bruin/MMath/LatinSquares.html – Henry Mar 15 '23 at 18:36
1

Using the method for row-complete cyclic Latin Squares given in the H.Bruin page cited by the other answer for n=8, gives:

$$\left( \begin{array}{cccccccc} 1 & 2 & 8 & 3 & 7 & 4 & 6 & 5 \\ 2 & 3 & 1 & 4 & 8 & 5 & 7 & 6 \\ 3 & 4 & 2 & 5 & 1 & 6 & 8 & 7 \\ 4 & 5 & 3 & 6 & 2 & 7 & 1 & 8 \\ 5 & 6 & 4 & 7 & 3 & 8 & 2 & 1 \\ 6 & 7 & 5 & 8 & 4 & 1 & 3 & 2 \\ 7 & 8 & 6 & 1 & 5 & 2 & 4 & 3 \\ 8 & 1 & 7 & 2 & 6 & 3 & 5 & 4 \end{array} \right)$$

Of course, any permutation of its rows will do.

But if what you really need is to run all the successive couples in the most efficient way, here is another way to do it. This sequence contains all the 56 different pairs and use only 57 different terms (even 56 if you use the fact that it starts and ends by the same symbol) instead of the 64 of the 8x8 latin square :

(2, 3, 1, 4, 8, 5, 7,
 6, 7, 5, 8, 4, 1, 3, 
 2, 1, 2, 8, 3, 7, 4,
 6, 5, 6, 4, 7, 3, 8,
 2, 5, 1, 6, 8, 7, 8,
 6, 1, 5, 2, 4, 3, 4,
 5, 3, 6, 2, 7, 1, 8,
 1, 7, 2, 6, 3, 5, 4, 2 )

and you can vary it by any translation or any of the 40320 permutations of the 8 symbols for your operations such as this one:

 (1, 2, 3, 4, 5, 6, 7, 8,
  7, 6, 5, 4, 3, 2, 1, 3,
  1, 5, 2, 7, 4, 8, 6, 8,
  4, 7, 2, 5, 1, 6, 3, 8,
  5, 7, 5, 8, 3, 6, 1, 4,
  2, 4, 6, 2, 8, 1, 7, 3,
  5, 3, 7, 1, 8, 2, 6, 4, 1}

You can think of such a sequence as a minimal string in base 8 containing all 2-digits combinations.

ogerard
  • 1,583
  • I don't understand enough of Latin squares to be sure, but if I understand "circular" as "wrapping around from the last column to the first" (i.e. the same way as your comment on my original question), than I don't think that the Bruin method provides circular row-complete Latin squares. Looking at the example, $(5,1)$ appears to occur twice: "regularly" as $(a_{3,4},a_{3,5})$ and "circular" as $(a_{1,8},a_{1,1})$. Is there something that I am missing? – hcc23 Oct 28 '14 at 21:27
  • No you don't miss anything. You spotted a mistake in my terminology. I should have said cyclic (I will edit it), because in the Williams construction described on the H. Bruin page, this is the same array of differences from one column to the next. In fact, this property might be considered a disadvantage if there is an interaction between the properties of your operations and this sequence of difference, making this series of experimental tests not "mixed" or "unbiased" enough. – ogerard Oct 28 '14 at 21:43
  • @hcc23 : I am also interested by your opinion on my sequential solution to your experimental problem. – ogerard Oct 28 '14 at 21:45