Incidence Matrix

The incidence matrix of a directed graph D is a p × q matrix where p and q are the number of vertices and edges respectively, such that if the edge leaves vertex, if it enters vertex and 0 otherwise (Note that many authors use the opposite sign convention.).

An oriented incidence matrix of an undirected graph G is the incidence matrix, in the sense of directed graphs, of any orientation of G. That is, in the column of edge e, there is one +1 in the row corresponding to one vertex of e and one −1 in the row corresponding to the other vertex of e, and all other rows have 0. All oriented incidence matrices of G differ only by negating some set of columns. In many uses, this is an insignificant difference, so one can speak of the oriented incidence matrix, even though that is technically incorrect.

The oriented or unoriented incidence matrix of a graph G is related to the adjacency matrix of its line graph L(G) by the following theorem:

A(L(G)) = B(G)^{T}B(G) - 2I_q\

where is the adjacency matrix of the line graph of G, B(G) is the incidence matrix, and is the identity matrix of dimension q.

The Kirchhoff matrix is obtained from the oriented incidence matrix M(G) by the formula

M(G) M(G)^{T}.

The integral cycle space of a graph is equal to the null space of its oriented incidence matrix, viewed as a matrix over the integers or real or complex numbers. The binary cycle space is the null space of its oriented or unoriented incidence matrix, viewed as a matrix over the two-element field.

Read more about Incidence Matrix:  Incidence Structures

Famous quotes containing the words incidence and/or matrix:

    Hermann Goering, Joachim von Ribbentrop, Albert Speer, Walther Frank, Julius Streicher and Robert Ley did pass under my inspection and interrogation in 1945 but they only proved that National Socialism was a gangster interlude at a rather low order of mental capacity and with a surprisingly high incidence of alcoholism.
    John Kenneth Galbraith (b. 1908)

    As all historians know, the past is a great darkness, and filled with echoes. Voices may reach us from it; but what they say to us is imbued with the obscurity of the matrix out of which they come; and try as we may, we cannot always decipher them precisely in the clearer light of our day.
    Margaret Atwood (b. 1939)