He descubierto que puedo demostrarlo como un teorema utilizando propiedades de los valores propios.
El truco está en que para una matriz de ceros y unos, el número de unos a lo largo de la diagonal es igual a la suma de los valores a lo largo de la diagonal (la traza de la matriz). Pero la traza de una matriz también es igual a la suma de sus valores propios (generalizados). Por lo tanto, basta con demostrar que $A$ tiene valores propios generalizados $0$ (con multiplicidad $n-1$ ) y $k$ (con multiplicidad 1).
Un aspecto positivo de este enfoque es que se generaliza a potencias mayores de $A$ y a matrices cuyas entradas no son sólo ceros y unos:
Sea $r$ sea un número entero positivo y $A$ ser cualquier $n\times n$ tal que $A^r = J$ . Entonces :
- Cada fila y columna de $A$ suma a $k \equiv n^{1/r}$ .
- El rastro de $A$ es igual a $k$ .
En detalle:
- Se nos da que $A^2 = J$ .
- A partir de aquí podemos demostrar que $AJ = JA = kJ$ para algún valor escalar $k$ . [Ver prueba más abajo.]
- Observando una sola columna de $AJ = kJ$ encontramos que el vector de unos es un vector propio de $A$ con valor propio $k$ .
- Combinación de $A^2 = J$ y $AJ = kJ$ obtenemos $A^3 = kA^2$ . Esto nos permite reescribir todas las potencias superiores de $A$ en términos de $A^2$ .
- Utilización de la regla de reescritura $A^3 = kA^2$ encontramos que los valores propios generalizados de $A$ son $k$ (con multiplicidad 1) y 0 (con multiplicidad $n-1$ ). [Véase la prueba más adelante].
- La traza de una matriz es la suma de sus valores propios generalizados; por tanto, la traza de $A$ es sólo $k+0+0+\ldots+0 = k$ .
- La traza de una matriz de ceros y unos es igual al número de unos a lo largo de la diagonal. Por lo tanto, hay exactamente $k$ a lo largo de la diagonal (exactamente $k$ vértices con bucles); QED.
Prueba de (2) observamos que la matriz $J$ calcula las sumas de columna/fila de una matriz: Para cualquier orden $n$ matriz $M$ , dejemos que $r_1, \ldots, r_n$ sean sus sumas de filas. Nótese que por las reglas de multiplicación de matrices, $MJ$ i $$MJ = \begin{bmatrix}r_1 & r_1 & \ldots & r_1\\r_2 & r_2 & \ldots & r_2\\\vdots & \vdots & &\vdots\\ r_n & r_n & \ldots & r_n\\\end{bmatrix}$$ y de forma similar $JM$ es la matriz de sumas de columnas.
Si $A^2 = J$ por hipótesis, entonces $A^3 = AJ = JA$ . Pero $AJ$ es la matriz de sumas de filas de $A$ y $JA$ es la matriz de sumas de columnas de $A$ . Si son iguales, entonces cada fila y columna de $A$ deben tener la misma suma- llámalo $k$ .
En consecuencia, $AJ = JA = kJ$ (la matriz en la que cada entrada es $k$ .)
Como corolario, podemos demostrar que $k^2 = n$ (el orden de la matriz) porque $J^2 = nJ$ (las sumas de filas de $J$ son todos $n$ ) y $J^2 = JA^2 = (JA)A = kJA = k(JA) = k(kJ) = k^2J$ Así que $nJ = k^2 J$ lo que significa que $k^2 = n$ .
Prueba de (5) : La fórmula generalizada de los valores propios est $$(A - \lambda I)^n v = 0.$$
A partir de (3), sabemos que $k$ es un valor propio y, por tanto, un valor propio generalizado. Si $n=1$ este debe ser el único valor propio y hemos terminado. De lo contrario, vamos a demostrar que 0 es otro valor propio generalizado y que tiene multiplicidad $n-1$ . Porque hay exactamente $n$ valores propios generalizados, podemos concluir que 0 es el sólo otro valor propio, y que $k$ tiene multiplicidad 1.
Considerando el valor propio $\lambda = 0$ la ecuación generalizada de valores propios se reduce a $A^n = 0$ . Pero porque $A^2 = J$ implica que $A^3 = kA^2$ podemos demostrar por inducción que $A^{r+2} = k^r A^2$ para números enteros $r \geq 0$ . Por lo tanto $A^n = k^{n-2} A^2 = k^{n-2} J$ . (Nota: $n>2$ porque $n$ es un cuadrado perfecto y estamos considerando sólo el caso $n>1$ .)
Por lo tanto, los vectores propios generalizados de $A$ con valor propio 0 son vectores $v$ tal que $$k^{n-2} J v = 0$$ o, eliminando la constante positiva $k^{n-2}$ , sólo $$Jv = 0.$$
Pero $Jv$ devuelve un vector en el que cada entrada es la suma de las entradas de $v$ :
$$Jv = (\sum_i v_i)\begin{bmatrix}1\\1\\\vdots \\ 1\end{bmatrix}$$
así que $J$ envía a cero sólo aquellos vectores cuyas entradas suman cero. El conjunto de todos estos vectores suma cero es un subespacio de dimensión $n-1$ por lo que hemos demostrado que $0$ es un valor propio generalizado de $A$ con multiplicidad algebraica $n-1$ .
Porque $k$ es un valor propio de $A$ y hay exactamente $n$ valores propios generalizados, se deduce que $k$ es el único otro valor propio generalizado y que tiene multiplicidad 1. Q.E.D.
0 votos
¿Y si $n$ no es un entero cuadrado?
0 votos
Entonces creo que la condición $A^2 = J$ es imposible de satisfacer.
0 votos
En $ij$ entrada de $A^{2}$ representa el número de paseos de longitud 2 entre vértices $v_{i}$ y $v_{j}$ . Como no supones que tu matriz sea simétrica, estás trabajando con digrafos. ¿Qué puedes decir de un vértice que no tiene un bucle?
0 votos
Sí, esa es la interpretación correcta. Los vértices sin bucles tienen aristas salientes hacia $k$ otros vértices distintos, y aristas entrantes desde $k$ otros vértices distintos. Exactamente un vértice tiene tanto una arista saliente como una entrante desde él, de modo que hay exactamente un camino de longitud 2 desde el vértice hasta sí mismo.
0 votos
@user326210 En particular, debe tener una salida y a exactamente otro vértice (por lo que sólo hay un camino de longitud 2 desde $v_{i}$ à $v_{i}$ ). Y un vértice con un bucle no puede tener esto en absoluto.
1 votos
Además, dos vértices con bucles no pueden ser adyacentes. Esto debería ser capaz de forzar todos los detalles.
0 votos
Parece que el único caso posible es cuando se tiene alguna permutación de la siguiente matriz: \begin{bmatrix} I_{k}^{1} & I_{k}^{2} & I_{k}^{3} & \dots & I_{k}^{k} \\ I_{k}^{1} & I_{k}^{2} & I_{k}^{3} & \dots & I_{k}^{k} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ I_{k}^{1} & I_{k}^{2} & I_{k}^{3} & \dots & I_{k}^{k} \end{bmatrix} donde $I_{k}^{1}=\begin{bmatrix} 1 & 1 & 1 & \dots & 1 \\ 0 & 0 & 0 & \dots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \dots & 0 \end{bmatrix}$ etc.
0 votos
En $I_{k}^{j}$ en el comentario anterior son todos $k \times k$ matrices en las que la fila de $1's$ es el $j'th$ fila de la matriz.