Espectro de la matriz de adyacencia de un grafo completo

Question

Haciendo el tonto en matlab, hice una descomposición de valores propios de la matriz de adyacencia de $K_5$ .

 A = [0     1     1     1     1;
      1     0     1     1     1;
      1     1     0     1     1;
      1     1     1     0     1;
      1     1     1     1     0];

Los valores propios son $4, -1, -1, -1, -1$ . Ahora parece evidente que el mayor valor propio de la matriz de adyacencia para $K_n$ sería $n-1$ . Lo que no entiendo es por qué $-1$ es un valor propio de multiplicidad $n-1$ . ¿Tiene algún significado especial?

Answer 1

Es posible dar un límite inferior a las multiplicidades de los valores propios de la matriz de adyacencia o laplaciana de un grafo $G$ utilizando la teoría de la representación.

Es decir, el espacio vectorial de funciones $G \to \mathbb{C}$ es un representación del grupo de simetría, y tanto la matriz de adyacencia como la laplaciana respetan esta acción de grupo. De ello se desprende que cada subrepresentación irreducible se encuentra en un eigespacio de las matrices de adyacencia y laplaciana, por lo que sus dimensiones dan un límite inferior a las multiplicidades.

En este caso concreto, $K_n$ tiene como grupo de simetría el grupo simétrico completo $S_n$ y la representación correspondiente se descompone en la representación trivial (que corresponde al valor propio $n-1$ ) y un $n-1$ -representación irreducible, por lo que sólo puede haber otro valor propio y debe tener multiplicidad $n-1$ . Además, la suma de los valores propios es $0$ porque la traza de la matriz de adyacencia es cero, por lo que el valor propio restante debe ser $-1$ .

Todo esto es una forma muy elegante de decir que

Cualquier permutación de un vector propio de $K_n$ es también un vector propio con el mismo valor propio. Si el vector propio no tiene todas sus entradas iguales, entonces sus permutaciones abarcan un espacio vectorial de dimensión $n-1$ por lo que el valor propio restante tiene multiplicidad $n-1$ .

Lo que a su vez es una forma muy elegante de decir que

Cualquier vector $v$ cuyas entradas suman cero es un vector propio de la matriz de adyacencia $A_n$ de $K_n$ Además, es fácil ver que $(A_n + I)v = 0$ para cualquier $v$ Por lo tanto $A_n v = -v$ .

Esta es una explicación sencilla, pero pasa por alto la lección más importante, que es que

Los gráficos altamente simétricos tienen valores propios de alta multiplicidad.

---

Otro argumento procede de la observación de que, por un lado, $\text{tr}(A^k)$ cuenta el número de paseos de longitud $k$ que comienzan y terminan en el mismo vértice y, por otro lado, $$\text{tr}(A^k) = \sum_{i=1}^n \lambda_i^k$$

donde $\lambda_i$ son los valores propios. Esta secuencia determina de forma única los valores propios (ejercicio), por lo que para demostrar el resultado deseado basta con demostrar que $$\text{tr}(A^k) = (n-1)^k + (n-1)(-1)^k.$$

Ahora, el número total de paseos de longitud $k-1$ es sólo $n(n-1)^{k-1}$ donde la primera $n$ cuenta el número de vértices iniciales posibles y cada factor de $n-1$ cuenta los posibles vértices siguientes. Si dicho paseo termina en el vértice original (por lo que es en sí mismo un paseo cerrado de longitud $k-1$ ), no se puede extender a un paseo cerrado de longitud $k$ ; de lo contrario, se puede extender de forma única como tal. Por lo tanto, se deduce que $$n(n-1)^{k-1} = \text{tr}(A^{k-1}) + \text{tr}(A^k)$$

y entonces el resultado deseado se deduce por inducción de la condición inicial $\text{tr}(A^0) = n$ .

Answer 2

