# Perron-Frobenius Theorem and Graph Laplacians

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$.
• 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? – 1yen Mar 21 '11 at 15:45