10
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ What's your motivation if I may ask? $\endgroup$ Oct 22, 2010 at 16:51
  • $\begingroup$ It is motivated by a problem in algebraic graph theory. $\endgroup$
    – Seva
    Oct 22, 2010 at 18:17
  • $\begingroup$ You're right. I wrongly supposed that so many rows are identical. I'll think again. $\endgroup$ Oct 23, 2010 at 6:31
  • 1
    $\begingroup$ 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... $\endgroup$
    – Suvrit
    Oct 23, 2010 at 12:35

3 Answers 3

6
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Fedor, can you provide a reference for that statement? $\endgroup$ Oct 23, 2010 at 14:09
  • 1
    $\begingroup$ 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}$. $\endgroup$ Oct 23, 2010 at 17:03
  • 3
    $\begingroup$ 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. $\endgroup$ Oct 23, 2010 at 17:07
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Looks an interesting approach, but will take me a while to read carefully... $\endgroup$
    – Seva
    Oct 23, 2010 at 21:34
0
$\begingroup$

What is the corresponding graph to this matrix?

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – Seva
    Oct 23, 2010 at 11:16
  • $\begingroup$ He doesn't have the rep to post a comment, though. $\endgroup$ Oct 23, 2010 at 11:22
  • 1
    $\begingroup$ @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. $\endgroup$ Oct 23, 2010 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.