Tenga en cuenta que $B = A + I$ es el $n \times n$ matriz de todos los $1$ 's, que es $e e^T$ donde $e$ es un vector columna de todos los $1$ 's. Obsérvese que $B e = n e$ Así que $e$ es un vector propio de $B$ con valor propio $n$ (y por tanto un vector propio de $A$ con valor propio $n-1$ ), mientras que todo vector ortogonal a $e$ está en $\rm Ker B$ por lo que es un vector propio de $B$ con valor propio $0$ y de $A$ con valor propio $-1$ .

Answer 3

Esto es demasiado para un comentario. No será una imagen completa, pero es un grupo de ideas interesantes en torno a esta cuestión.

Un gráfico conectado de diámetro $d$ tiene al menos $d + 1$ valores propios distintos. Por lo tanto, el único gráfico conectado que puede tener sólo 2 valores propios distintos es el gráfico de diámetro 1, ¡el gráfico completo!

La clase de grafos fuertemente regulares es una clase que siempre realiza ese límite, es decir, tienen exactamente $d+1$ valores propios distintos (y no más). Un gráfico completo es fuertemente regular.

Todo $k$ -Los gráficos regulares tienen $k$ como un valor propio con multiplicidad igual al número de componentes conectados en el gráfico. Por lo tanto, una componente conectada $k$ -El gráfico regular tiene $k$ como un valor propio de multiplicidad 1. Y, para cualquier otro valor propio, $\lambda$ tenemos $|\lambda| \leq k$ .

Las primeras secciones de "Algebraic Graph Theory" de Biggs tienen un montón de estas ideas.

Answer 4

Cada valor propio de la matriz de adyacencia de un grafo corresponde a lo que llamo un espectral realización geométrica del gráfico.

A realización geométrica asocia los vértices con puntos no necesariamente distintos en el espacio euclidiano de alguna dimensión (las aristas pueden considerarse segmentos no necesariamente degenerados que unen esos puntos).

Una matriz cuya filas forman una base ortogonal del eigespacio tiene columnas sirven como vectores de coordenadas de los vértices de a (proyección de a) espectral realización. Una realización espectral tiene dos propiedades clave:

• Es armonioso : Cada automorfismo del grafo induce una isometría "rígida" en la realización.
• Es eigenic para cualquier vértice $v$ tenemos $\lambda [v] = \sum_{u \text{ adj } v} [u]$ , donde $[x]$ da el vector de coordenadas del vértice $x$ y $\lambda$ es el valor propio asociado.

Ahora, el gráfico completo $K_n$ tiene dos realizaciones espectrales en $\mathbb{R}^n$ (aunque pueden proyectarse en espacios de menor dimensión).

• $\lambda=n-1$ : El "punto", con todo $n$ vértices realizados por el vector de coordenadas "todo 1".
• $\lambda=-1$ : El "regular" (centrado en el origen) $n$ -simplex" (segmento, triángulo, tetraedro, etc.).

En el caso del simplex, el hecho de estar centrado en el origen implica que sus vectores de vértice satisfacen $[v_0]+[v_1]+[v_2]+[v_3]+[v_4]=0$ . Para cualquier $v_i$ podemos escribir

$$-1\;[v_i] = \sum_{j\ne i} [v_j]$$

Como un gráfico completo tiene cada vértice adyacente a todos los demás, esto es precisamente una declaración de la propiedad eigenica para el valor propio $-1$ .

Obsérvese que la realización del "punto" -aunque en sí mismo $0$ -dimensional--- determina un $1$ -espacio vectorial de dimensiones; el "simplex" utiliza el resto de $n-1$ dimensiones, que representan la multiplicidad de valores propios $-1$ .

---

Para más información, consulte mi post sobre Bloog "Realizaciones espectrales de grafos" . Allí encontrará un enlace a una nota que incluye cientos de ilustraciones de realizaciones espectrales de gráficos altamente simétricos.

Answer 5

Considerar la matriz $J_n$ tiene $n$ orden de todos. $A(K_n) = J_n - I_n$ los valores propios de $J_n$ son $n$ y $0$ los valores propios de $I_n$ es $1$ . aplicar la teoría de los mapas espectrales.