Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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
1  
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

3 Answers 3

up vote 6 down vote accepted

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

share|improve this answer
    
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
2  
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)$$

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

share|improve this answer
    
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?

share|improve this answer
    
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
1  
@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
    
@Qiaochu: I've made a very explicit remark about loops, haven't I? (In fact, I also had the idea to replce "graphs" with "simple graphs" in my comment, but there doesn't seem to be a way to edit comments!) –  Seva Oct 23 '10 at 21:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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