Laplacian matrix: Difference between revisions

Revision as of 21:38, 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)^{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. It is also a [[linea
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 1: / Line 1: @@
 ==Definition==
-Suppose <math>G</math> is a [[finite graph|finite]] [[undirected graph]]. Let <math>n</math> be the size of the vertex set <math>V(G)</math>. Fix a bijective correspondence <math>v:\{ 1,2,\dots,n\} \to V(G)</math>. The '''Laplacian matrix''' of <math>G</math> is a <math>n \times n</math> matrix defined in the following equivalent ways:
+Suppose <math>G</math> is a [[finite graph|finite]] [[undirected graph]]. Let <math>n</math> be the size of the vertex set <math>V(G)</math>. Fix a bijective correspondence <math>v:\{ 1,2,\dots,n\} \to V(G)</math>. The '''Laplacian matrix''' of <math>G</math> is a <math>n \times n</math> [[linear:square matrix|square matrix]] defined in the following equivalent ways:
 # It is the matrix difference <math>D - A</math> where <math>D</math> is the [[defining ingredient::degree matrix]] of <math>G</math> and <math>A</math> is the [[defining ingredient::adjacency matrix]] of <math>G</math>, both for the same vertex mapping <math>v</math>.
 # 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,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.
 ==Properties==
-The Laplacian matrix is a [[linear:diagonally dominant matrix|diagonally dominant matrix]].
+* The Laplacian matrix of a graph is always a [[linear:symmetric positive-definite matrix|symmetric positive-definite matrix]] (this can easily be seen from version (2) of the definition. It is also a [[linea
+* The Laplacian matrix is a [[linear:diagonally dominant matrix|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.