Given an integer $n\ge 1$, what is the largest eigenvalue $\lambda\_n$ of the matrix $M\_n=(m\_{ij})\_{1\le i,j\le n}$ with the elements $m\_{ij}$ equal to $0$ or $1$ according to whether $ij>n$ or $ij\le n$?


It is not difficult to show that
 $$ c\sqrt n \le \lambda\_n \le C\sqrt{n\log n} $$
for appropriate positive absolute constants $c$ and $C$, and numerical
computations seem to suggest that the truth may lie somewhere in between.




---


To make the problem a little bit "more visual", the first four matrices in question are as follows:



> 
> $M\_1=\begin{pmatrix} 1 \end{pmatrix}$ $\quad$
>  $M\_2=\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$ $\quad$
>  $M\_3=\begin{pmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{pmatrix}$ $\quad$
>  $M\_4=\begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{pmatrix}$
> 
> 
> 



The largest eigenvalue of a "hyperbolic" matrix
I think, $C\sqrt{n}$ is an upper bound aswell. Take vector $x=(x\_1,\dots,x\_n)$ with $x\_j=j^{-1/2}$. Then $(Ax)\_i$ behaves like $C\sqrt{n/i}=C\sqrt{n}x\_i$. But we know that if $(Ax)\_i\leq C x\_i$ for vector $x$ with positive coordinates, then the largest eigenvalue of $A$ does not exceed $C$ (kind of Perron-Frobenius).


(This answer is very ugly displayed, I do not know why).


