Autovalor problema: Demostrar que todos los autovalores de $A$ $1$.

Question

He aquí un lindo problema que frecuentemente fue dada por la tarde Herbert Wilf durante sus conversaciones.

Problema: Vamos a $A$ ser $n \times n$ matriz con entradas desde $\{0,1\}$, teniendo todos los autovalores positivos. Demostrar que todos los autovalores de $A$ $1$.

Sugerencia:

El uso de la AM-GM de la desigualdad de relacionar la traza y el determinante.

Answer 1

Si se quiere utilizar el AM-GM de la desigualdad, que podría proceder de la siguiente manera: Desde $A$ todos $1$'s, o $0$'s en la diagonal, se sigue que $tr(A)\leq$n. Ahora el cálculo del determinante mediante la expansión a lo largo de cualquier fila/columna, uno puede ver fácilmente que el determinante es un número entero, ya que se trata de una suma de productos de la matriz de entradas (hasta firmar). Dado que todos los valores propios son positivos, esta entero debe ser positivo. AM-GM de la desigualdad implica $$det(A)^{\frac{1}{n}}=\left(\prod_{i}\lambda_{i}\right)^{\frac{1}{n}}\leq \frac{1}{n}\sum_{i=1}^{n}\lambda_{i}\leq 1.$$ Desde $det(A)\neq 0$ y $m^{\frac{1}{n}}>1$ para $m>1$, por encima de la desigualdad de las fuerzas de $det(A)=1$. Por tanto, tenemos la igualdad que sucede precisamente cuando $\lambda_{i}=\lambda_{j}$ para todo $i,j$. La combinación de esta con la anterior igualdad se da el resultado.

Answer 2

Supongamos que a tiene una columna con solo cero entradas, entonces debemos tener cero como un valor propio. (por ejemplo, la expansión de det(A-rI) el uso de la columna). Así que debe ser verdad que en la satisfacción de las OP requisitos que debe tener cada columna contiene un 1. Lo mismo es cierto para las filas por el mismo argumento. Ahora supongamos que tenemos una relación lineal entre las filas, entonces existe una combinación lineal de estas filas que da lugar a una nueva matriz con una fila cero. Ya hemos visto que esto no está permitido así que debemos tener filas linealmente independientes. Estoy tratando de forzar a la forma de la permisible matrices a ser restringido suficiente para dar el resultado. Independencia lineal de las filas nos da un vistazo a la invertability de tales matrices, pero por desgracia no su diagonalizability. El polinomio mínimo de $(1-r)^n$ los resultados de la parte superior o inferior de matrices triangulares con otras a lo largo de la diagonal, y sospecho que puede ser capaz de completar esta prueba mirando lo que sucede a este polinomio cuando hay desviaciones de la forma triangular. El resultado vinculado por user1551 puede ser la clave. Tratando de ganar algo de intuición acerca de lo que son las posibilidades que nos lleva a coincidir con el teorema binomial con Newton identidades: http://en.wikipedia.org/wiki/Newton%27s_identities#Expressing_elementary_symmetric_polynomials_in_terms_of_power_sums

y el hecho de que el seguimiento debe ser $n$(en diagonal) y el determinante 1. Me gustaría mostrar que cualquier desviación de este polinomio mínimo debe conducir a un no positivo autovalor. Dos aspectos del análisis, de una combinatoria argumento para mostrar qué tipos de modificaciones(desde triangular) son permisibles, mientras que el mantenimiento de la fila/columna de la independencia y mirando el geométrica efectos de la no-dominante términos en los que resulta característico de los polinomios. Tal vez algún tipo de inducción argumento de la superficie de aquí.

Answer 3

Desde $\det(A) \neq 0$, $A$ es nonsingular y todas las diagonales de $Un$ debe ser igual a uno. Lado, sabemos que la relación entre el determinante y la traza es \begin{align*} \det(A) &= \exp(tr(\ln(A))) \\ &= \exp(0) \\ &= \exp(\sum_i \ln(\lambda_i)) \\ \end{align*}. Paso 2 tiene porque todas las diagonales de $Un$ son uno, por lo que su registro es cero, y el paso 3 porque natural registros analíticos. Esto sugiere $$\sum_i \ln(\lambda_i) = 0$$,, $$\prod_i \lambda_i = 1$$.

Luego, debido a que todas las diagonales de $A$, $tr(A) = \sum_i \lambda_i = $ n debe ser verdadera. Por lo tanto, el AM-GM de la desigualdad de los estados $$ \left[ \prod_{i} \lambda_i \right)^{\frac{1}{n}} \leq \frac{1}{n} \sum_{i} \lambda_{i}$$, con igualdad de retención sólo cuando $\lambda_i = \lambda_j$ $\forall (i,j$. Por lo tanto, $$ 1^{\frac{1}{n}} = \frac{1}{n} \cdot$ n$, y todos los autovalores de $Un$ debe ser igual. Desde $\prod_i \lambda_i = 1$, todos los autovalores debe ser uno.