Laplacian matrix: Difference between revisions

Latest revision as of 01:30, 26 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.

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.
The Laplacian matrix has determinant zero, i.e., it is non-invertible. More specifically, its kernel contains the vector with all coordinates one, and is therefore at least one-dimensional. Moreover, the dimension of the kernel equals the number of connected components of the graph, and an explicit basis for the kernel is as follows: for each connected component, the corresponding basis vector is the sum of the standard basis vectors for the vertices in that component. In particular, if the whole graph is connected, the kernel is one-dimensional, the nullity is one, and the rank is $n-1$ .

@@ 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 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>.
+# 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.
+Other names for the Laplacian matrix are '''graph Laplacian''', '''admittance matrix''', '''Kirchhoff matrix''', and '''discrete Laplacian'''.
 ==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-semidefinite matrix|symmetric positive-definite matrix]] (this can easily be seen from version (2) of the definition).
+* 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.
+* The Laplacian matrix has determinant zero, i.e., it is non-invertible. More specifically, its kernel contains the vector with all coordinates one, and is therefore at least one-dimensional. Moreover, the dimension of the kernel equals the number of [[connected component]]s of the graph, and an explicit basis for the kernel is as follows: for each connected component, the corresponding basis vector is the sum of the standard basis vectors for the vertices in that component. In particular, if the whole graph is connected, the kernel is one-dimensional, the nullity is one, and the rank is <math>n - 1</math>.