How can the Perron-Frobenius theorem be used to show that for a connected graph, there is a simple eigenvector that is (i) real and (ii) smallest in magnitude and (iii) has an associated eigenvector that is positive?

The graph Laplacian is given as $L = D-A$, where $A$ is the non-negative adjacency matrix of the graph. The Perron-Frobenius theorem allows us to state that

$\rho(A) > 0$ and is a simple eigenvalue of $A$

$Ax = \rho(A)x$ with all elements of $x$ positive.

The matrix $D$ is diagonal with positive elements. It is well-known that for a connected graph, 0 is the smallest eigenvalue of $L$ and it is simple, and $x=\mathbb{1}$ (vector of all ones) is the associated positive eigenvector.

I am confused mainly because $L$ is no longer a non-negative (or non-positive) matrix. Any ideas?


If you're positive that the question is about the Laplacian and not the adjacency matrix, then you should consider $\lambda I - L$ for a sufficiently large value of $\lambda$.

  • $\begingroup$ Is the argumentation, then, that if a matrix $U$ diagonalizes $L$, then it also diagonalizes $\lambda I-L$ for arbitrary $\lambda$. And in particular, for $\lambda > \max_i D_{ii}$, $\lambda I-L$ is a non-negative matrix? $\endgroup$ – 1yen Mar 21 '11 at 15:45
  • $\begingroup$ 1yen: yes, that's it. (You need slightly more than non-negativity to argue that the associated eigenvector is positive, though; you need to show that some power of the matrix is positive, don't you?) $\endgroup$ – Qiaochu Yuan Mar 21 '11 at 15:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.