límite superior para la suma del valor absoluto de los valores propios, la matriz correspondiente es simétrica real con diagonal 0's

Question

$A=\left(a_{ij}\right)\in M_{n\times n}(\mathbb R)$ s.t. $a_{ij}=a_{ji}=\begin{cases}0,&i=j\\0\lor 1&i\ne j\end{cases}$

Los valores propios de $A$ son $\lambda_1, \dots, \lambda_n$

Quiero encontrar un límite superior de $\sum |\lambda_j|$ .

Será mejor si alguien puede dar un límite superior $\frac{1}{2}n^{\frac{3}{2}}$ aproximadamente cuando n es suficientemente grande.(o incluso menor que él)

Answer 1

Supongamos que hay $m$ entradas distintas de cero en $A$ . Entonces usando Cauchy-Schwartz y el hecho de que aquí $m=\text{Tr}(A^2)=\sum_{i =1}^n \lambda_i^2$ ya tienes el límite:

\begin{equation} \sum_{i =1}^n \vert\lambda_i\vert \leq \bigg(n\sum_{i =1}^n \lambda_i^2\bigg)^{1/2}=(nm)^{1/2}. \end{equation}

Esto no utiliza realmente el hecho de que la diagonal es cero. Para la matriz con todos los off-diagonales igual a 1, esto está fuera por un aproximadamente $\sqrt{n}$ factor, así que no estoy seguro de lo bueno que es. Si permites que las entradas fuera de diagonal sean $-1$ además, este límite es en realidad ajustado, como demostró Hao Huang utilizando una firma de la matriz de adyacencia del hipercubo booleano en la reciente resolución de la Conjetura de la Sensibilidad.