Maximum number of distinct elements in matrix of size $p \times p$, given for any row/column, there are $\le p-1$ distinct elements.

Question

Prove that for any given prime $p \ge 5$, there doesn't exist any matrix of size $p\times p : [x_{i,j} | i,j\in \mathbb{Z}, 0\le i,j \le p-1]$, such that

• $\forall i_0, \exists j_1, j_2 (x_{i_0,j_1} = x_{i_0,j_2})$, i.e., for any row $i_0$, there are $\le p-1$ distinct elements in it
• $\forall j_0, \exists i_1, i_2 (x_{i_1,j_0} = x_{i_2,j_0})$, i.e., for any column $j_0$, there are $\le p-1$ distinct elements in it
• $\exists\mathbb{S} \text{ s.t.} \left\vert \mathbb{S}=\{y \,\,| \,\,\exists i, j (y = x_{i,j})\} \right\vert > (p-1)^2$, i.e., there are $> (p-1)^2$ distinct elements in the matrix

---

This is to complete the proof in my answer here, I was able to prove the cases for large $n$ and some other cases, but some cases are still left to prove. The above problem seems to be the base case for all the other cases. I don't believe this counts as a duplicate, but if it does I can remove it.

I have used contradiction to show there cannot exist a set with $\ge (p-1)^2 + \frac{p-1}{2}$ distinct elements in that answer, but I have not used the fact that $p$ is prime anywhere; and checking for some small examples, it seems really important that $p$ is prime, but I cannot think on how to use this.

Answer 1

Call a square matrix "qualifying" if no row or column has all distinct entries.

Fix an integer $n\ge 2$, and let $M$ be an $n{\times}n$ matrix such that the $(n-1)^2$ entries $M[i,j]$ entries with $1\le i,j\le n-1$ are all distinct, and also

• $M[i,n]=M[i,n-1]\;$for $1\le i\le n-1$.$\\[4pt]$
• $M[n,j]=M[n-1,j]\;$for $1\le j\le n-1$.$\\[4pt]$
• $M[n,n]=M[n-1,n-1]$, hence also $M[n.n]=M[n,n-1]$ and $M[n,n]=M[n-1,n]$.

Then $M$ is a qualifying $n{\times}n$ matrix with exactly $(n-1)^2$ distinct entries.

But for $n\ge 4$ we can do better . . .

Fix an integer $n\ge 4$, and let $M$ be an $n{\times}n$ matrix expressed in block form as $$ M= \begin{bmatrix} A&C\\ D&B\\ \end{bmatrix} $$ where

• $A$ is a $2{\times}2$ matrix with all equal entries.$\\[4pt]$
• $B$ is a qualifying $(n-2){\times}(n-2)$ matrix with exactly $(n-3)^2$ distinct entries.$\\[4pt]$
• $C$ is a $2{\times}(n-2)$ matrix with all distinct entries.$\\[4pt]$
• $D$ is an $(n-2){\times}2$ matrix with all distinct entries.

and such that none of $A,B,C,D$ has any entries in common with any of the others.

Since the matrices $A,B$ are qualifying, it follows that $M$ is qualifying.

Summing the number of distinct entries for $A,B,C,D$ we get $$ 1+(n-3)^2+2(n-2)+2(n-2) = n^2-2n+2 = (n-1)^2+1 $$ hence $M$ is a qualifying $n{\times}n$ matrix with exactly $(n-1)^2+1$ distinct entries.

As an example, for $n=5$, the matrix $$ M= \begin{bmatrix} 0&0&1&2&3\\ 0&0&4&5&6\\ 7&8&13&!4&14\\ 9&10&15&16&16\\ 11&12&15&16&16\\ \end{bmatrix} $$ is a qualifying $5{\times}5$ matrix with exactly$\,17=(5-1)^2+1\;$distinct entries.