Radio espectral de un gráfico tripartito completo

La matriz de adyacencia del grafo tripartito completo$\mathcal K_{4,4,12}$es el$20 \times 20$matriz simétrica

$$\mathrm A := \underbrace{\begin{bmatrix} 0 & 1 & 1 & 1 & 1\\ 1 & 0 & 1 & 1 & 1\\ 1 & 1 & 0 & 0 & 0\\ 1 & 1 & 0 & 0 & 0\\ 1 & 1 & 0 & 0 & 0\end{bmatrix}}_{=: \mathrm M} \otimes 1_4 1_4^\top = \mathrm M \otimes 1_4 1_4^\top$$

Desde$\rm A$es simétrico, su radio espectral es igual a su norma espectral, es decir,

$$\rho (\mathrm A) = \| \mathrm A \|_2 = \sigma_{\max} (\mathrm A) = \sqrt{\lambda_{\max} \left( \mathrm A^\top \mathrm A \right)} = \sqrt{\lambda_{\max} \left( \mathrm A^2 \right)}$$

dónde

$$\mathrm A^2 = \mathrm M^2 \otimes 1_4 \underbrace{1_4^\top 1_4}_{=4} 1_4^\top = \mathrm M^2 \otimes 4 \, 1_4 1_4^\top = 4 \mathrm M^2 \otimes 1_4 1_4^\top$$

y

$$\lambda_{\max} \left( \mathrm A^2 \right) = 4 \cdot \lambda_{\max} \left( \mathrm M^2 \right) \cdot \underbrace{\lambda_{\max} \left( 1_4 1_4^\top \right)}_{= \mbox{tr} \left( 1_4 1_4^\top \right) = 4} = 16 \cdot \lambda_{\max} \left( \mathrm M^2 \right)$$

Usando SymPy ,

>>> from sympy import *
>>> M = Matrix([[0,1,1,1,1],
                [1,0,1,1,1],
                [1,1,0,0,0],
                [1,1,0,0,0],
                [1,1,0,0,0]])
>>> (M**2).eigenvals()
{0: 2, 9: 1, 4: 1, 1: 1}

y por lo tanto,$\lambda_{\max} \left( \mathrm M^2 \right) = 9$. Por último, el radio espectral de$\rm A$es

$$\rho (\mathrm A) = \sqrt{\lambda_{\max} \left( \mathrm A^2 \right)} = 4 \sqrt{\lambda_{\max} \left( \mathrm M^2 \right)} = 4 \sqrt{9} = 12$$

Puedo confirmar la declaración, pero no tengo idea de por qué uno esperaría que fuera verdad. Calculé los radios espectrales numéricamente con numpy, y ambos resultaron ser$12$. Usé numpy y la función numpy.linalg.eigsque proporciona los vectores propios asociados, así como los valores propios. Los vectores propios se devuelven normalizados, pero en este caso, tenían una estructura simple y pude encontrar fácilmente vectores propios con componentes enteros para poder hacer aritmética exacta.

Aquí está mi secuencia de comandos de Python para confirmar los vectores propios. En caso de que no conozca Python, A es la matriz de adyacencia de$K_{4,4,12}$y B el de$K_{2,9,9}$. El vector propio de A es

$$(3,3,3,3,3,3,3,3,2,2,2,2,2,2,2,2,2,2,2,2)$$ y el vector propio de B es $$(3,3,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2)$$

import numpy as np

A = np.ones((20,20), dtype=int)
A[0:4,0:4]=0
A[4:8,4:8]=0
A[8:20,8:20]=0

x = np.array(8*[3]+12*[2])
y = np.array(20*[0], dtype=int)
z= 12*x-A@x
assert all(y[i]==z[i] for i in range(20))

B=np.ones((20,20), dtype=int)
B[0:2,0:2]=0
B[2:11,2:11]=0
B[11:20,11:20]=0

x = np.array(2*[3]+18*[2])
y = np.array(20*[0], dtype=int)
z= 12*x-B@x
assert all(y[i]==z[i] for i in range(20))

Observamos que las matrices son irreducibles, por lo que se aplica el teorema de Perron-Frobenius. Una de las afirmaciones es que el valor propio de Perron-Frobenius es el único con un vector propio asociado de elementos no negativos, lo que prueba que$12$es el valor propio máximo en ambos casos.

EDITAR Pensándolo bien, con este ejemplo como guía, deberíamos poder calcular el radio espectral de cualquier completo$k$-gráfico de partículas. Esperamos que el vector propio de Perron-Frobenius sea un "vector de bloque" de$k$bloques, donde cada bloque es un vector constante cuya longitud es el tamaño de la parte correspondiente del gráfico. No puedo hacer esto de la cabeza, pero no suena difícil. No veo una fórmula, pero este enfoque reduce el problema a encontrar los valores propios de un$k\times k$matriz. En el presente caso, solo tendríamos que mostrar que el valor propio más grande de

$$\pmatrix{ 0&4&12\\ 4&0&12\\ 4&4&0 } \text { and } \pmatrix{ 0&9&9\\ 2&0&9\\ 2&9&0}$$ son ambos $12$.