6
$\begingroup$

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.

  • 0
    Thank Davide Giraudo. I'll see the solution. I would like to thank also Xoff and joriki for your participation :-).2012-08-01

2 Answers 2

3

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

  • 0
    This solution is nice !2012-08-02
0

This is not an answer, just an example, but there are no such matrix with rank $ 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)

  • 0
    Using the \pmatrix{0&2\\2&0} block on the diagonal and $1$s everywhere else, you can get $\lceil n/2\rceil+1$.2012-08-01