1
$\begingroup$

We define a "latin square" to be an $n \times n$ grid filled with the numbers $1$ through $n$ such that every number appears in every row and every column exactly once. I need to prove that in any $n \times n$ symmetric (with respect to the main diagonal) Latin square where $n$ is odd, every number 1, 2, 3, . . . , n must appear at least once on the main diagonal.

What I've tried: I have attempted a proof by contradiction, assuming that there exists some number $i$ from between $1$ and $n$ which does not exist on the diagonal. Then I attempt to show that for the first element along the main diagonal $i$ must somewhere (call this place index $k$) in the second to $nth$ place in the first row and first column respectively. The second element of the diagonal must be in the third though $(k-1)th$ or $(k+1)th$ through $nth$ place. The $jth$ diagonal element will have $i$ in the places other than those taken by $j-1$ other $i$'s. And finally for the $nth$ diagonal element, $i$ can't be in $n-1$ places, but if $i$ isn't in the diagonal, then $i$ must be in one of those places. Therefore we have reached a contradiction.

However I did not utilize $n$ being odd or the symmetric nature of the square, so I believe I am making some mistake. Any help would be much appreciated.

$\endgroup$
  • $\begingroup$ What happened when you tried out your proof on the $2\times2$ Latin square? $\endgroup$ – bof Jan 25 '18 at 18:25
  • $\begingroup$ @bof I agree that it has to do with the fact that the only way to place $i$ and not have it be on the major diagonal is to have $i$'s along the minor diagonal, which is not possible to do without intersecting the major diagonal in an odd matrix. How do I show that the only way to satisfy the requested condition is to place $i$'s along the minor diagonal? $\endgroup$ – Raton Jan 25 '18 at 21:21
2
$\begingroup$

In order for the Latin Square to be symmetric about the main diagonal, each number must occur an equal number of times above the diagonal and below the diagonal. This is not possible when $n$ is odd, unless each number has an odd number of occurances on the diagonal itself. I.e., each number must have at least 1 occurance on the main diagonal.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.