Problem 1491

4. (a) Suppose that an $n \times n$ coveralls matrix $A$ exists for some $n>1$. Let $x \in\{1,2, \ldots, 2 n-1\}$ be a fixed number that does not appear on the fixed diagonal of $A$. Such an element must exist, since the diagonal can contain at most $n$ different numbers. Let us call the union of the $i$ th row and the $i$ th column the $i$ th cross. There are $n$ crosses, and each of them contains exactly one $x$. On the other hand, each entry $x$ of $A$ is contained in exactly two crosses. Hence $n$ must be even. However, 1997 is an odd number; hence no coveralls matrix exists for $n=1997$. (b) For $n=2, A_{2}=\left[\begin{array}{ll}1 & 2 \\ 3 & 1\end{array}\right]$ is a coveralls matrix. For $n=4$, one such matrix is, for example,
$$A_{4}=\left[\begin{array}{llll} 1 & 2 & 5 & 6 \\ 3 & 1 & 7 & 5 \\ 4 & 6 & 1 & 2 \\ 7 & 4 & 3 & 1 \end{array}\right]$$
This construction can be generalized. Suppose that we are given an $n \times n$ coveralls matrix $A_{n}$. Let $B_{n}$ be the matrix obtained from $A_{n}$ by adding $2 n$ to each entry, and $C_{n}$ the matrix obtained from $B_{n}$ by replacing each diagonal entry (equal to $2 n+1$ by induction) with $2 n$. Then the matrix
$$A_{2 n}=\left[\begin{array}{ll} A_{n} & B_{n} \\ C_{n} & A_{n} \end{array}\right]$$
is coveralls. To show this, suppose that $i \leq n$ (the case $i>n$ is similar). The $i$ th cross is composed of the $i$ th cross of $A_{n}$, the $i$ th row of $B_{n}$, and the $i$ th column of $C_{n}$. The $i$ th cross of $A_{i}$ covers $1,2, \ldots, 2 n-1$. The $i$ th row of $B_{n}$ covers all numbers of the form $2 n+j$, where $j$ is covered by the $i$ th row of $A_{n}$ (including $j=1$). Similarly, the $i$ th column of $C_{n}$ covers $2 n$ and all numbers of the form $2 n+k$, where $k>1$ is covered by the $i$ th column of $A_{n}$. Thus we see that all numbers are accounted for in the $i$ th cross of $A_{2 n}$, and hence $A_{2 n}$ is a desired coveralls matrix. It follows that we can find a coveralls matrix whenever $n$ is a power of 2. Second solution for part $b$. We construct a coveralls matrix explicitly for $n=2^{k}$. We consider the coordinates/cells of the matrix elements modulo $n$ throughout the solution. We define the $i$-diagonal $(0 \leq i < n)$ into cycles of length larger than 1. Due to the diagonal translational symmetry (modulo $n$), all the cycles within a given $i$-diagonal must be of equal length and thus of an even length, since $n=2^{k}$. The construction of a coveralls matrix is now obvious. We select a number, say 1, to place on all the cells of the 0-diagonal. We pair up the remaining numbers and assign each pair to an $i$-diagonal, say $(2 i, 2 i+1)$. Going along each cycle within the $i$-diagonal we alternately assign values of $2 i$ and $2 i+1$. Since the cycle has an even length, a cell will be related only to a cell of a different number, and hence each cross will contain both $2 i$ and $2 i+1$.