Generalized silver matrix (related to defining number) - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T13:53:05Z http://mathoverflow.net/feeds/question/88255 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/88255/generalized-silver-matrix-related-to-defining-number Generalized silver matrix (related to defining number) mathlove1357 2012-02-12T03:03:41Z 2012-05-09T14:59:47Z <p>Let $S={1,2,\dots,m+n-1}$.</p> <p>An $m\times n$ matrix($\in S^{m\times n}$) is called silver matrix if</p> <p>(a) There is no same numbers in the row or column. (like latin square)</p> <p>(b) {$i$ th row}$\cup${$i$ th column}=S for all $1\leq i\leq min(m,n)$</p> <p>Does silver matrix exist for all $m\neq n$ ?</p> <p>If this conjecture is true, $d(K_m\times K_n, m+n-1) = mn-min(m,n)$ ($m\neq n$)</p> <p>($d$ is defining number, $\times$ is cartesian product)</p> http://mathoverflow.net/questions/88255/generalized-silver-matrix-related-to-defining-number/96449#96449 Answer by Gjergji Zaimi for Generalized silver matrix (related to defining number) Gjergji Zaimi 2012-05-09T13:29:00Z 2012-05-09T14:59:47Z <p>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.</p> <p>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.</p> <p>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.</p>