tailieunhanh - Báo cáo toán học: "Kernels of Directed Graph Laplacians"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Kernels of Directed Graph Laplacians. | Kernels of Directed Graph Laplacians J. S. Caughman and J. J. P. Veerman Department of Mathematics and Statistics Portland State University PO Box 751 Portland OR 97207. caughman@ veerman@ Submitted Oct 28 2005 Accepted Mar 14 2006 Published Apr 11 2006 Mathematics Subject Classification 05C50 Abstract. Let G denote a directed graph with adjacency matrix Q and indegree matrix D. We consider the Kirchhoff matrix L D Q sometimes referred to as the directed Laplacian. A classical result of Kirchhoff asserts that when G is undirected the multiplicity of the eigenvalue 0 equals the number of connected components of G. This fact has a meaningful generalization to directed graphs as was observed by Chebotarev and Agaev in 2005. Since this result has many important applications in the sciences we offer an independent and self-contained proof of their theorem showing in this paper that the algebraic and geometric multiplicities of 0 are equal and that a graph-theoretic property determines the dimension of this eigenspace - namely the number of reaches of the directed graph. We also extend their results by deriving a natural basis for the corresponding eigenspace. The results are proved in the general context of stochastic matrices and apply equally well to directed graphs with non-negative edge weights. Keywords Kirchhoff matrix. Eigenvalues of Laplacians. Graphs. Stochastic matrix. 1 Definitions Let G denote a directed graph with vertex set V 1 2 . N and edge set E c V X V. To each edge uv 2 E we allow a positive weight uv to be assigned. The adjacency matrix Q is the N X N matrix whose rows and columns are indexed by the vertices and where the ij-entry is j if ji 2 E and zero otherwise. The in-degree matrix D is the N X N diagonal matrix whose ii-entry is the sum of the entries of the ith row of Q. The matrix L D Q is sometimes referred to as the Kirchhoff matrix and sometimes as the directed graph Laplacian of G. A variation on this matrix can be defined as