Incidence matrix

In mathematics, the incidence matrix of an undirected graph G is a p × q matrix [b_ij] where p and q are the number of vertices and edges respectively, such that b_ij = 1 if the vertex v_i and edge x_j are incident and 0 otherwise.

The incidence matrix of a directed graph G is a p × q matrix [b_ij] where p and q are the number of vertices and edges respectively, such that b_ij = - 1 if the edge x_j leaves vertex v_i, 1 if it enters vertex v_i 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) - 2I_q

where A(G) and B(G) are the adjacency matrix and incidence matrix respectively and I_q 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 [b_ij] where p and q are the number of points and lines respectively, such that b_ij = 1 if the point p_i and line L_j are incident and 0 otherwise. In this case the incidence matrix is also a biadjacency matrix of the Levi graph of the structure.