# The Isomorphic Version of [PERSON]'s and [PERSON]'s Nestedness
## 1 Introduction
We propose an extended metric based on the discrepancy to repair this problem. We define for a matrix \(M\) set \(\mathcal{M}\), which contains all matrices that can be achieved by permuting in \(M\) columns and rows with identical sums. (Notice, if we consider all matrices in \(\mathcal{M}\) as bi-adjacency matrices, then the corresponding set of bipartite graphs is isomorphic. Consider a bipartite graph \(G=(U,V,E)\) in this set. The definition of isomorphic graphs allows only the permutation of vertex labels with the same vertex degree in \(U\) or \(V\). This corresponds to the permutation of columns and rows in the corresponding bi-adjacency matrix with the same sums.) However, changing the row order in \(M\) would not change the discrepancy of \(M\) because the number of minimal shifts in each row stays the same. Finding an optimal labelling for a given bipartite graph \(G\), such that its bi-adjacency matrix has a minimum discrepancy under all bi-adjacency matrices of isomorphic graphs of \(G\), can be done by _only permuting the columns of its bi-adjacency matrix_. We define the _isomorphic discrepancy_ of \(M\) as the minimum number of shifts under all matrices in \(\mathcal{M}\) to achieve \(F\). In other words, the _isomorphic discrepancy_ finds an optimal labelling for a bipartite graph regarding a minimum number of shifts in its bi-adjacency matrix to achieve its nested matrix \(F\). In Example 4, the discrepancy of \(M\) would be overestimated or the nestedness be underestimated, respectively. We show that the isomorphic discrepancy for a matrix \(M\) can be calculated in transforming our problem into less than \(n\)_minimum perfect weighted matching problems in a bipartite graph._ (Given a bipartite graph, \(G=(U,V,E)\) with \(|U|=|V|\), and weight function \(w:E\mapsto\mathbb{R}\). The _perfect matching problem_ asks for a subset \(M\subset E\) of edges such that each vertex of \(G\) is in exactly one edge of \(M\). The _minimum perfect weighted matching problem_ asks for a perfect matching \(M\) minimizing \(w(M)=\sum_{m_{i}\in M}w(m_{i})\).) More clearly, we construct **for each fixed column sum**\(s\) a bipartite graph \(G_{s}\)**separately**. Each edge \(\{u_{i},v_{j}\}\) in a minimum perfect weighted matching of \(G_{s}\) tells us that column \(i\) in matrix \(M\) needs to be moved on position \(j\). In the resulting matrix, all columns with sum \(s\) are reordered without violating the non-increasing column sums property. We repeat this approach whenever there exist at least two columns with the same column sum. The resulting matrix is a matrix in \(I_{M}\) with a minimum discrepancy. One of the most important books about matching theory is from [PERSON] (2003). One suitable algorithm for our scenario is from [PERSON] (2003), which achieves an \(O(n^{3})\) asymptotic running time, if we follow our approach. Please observe that there exist other approaches and assumptions of what a nested matrix \(N\) for \(M\) has to look like. One approach is to find an \(M^{\prime}\in\mathcal{M}\) such that a minimal number of 0 s can be replaced by 1 s to become nested. This problem is known as the _minimal chain completion problem_ and was shown to be NP-complete in 1981 by [PERSON] (1981). (It is an open problem whether there is an algorithm to find a solution in polynomial asymptotic running time for NP-complete problems. For more information consider the classical book of [PERSON] and [PERSON] [PERSON] (2003).) The opposite problem is to delete a minimal number of 0s in \(M^{\prime}\in\mathcal{M}\) to achieve a nested matrix that is also NP-complete (exchange the rules of 1 s and 0 s to see this). An approximation algorithm was given in the Phd-thesis of [PERSON] in 2011 [PERSON] (2011). There are different definitions of nestedness in the ecological community, and several procedures to compute it. For an overview, see the nestedness guide [PERSON] et al. (2011) which also includes the discrepancy of Brualdi and Sanderson (there called BR).