Idempotent and commutative Latin squares of even order.

890 Views Asked by At

Definition: A Latin square is said to be idempotent iff $\forall i=1,\cdots, m,[(i,i)=i]$

Definition: A Latin square is said to be commutative iff $\forall i,j((i,j)=(j,i))$ such that $1\leq i,j\leq m$ and $(i,j)$ denotes the entry at the $i$th row and $j$th column.

The order of a Latin square refers to the number of distinct symbols found within a Latin square.

Proposition: Show that there exist no idempotent and commutative Latin squares of even order.

Proof Attempt: Consider the last entry of the first row of $2n \times 2n$ array such that $n\in\Bbb{N}$. For the sake of contradiction, suppose this an array of an idempotent and commutative Latin square. Observe that $\forall i(1\leq 1\leq 2n)$, the $(i,i)$ entry has entry $i$, due to idempotence. Since it's commutative $\forall k\in\Bbb{N}((i+k, i-k)=(i-k, i+k))$. Note that $(i-(i-1), i+(i-1))=(1, 2i-1)$ and $2i-1$ is odd. Thus, any $i=1,\cdots,n$ is in some entry $(1, 2i-1)$. Moreover, we assert that any $i=n+1,\cdots 2n$ cannot be in the entry $(1,2n)$. Keep in mind, $\forall i\forall k((i,i)=i=(i+k, i-k)=(i-k, i+k))$ due to commutativity and idempotence of our latin square. We now consider $i$ such that $n+1\leq i\leq 2n$. Note $(n+j,n+j)$ is at the $(n+j)th$ column of the array; $1\leq j\leq n$. Since $(n+j)-k=1 \Leftrightarrow k=(n+j)-1$ and $(n+j)+(n+j)-1=2n+(2j-1)$ such that $1\leq j\leq n$, then we have $1 \leq 2j-1 \leq 2n-1$ which further imply that $\forall k(n+j=(n+j-k, n+j+k)\neq (1,2n))$ where $k=(n+j)-1$ and $1\leq j\leq n$. Thus, $(1, 2n)\neq n+1, \cdots, 2n$. Since $1,\cdots, n$ are odd-index entries of row 1 of the array, then none of the symbols $1,2,3,\cdots, 2n$ can be in entry $(1,2n)$. Therefore, the array with its assumed restrictions can never be completed to be a Latin square; the proposition holds.

1

There are 1 best solutions below

0
On BEST ANSWER

There is an easier proof:

As the square is commutative, each number must occur an equal number of times above the diagonal and below the diagonal. The total number of occurances of any number in these areas will therefore be even. For a square of even order, every number must occur an even number of times. Therefore any number on the diagonal (the only remaining area) must also occur an even number of times. Therefore the square cannot be idempotent.