Spectral radius of a complete tripartite graph

Question

I am reading an article that mentions that it can be checked that $K_{4,4,12}$ and $K_{2,9,9}$ have the same spectral radius, namely, $12$, i.e., according to the corresponding adjacency matrices with a convenient labeling. For example, the adjacency matrix of $K_{4,4,12}$ would be

$$\begin{bmatrix} 0_{4 \times 4} & (1) & (1)\\ (1) & 0_{4 \times 4 } & (1)\\ (1) & (1) & 0_{12 \times 12} \end{bmatrix}$$

where $K_{4,4,12}$ and $K_{2,9,9}$ are complete $3$-partite graphs. How did they calculate the spectral radius?

Answer 1

I can confirm the statement, but I have no idea why one would expect it to be true. I computed the spectral radii numerically with numpy, and they both turn out to be $12$. I used numpy, and the function numpy.linalg.eigs which gives the associated eigenvectors as well as the eigenvalues. The eigenvectors are returned normalized, but in this case, they were of simple structure, and I was easily able to find eigenvectors with integer components so that I could do exact arithmetic.

Here is my python script for confirming the eigenvectors. In case you don't know python, A is the adjacency matrix of $K_{4,4,12}$ and B that of $K_{2,9,9}$. The eigenvector of A is $$ (3,3,3,3,3,3,3,3,2,2,2,2,2,2,2,2,2,2,2,2)$$ and the eigenvector of B is $$ (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))

We note that the matrixes are irreducible, so the Perron-Frobenius theorem applies. One of assertions is that the Perron-Frobenius eigenvalue is the only one with an associated eigenvector of non-negative elements, which proves that $12$ is the maximum eigenvalue in both cases.

EDIT On second thought, with this example as a guide, we should be able to work out the spectral radius of any complete $k$-partite graph. We expect the Perron-Frobenius eigenvector to be a "block vector" of $k$ blocks, where each block is a constant vector whose length is the size of the corresponding part of the graph. I can't do this off the top of my head, but it doesn't sound hard. I don't see a formula, but this approach reduces the problem to finding the eigenvalues of a $k\times k$ matrix. In the instant case, we would just have to show that the largest eigenvalue of $$ \pmatrix{ 0&4&12\\ 4&0&12\\ 4&4&0 } \text { and } \pmatrix{ 0&9&9\\ 2&0&9\\ 2&9&0} $$ are both $12$.

Answer 2

The adjacency matrix of the complete tripartite graph $\mathcal K_{4,4,12}$ is the $20 \times 20$ symmetric matrix

$$\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$$

Since $\rm A$ is symmetric, its spectral radius is equal to its spectral norm, i.e.,

$$\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)}$$

where

$$\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$$

and

$$\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)$$

Using 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}

and, thus, $\lambda_{\max} \left( \mathrm M^2 \right) = 9$. Lastly, the spectral radius of $\rm A$ is

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