Incidence matrix

Summary

The incidence matrix of a graph records which vertices lie on which edges. It has a row for each vertex, a column for each edge, and a nonzero entry where the vertex is an end of the edge. In the oriented version the two ends get opposite signs, and the product of the matrix with its transpose is the Laplacian matrix. More generally, an incidence matrix describes any incidence relation between two finite sets, such as points and blocks of a design.