Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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$.

share|improve this answer
    
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
    
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?) –  Qiaochu Yuan Mar 21 '11 at 15:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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