cómo probar la siguiente declaración para esta matriz.

Question

Vamos $A:=[a_{ij}]_{n×n}$ , $a_{ij}=0$ o $a_{ij}=1$ $\exists m \in\mathbb N$ tal que $A^m=J-I$ donde $I$ es la matriz identidad y $J=[1]_{n×n}$ (cada entrada es $1$). Cómo probar:

1. $\exists a \in\mathbb N$ tal que $n=a^m+1$, y
2. $m$ es impar.

Gracias de antemano.

Answer 1

(El problema es que el enunciado es falso cuando $n=1$, pero vamos a ignorar este caso de degeneración.) Tenemos al menos tres pruebas.

Prueba 1 (adaptada de la prueba por Anon; véase su comentario). Tenemos $$\det (A)^m=\det (A^m)=\det(J-I)=(-1)^{n-1}(n-1)$$ y, por tanto,$n=|\det(A)|^m+1$.

Prueba 2 (adaptado del Teorema 1 de la C. W. H. Lam, J. H. van Lint, Gráficos con Caminos de Longitud Fija, Revista de Teoría Combinatoria B, vol. 24, Nº 3, 1978; gracias a @darij_grinberg de la información): $A^m=J−I$ implica que el $AJ−A=A^{m+1}=JA−A$. Por lo tanto $AJ=JA$, es decir, todas las sumas de fila y columna de sumas de $A$ son iguales a los naturales entero $c$. Por lo tanto $AJ=JA=cJ$ y a su vez $A^mJ=c^mJ$. Pero por la propiedad de $A$, también tenemos $A^mJ=(J−I)J=(n−1)J$. Por lo tanto,$c^m=n−1$.

Prueba 3: Como $2 = 1^m+1$, podemos suponer que la $n\ge3$. Desde $A$ es un entrywise no negativo, por Perron-Frobenius teorema, el radio espectral $\rho(A)$ $A$ es un máximo autovalor de a $A$. Por lo tanto $\rho(A)^m$ a un máximo autovalor de a $A^m$. Pero cuando $n\ge3$, el máximo autovalor de a $A^m=J-I$ es único, es decir,$n-1$. Por lo tanto $\rho(A)^m=n-1$ o $n=\rho(A)^m+1$. Finalmente, como los autovalores de a $A^m=J-I$ $n-1$ (simple autovalor) y $-1$ (con multiplicidad $n-1$), los autovalores de a $A$ $\rho(A)=(n-1)^{1/m}$ y un número de $m$-th raíces de $-1$. Por lo tanto $\rho(A)=|\det(A)|$ y a su vez $\rho(A)$ es un número entero.