Transversals of Latin Squares

Question

According to this thesis, page $28$, the following Latin Square has $3$ $0$-s transversals: $$\begin{bmatrix}1 & 2 & 3 & 4 & 5\\ 2 & 4 & 1 & 5 & 3\\ 3 & 5 & 4 & 2 & 1\\ 4 & 1 & 5 & 3 & 2\\5 & 3 & 2 & 1 & 4\end{bmatrix} \implies \begin{bmatrix}1 & & & &\\ & & & 5 & \\ & & 4 & & \\ & & & & 2\\ & 3\end{bmatrix}, \begin{bmatrix}& & & 4 &\\2 & & & &\\ & & & & 1 \\ & & 5 & &\\ & 3\end{bmatrix}, \begin{bmatrix}& & & &5\\& & 1 & &\\ & & & 2 &\\4 & & & &\\& 3\end{bmatrix}.$$ The definition of a $0$-s transversal for a Latin square of order $n$ is

a set of $n$ ordered triples such that the first and second entries are the rows and columns respectively in which the values $1,\ldots,n$ occur exactly once and the third entry of the triple is the value, of which there are $n$ distinct values.

Basically, we need to visit each row and column only once and we must have $5$ distinct symbols at the end. I can represent each transversal as $$t_1 = \{(1,1,1),(2,4,5),(3,3,4),(4,5,2),(5,2,3)\}$$ $$t_2 = \{(1,4,4),(2,1,2),(3,5,1),(4,3,5),(5,2,3)\}$$ $$t_3 = \{(1,5,5),(2,3,1),(3,4,2),(4,1,4),(5,2,3)\}$$ So why are these the only three? How do I know there are only three of them?

Answer 1

I don't think there's any slick way to determine that this Latin square has exactly $3$ transversals---we just count them. E.g., here's some GAP code:

L:=[[1,2,3,4,5],[2,4,1,5,3],[3,5,4,2,1],[4,1,5,3,2],[5,3,2,1,4]];;

ExtendPartialTransversal:=function(T)
  local i,j,TNew;

  # we try to add entry (i,j,L[i][j]) to T without clashing  

  # looking at row i
  i:=Size(T)+1;

  # looking at column j
  for j in [1..5] do

    # column already used
    if(ForAny([1..i-1],k->T[k][2]=j)) then continue; fi;

    # symbol already used
    if(ForAny([1..i-1],k->T[k][3]=L[i][j])) then continue; fi;

    # add to partial transversal
    TNew:=Concatenation(T,[[i,j,L[i][j]]]);

    # if transversal complete, then print, otherwise extend
    if(Size(TNew)=5) then
      Print(TNew,"\n");
    else
      ExtendPartialTransversal(TNew);
    fi;

  od;
end;;

# start with the empty partial transversal
ExtendPartialTransversal([]);

which returns the three transversals:

[ [ 1, 1, 1 ], [ 2, 4, 5 ], [ 3, 3, 4 ], [ 4, 5, 2 ], [ 5, 2, 3 ] ]
[ [ 1, 4, 4 ], [ 2, 1, 2 ], [ 3, 5, 1 ], [ 4, 3, 5 ], [ 5, 2, 3 ] ]
[ [ 1, 5, 5 ], [ 2, 3, 1 ], [ 3, 4, 2 ], [ 4, 1, 4 ], [ 5, 2, 3 ] ]

and shows there's no others by exhaustive search.

Answer 2

A latin square is represented as $t_i=(r,c,s)$ which means that r represents row of the latin square, c represents column of the latin square and s is the number whose location is $row=r\;\;and\;\;column=c$.

Answer 3

"I'm working with a larger latin squares (specifically $10\times10$). In my situation, we already know the position of some transversals. I want to see if, of all the completions I have found, one of them could be decomposed into transversals."

If you find all the transversals of the Latin square, then it is easy to find disjoint transversals.

Example

This diagonal Latin square

0 2 4 7 8 9 5 6 3 1
5 1 9 6 3 2 4 8 0 7
6 7 2 9 1 0 8 3 5 4
9 4 0 3 5 7 2 1 6 8
7 0 3 8 4 6 9 2 1 5
2 8 6 0 7 5 1 4 9 3
1 5 8 4 2 3 6 9 7 0
4 3 5 1 9 8 0 7 2 6
3 9 1 5 6 4 7 0 8 2
8 6 7 2 0 1 3 5 4 9

has $104$ diagonal transversals.

