On the spectra of nonsymmetric Laplacian matrices

A Laplacian matrix, L = (l(ij)) is an element of R-n x n, has nonpositive off-diagonal entries and zero row sums. As a matrix associated with a weighted directed graph, it generalizes the Laplacian matrix of an ordinary graph. A standardized Laplacian matrix is a Laplacian matrix with - 1/n <= l(ij) <= 0 whenever j not equal i. We study the spectra of Laplacian matrices and relations between Laplacian matrices and stochastic matrices. We prove that the standardized Laplacian matrices (L) over tilde are semiconvergent. The multiplicities of 0 and 1 as the eigenvalues of (L) over tilde are equal to the in-forest dimension of the corresponding digraph and one less than the in-forest dimension of the complementary digraph, respectively. We localize the spectra of the standardized Laplacian matrices of order n and study the asymptotic properties of the corresponding domain. One corollary is that the maximum possible imaginary part of an eigenvalue of (L) over tilde converges to 1/pi as n -> infinity. (c) 2004 Elsevier Inc. All rights reserved.