¿Cuál es el menor valor absoluto posible de un no-cero autovalor de una $n$ por $n$ matriz cuadrada cuyas entradas son o $0$ o $1$ (todas las operaciones son más de $\mathbb{R}$)? Yo estaría interesado en estimaciones o límites, ya que me imagino que una respuesta exacta es difícil.
Hice esta pregunta anteriormente en https://math.stackexchange.com/questions/666493/smallest-non-zero-eigenvalue-of-a-0-1-matrix .
El más pequeño distinto de cero autovalor puede disminuir al menos de manera exponencial, incluso para las matrices que son escasos, simétrica y invertible.
Explícitamente, vamos a $M_n$ ha $1$'s en el anti-diagonal, y también en el el primer y tercer fuera de las diagonales por encima de ella. Por ejemplo, aquí está la matriz de $n=13$:
0 0 0 0 0 0 0 0 0 1 0 1 1
0 0 0 0 0 0 0 0 1 0 1 1 0
0 0 0 0 0 0 0 1 0 1 1 0 0
0 0 0 0 0 0 1 0 1 1 0 0 0
0 0 0 0 0 1 0 1 1 0 0 0 0
0 0 0 0 1 0 1 1 0 0 0 0 0
0 0 0 1 0 1 1 0 0 0 0 0 0
0 0 1 0 1 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0 0 0 0 0
1 0 1 1 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0
Entonces (tanto como en esta respuesta) la inversa de la matriz $M_n^{-1}$ es anti-triangular, con una constante antidiagonals; por lo tanto, está determinado por su fila inferior, y esta fila inferior se $1, -1, 1, -2, 3, -4, 6, -9, 13, -19, 28, -41, \ldots$, con la alternancia de signos y valores absolutos que satisface la recurrencia $t_m = t_{m-1} + t_{m-3}$. Por lo tanto $t_m$ crece como un múltiplo de $C^m$ donde $C = 1.46557\ldots$ es la verdadera raíz de la $C^3 = C^2 + 1$, y los de la diagonal principal de $M_n^{-1}$ tiene signo constante. Aquí es $M_{13}^{-1}$:
0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 1 -1
0 0 0 0 0 0 0 0 0 0 1 -1 1
0 0 0 0 0 0 0 0 0 1 -1 1 -2
0 0 0 0 0 0 0 0 1 -1 1 -2 3
0 0 0 0 0 0 0 1 -1 1 -2 3 -4
0 0 0 0 0 0 1 -1 1 -2 3 -4 6
0 0 0 0 0 1 -1 1 -2 3 -4 6 -9
0 0 0 0 1 -1 1 -2 3 -4 6 -9 13
0 0 0 1 -1 1 -2 3 -4 6 -9 13 -19
0 0 1 -1 1 -2 3 -4 6 -9 13 -19 28
0 1 -1 1 -2 3 -4 6 -9 13 -19 28 -41
1 -1 1 -2 3 -4 6 -9 13 -19 28 -41 60
Por lo tanto el seguimiento de $M_n^{-1}$ crece como $\pm C^n$, para su mayor autovalor crece al menos como $\pm C^n/n$. Por lo tanto, el menor autovalor de $M_n$ es $O(n/C^n)$.
(Numī sugiere que, de hecho, sólo hay una muy pequeña autovalor, que es lo $O(C^{-n})$; por ejemplo, $M_{13}$ tiene un autovalor $0.008902\ldots$, y el siguiente más pequeño autovalores son acerca de $-.78$ e $.82$.)
He aquí algunos gp de código para generar la matriz de $M_n$ y el valor absoluto de m(n) de su mínimo autovalor:
M(n) = matrix(n,n,i,j, (i+j == n+1) + (i+j == n) + (i+j == n-2))
m(n) = vecmin(abs(real(polroots(charpoly(M(n))))))
Hay una bastante crudo límite inferior, es decir,$1/n^{n-1}$. Esto se obtiene mediante la observación de que el producto de los autovalores distintos de cero es uno de los simétrica funciones, por lo tanto aquí debe tener valor absoluto, al menos uno. El mayor posible absoluta autovalor de un tamaño $n$ $0-1$ la matriz es $n$, por lo que tenemos $s\cdot n^{n-1} \geq 1$ donde $s$ es el menor valor absoluto de un valor distinto de cero autovalor.
Esto es realmente crudo, ya que si uno de los autovalores es $n$, entonces la matriz es de rango uno, así que no va a ceder nada interesante, y a lo largo de estas líneas, tengo la sospecha de que si el mayor autovalor es cercano al máximo ($n$), luego el otro autovalores será mucho menor (posiblemente menos de lo que uno en valor absoluto), por lo que el producto argumento no le da nada cerca ...
Ya que para valores pequeños de $n$, hay realmente no se que muchos de $0-1$ matrices (y muchos, por ejemplo, el determinante cero, probablemente puede ser descartados.), es posible calcular el mínimo absoluto autovalor. En una tabla de estos sería de gran ayuda. Uno que puedo hacer con la mano; si $n=2$,, a continuación, $s = 1/\gamma$ (recíproco de la proporción áurea).
El circulantes de la matriz con la primera fila $c_0,c_{n-1},\dots,c_2,c_1$ tiene los autovalores $$\lambda_j=c_0+c_{n-1}\omega_j+\cdots+c_2\omega_j^{n-2}+c_1\omega_j^{n-1}$$ where $\omega_j=e^{2\pi ij/n}$, so if you can find a small sum of $$n th raíces de la unidad, usted puede encontrar un 0-1 de la matriz con un pequeño autovalor. Hay una cierta discusión de la cuestión de una pequeña suma de las raíces de la unidad aquí.
No estoy sugiriendo que circulantes matrices dará la más pequeña posible autovalores, sólo que lo que se obtiene de ellos le dará algún tipo de enlazado.
Esta no es una respuesta, pero algunos de los comentarios que el OP puede encontrar interesantes. Para matrices simétricas, una pregunta relacionada ha sido estudiado con anterioridad, a saber, el de la delimitación de la más grande y más pequeño de los valores propios, para obtener más general de las matrices.
En particular, vamos a $S_n[a,b]$ denota el conjunto de $n\times n$ simétrica real de las matrices con entradas en el intervalo de $[a,b]$ ($a < b$ se supone). Entonces, para $n \ge 2$, X. Zhang (2005) demuestra que para $A \in S_n[a,b]$, \begin{equation*} \lambda_{\min}(A) \ge \begin{cases} n(a-b)/2, & n\ \text{odd}\\ (na-\sqrt{a^2+(n^2-1)b^2})/2, & n\ \text{even}.\end{casos} \end{ecuación*} Él va a proporcionar un iff la caracterización de cuando la igualdad se produce en la desigualdad anterior.
Siguiendo las ideas en los enlaces de papel (combinado con algunos Perron-Frobenius teoría) es posible que se puedan derivar de los resultados para $|\lambda(A)|$, pero ahora mismo no tengo tiempo para pensar en eso.
Edit. Debo añadir la advertencia de que la caracterización de $\lambda_j(A)$ para $A \in S_n[a,b]$ es todavía un problema abierto, lo que significa que puede ser difícil conseguir algo para $|\lambda_j(A)|$ incluso para matrices simétricas.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
