# The Isomorphic Version of [PERSON]'s and [PERSON]'s Nestedness
## 2 The Discrepancy Problem for Isomorphic Matrices  
Let \(M\) be an \(m\times n\) bi-adjacency matrix with non-increasing row sums \((r_{1},\ldots,r_{m})\), and non-increasing column sums \((c_{1},\ldots,c_{n})\), and \(G\) the corresponding bipartite graph. Furthermore, let \(\mathcal{G}\) be the set of all isomorphic graphs of \(G\). Then, all bi-adjacency matrices corresponding to a graph \(G^{\prime}\in\mathcal{G}\) can be achieved by permuting columns and rows with equal sums in \(M\). We denote the set of these matrices by \(\mathcal{M}\). The discrepancy of \(M\) given by [PERSON] and [PERSON] [PERSON] and [PERSON] (2003) is the minimum number of shifts to achieve the corresponding Ferrers matrix \(F\) as described in the last section. We denote the discrepancy of \(M\) by \(disc(M)\). We now give the definition of the _isomorphic discrepancy_\(Id(M)\) of M, which is defined by  
\[Id(M):=min_{B\in\mathcal{M}}disc(B). \tag{1}\]  
In other words, we try to find a matrix in \(\mathcal{M}\) with minimal discrepancy. We also want to mention that this new metric should be invariant against the transposition of \(M\). This can be achieved by transposing \(M\) to its transposed matrix \(M^{t}\) and determining \(Id(M^{t})\). The _general isomorphic discrepancy_ of \(M\) is then the minimum value (or the mean value) of \(Id(M)\) and \(Id(M^{t})\). We here focus on \(Id(M)\) because the calculation of \(Id(M^{t})\) can be done analogously. A simple approach is to permute all columns and rows with equal sums, and to choose a permutation of \(M\) that yields the minimum discrepancy. This can lead to the determination of exponentially many possible permutations. Please observe that it is sufficient for our problem to permute columns in \(M\) and keep the rows fixed. The reason is that exchanging the order of rows with the same sums leads to exactly the same discrepancy because the corresponding rows of the Ferrers matrix are identical. Consider our Example 4. It can be seen that each permutation of the first three rows in \(M\) or \(M^{\prime}\) lead to the same kind of shifts, and so to the same discrepancy as before. Following this approach, we will not necessarily generate all matrices in \(\mathcal{M}\), but the subset \(I_{M}\) that consists of all matrices that were yielded by a permutation of columns in \(M\) with the same sum. Hence, matrices in \(I_{M}\) possess the whole range of possible discrepancies that occur for matrices in \(\mathcal{M}\). Hence, _it is sufficient to permute columns for the calculation of \(Id(M)\)_. More formally, we find  
\[Id(M)=min_{B\in\mathcal{M}}disc(B)=min_{B\in I_{M}}disc(B). \tag{2}\]  
Consider all matrices with row sums \((r_{1},\ldots,r_{m})\) and column sums \((c_{1},\ldots,c_{n})\). Then, it follows that all of them possess the same unique Ferrers matrix \(F\) with column sums \((c_{1}^{\prime},\ldots,c_{n}^{\prime})\). (Recall that the lists are non-increasing.) [PERSON] and [PERSON] showed [PERSON] and [PERSON] (2003) that there is always one matrix \(A\) with row sums \((r_{1},\ldots,r_{m})\) and column sums \((c_{1},\ldots,c_{n})\) that has _minimum possible discrepancy_\(disc(A)=\sum_{j=1}^{n}(c_{j}^{\prime}-c_{j})^{+}\), where \((a)^{+}:=\max\{a,0\}\) for \(a\in\mathbb{R}\). Matrix \(A\) can be found by moving in \(F\)\(1\) s from columns \(j\) with \(c_{j}^{\prime}-c_{j}>0\), to columns \(i\) with \(c_{i}^{\prime}-c_{i}<0\). Consider Example 5. **Example 5**. : _For matrix \(M:= \begin{pmatrix}1&1&1&0\\ 1&1&1&0\\ 1&1&1&0\\ 1&1&0&0\\ 1&0&0&1\\ 1&0&1&0\end{pmatrix} \), we have \(disc(M)=4\), and corresponding Ferrers matrix_  
\[F:= \begin{pmatrix}1&1&1&0\\ 1&1&1&0\\ 1&1&1&0\\ 1&1&0&0\\ 1&1&0&0\\ 1&1&0&0\\ 1&1&0&0\end{pmatrix} \text{. We construct matrix }A= \begin{pmatrix}1&0&1&1\\ 1&0&1&1\\ 1&0&1&1\\ 1&1&0&0\\ 1&1&0&0\\ 1&1&0&0\end{pmatrix} \text{ with }disc(A)=\sum_{j=1}^{n}(c_{j}^{\prime}-c_{j})^{+}=3\text{ by }\]  
_shifting three \(1\) s of the second column in \(F\) to the fourth column.