Incidence matrix

Definition

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)$. The incidence matrix, also called the unoriented incidence matrix, of $G$ is a $m\times n$ matrix defined as follows: The $(i,j)^{th}$ entry of the matrix is defined to be:

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

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)$. The incidence matrix, also called the oriented incidence matrix, of $G$ is a $m\times n$ matrix defined as follows: The $(i,j)^{th}$ entry of the matrix is defined to be:

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

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.