Tags: #definition

Laplacian (Kirchoff) matrix

Let $G$ be a graph with $n$ vertices. The Laplacian matrix of $G$ is the $n\times n$ matrix

where $d_i$ is the degree of the $i$th vertex and $A$ is the adjacency matrix.

If $G$ is directed graph, $d_i$ is instead the in-degree of $i$.

If $G$ is a weighted graph, note that the degree is the sum of the weights of the edges connected to $i$ (and if it is directed, we take the sum over all in-edges)

Properties

Undirected case:

• All row and columns sum to 0, and hence the determinant is also 0.
• $(1,\dots ,1{)}^T$ is always an eigenvector of $L$ with eigenvalue 0.
  Directed case:
• All columns sum to 0

Example

Let $G$ be the following graph:

Its Laplacian matrix as an UNDIRECTED graph is

as a DIRECTED graph, it is