In mathematics, the incidence matrix of an undirected graph G is a p × q matrix [bij] where p and q are the number of vertices and edges respectively, such that bij = 1 if the vertex vi and edge xj are incident and 0 otherwise.
The incidence matrix of a directed graph G is a p × q matrix [bij] where p and q are the number of vertices and edges respectively, such that bij = - 1 if the edge xj leaves vertex vi, 1 if it enters vertex vi and 0 otherwise.
The incidence matrix is related to the adjacency matrix of a graph by the following theorem:
- A(G) = B(G)TB(G) - 2Iq
where A(G) and B(G) are the adjacency matrix and incidence matrix respectively and Iq is the identity matrix of dimension q.
The cycle space of a graph is equal to the null space of its incidence matrix.
The incidence matrix of an incidence structure C is a p × q matrix [bij] where p and q are the number of points and lines respectively, such that bij = 1 if the point pi and line Lj are incident and 0 otherwise. In this case the incidence matrix is also a biadjacency matrix of the Levi graph of the structure.
