Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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)

share|improve this question
    
What is the smallest value of $\max(m,n)$ for which you don't know the answer? –  Yemon Choi Feb 12 '12 at 8:03
    
I want to prove this conjecture for all $m\neq n$. –  mathlove1357 Feb 12 '12 at 8:12
    
If you want to prove it for all such m and n, then presumably you can prove it for some particular values of m and n. Which is the smallest pair for which you do not yet know the answer? –  Yemon Choi Feb 12 '12 at 8:37
    
(7,6). It looks possible, but I don't know the answer. –  mathlove1357 Feb 12 '12 at 11:25
1  
Looks like the problem appears here: ams.org/notices/199709/people.pdf Still no idea what is the defining number so more elucidation is necessary. –  Felix Goldberg May 9 '12 at 9:10
show 1 more comment

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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