¿Un grafo regular conexo tiene k bucles?

Question

Supongamos que $A$ es una orden- $n$ matriz de ceros y unos tal que $A^2 = J$ la matriz de todos los unos. Demuestre que $A$ tiene exactamente $k$ a lo largo de la diagonal, donde $k^2 = n$ .

Puedo demostrar que $AJ=JA=kJ$ en términos de teoría de grafos, $A$ es un grafo regular de orden $k$ . Y $A$ está conectado, o bien $A^2$ tendría ceros. Me pregunto si existe un teorema que pueda establecer que la gráfica tiene exactamente $k$ ¿bucle? O quizá sea más obvio desde una perspectiva matricial.

Sé que la regularidad y la conectividad por sí solas no son suficientes, ya que por ejemplo la matriz

$$A_\varnothing=\begin{bmatrix}1& & &1\\ &1&1& \\1& &1& \\&1&&1\end{bmatrix}$$

est $k$ -regular y conectado, pero no satisface $A_\varnothing^2 = J$ y no tiene $k$ a lo largo de la diagonal.

Un ejemplo hace exhibir esta propiedad es

$$A_\checkmark = \begin{bmatrix}1&1&&\\&&1&1\\1&1&&\\&&1&1\end{bmatrix}$$

Answer 1

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:

1. Se nos da que $A^2 = J$ .
2. A partir de aquí podemos demostrar que $AJ = JA = kJ$ para algún valor escalar $k$ . [Ver prueba más abajo.]
3. Observando una sola columna de $AJ = kJ$ encontramos que el vector de unos es un vector propio de $A$ con valor propio $k$ .
4. 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$ .
5. 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].
6. 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$ .
7. 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.

Answer 2

Es poco probable que encuentres un teorema que diga esto, sólo tienes que argumentar combinatoriamente.

En primer lugar, si $G$ est $k$ -regular, y tenemos un vértice $v$ con un bucle, entonces el número de vértices de $G$ viene dada por $1+(k-1)+(k-1)k) = k^{2}$ ( $v$ vértices con una arista de salida de $v$ , vértices con una arista de salida de uno de los conjuntos anteriores; todos ellos son distintos porque de lo contrario habría dos caminos). Por lo tanto $n=k^{2}$ .

Consideremos los vértices con bucles; no puede haber aristas entre estos vértices porque eso daría dos paseos de longitud 2 entre ellos (bucle luego arista, o arista luego bucle). Por tanto, si fijamos un vértice $v$ con un bucle, entonces hay $(k-1)$ vértices sin bucles en su conjunto de salida. Cualquier otro vértice $v^{\prime}$ con un bucle debe estar a una distancia 2 de $v$ por lo que debe haber un $w$ en el conjunto de $v$ con un borde exterior a $v^{\prime}$ . Pero sólo debe haber un camino de longitud 2 desde $v$ à $v^{\prime}$ así que $w$ es única. Esto nos dice que puede haber como máximo $k-1$ vértices distintos de $v$ con bucles, lo que da un total de como máximo $k$ vértices con bucles.

Le dejo a usted la tarea de demostrar que la igualdad se cumple realmente.