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 isa 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.

This article is licensed under the GNU Free Documentation License. It uses material from Wikipedia article. Browse Wikipedia for more information.