Laplacian matrix: Difference between revisions

Revision as of 21:16, 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$ 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$ .

Properties

The Laplacian matrix is a diagonally dominant matrix.

@@ Line 4: / Line 4: @@
 # 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 the [[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 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>.
 ==Properties==
 The Laplacian matrix is a [[linear:diagonally dominant matrix|diagonally dominant matrix]].