Incidence matrix - Definition and Overview

In mathematics, the incidence matrix of an undirected graph G is a p × q matrix <math>[b_{ij}]<math> where p and q are the number of vertices and edges respectively, such that <math>b_{ij} = 1<math> if the vertex <math>v_i<math> and edge <math>x_j<math> are incident and 0 otherwise.

The incidence matrix of a directed graph G is a p × q matrix <math>[b_{ij}]<math> where p and q are the number of vertices and edges respectively, such that <math>b_{ij} = -1<math> if the edge <math>x_j<math> leaves vertex <math>v_i<math>, <math>1<math> if it enters vertex <math>v_i<math> and 0 otherwise.

The incidence matrix is related to the adjacency matrix of a graph by the following theorem:

<math>

A(G) = B(G)^{T}B(G) - 2I_q <math>

where <math>A(G)<math> and <math>B(G)<math> are the adjacency matrix and incidence matrix respectively and <math>I_q<math> is the identity matrix of dimension q.

The cycle space of a graph is equal to the null space of its incidence matrix.

Example Usage of Incidence