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.

Other names for the Laplacian matrix are graph Laplacian, admittance matrix, Kirchhoff matrix, and discrete Laplacian.

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.
• The Laplacian matrix has determinant zero, i.e., it is non-invertible. More specifically, its kernel contains the vector with all coordinates one, and is therefore at least one-dimensional. Moreover, the dimension of the kernel equals the number of connected components of the graph, and an explicit basis for the kernel is as follows: for each connected component, the corresponding basis vector is the sum of the standard basis vectors for the vertices in that component. In particular, if the whole graph is connected, the kernel is one-dimensional, the nullity is one, and the rank is $n-1$.