# The Isomorphic Version of [PERSON]'s and [PERSON]'s Nestedness
## 1 Introduction  
In applied fields like ecology, a \(0,1\)-matrix \(M\) often represents the presence or absence of certain relationships between species or objects, for example, which bee species pollinates which plants or the occurrence and absence of species on several islands. \(M\) is often called a _contingency table_. Such a matrix \(M\) can represent a bipartite graph (A bipartite graph \(G=(U,V,E)\) consists of two disjoint vertex sets \(U\) and \(V\) such that all edges are of the form \(\{u,v\}\), where \(u\in U\) and \(v\in V\)). Connections of bees and plants are given by edges. Matrix \(M\) is then called a _bi-adjacency matrix_. (For a bipartite graph \(G=(U,V,E)\) with \(m:=|U|\) and \(n:=|V|\), we construct its \(m\times n\)_bi-adjacency matrix_\(M\) as follows: rows \(1,\ldots,m\) represent vertices \(u_{1},\ldots,u_{m}\) in \(U\), and columns \(1,\ldots,n\) correspond to vertices \(v_{1},\ldots,v_{n}\) in \(V\). If edge \(\{u_{i},v_{j}\}\in E\), then we set \(M_{i,j}=1\); otherwise, we have \(M_{i,j}=0\).) Ecologists call a matrix _nested_ if we find for every row pair \(i,j\) in \(M\) the following condition; if \(i\) has equal or a smaller number of \(1\) s than \(j\) then \(M_{i,k}=1\) if and only if \(M_{j,k}=1\). Consider in Figure 1 the nested matrix \(N\) that represents the relationships between bee and plant species, and their corresponding bipartite graph. The term _nestedness_ has already been introduced in 1937 by [PERSON] [1]. A comprehensive history, discussion, and a definition of nestedness is given by [PERSON] et al. [2]. They describe nestedness  
Figure 1: A bipartite graph and its bi-adjacency matrix \(N\). Matrix \(N\) is nested because each bee pollinates the same plants as all bees which pollinate more or an equal number of plants. as follows: \"In a nested pattern, the species composition of small assemblages is a nested subset of the species composition of large assemblages\". Interpreting nestedness regarding biological properties in networks is quite interesting. In matrix \(N\) of Figure 1 bees b, c, and d pollinate less plants than bee a. However, it does not happen that these bees pollinate other plants than bee a. In a nested matrix, we find, for an arbitrary pair of bee species, that the bee species with less than or an equal number of pollinated plants always pollinates a subset of the plant species that is pollinated from the other one. Hence, it cannot happen that a specialized bee pollinates other plants than a bee which pollinates more plant species. An opposite scenario is that all bee pairs pollinate pairwise different plants like in matrix \(M\) of Example 1. **Example 1**. : _Matrix \(M= \begin{array}{cccc}A&B&C&D\\ a&b\\ c&0&1&0&0\\ 0&0&1&0\end{array} \) is not nested since each bee pollinates a different plant than every other bee._  
Imagine the extinction of a specialized bee in a nested matrix. Since this bee only pollinates plants, which are also pollinated from more generalized bees (bees which pollinate more plants), the pollination for all plants is still preserved. Even the extinction of a generalized bee would preserve the pollination of plants that are still pollinated by specialized bees. In contrast, the extinction of bee a in matrix \(M\) of Example 1 would lead to the extinction of plants \(A\) and \(D\) because no other bee can provide this service for these plants. Real data matrices are mostly not nested (which can be seen in our experimental Section 3). However, it seems that understanding \"how much\" ecological matrices are nested is important due to the fact that nestedness has been suggested as key to the stability of complex ecological systems. More information about stability and nestedness can be found, for example, in the following articles [3; 4; 5; 6]. Notice that it is always possible to exchange columns and rows in a given matrix such that one finds non-increasing column and row sums. This indeed results in a different matrix. Anyway, it contains exactly the same relationships as before, and let us consider Example 2.