The Intersections of Commutative Latin Squares

Abstract

A Latin square of order $n$ is an $n\times n$ array such that each of the integers $1,2,\dots ,n$ (or any set of $n$ distinct symbols) occurs exactly once in each row and each column. A Latin square $L=[l_{i,j}]$ is said to be \underline{commutative} provided that $l_{i,j}=l_{j,i}$ for all $i$ and $j$. Two Latin squares, $L=[l_{i,j}]$ and $M=[m_{i,j}]$, are said to have \underline{intersection} $k$ if there are exactly $k$ cells $(i,j)$ such that $l_{i,j}=m_{i,j}$.

Let $I[n]=\{0,1,2,\dots ,n^2-9,n^2-8,n^2-7,n^2-6,n^2\}$, $H[n]=I[n]\cup \{n^2-7,n^2-4\}$, and $J[n]$ be the set of all integers $k$ such that there exists a pair of commutative Latin squares of order $n\$whichhaveintersection\text{(}k$. In this paper, we prove that $J[n]=I[n]$ for each odd $n\ge 7$, $J[n]=H[n]$ for each even $n\ge 6$, and give a list of $J[n]$ for $n\le 5$. This totally solves the intersection problem of two commutative Latin squares.