Laplacian matrix: Difference between revisions

Revision as of 21:40, 25 May 2014

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:

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$ .
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$ .
It is a matrix defined as follows:
- For $1 \leq i \leq n$ , the $(i, i)^{t h}$ entry equals the degree of vertex $v (i)$ .
- For $1 \leq i, j \leq n$ with $i \neq j$ , the $(i, j)^{t h}$ 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.

@@ Line 6: / Line 6: @@
 # It is the product <math>M^TM</math> where <math>M</math> is an ''oriented'' [[incidence matrix]] of <math>G</math> (where the vertices are ordered by the function <math>v</math>) and <math>M^T</math> is the [[linear:matrix transpose|matrix transpose]] of <math>M</math>.
 # It is a matrix defined as follows:
-* For <math>1 \le i \le n</math>, the <math>(i,i)^{th}</math> entry equals the [[degree of a vertex|degree]] of vertex <math>v(i)</math>.
+#* For <math>1 \le i \le n</math>, the <math>(i,i)^{th}</math> entry equals the [[degree of a vertex|degree]] of vertex <math>v(i)</math>.
-* For <math>1 \le i,j \le n</math> with <math>i \ne j</math>, the <math>(i,j)^{th}</math> entry is -1 if <math>v(i)</math> and <math>v(j)</math> are adjacent, and 0 otherwise.
+#* For <math>1 \le i,j \le n</math> with <math>i \ne j</math>, the <math>(i,j)^{th}</math> entry is -1 if <math>v(i)</math> and <math>v(j)</math> are adjacent, and 0 otherwise.
+Other names for the Laplacian matrix are '''graph Laplacian''', '''admittance matrix''', '''Kirchhoff matrix''', and '''discrete Laplacian'''.
 ==Properties==