Namespaces
Variants
Actions

Incidence matrix

From Encyclopedia of Mathematics
Jump to: navigation, search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

2020 Mathematics Subject Classification: Primary: 05B20 [MSN][ZBL]

A matrix encoding the relation defining an incidence structure, typically in the finite case.

An incidence system $S = (A,\mathfrak{B},I)$ consists of two sets $A$ and $\mathfrak{B}$ with an incidence relation $I$ between their elements, which is written as $a\,I\,B$ for $a \in A$, $B \in \mathfrak{B}$. In this case one says that the element $a$ is incident with $B$, or that $B$ is incident with $a$. If $A = \{a_1,\ldots,a_n\}$ and $\mathfrak{B} = \{B_1,\ldots,B_m\}$ are finite sets, then the incidence matrix $\Sigma$, where $\Sigma_{ij} = 1$ if $a_i\,I\,B_j$, and $\Sigma_{ij} = 0$ otherwise. The matrix $\Sigma$ determines $S$ up to an isomorphism.

A hypergraph $(V,\mathcal{E})$ consists of a vertex set $V$ and a family of edges $\mathcal{E}$ each of which is a subset of $V$. A vertex $v \in V$ is incident with an edge $E \in \mathcal{E}$ if $v \in E$, so a hypergraph is an incidence system in which the relation is membership. As before, if $V = \{v_1,\ldots,v_n\}$ and $\mathcal{E} = \{E_1,\ldots,E_m\}$ are finite sets, then the incidence matrix $\Sigma$, where $\Sigma_{ij} = 1$ if $v_i \in E_j$, and $\Sigma_{ij} = 0$ otherwise.

An unoriented graph may be regarded as a case of a hypergraph in which all edges are of size 1 (if loops are allowed) or 2. A directed graph $(V,\mathcal{E})$ consists of a vertex set $V$ and a family of edges $\mathcal{E}$ each of which is an ordered pair of $V$; if $(x,y) \in \mathcal{E}$ we say that the edge is directed from $x$ to $y$. Again, if $V = \{v_1,\ldots,v_n\}$ and $\mathcal{E} = \{E_1,\ldots,E_m\}$ are finite sets, then the incidence matrix $\Sigma$ has entries $0,\pm 1$ defined by $$ \Sigma_{ij} = \begin{cases} +1 & \text{if}\, E_j\,\text{is directed from}\,v_i \\ -1 & \text{if}\, E_j\,\text{is directed to}\,v_i \\ 0 & \text{otherwise} \end{cases}\ . $$

In the case of graphs, the product $L = \Sigma\Sigma^\top$ is the graph Laplacian. The off-diagonal entries $L_{ij}$ count (with sign) the number of edges going between $v_i$ and $v_j$ and the diagonal entries $L_{ii}$ count (without sign) the total number of edges going from or to $v_i$. Even for undirected graphs, it may be convenient to assign an arbitrary orientation to each edge and consider the oriented incidence matrix. In this case we have $L = D - A$ where $D$ is a diagonal matrix encoding the degree of each vertex and $A$ is the undirected adjacency matrix.

References

  • B. Bollobas, Graph Theory, Graduate Texts in Mathematics 63 Springer (1979) ISBN 3-540-90399-2
  • Marshall Hall jr, Combinatorial Theory, Wiley Classics Library 71 (2nd edition) John Wiley & Sons (2011) ISBN 1118031113 Zbl 0907.05002
How to Cite This Entry:
Incidence matrix. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Incidence_matrix&oldid=54565