Spectral radius of a graph

Question

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.

Answer 1

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.

Answer 2

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.