The incidence matrix of a Graph G is a matrix of dimensions where p and q are the number of vertices and edges respectively, such that if the vertex and edge are incident and 0 otherwise.

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

where and are the adjacency matrix and incidence matrix respectively and is the identity matrix of dimension q.