Laplacian matrix

Definition

Suppose $G$ is a finite undirected graph. Let $n$ be the size of the vertex set $V(G)$. Fix a bijective correspondence $v:\{1,2,\dots ,n\}\to V(G)$. The Laplacian matrix of $G$ is a $n\times n$ square matrix defined in the following equivalent ways:

1. It is the matrix difference $D-A$ where $D$ is the degree matrix of $G$ and $A$ is the adjacency matrix of $G$, both for the same vertex mapping $v$.
2. It is the product $M^{T}M$ where $M$ is an oriented incidence matrix of $G$ (where the vertices are ordered by the function $v$) and $M^{T}$ is the matrix transpose of $M$.
3. It is a matrix defined as follows:

• For $1\leq i\leq n$, the $(i,i)^{th}$ entry equals the degree of vertex $v(i)$.
• For $1\leq i,j\leq n$ with $i\neq j$, the $(i,j)^{th}$ entry is -1 if $v(i)$ and $v(j)$ are adjacent, and 0 otherwise.

Properties

• The Laplacian matrix of a graph is always a symmetric positive-definite matrix (this can easily be seen from version (2) of the definition.
• The Laplacian matrix is a diagonally dominant matrix: the magnitude of the diagonal entry is greater than or equal to the sum of the magnitudes of the off-diagonal entries in its row. In this case, in fact, exact equality holds for every row.