Incidence matrix - Revision history

Vipul at 21:22, 25 May 2014

2014-05-25T21:22:13Z

← Older revision		Revision as of 21:22, 25 May 2014
Line 24:		Line 24:
	===Oriented incidence matrix for a finite undirected graph===		===Oriented incidence matrix for a finite undirected graph===

	For a finite undirected graph, an oriented incidence matrix is defined as a matrix that arises as an oriented incidence matrix for some directed graph that has the same edge set as the undirected graph. Note that such an oriented incidence matrix is non-unique (Even after we fix the ordering of the vertices and the ordering of the edges), because it depends on the choice of orientation for each edge. The oriented incidence matrix is useful because the product of its [[matrix transpose]] with it is well-defined and equals the [[Laplacian matrix]] of the graph.		For a finite undirected graph, an oriented incidence matrix is defined as a matrix that arises as an oriented incidence matrix for some directed graph that has the same edge set as the undirected graph. Note that such an oriented incidence matrix is non-unique (Even after we fix the ordering of the vertices and the ordering of the edges), because it depends on the choice of orientation for each edge.

			One possible choice of orientation uses the ordering. Explicitly, if the vertex set bijection is <math>v: \{ 1,2,\dots,n \} \to V(G)</math>, and there is an edge joining <math>v(i)</math> and <math>v(j)</math> with <math>i < j</math>, we assign vertex <math>i</math> as the source of the edge and vertex <math>j</math> as the target of the edge. Note that this choice of orientation is ''not'' insensitive to changes in the bijection. In particular, this means that if we permute the ordering of the vertices, the new oriented incidence matrix is not simply equal to the old oriented incidence matrix times a permutation matrix.

			The oriented incidence matrix is useful because the product of its [[matrix transpose]] with it is well-defined and equals the [[Laplacian matrix]] of the graph.

	==Attributes of the incidence matrix==		==Attributes of the incidence matrix==

Vipul: /* =Unoriented incidence matrix for a finite directed graph */

2014-05-25T21:18:37Z

=Unoriented incidence matrix for a finite directed graph

← Older revision		Revision as of 21:18, 25 May 2014
Line 10:		Line 10:
	Note that the incidence matrix depends on the choice of the bijections <math>e</math> and <math>v</math>, but the dependence is well-understood: changing the bijection on the edge set corresponds to left multiplication by a permutation matrix (permuting the rows) whereas changing the bijection on the vertex set corresponds to right multiplication by a permutation matrix (permuting the columns).		Note that the incidence matrix depends on the choice of the bijections <math>e</math> and <math>v</math>, but the dependence is well-understood: changing the bijection on the edge set corresponds to left multiplication by a permutation matrix (permuting the rows) whereas changing the bijection on the vertex set corresponds to right multiplication by a permutation matrix (permuting the columns).

	===Unoriented incidence matrix for a finite directed graph==		===Unoriented incidence matrix for a finite directed graph===

	The unoriented incidence matrix for a finite directed graph is defined as being equal to the unoriented incidence matrix for the undirected graph with the same vertex set and edge set. As usual, we need to specify a labeling of the vertex set and edge set.		The unoriented incidence matrix for a finite directed graph is defined as being equal to the unoriented incidence matrix for the undirected graph with the same vertex set and edge set. As usual, we need to specify a labeling of the vertex set and edge set.

Vipul: /* Definition */

2014-05-25T21:15:00Z

Definition

Vipul at 21:04, 25 May 2014

2014-05-25T21:04:36Z

← Older revision		Revision as of 21:04, 25 May 2014
Line 1:		Line 1:
	==Definition==		==Definition==

	===~~For~~ a finite undirected graph===		===Unoriented incidence matrix for a finite undirected graph===

	Suppose <math>G</math> is a [[finite graph\|finite]] [[undirected graph]]. Let <math>m</math> be the size of the edge set <math>E(G)</math> and <math>n</math> be the size of the vertex set <math>V(G)</math>. The '''incidence matrix''', also called the '''unoriented incidence matrix''', of <math>G</math> is a <math>m \times n</math> matrix defined as follows: The <math>(i,j)^{th}</math> entry of the matrix is defined to be:		Suppose <math>G</math> is a [[finite graph\|finite]] [[undirected graph]]. Let <math>m</math> be the size of the edge set <math>E(G)</math> and <math>n</math> be the size of the vertex set <math>V(G)</math>. Denote by <math>e : \{ 1,2,\dots,m \} \to E(G)</math> and <math>v: \{1,2,\dots,n \} \to V(G)</math> bijections that label the edge set and vertex set respectively. The '''incidence matrix''', also called the '''unoriented incidence matrix''', of <math>G</math> with respect to these labelings is a <math>m \times n</math> matrix defined as follows: The <math>(i,j)^{th}</math> entry of the matrix is defined to be:

	* 1 if vertex <math>j</math> is incident on (i.e., equals one of the endpoints of) edge <math>i</math>		* 1 if vertex <math>j</math> is incident on (i.e., equals one of the endpoints of) edge <math>i</math>
	* 0 if vertex <math>j</math> is not incident on (i.e., does not equal one of the endpoints of) edge <math>i</math>.		* 0 if vertex <math>j</math> is not incident on (i.e., does not equal one of the endpoints of) edge <math>i</math>.

	===~~For~~ a finite directed graph===		Note that the incidence matrix depends on the choice of the bijections <math>e</math> and <math>v</math>, but the dependence is well-understood: changing the bijection on the edge set corresponds to left multiplication by a permutation matrix (permuting the rows) whereas changing the bijection on the vertex set corresponds to right multiplication by a permutation matrix (permuting the columns).

			===Oriented incidence matrix for a finite directed graph===

	Suppose <math>G</math> is a [[finite graph\|finite]] [[directed graph]]. Let <math>m</math> be the size of the edge set <math>E(G)</math> and <math>n</math> be the size of the vertex set <math>V(G)</math>. The '''incidence matrix''', also called the '''oriented incidence matrix''', of <math>G</math> is a <math>m \times n</math> matrix defined as follows: The <math>(i,j)^{th}</math> entry of the matrix is defined to be:		Suppose <math>G</math> is a [[finite graph\|finite]] [[directed graph]]. Let <math>m</math> be the size of the edge set <math>E(G)</math> and <math>n</math> be the size of the vertex set <math>V(G)</math>. The '''incidence matrix''', also called the '''oriented incidence matrix''', of <math>G</math> is a <math>m \times n</math> matrix defined as follows: The <math>(i,j)^{th}</math> entry of the matrix is defined to be:
