Incidence matrix

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