El mayor valor propio de una matriz "hiperbólica

Question

Dado un número entero $n\ge 1$ ¿cuál es el mayor valor propio $\lambda_n$ de la matriz $M_n=(m_{ij})_{1\le i,j\le n}$ con los elementos $m_{ij}$ igual a $0$ o $1$ en función de si $ij>n$ o $ij\le n$ ?

No es difícil demostrar que $$c\sqrt n \le \lambda_n \le C\sqrt{n\log n}$$ para constantes absolutas positivas adecuadas $c$ y $C$ y numérico parecen sugerir que la verdad se encuentra en algún punto intermedio.

---

Para hacer el problema un poco "más visual", las cuatro primeras matrices en cuestión son las siguientes:

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

Answer 1

Creo, $C\sqrt{n}$ también es un límite superior. Tomemos el vector $x=(x_1,\dots,x_n)$ con $x_j=j^{-1/2}$ . Entonces $(Ax)_i$ se comporta como $C\sqrt{n/i}=C\sqrt{n}x_i$ . Pero sabemos que si $(Ax)_i\leq C x_i$ para el vector $x$ con coordenadas positivas, entonces el mayor valor propio de $A$ no supera $C$ (tipo Perron-Frobenius).

(Esta respuesta se muestra muy fea, no sé por qué).

Answer 2

Puedo obtener un límite superior de $C \sqrt{n} \sqrt[4]{\log n}$ y debería ser posible impulsar esta técnica para conseguir $C_l \sqrt{n} \sqrt[2l]{\log n}$ para cualquier $l$ aunque el enfoque de Fedor podría ser mucho más simple.

Primero observamos que para cualquier número entero positivo $l$ tenemos $\text{tr } M_n^{2l} = \sum_{i=1}^{n} \lambda_i^{2l} \ge \lambda_n^{2l}$ ya que los valores propios son reales, donde $\lambda_1, ... \lambda_n$ son los valores propios de $M_n$ . Para $l = 1$ no es difícil ver que $\text{tr } M_n^2$ es el número de pares ordenados $(i, j)$ tal que $ij \le n$ o $\sum_{i \le n} \lfloor \frac{n}{i} \rfloor = n \log n + O(n)$ que, en particular, da un límite superior de la forma $C \sqrt{n \log n}$ .

Ahora toma $l = 2$ . Entonces $\text{tr } M_n^4$ es el número de cuatrillizos $(v_1, v_2, v_3, v_4)$ tal que $v_i v_{i+1} \le n$ en orden cíclico. Distinguimos tres casos.

Caso: $v_1 = k > v_3$ . Entonces $v_2, v_4$ puede ser cualquier número entero positivo menor o igual que $\left\lfloor \frac{n}{k} \right\rfloor$ y $v_3$ puede ser cualquier número entero positivo menor que $k$ lo que da

$$\sum_{k \le n} \left\lfloor \frac{n}{k} \right\rfloor^2 (k-1) = n^2 \log n + O(n^2)$$

cuatrillizos.

Caso: $v_1 = k = v_3$ . Existen $O(n^2)$ posibilidades aquí.

Caso: $v_1 = k < v_3$ . El mismo número que en el primer caso por simetría.

Esto da $\text{tr } M_n^4 = 2n^2 \log n + O(n^2)$ . De nuevo, creo que este argumento puede llevarse más lejos.

Edita: Podemos argumentar de forma similar para $l = 3$ . Ahora contamos sextillizos $(v_1, ... v_6)$ . El triplete $(v_1, v_3, v_5)$ pueden estar en uno de los seis órdenes posibles (descontando los casos en los que algunos de ellos son iguales, lo que creo que es $O(n^3)$ ), todas ellas accesibles entre sí mediante permutación cíclica y reflexión, por lo que WLOG $v_1 \ge v_3 \ge v_5$ . Entonces $v_2, v_6$ puede ser cualquier número entero positivo menor o igual que $\lfloor \frac{n}{v_1} \rfloor$ mientras que $v_4$ puede ser cualquier número entero positivo menor o igual que $\lfloor \frac{n}{v_3} \rfloor$ y $v_5$ puede ser cualquier número entero positivo menor o igual que $v_3$ lo que da

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

sextillizos. Nuestra hipótesis WLOG sobredimensiona por un factor de $6$ (hasta un error de tamaño $O(n^3)$ ), lo que da $\text{tr } M_n^6 = 6n^3 \log n + O(n^3)$ y un límite superior de $C \sqrt{n} \sqrt[6]{\log n}$ .

Answer 3

¿Cuál es el gráfico correspondiente a esta matriz?