Question

Let $S={1,2,\dots,m+n-1}$.

An $m\times n$ matrix($\in S^{m\times n}$) is called silver matrix if

(a) There is no same numbers in the row or column. (like latin square)

(b) {$i$ th row}$\cup${$i$ th column}=S for all $1\leq i\leq min(m,n)$

Does silver matrix exist for all $m\neq n$ ?

If this conjecture is true, $d(K_m\times K_n, m+n-1) = mn-min(m,n)$ ($m\neq n$)

($d$ is defining number, $\times$ is cartesian product)

Answer 1

Yes. Silver matrices exist for all $n=m$ when $n$ is even and for all $n\neq m$. Notice that the problem for square matrices is essentially problem 4 in the 1997 International Math Olympiad.

One basic construction one needs is a symmetric latin square. These exist for all orders and are essentially equivalent to edge colorings of complete graphs. A symmetric latin square of even order can be taken to have a constant diagonal while a symmetric latin square of odd order must have all elements appearing exactly once on the diagonal.

Returning to your problem: Paste together the lower triangular part of a $2a\times 2a$ symmetric latin square and the upper triangular part of a $2b\times 2b$ symmetric latin square whose alphabets have only one letter in common, the one on the diagonal. Do this by identifying the last $c$ diagonal elements of the first with the first $c$ diagonal elements of the second. Where $c$ is some number with $c\le 2\min(a,b)$. This gives you a $c\times(2a+2b-c)$ silver matrix (take the obvious $c$ rows and rearrange the columns). So you get a construction for all $m,n$ both even or both odd but unequal. The case with $m-n$ odd can be dealt with similarly by playing around with symmetric latin squares of odd order.