Laplacian matrix

From Wikipedia, the free encyclopedia

This article or section needs copy editing for grammar, style, cohesion, tone or spelling.
You can assist by editing it now. A how-to guide is available. (February 2008)

In the mathematical field of graph theory the Laplacian matrix, sometimes called admittance matrix or Kirchhoff matrix, is a matrix representation of a graph. Together with Kirchhoff's theorem it can be used to calculate the number of spanning trees for a given graph. The Laplacian matrix can be used to find many others properties of the graph, see spectral graph theory.

1 Definition
2 Example
3 Properties
4 References
5 See also
6 External links

[edit] Definition

Given a graph G with n vertices (without loops or multiple edges), its Laplacian matrix $L:=(\ell_{i,j})_{n \times n}$ is defined as^[1]

$\ell_{i,j}:= \begin{cases} \deg(v_i) & \mbox{if}\ i = j \\ -1 & \mbox{if}\ i \neq j\ \mbox{and}\ v_i \text{ is adjacent to } v_j \\ 0 & \text{otherwise} \end{cases}$

That is, it is the difference of the degree matrix and the adjacency matrix of the graph. In the case of directed graphs, either the indegree or the outdegree might be used, depending on the application.

[edit] Example

Here is a simple example of a labeled graph and its Laplacian matrix.

Labeled graph	Laplacian matrix
	$\begin{pmatrix} 2 & -1 & 0 & 0 & -1 & 0\\ -1 & 3 & -1 & 0 & -1 & 0\\ 0 & -1 & 2 & -1 & 0 & 0\\ 0 & 0 & -1 & 3 & -1 & -1\\ -1 & -1 & 0 & -1 & 3 & 0\\ 0 & 0 & 0 & -1 & 0 & 1\\ \end{pmatrix}$

[edit] Properties

For a graph G and its admittance matrix L with eigenvalues $\lambda_0 \le \lambda_1 \le \cdots \le \lambda_{n-1}$ :

L is always positive-semidefinite ( $\forall i, \lambda_i \ge 0$ ).
The number of times 0 appears as an eigenvalue in the Laplacian is the number of connected components in the graph.
$λ 0$ is always 0.
$λ 1$ is called the algebraic connectivity.
The smallest non-trivial eigenvalue of L is called the spectral gap.