Line 16:		Line 18:
	* 0 if vertex <math>j</math> is not incident on (i.e., does not equal one of the endpoints of) edge <math>i</math>.		* 0 if vertex <math>j</math> is not incident on (i.e., does not equal one of the endpoints of) edge <math>i</math>.

			===Oriented incidence matrix for a finite undirected graph===

			For a finite undirected graph, an oriented incidence matrix is defined as a matrix that arises as an oriented incidence matrix for some directed graph that has the same edge set as the undirected graph. Note that such an oriented incidence matrix is non-unique (Even after we fix the ordering of the vertices and the ordering of the edges), because it depends on the choice of orientation for each edge. The oriented incidence matrix is useful because the product of its [[matrix transpose]] with it is well-defined and equals the [[Laplacian matrix]] of the graph.
	==Attributes of the incidence matrix==		==Attributes of the incidence matrix==

Vipul: Created page with "==Definition== ===For a finite undirected graph=== Suppose $G$ is a finite undirected graph. Let $m$ be the size of the edge set <..."

2014-05-25T19:53:18Z

Created page with "==Definition== ===For a finite undirected graph=== Suppose <math>G</math> is a finite undirected graph. Let <math>m</math> be the size of the edge set <..."

New page

==Definition==

===For a finite undirected graph===

Suppose <math>G</math> is a [[finite graph|finite]] [[undirected graph]]. Let <math>m</math> be the size of the edge set <math>E(G)</math> and <math>n</math> be the size of the vertex set <math>V(G)</math>. The '''incidence matrix''', also called the '''unoriented incidence matrix''', of <math>G</math> is a <math>m \times n</math> matrix defined as follows: The <math>(i,j)^{th}</math> entry of the matrix is defined to be:

* 1 if vertex <math>j</math> is incident on (i.e., equals one of the endpoints of) edge <math>i</math>
* 0 if vertex <math>j</math> is not incident on (i.e., does not equal one of the endpoints of) edge <math>i</math>.

===For a finite directed graph===

Suppose <math>G</math> is a [[finite graph|finite]] [[directed graph]]. Let <math>m</math> be the size of the edge set <math>E(G)</math> and <math>n</math> be the size of the vertex set <math>V(G)</math>. The '''incidence matrix''', also called the '''oriented incidence matrix''', of <math>G</math> is a <math>m \times n</math> matrix defined as follows: The <math>(i,j)^{th}</math> entry of the matrix is defined to be:

* 1 if vertex <math>j</math> is the target vertex of edge <math>i</math>
* -1 if vertex <math>j</math> is the source vertex of edge <math>i</math>
* 0 if vertex <math>j</math> is not incident on (i.e., does not equal one of the endpoints of) edge <math>i</math>.

==Attributes of the incidence matrix==

{| class="sortable" border="1"
! Attribute !! Value for unoriented incidence matrix of a finite simple undirected graph !! Explanation !! Value for oriented incidence matrix of a finite simple directed graph !! Explanation
|-
| Set of entry values || 0 and 1 || Obvious from the definition.<br>Note that for a matrix with a nonzero number of rows and columns, there exists at least one 1, and the only case that there are no 0s arises when the matrix is the graph with two vertices and one edge joining them. || 0, 1, and -1 || Obvious from the definition.<br>Note that for a matrix with a nonzero number of rows and columns, there exists at least one 1 and at least one -1, and the only case that there are no 0s arises when the matrix is the graph with two vertices and one directed edge between them.
|-
| Row sum || 2 || Two 1s in each row, corresponding to the vertices at the endpoints of the edge. The remaining entries are equal to 0.<br>Note that relaxing the condition of simplicity will make this false. || 0 || One -1 and one 1 in each row, the remaining entries are 0.
|}