TOPICS
Search

Incidence Matrix


IncidenceMatrix

The incidence matrix of a graph gives the (0,1)-matrix which has a row for each vertex and column for each edge, and (v,e)=1 iff vertex v is incident upon edge e (Skiena 1990, p. 135). However, some authors define the incidence matrix to be the transpose of this (including the standard form of the embedding-encoding generalization known as the rigidity matrix), with a column for each vertex and a row for each edge. The physicist Kirchhoff (1847) was the first to define the incidence matrix.

The incidence matrix of a graph (using the first definition) can be computed in the Wolfram Language using IncidenceMatrix[g]. Precomputed incidence matrices for a many named graphs are given in the Wolfram Language by GraphData[graph, "IncidenceMatrix"].

The incidence matrix C of a graph and adjacency matrix L of its line graph are related by

 L=C^(T)C-2I,
(1)

where I is the identity matrix (Skiena 1990, p. 136).

For a k-D polytope Pi_k, the incidence matrix is defined by

 eta_(ij)^k={1   if Pi_(k-1)^i belongs to Pi_k^j; 0   if Pi_(k-1)^i does not belong to Pi_k^j.
(2)

The ith row shows which Pi_ks surround Pi_(k-1)^i, and the jth column shows which Pi_(k-1)s bound Pi_k^j. Incidence matrices are also used to specify projective planes. The incidence matrices for a tetrahedron ABCD are

eta^01ABC
11111
eta^1ADBDCDBCACAB
A100011
B010101
C001110
D111000
eta^2BCDACDABDABC
AD0110
BD1010
CD1100
BC1001
AC0101
AB0011
eta^3ABCD
BCD1
ACD1
ABD1
ABC1

See also

Adjacency Matrix, k-Chain, k-Circuit, Integer Matrix, Rigidity Matrix

Explore with Wolfram|Alpha

References

Bruck, R. H. and Ryser, H. J. "The Nonexistence of Certain Finite Projective Planes." Canad. J. Math. 1, 88-93, 1949.Kirchhoff, G. "Über die Auflösung der Gleichungen, auf welche man bei der untersuchung der linearen verteilung galvanischer Ströme geführt wird." Ann. Phys. Chem. 72, 497-508, 1847.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 135-136, 1990.

Referenced on Wolfram|Alpha

Incidence Matrix

Cite this as:

Weisstein, Eric W. "Incidence Matrix." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/IncidenceMatrix.html

Subject classifications