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.

  • 3
    It has been discussed [here](http://www.artofproblemsolving.com/Forum/viewtopic.php?f=79&t=491031]), with a nice solution.2012-08-01
  • 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 $

$$ \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
    Thank you but I remarked this ;-). Indeed, we can find many of (symmetric) matrices like that.2012-08-01
  • 0
    do you have an example of matrix of rank 3 for $n=5$ ?2012-08-01
  • 0
    No, I have just an other example for $n=4$ :(.2012-08-01
  • 0
    What do you mean "upper bound"? $\text{rank} \leq \lceil\frac{3n}{4}\rceil$?2012-08-01
  • 1
    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.2012-08-01
  • 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