Incidence matrix

Definition

Unoriented incidence matrix for a finite undirected graph

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

• 1 if vertex $v(j)$ is incident on (i.e., equals one of the endpoints of) edge $e(i)$
• 0 if vertex $v(j)$ is not incident on (i.e., does not equal one of the endpoints of) edge $e(i)$.

Note that the incidence matrix depends on the choice of the bijections $e$ and $v$, 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

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.

Oriented incidence matrix for a finite directed graph

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

• 1 if vertex $v(j)$ is the target vertex of edge $e(i)$
• -1 if vertex $v(j)$ is the source vertex of edge $e(i)$
• 0 if vertex $v(j)$ is not incident on (i.e., does not equal one of the endpoints of) edge $e(i)$.

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.

One possible choice of orientation uses the ordering. Explicitly, if the vertex set bijection is $v:\{1,2,\dots ,n\}\to V(G)$, and there is an edge joining $v(i)$ and $v(j)$ with $i<j$, we assign vertex $i$ as the source of the edge and vertex $j$ 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

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