The largest eigenvalue of a "hyperbolic" matrix 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}$

 A: 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).
A: I can get an upper bound of $C \sqrt{n} \sqrt[4]{\log n}$ and it should be possible to push this technique to get $C_l \sqrt{n} \sqrt[2l]{\log n}$ for any $l$, although Fedor's approach might be a lot simpler.
First we observe that for any positive integer $l$ we have $\text{tr } M_n^{2l} = \sum_{i=1}^{n} \lambda_i^{2l} \ge \lambda_n^{2l}$ since the eigenvalues are real, where $\lambda_1, ... \lambda_n$ are the eigenvalues of $M_n$.  For $l = 1$ it's not hard to see that $\text{tr } M_n^2$ is the number of ordered pairs $(i, j)$ such that $ij \le n$, or $\sum_{i \le n} \lfloor \frac{n}{i} \rfloor = n \log n + O(n)$, which in particular certainly gives an upper bound of the form $C \sqrt{n \log n}$.
Now take $l = 2$.  Then $\text{tr } M_n^4$ is the number of quadruplets $(v_1, v_2, v_3, v_4)$ such that $v_i v_{i+1} \le n$ in cyclic order.  We distinguish three cases.
Case:  $v_1 = k > v_3$.  Then $v_2, v_4$ can be any positive integers less than or equal to $\left\lfloor \frac{n}{k} \right\rfloor$ and $v_3$ can be any positive integer less than $k$, which gives 
$$\sum_{k \le n} \left\lfloor \frac{n}{k} \right\rfloor^2 (k-1) = n^2 \log n + O(n^2)$$
quadruplets.
Case:  $v_1 = k = v_3$.  There are $O(n^2)$ possibilities here.
Case:  $v_1 = k < v_3$.  Same number as the first case by symmetry.
This gives $\text{tr } M_n^4 = 2n^2 \log n + O(n^2)$.  Again, I think this argument can be pushed further.
Edit:  We can argue similarly for $l = 3$.  We are now counting sextuplets $(v_1, ... v_6)$.  The triplet $(v_1, v_3, v_5)$ can be in one of six possible orders (discounting the cases where some of them are equal, which I think is $O(n^3)$), all of which can be reached from each other by cyclic permutation and reflection, so WLOG $v_1 \ge v_3 \ge v_5$.  Then $v_2, v_6$ can be any positive integers less than or equal to $\lfloor \frac{n}{v_1} \rfloor$ while $v_4$ can be any positive integer less than or equal to $\lfloor \frac{n}{v_3} \rfloor$ and $v_5$ can be any positive integer less than or equal to $v_3$, which gives
$$\sum_{n \ge v_1 \ge v_3} \left\lfloor \frac{n}{v_1} \right\rfloor^2 \left\lfloor \frac{n}{v_3} \right\rfloor v_3 = n^3 \sum_{n \ge v_1 \ge v_3} \frac{1}{v_1^2} + O(n^3) = n^3 \log n + O(n^3)$$
sextuplets.  Our WLOG assumption overcounts by a factor of $6$ (up to an error of size $O(n^3)$), which gives $\text{tr } M_n^6 = 6n^3 \log n + O(n^3)$ and an upper bound of $C \sqrt{n} \sqrt[6]{\log n}$.  
A: What is the corresponding graph to this matrix?
