6
$\begingroup$

Let $G$ be a directed graph and $A$ be the corresponding adjacency matrix. Let $\rho$ denote the spectral radius, and let $I$ be the identity matrix.

  1. What can we say about $G$ when the spectral radius of $A$ is less than $1$?

  2. Is there any graph property that shows us that fact? More generally, which is equivalent to it?

I know that this is spectral graph theory topic, but I'm not an expert in this field. I know that classic result, that $[A^k]_{ij}$ shows the $k$ length walks from $i$ to $j$, and when $\rho(A) < 1$, then exist $(I-A)^{-1}$, and the Neumann-series of $A$ converges to it. Furthermore because $A$ is nonnegative $\rho(A)=\lambda_{\max}$ without abolute value, and $(I-A)^{-1}$ is also nonnegative. That's all I know. Is there any result, that say some graph property which is equivalent to $\rho(A)< 1$?

$\endgroup$

1 Answer 1

7
$\begingroup$

The characteristic polynomial of an integer matrix is a monic integer polynomial. The product of the non-zero eigenvalues is thus equal to a non-zero integer, so the only way for $\rho(A) < 1$ is for this to be an empty product, that is if $\rho(A) = 0$ and all eigenvalues are zero.

This is equivalent to the property that $A$ is nilpotent, i.e. $A^n = 0$ for some $n$. If you think about the "number of walks" interpretation, this is, in turn, equivalent to $A$ having no directed cycles.

$\endgroup$
6
  • $\begingroup$ Equivalent? $\endgroup$
    – user153012
    Commented Nov 12, 2014 at 0:39
  • $\begingroup$ @user153012 Why would it be equivalent? That statement isn't true, at least according to the answers. I suspect the wikipedia article is mistakenly conflating invertibility of $I-A$ and the convergence of the formal power series. $\endgroup$
    – Erick Wong
    Commented Nov 12, 2014 at 5:09
  • $\begingroup$ Maybe then I've misunderstood the last sentence in your answer. $\endgroup$
    – user153012
    Commented Nov 12, 2014 at 5:14
  • $\begingroup$ @user153012 Oh, yes, $\rho(A)<1$ is equivalent to $A$ having no directed cycles. But neither is equivalent to $I-A$ being invertible. $\endgroup$
    – Erick Wong
    Commented Nov 12, 2014 at 10:07
  • 1
    $\begingroup$ @user153012 Isn't "$A$ is acyclic" a very graph-y property? $\endgroup$
    – Erick Wong
    Commented Mar 22, 2016 at 15:58

You must log in to answer this question.

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