Incidence Matrix

The incidence matrix of a directed graph D is a p × q matrix where p and q are the number of vertices and edges respectively, such that if the edge leaves vertex, if it enters vertex and 0 otherwise (Note that many authors use the opposite sign convention.).

An oriented incidence matrix of an undirected graph G is the incidence matrix, in the sense of directed graphs, of any orientation of G. That is, in the column of edge e, there is one +1 in the row corresponding to one vertex of e and one −1 in the row corresponding to the other vertex of e, and all other rows have 0. All oriented incidence matrices of G differ only by negating some set of columns. In many uses, this is an insignificant difference, so one can speak of the oriented incidence matrix, even though that is technically incorrect.

The oriented or unoriented incidence matrix of a graph G is related to the adjacency matrix of its line graph L(G) by the following theorem:

where is the adjacency matrix of the line graph of G, B(G) is the incidence matrix, and is the identity matrix of dimension q.

The Kirchhoff matrix is obtained from the oriented incidence matrix M(G) by the formula

The integral cycle space of a graph is equal to the null space of its oriented incidence matrix, viewed as a matrix over the integers or real or complex numbers. The binary cycle space is the null space of its oriented or unoriented incidence matrix, viewed as a matrix over the two-element field.