In mathematics, an incidence matrix is a logical matrix that shows the relationship between two classes of objects, usually called an incidence relation. If the first class is X and the second is Y, the matrix has one row for each element of X and one column for each mapping from X to Y. The entry in row x and column y is 1 if the vertex x is part of (called incident in this context) the mapping that corresponds to y, and 0 if it is not. There are variations; see below.

Incidence matrix is a common graph representation in graph theory. It is different to an adjacency matrix, which encodes the relation of vertex-vertex pairs.

In graph theory an undirected graph has two kinds of incidence matrices: unoriented and oriented.

The unoriented incidence matrix (or simply incidence matrix) of an undirected graph is a ${\displaystyle n\times m}$ matrix B, where n and m are the numbers of vertices and edges respectively, such that

For example, the incidence matrix of the undirected graph shown on the right is a matrix consisting of 4 rows (corresponding to the four vertices, 1–4) and 4 columns (corresponding to the four edges, ${\displaystyle e_{1},e_{2},e_{3},e_{4}}$):

If we look at the incidence matrix, we see that the sum of each column is equal to 2. This is because each edge has a vertex connected to each end.

The incidence matrix of a directed graph is a ${\displaystyle n\times m}$ matrix B where n and m are the number of vertices and edges respectively, such that

(Many authors use the opposite sign convention.)