# Smallest possible rank of an $n×n$ matrix that has zeros along the main diagonal and strictly positive real numbers off the main diagonal

A problem in IMC 2012 in which i'm interested but I have no answer. Can you help me? Many thanks.

Problem : Let $n$ be a fixed positive integer. Determine the smallest possible rank of an $n\times n$ matrix that has zeros along the main diagonal and strictly positive real numbers off the main diagonal.

-
It has been discussed here, with a nice solution. –  Davide Giraudo Aug 1 '12 at 16:38
Thank Davide Giraudo. I'll see the solution. I would like to thank also Xoff and joriki for your participation :-). –  lottakaka Aug 1 '12 at 21:58

The problem has been solved at the website Art Of Problem Solving. The minimal rank is $2$ for two times two matrices, and $3$ for $n\geq 3$. A matrix of minimal rank is given: its entries are $a_{i,j}:=(i-j)^2$.

-
This solution is nice ! –  Xoff Aug 2 '12 at 13:32

This is not an answer, just an example, but there are no such matrix with rank $<n$ for $n<4$. For $n=4$, you have a simple matrix of rank 3 :

$$\left(\begin{array}{cccc}0 & 2 & 1 & 1 \\ 2 & 0 & 1 & 1\\1 & 1 & 0 & 2 \\ 1 & 1 & 2 & 0 \end{array}\right)$$

So an upper bound is $\lceil\frac{3n}{4}\rceil$... and even $1+\lceil\frac{n}{2}\rceil$ (Joriki)

-
Thank you but I remarked this ;-). Indeed, we can find many of (symmetric) matrices like that. –  lottakaka Aug 1 '12 at 14:43
do you have an example of matrix of rank 3 for $n=5$ ? –  Xoff Aug 1 '12 at 14:46
No, I have just an other example for $n=4$ :(. –  lottakaka Aug 1 '12 at 15:15
What do you mean "upper bound"? $\text{rank} \leq \lceil\frac{3n}{4}\rceil$? –  lottakaka Aug 1 '12 at 15:17
yes, (but I wonder if the solution is 3). To obtain the bound, you can make a $4n\times 4n$ matrices : On the diagonal, put copies of this matrix, and 1 everywhere else. –  Xoff Aug 1 '12 at 15:20
show 1 more comment