Valores propios del complemento de un gráfico

Question

Dejemos que $A$ y $\widetilde A$ sean las matrices de adyacencia de un grafo $G$ y de su complemento, respectivamente.

1. ¿Existe alguna relación entre los valores propios de $A + \widetilde A$ y los valores propios de $A$ y $\widetilde A$ ?

2. Además, haga $A$ y $\widetilde A$ tienen el mismo conjunto de vectores propios?

Gracias.

Answer 1

Editar (bis). Hay dos respuestas, dependiendo de si se permiten los bucles sobre los vértices o no. Además, se describe completamente el caso de los grafos regulares.

1. Si se permiten los bucles

La relación entre matrices es $$A+{\widetilde A}=J$$ donde $J={\bf1}{\bf1}^T$ es la matriz todo-uno. La primera consecuencia es que la suma de los valores propios de $A$ y ${\widetilde A}$ es igual a $|V|$ donde $V$ es el conjunto de vértices.

Una segunda consecuencia se refiere a los valores propios múltiples. Si $\lambda$ es un valor propio de $A$ de multiplicidad $m\ge2$ entonces $-\lambda$ es un valor propio de ${\widetilde A}$ de multiplicidad mayor o igual a $m-1$ . Basta con considerar la intersección del eigespacio con el hiperplano ${\bf1}^\bot$ . En concreto, se trata de un caso en el que $A$ y ${\widetilde A}$ comparten vectores propios comunes.

2. Si no se permiten los bucles

Aquí $$A+{\widetilde A}=K:=J-I_V$$ La suma de los valores propios de $A$ es la opuesta a la de ${\widetilde A}$ .

Si $\lambda$ es un valor propio de $A$ de multiplicidad $m\ge2$ entonces $-1-\lambda$ es un valor propio de ${\widetilde A}$ de multiplicidad mayor o igual a $m-1$ . De nuevo, este es un caso en el que $A$ y ${\widetilde A}$ comparten vectores propios comunes.

3. Gráficos regulares

Si un grafo es regular y conexo (gracias a Emil por haber precisado el punto), entonces $\bf1$ es un vector propio, con valor propio $d$ el grado de cada vértice. Es un valor propio simple porque $A$ es irreducible (conectividad). Los otros eigespacios están contenidos en $\bf1^\bot$ porque $A$ es simétrica. Por lo tanto, los vectores propios de $A$ siguen siendo vectores propios para $\widetilde A$ con la misma multiplicidad. La correspondencia entre los valores propios es $\lambda\rightarrow-1-\lambda$ .

Obsérvese también que $d$ es el valor propio de Perron de $A$ , $n-1-d$ siendo el de $\widetilde A$ . Por lo tanto, deducimos $$\lambda\in D(0;d)\cap D(-1;n-1-d)$$ para todos los demás valores propios de $A$ .