Más pequeño distinto de cero autovalor de a (0,1) de la matriz

Question

¿Cuál es el menor valor absoluto posible de un no-cero autovalor de una $n$ $n$ matriz cuadrada cuyas entradas son o $0$ o $1$ (todas las operaciones son más de $\mathbb{R}$)?

Answer 1

Para un $2\times 2$ matriz, el más pequeño es $\left| \dfrac{1-\sqrt{5}}{2}\right|$ $\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$ o $\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}$.

---

Para un $3\times 3$ matriz, el más pequeño es $\left|\frac{1}{2}(3-\sqrt{5})\right|$ $\begin{pmatrix} 1 & 0 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{pmatrix}$ o de cualquier otra matriz con todas las entradas $1$ a excepción de una sola apagado (principal) de la diagonal $0$.

---

Mejor hasta el momento hay más cálculos para ejecutar y comprobar

Para un $4\times 4$ matriz, el más pequeño es $\left|2-\sqrt{3}\right|$ $\begin{pmatrix} 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \end{pmatrix}$

Answer 2

Considere la posibilidad de la $n\times n$ matriz $$E_n = \vec{1} \vec{1}^T + e_1 e_1^T - I$$ donde $\vec{1}$ es el vector de todos, $e_1$ es el vector con un $1$ en el primer elemento y ceros en otros lugares, y $I$ es la matriz identidad. En otras palabras, $E_n$ tiene queridos en todas partes, excepto el último, $n-1$ elementos de la diagonal.

Empíricamente, me estoy encontrando que el más pequeño distinto de cero autovalor en valor absoluto es de aproximadamente $-1/n$. Sospecho que podría ser delimitada de manera rigurosa, y si puedo hacerlo, voy a editar esta respuesta. Pero parece claro para mí que el más pequeño distinto de cero autovalor no se apartó de cero.

EDIT: Los autovalores de a $E_n$ $n>2$ $-1$ y $$\frac{n-1\pm\sqrt{(n-1)^2+4}}{2}=\frac{n-1}{2}\pm\sqrt{\left(\frac{n-1}{2}\right)^2+1}.$$ El menor valor absoluto es, por tanto, $$\sqrt{\left(\frac{n-1}{2}\right)^2+1}-\frac{n-1}{2}\geq \frac{1}{n-1}.$$ Por supuesto, esto no es un obligado para todos los $\{0,1\}$ matrices, sólo para este.

EDICIÓN: Juan Habert de las matrices 3x3 y 4x4 matrices hacer mejor que esto. Para una matriz de todos, excepto un solo fuera de la diagonal cero, los valores propios son 0 (con $n-2$ multiplicty) y $$\frac{n}{2} \pm \sqrt{ \frac{n^2}{4} - 1 } \geq \frac{1}{n}.$$ He verificado esta numéricamente a a $n=1000$.