Among them there are $8$ sets of $10$ non-intersecting transversals, which gives $8$ orthogonal diagonal Latin squares for a given diagonal Latin square

#1

 0 1 2 3 4 5 6 7 8 9
 9 7 4 1 3 0 8 5 2 6
 2 5 8 9 6 7 0 1 4 3
 8 4 3 6 2 9 7 0 5 1
 7 6 9 8 5 4 1 2 3 0
 3 2 6 4 8 1 5 9 0 7
 4 8 7 0 9 2 3 6 1 5
 1 0 5 2 7 3 9 4 6 8
 5 3 1 7 0 6 2 8 9 4
 6 9 0 5 1 8 4 3 7 2

#2
 0 1 2 3 4 5 6 7 8 9
 9 7 4 1 3 0 8 5 2 6
 2 5 8 9 6 7 0 1 4 3
 8 4 3 6 2 9 7 0 5 1
 7 6 9 8 5 4 1 2 3 0
 3 2 6 5 8 1 4 9 0 7
 5 8 7 0 9 2 3 6 1 4
 1 0 5 2 7 3 9 4 6 8
 4 3 1 7 0 6 2 8 9 5
 6 9 0 4 1 8 5 3 7 2

#3
 0 1 2 3 4 5 6 7 8 9
 9 7 4 8 3 0 1 5 2 6
 2 5 8 9 6 7 0 1 4 3
 1 4 3 6 2 9 7 0 5 8
 7 6 9 1 5 4 8 2 3 0
 3 2 6 4 8 1 5 9 0 7
 4 8 7 0 9 2 3 6 1 5
 8 0 5 2 7 3 9 4 6 1
 5 3 1 7 0 6 2 8 9 4
 6 9 0 5 1 8 4 3 7 2

#4
 0 1 2 3 4 5 6 7 8 9
 9 7 4 8 3 0 1 5 2 6
 2 5 8 9 6 7 0 1 4 3
 1 4 3 6 2 9 7 0 5 8
 7 6 9 1 5 4 8 2 3 0
 3 2 6 5 8 1 4 9 0 7
 5 8 7 0 9 2 3 6 1 4
 8 0 5 2 7 3 9 4 6 1
 4 3 1 7 0 6 2 8 9 5
 6 9 0 4 1 8 5 3 7 2

#5
 0 1 2 3 4 5 6 7 8 9
 3 7 4 1 9 6 8 5 2 0
 6 5 8 9 2 3 0 1 4 7
 8 4 9 2 0 7 3 6 5 1
 9 6 7 8 5 4 1 0 3 2
 2 9 0 4 8 1 5 3 7 6
 4 8 3 6 7 0 9 2 1 5
 1 3 5 0 6 2 7 4 9 8
 5 0 1 7 3 9 2 8 6 4
 7 2 6 5 1 8 4 9 0 3

#6
 0 1 2 3 4 5 6 7 8 9
 3 7 4 1 9 6 8 5 2 0
 6 5 8 9 2 3 0 1 4 7
 8 4 9 2 0 7 3 6 5 1
 9 6 7 8 5 4 1 0 3 2
 2 9 0 5 8 1 4 3 7 6
 5 8 3 6 7 0 9 2 1 4
 1 3 5 0 6 2 7 4 9 8
 4 0 1 7 3 9 2 8 6 5
 7 2 6 4 1 8 5 9 0 3

#7
 0 1 2 3 4 5 6 7 8 9
 3 7 4 8 9 6 1 5 2 0
 6 5 8 9 2 3 0 1 4 7
 1 4 9 2 0 7 3 6 5 8
 9 6 7 1 5 4 8 0 3 2
 2 9 0 4 8 1 5 3 7 6
 4 8 3 6 7 0 9 2 1 5
 8 3 5 0 6 2 7 4 9 1
 5 0 1 7 3 9 2 8 6 4
 7 2 6 5 1 8 4 9 0 3

#8
 0 1 2 3 4 5 6 7 8 9
 3 7 4 8 9 6 1 5 2 0
 6 5 8 9 2 3 0 1 4 7
 1 4 9 2 0 7 3 6 5 8
 9 6 7 1 5 4 8 0 3 2
 2 9 0 5 8 1 4 3 7 6
 5 8 3 6 7 0 9 2 1 4
 8 3 5 0 6 2 7 4 9 1
 4 0 1 7 3 9 2 8 6 5
 7 2 6 4 1 8 5 9 0 3