Graph Laplacian

• Given an arbitrary orientation to the edge set , the graph Laplacian can be defined as

  • The Laplacian is self-adjoint and positive semi-definite

• The Laplacian associated with a weighted graph is given by

• We may define an Edge Laplacian for any defined as

  • The set of nonzero eigenvalues of is equal to the set of nonzero eigenvalues of
  • The nonzero eigenvalues of and are equal to the square of the nonzero singular values of .
  • If has connected components , the edge Laplacian of has a block diagonal form
    This can be interpreted as an adjacency matrix, where edges that share common vertices are considered non-adjacent.

• For any digraph, the vector of all ones is the eigenvector associated with the zero eigenvalue of

  • The in-degree version of the Laplacian captures how a node is influenced by others.
  • The out-degree version of the Laplacian captures how a node influences other nodes.

• (Mesbahi e2.5) Let be a graph, then

  • Intuition: The adjacency matrix can be arranged as a block diagonal matrix through reordering of matrices. The rank of which is known to be the sum of the ranks of the block matrices).

    Let be a block in the Laplacian with . Then, . This is the case because is positive semi-definite. Therefore it has as an eigenvalue exactly once (by Mesbahi 2.8).

• (Mesbahi 2.8) Let be the Laplacian of . Sort the eigenvalues as . We refer to this listing as the **Laplacian spectrum

  is connected if and only if

  • since is positive semi-definite. This corresponds to the eigenvector of all s (and it is because the sum of any row on an incident matrix is ).
  • Using the Spectral Properties of the Laplacian, we can extend the connectivity inequality
    Provided that is not the complete graph.

• (Mesbahi 2.9) Kirchhoff’s Matrix tree Theorem Consider the graph with vertices and edges. Then using the determinant

  for any vertex .

  (Mesbahi 2.10, Wilson 10.3) Let be the number of spanning trees in . Then

  In other words, the number of spanning trees of is equal to the cofactor of any element of .

  (Mesbahi 2.12) A directed graph version can be defined as follows. Let be an arbitrary vertex of a weighted digraph . Then

  Where is the set of spanning -arborescences in .

• (Mesbahi 3.8) A digraph on vertices contains an arborescence if and only if

  In that case is spanned by the vector of all ones.

• (Mesbahi 3.10) Let be a weighted digraph on vertices. By the Gerschgorin Disk Theorem

  Where is the maximum weighted in-degree in .

  Thus, every eigenvalue of has non-negative real parts.

• (Mesbahi 3.11) Let be the Jordan decomposition of the in-degree Laplacian for . When contains an arborescence, thee nonsingular matrix can be chosen such that

  Where is the Jordan block associated with , and each has positive real parts.

  This implies that

  And

  Where is the first column of and the first row of .

Factorization Lemma §

• (Mesbahi 3.22) Let be graphs on and vertices respectively. Then
  That is, The Laplacian of the Cartesian Product is the Kronecker sum of the Laplacians of the individual graphs.
• (Mesbahi 3.23) Let be graphs on and vertices such that and respectively have as eigenvalues: and with associated eigenvectors and . Then
  Is the eigenvector associated with the eigenvalue of .

Links §

• Graph Theoretic Methods in Multiagent Networks by Mesbahi and Egerstedt