# The lower bound on the number of numbers needed to fill a matrix in a special way.

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.

-
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

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}$$