Laplacian matrix - Revision history

Vipul at 01:30, 26 May 2014

2014-05-26T01:30:54Z

← Older revision		Revision as of 01:30, 26 May 2014
Line 13:		Line 13:
	==Properties==		==Properties==

	* 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 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 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>.

Vipul at 21:40, 25 May 2014

2014-05-25T21:40:07Z

← Older revision		Revision as of 21:40, 25 May 2014
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 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:		# 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==		==Properties==

Vipul: /* Properties */

2014-05-25T21:39:15Z

Properties

← Older revision		Revision as of 21:39, 25 May 2014
Line 11:		Line 11:
	==Properties==		==Properties==

	* 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 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 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.

Vipul at 21:38, 25 May 2014

2014-05-25T21:38:51Z

← Older revision		Revision as of 21:38, 25 May 2014
Line 1:		Line 1:
	==Definition==		==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 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 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==		==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.

Vipul at 21:16, 25 May 2014

2014-05-25T21:16:53Z

← Older revision		Revision as of 21:16, 25 May 2014
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 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==		==Properties==

	The Laplacian matrix is a [[linear:diagonally dominant matrix\|diagonally dominant matrix]].		The Laplacian matrix is a [[linear:diagonally dominant matrix\|diagonally dominant matrix]].

Vipul: Created page with "==Definition== Suppose $G$ is a finite undirected graph. Let $n$ be the size of the vertex set $V(G)$ . Fix a bijective c..."

2014-05-25T19:31:55Z

Created page with "==Definition== Suppose <math>G</math> is a finite undirected graph. Let <math>n</math> be the size of the vertex set <math>V(G)</math>. Fix a bijective c..."

New page

==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:

# 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>.

==Properties==

The Laplacian matrix is a [[linear:diagonally dominant matrix|diagonally dominant matrix]].