1
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ I computed the spectral radii numerically, and they both turn out to be $12$ for what that's worth. $\endgroup$
    – saulspatz
    Commented Apr 17, 2018 at 17:39
  • $\begingroup$ would you please mention how? and which method did u use $\endgroup$
    – emelie
    Commented Apr 17, 2018 at 17:44
  • $\begingroup$ Related: math.stackexchange.com/q/2738091/339790 $\endgroup$ Commented Apr 17, 2018 at 19:39

2 Answers 2

1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Sorry, but how did you find the adjacency matrix? I only saw M to be the adjacency matrix, so why is there a direct sum? $\endgroup$
    – emelie
    Commented Apr 17, 2018 at 21:41
  • $\begingroup$ Also,would you please explain why is the spectral radius equal to the spectral norm? How does $A$ being symmetric help? Thank you $\endgroup$
    – emelie
    Commented Apr 17, 2018 at 21:41
  • $\begingroup$ It is not a direct sum, it is a Kronecker product. For symmetric matrices (which have real eigenvalues), the spectral radius is equal to the spectral norm. Take a look at this. $\endgroup$ Commented Apr 17, 2018 at 22:02
  • $\begingroup$ $\rm M$ is not an adjacency matrix. I viewed $\rm A$ as a $5 \times 5$ block matrix where each block is $4 \times 4$. Then wrote it using the Kronecker product so that I could focus on $5 \times 5$ matrix $\rm M$ instead of on $20 \times 20$ matrix $\rm A$. $\endgroup$ Commented Apr 17, 2018 at 22:10
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .