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)^{T}B(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.

Word Browser