Looking for a special case of latin squares

February 1, 2007 4:29 PM

Mathfilter: Is there a name for the special case of the latin square in which each possible pair of adjacent elements appears exactly once in all the rows?

Sorry my description is so convoluted. Here's an example latin square that displays this property:

1  2  3  4
2  4  1  3
3  1  4  2
4  3  2  1

Are there any proofs about the existance or non-existance of such squares for other sizes? Better yet, is there an algorithm for generating them?

posted by Eamon to science & nature (8 comments total)

Do you mean like this for order-6?

123456
246135
362514
415263
531642
654321

If so, I believe its a certain type of matrix but I can't recall the name. I used a pretty simple rule for building that one which should generalize to NxN.

Here's a hint: If integer x is followed by y in one row, it will be followed by y+1 in the row below it.
posted by vacapinta at 5:07 PM on February 1, 2007

None exist for size 3: If "a b c" are the elements in row 1, then "a c" cannot be adjacent in any row because then "a" would be in column 1 or "c" would be in column 3.
posted by mbrubeck at 5:09 PM on February 1, 2007

vacapinta's rule looks like it will work for all even n, but no odd n (at least not without modification).
posted by mbrubeck at 5:11 PM on February 1, 2007

I wrote a program that searches all the possible squares of a given size. It's a very brute-force approach. It gives results for 4 and 6 in short order, quickly gives no results for 3 or 5, and I'm still waiting on 7 and 8. eamon.py
posted by jepler at 5:54 PM on February 1, 2007

An easier way to describe vacapinta's rule (I think) is the following appealing formulation: to make an n x n square with the desired property, place in position (ij) the result of reducing ij modulo (n+1). Without thinking about it too hard, I guess this should work whenever n+1 is prime, i.e. this handles n=4 (OP's case), n=6 (vacapinta's case), n=10, etc., but not n=8.
posted by escabeche at 8:28 PM on February 1, 2007

Indeed, my implementation of vacapinta's method fails to produce an 8x8 square and a 14x14 square. It quickly produces a 98x98 board, but the 996x996 board takes a bit of time. eamon2.py

escabeche's method works, though I have to change my row and column numbers to be 1-based rather than 0-based. It quickly generates a 996x996 board, with the "verify" step taking the majority of the time. eamon3.py.
posted by jepler at 7:17 AM on February 2, 2007

I meant a 96x96 board, not 98x98.
posted by jepler at 7:17 AM on February 2, 2007

Thanks so much, everybody! I think it would be relatively easy to prove that such a square exists of size n x n iff n+1 is prime now. For my specific application (experimental design), I can focus on an algorithm that minimizes the reappearance of pairs when this isn't the case.
posted by Eamon at 9:30 AM on February 2, 2007