# 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}$

-
What's your motivation if I may ask? – Nikita Sidorov Oct 22 '10 at 16:51
It is motivated by a problem in algebraic graph theory. – Seva Oct 22 '10 at 18:17
You're right. I wrongly supposed that so many rows are identical. I'll think again. – Denis Serre Oct 23 '10 at 6:31
Some simple calculations show that the trace of the matrix is $\lfloor \sqrt{n} \rfloor$, and the rank is $\lfloor \sqrt{4n+1}\rfloor-1$---but this does not seem to be immediately useful... – Suvrit Oct 23 '10 at 12:35

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

-
Fedor, can you provide a reference for that statement? – Qiaochu Yuan Oct 23 '10 at 14:09
I don't know a reference, but it's really easy to prove. Perron-Frobenius tells you that there's a unique positive eigenvector $v_+$, and the corresponding eigenvalue $\lambda$ is maximal. Furthermore, for any positive vector $v'$, $A^k v'$ tends to $c\lambda^k v_+$. Now apply this with $v'$ being the vector $x$ that Fedor wrote down. By his observation, $(A/C\sqrt{n})^k x$ goes to $0$, which implies that $\lambda < C \sqrt{n}$. – Dylan Thurston Oct 23 '10 at 17:03
I may prove it instead:) If $(Ax)_i\leq Cx_i$ and $x$ has positive coordinates, then for each vector $y\in \mathbb{R}^n$ we have $|(Ay)_i|\leq C|y_i|$ for at least one $i$. Indeed, choose $i$ such that $|y_i|/x_i$ is maximal, denote this maximal value by $p$. Then $$C|y_i|=p\cdot Cx_i\geq p(Ax)_i=p\sum a_{i,j} x_j\geq \sum a_{i,j} |y_j|=\geq (Ay)_i$$ by maximality. – Fedor Petrov Oct 23 '10 at 17:07

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

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

-
Looks an interesting approach, but will take me a while to read carefully... – Seva Oct 23 '10 at 21:34

What is the corresponding graph to this matrix?

-
There are no graphs for which $M_n$ are adjacency matrices since each $M_n$ has non-zero elements on the main diagonal. You can, of course, consider the graph on the vertex set $[n]$ with two distinct vertices $i,j\in[n]$ adjacent if and only if $ij\le n$, and attach loops to those vertices $i\in[n]$ with $i^2\le n$. Anyway, this does not help much. An editing request: would you mind to re-post your question as a comment to the problem, not as an answer? – Seva Oct 23 '10 at 11:16
He doesn't have the rep to post a comment, though. – J. M. Oct 23 '10 at 11:22
@Seva: you can consider graphs with loops. I have never seen the point of ignoring loops or multiple edges for the purposes of analyzing matrices like M_n. – Qiaochu Yuan Oct 23 '10 at 13:53