2
$\begingroup$

I researched about the spectral radius and was confused. There are two definitions.

  1. The spectral radius of a finite graph is defined to be the spectral radius of its adjacency matrix. the spectral radius of a square matrix is the largest absolute value of its eigenvalues.

  2. The largest eigenvalue in the spectrum of a graph is the spectral radius of a graph.

When they are equivalent? If the graph is connected, these definitions are equivalent?

Thanks for the help.

$\endgroup$

2 Answers 2

4
$\begingroup$

By the Perron–Frobenius theorem:

  • If $A$ is a $n\times n$ real matrix with strictly positive entries, it has a positive real eigenvalue $r$ such that any other eigenvalue $\lambda$ satisfies $|\lambda| < r$. There's also some other stuff about the eigenvector associated to $r$ that you don't need here.
  • If $A$ is an $n \times n$ real matrix with nonnegative entries, then we can only say $|\lambda| \le r$ for other eigenvalues. The eigenvalue $r$ could appear multiple times, we could have complex eigenvalues with absolute value $r$, and so forth.

The second case applies in particular to adjacency matrices of graphs. (Also, these are symmetric, so all their eigenvalues are real). So the spectral radius is $r$, and it is both the largest eigenvalue, and the largest absolute value of an eigenvalue: your definitions are equivalent.

As a bonus, if the graph is connected, then the adjacency matrix is an irreducible matrix, and the Perron–Frobenius theorem additionally tells us that the eigenvalue $r$ is simple (it only appears once, both algebraically and geometrically). But we don't need the graph to be connected for the definitions to be equivalent.

$\endgroup$
2
  • $\begingroup$ Dear Misha, thanks for your answer, but why they are equivalent? $\endgroup$
    – N math
    Sep 1, 2021 at 17:54
  • $\begingroup$ One of your definitions says that the spectral radius is the largest eigenvalue. The other definition says that the spectral radius is the largest absolute value of any eigenvalue. I just explained why those are the same number. $\endgroup$ Sep 1, 2021 at 18:05
2
$\begingroup$

If the eigenvalue of largest norm was negative then $\sum\limits_{i=1}^n \lambda_i^k$ would be negative for large odd values of $k$.

However we know that $\sum\limits_{i=1}^n \lambda_i^k = \operatorname{Tr}(A^k)$, and this last quantity is non-negative as the diagonal of $A^k$ is clearly non-negative. We conclude there can't be a negative eigenvalue with norm strictly larger than all other eigenvalues.

$\endgroup$

You must log in to answer this question.

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