Laplacian matrix: Information from Answers.com

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 other properties of the graph, see spectral graph theory.

1 Definition
2 Example
3 Properties
4 Deformed Laplacian
5 As an operator
6 See also
7 References

Definition

Given a graph G with n vertices (without self-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.

The normalized laplacian matrix is defined as^[1]

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

Example

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

Labeled graph	Laplacian matrix
	$\left(\begin{array}{rrrrrr} 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{array}\right)$

Properties

For a graph G and its Laplacian 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,\quad \lambda_0 = 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 because every Laplacian matrix has an eigenvector of $[1,1,\dots,1]$ that, for each row, adds the corresponding node's degree to a "-1" for each neighbor, thereby producing zero by definition.
$λ 1$ is called the algebraic connectivity.
The smallest non-trivial eigenvalue of L is called the spectral gap or Fiedler value.

Deformed Laplacian

The deformed Laplacian is commonly defined as

Δ(s) = I - s A + s 2 (D - I)

where I is the unit matrix, A is the adjacency matrix, and D is the degree matrix, and s is a (complex-valued) number. Note that normal Laplacian is just $Δ(1)$ .

As an operator

The Laplacian matrix can be generalized to the case of graphs with an infinite number of vertices and edges; this generalization is known as the discrete Laplace operator.

References

^ ^a ^b Weisstein, Eric W. "Laplacian Matrix." From MathWorld—A Wolfram Web Resource.

This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)

Donate to Wikimedia

	What are the following terms- eignvalues of matrix-entries of matrix-equality of matrix-matrix of groups-identity of matrix-inverse matrix-multiplication of matrices? Read answer...
	What is the -matrix of groups-identity of matrix-inverse matrix-multiplication of matrices? Read answer...
	Reflexive matrix for a given matrix? Read answer...

	What is the difference between guassian laplacian and gabor pyramids?
	Find the solutions of laplacian equation in cartesian coordinates?
	Why you are using Laplacian derivatives during image sharpening in dip?

Laplacian matrix

Contents