Incidence Matrices

Definition: For a graph $G$ on vertex set $V(G) = \left\{ x_1, x_2, ..., x_n\right\}$ and edge set $V(G) = \left\{ e_1, e_2, ..., e_m\right\}$, then $I(G)$ is the $n \: x \: m$ incidence matrix if $I(i , j) = 1$ whenever $x_i$ and $e_j$ are incident.

Let's first look at an example of an incidence matrix example for the following graph where we put a "$1$" whenever a vertex is incident to an edge, and we put a "$0$" if that vertex is not incident to that edge. We thus obtain the following table:

	Edge $1$	Edge $2$	Edge $3$	Edge $4$	Edge $5$	Edge $6$	Edge $7$
Vertex $1$	$1$	$0$	$0$	$0$	$1$	$0$	$0$
Vertex $2$	$1$	$1$	$0$	$0$	$0$	$1$	$1$
Vertex $3$	$0$	$1$	$1$	$0$	$0$	$0$	$0$
Vertex $4$	$0$	$0$	$1$	$1$	$0$	$0$	$1$
Vertex $5$	$0$	$0$	$0$	$1$	$1$	$1$	$0$

So the corresponding incidence matrix for the following graph can be created by turning the table into a matrix as follows:

(1)

\begin{align} I(G) = \begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 0 \end{bmatrix} \end{align}

We can also look at incidence matrices for digraphs, for example, the following digraph matches the incidence matrix below it:

(2)

\begin{align} I(G) = \begin{bmatrix} 1 & 0 & 0 & 0 & -1 & 0 & 0 \\ 0 & 0 & 0 & 0 & -1 & -1& 0 \\ 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & -1 & -1 & 0 & 0 & 0 & 0 \\ -1 & 1 & 0 & 0 & 0 & 1 & 0 \end{bmatrix} \end{align}

Notice that in directed graphs, we correspond the rows of the incidence matrix as vertices, but the columns of the incidence matrix is arcs. $1$s refer to arcs incident from a vertex, while "$-1$"s refer to arcs incident to a vertex. $0$s of course refer to vertices and arcs that aren't incident at all.

Let's now look at some properties of incidence matrices.

Proposition 1: If $G$ is a graph, $I(G)$ is the incidence matrix of $G$, $V(G)$ is the vertex get of $G$, and $E(G)$ is the edge/arc set of $G$, then the incidence matrix is a $\mid V(G) \mid \times \mid E(G) \mid$ sized matrix.

The incidence matrix is an $n \times m$ matrix that results from the vertices listed as the rows of the matrix and the edges/arcs listed as the columns of the matrix. Hence the size of the incidence matrix $I(G)$ is $\mid V(G) \mid \times \mid E(G) \mid$, also denoted as $I(G)_{\mid V(G) \mid \times \mid E(G) \mid}$, or rather $n = \mid V(G) \mid$ and $m = \mid E(G) \mid$.

Note that if $\mid V(G) \mid = \mid E(G) \mid$, then $I(G)$ is a square matrix.

Proposition 2: If $G$ is a not a digraph and $I(G)$ is the incidence matrix of $G$ where $x_i \in V(G)$ then $\sum_{k = 1}^{m} (I)_{ik} = (I)_{i1} + (I)_{i2} + ... + (I)_{im} = \deg(x_i)$ (the sum of all entries in row $i$ is equal to the degree of vertex $x_i$).

Each row in $I(G)$ corresponds to all edges incident with the vertex of that row, so the sum of the entries in any row is equal to the degree of the vertex represented by that row.

Proposition 3: If $G$ is not a digraph, and $I(G)$ is the incidence matrix of $G$, then $\sum_{i=1}^{n} ( \sum_{k = 1}^{m} (I)_{ik} ) = \sum_{x \in V(G)} \deg(x)$ (the sum of all entries in the incidence matrix of $G$ is equal to the sum of all vertex degrees in $G$).

Proposition 4: If $G$ is a digraph, and $I(G)$ is the incidence matrix of $G$, then $\sum_{(I)_{ik} = 1} 1 = \deg ^+ (x_i)$ (the sum of all elements in row $i$ that are $1$ is equal to the out-degree of vertex $x_i$), and $\sum_{(I)_{ik} = -1} -1 = \deg ^- (x_i)$(the sum of all elements in row $i$ that are $-1$ is equal to the in-degree of vertex $x_i$).

For any row of the incidence matrix for a digraph, any $1$ corresponds to an arc incident from the vertex corresponding to that row, and any $-1$ corresponds to an arc incident to the vertex corresponding to that row. The sum of all $1$s will thus equal the out-degree of that vertex, and the sum of all $-1$s will thus equal the in-degree of that vertex.