Check my proof on Latin Squares

168 Views Asked by At

Define a set of $n - 1$ mutually orthogonal squares $A_1, \ldots, A_{n-1}$, where n is a prime number. If we set the element $(i, j)$ in square $A_h$ as $i + hj$ then the squares in the set are mutually orthogonal squares.

(1) each square is a Latin square

for fixed $j$, $i + hj$ takes the value of each of the $n$ integers $\pmod n$ as $i$ runs through $\{1,\ldots,n\}$.

similarly for fixed $i$, $hj$ takes all $n$ values for fixed $h$ and $j$ running through $\{1,\ldots,n\}$, because $h$ and $j$ are nonzero elements of the integers modulo $n$, and $n$ is prime.

(2) the squares are mutually orthogonal

let $a_{pq} = a_{rs}$ in $A_k$. then $p + kq = r + ks$.

in $A_m$,

$a_{pq} = p + mq$, $a_{rs} = r + ms$, so

$(p + kq) - (r + ks) = (p - r) + k(q - s) = ny$, where $y$ is an integer

suppose $a_{pq} = a_{rs}$ in $A_m$ also.

$(p - r) + m(q - s) = nz$, where z is an integer

then $ny - nz = (k - m)(q - s) = nw$, where $w$ is an integer

But $k, m < n$ and $q, s \le n$.

So $k - m < n$ and $q - s < n$ (because $q$ and $s$ are distinct), and the prime $n$ can divide neither.

Hence, $a_{pq}$ and $a_{rs}$ must be distinct in $A_m$.

1

There are 1 best solutions below

6
On

Essentially, your construction either skips some residues or it visits the same residue at the same $(i,j)$ for all $A_h$.

Suppose column $(i,-)$ of $A_h$ does not contain a residue $g:0\leq g<n$ mod $n$, but does contain $g+1$ at entry $(i,J)$. Then $(i-1,J)=i-1+hJ=g+1-1$ implies column $(i-1,-)$ does not contain the same set as column $(i,-)$, implies $A_h$ is not a Latin square. Likewise, $g-1$ being at $(i,J)$ implies $g$ is at $(i+1,J)$. Therefore $i+hj$ must visit every congruence class for $A_h$ to be a Latin square, therefore $j$ must visit every congruence class.

Likewise, if $j$ visits the same congruence class twice, so does $i+hJ=i+hL$ for two distinct $J, L$ and every column $(i,-)$, so that again $A_h$ is not a Latin square. Therefore $j$ must visit every residue mod $n$, for every $A_h$. Therefore $(i,J)_h=i+hJ \equiv_n i$ for some J in the index of $j$, and since the index of $j, i$ is independent of $h$, $(i,J)_h=(i,J)_k$ for all $A_h, A_k$. Therefore $A_h, A_k$ cannot be mutually orthogonal.