Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let's take any natural number $n>0$. Let $k$ be the smallest natural number greater than $n/2.$ Now let $A$ be any $n$-element set, and let $M$ be a $k\times k$ matrix over $A$. Suppose that for any row $r$ of $M$, the elements in $r$ are pairwise different. Suppose the same about every column $c$ of $M$. I would like to know whether this implies that every element of $A$ can be found in the matrix $M$.

This is something that I've extracted from a different problem I'm thinking about. It looks true to me, but I'm not good at combinatorics, and I can't think of a way to prove this.

I will welcome both hints and full solutions.

Thank you very much.

share|improve this question
    
This is wrong. Pick $n=2$, then... –  Giovanni De Gaetano Jan 14 '13 at 12:07
    
@Giovanni Sorry, I've defined $k$ incorrectly. It should be the smallest natural number greater than $n/2$. I'll edit the question. –  Bartek Jan 14 '13 at 12:15
    
No problems, but it is wrong as well. Consider $n=3$, then $k=2$. Let $A=\{a,b,c\}$, and consider the $2\times 2$-matrix with $a$ in both the places in the diagonal and $b$ otherwise. This respect your condition but you cannot find $c$ in it. Perhaps we can try to find the smallest $k(n)$ such that your condition on rows and columns implies that you can find all the elements of $A$... ...but the answer would be $k(n)=n$ always, can you prove it? –  Giovanni De Gaetano Jan 14 '13 at 12:47
    
@Giovanni Thank you very much. I will need to think about this. There's something that's bothering me here, but I can't quite put my finger on it. –  Bartek Jan 14 '13 at 12:55
    
@Giovanni Yes, I think I can prove it. We can notice that there always is such a matrix for $k=n$. We can just cycle a fixed permutation of $A$ throughout the rows. It's now enough to prove that it doesn't work for $k=n-1$ because any smaller matrix sits inside a $(n-1)\times(n-1)$ matrix. So I need to prove that there is such an $(n-1)\times(n-1)$ matrix over $A$ lacking some element of $A$. But there is such a matrix because we know there is such an $(n-1)\times(n-1)$ matrix over any $n-1$-element set. So we can take $A\setminus\{a\}$ for some $a\in A.$ Is this correct? –  Bartek Jan 14 '13 at 14:26
show 3 more comments

1 Answer

up vote 2 down vote accepted

In the answer I'm summarizing the discussion above.

The statement of the OP is unfortunately wrong, as a counterexample we can consider $A=\{a,b,c\}$, so $n=3$ and $k=2$. Then the matrix: $$\begin{pmatrix} a&b \\ b&a \end{pmatrix}$$ is a counterexample to the statement above.

Fixing $A=\{1,...,n\}$, a follow up question is to determine $k(n)$ such that any $k(n) \times k(n)$ matrix fulfilling the condition of the question on rows and columns contains all the elements of $A$.

In this case $k(n)=n$. To prove it it is enough to observe that we can construct such an $(n-1)\times (n-1)$ matrix using only $(n-1)$ elements. An example is built as following: $$\begin{pmatrix} 1 & n-1 & \cdots & 2 \\ 2 & 1 & \cdots & 3 \\ \vdots & \vdots & \ddots & \vdots \\ n-1 & n-2 & \cdots & 1 \end{pmatrix}$$

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.