# The Isomorphic Version of [PERSON]'s and [PERSON]'s Nestedness
## 2 The Discrepancy Problem for Isomorphic Matrices
Then, the isomorphic discrepancy of matrix \(M\) is_  
\[Id(M)=\sum_{i=1}^{k}\left(\min_{\sigma_{i}\in\Sigma_{i}}\sum_{j:c_{j}=x_{i}}(F_ {j}-M_{j}^{\sigma_{i}})\right).\]  
Proof: Since the isomorphic discrepancy is the minimum discrepancy in the set of all matrices in \(I_{M}\) (Equation (2)), and for each matrix \(B\in I_{M}\) there exists a permutation \(\sigma=\circ_{i=1}^{k}\sigma_{i}\) with \(\sigma\in\Sigma\) and \(B=M^{\sigma}\), we get for the isomorphic discrepancy of \(M\)  
\[Id(M)\stackrel{{ Equation(2)}}{{=}}min_{B\in I_{M}}disc(B)=min_{ \sigma\in\Sigma}disc(M^{\sigma})\stackrel{{ Proposition \ref{prop:1}}}{{=}}\min_{\sigma\in\Sigma}\left(\sum_{j=1}^{n}(F_{j}-M_{j}^{ \sigma})\right). \tag{4}\]Since each \(\sigma\) is the convolution of \(k\) permutations \(\sigma_{i}\) that permute only the column indices with same sums (\(\sigma=\sigma_{i=1}^{k}\sigma_{i}\)), we can rewrite  
\[\left(\sum_{j=1}^{n}(F_{j}-M_{j}^{\sigma})\right)=\sum_{i=1}^{k}\left(\sum_{j:x _{j}=x_{i}}(F_{j}-M_{j}^{\sigma_{i}})\right)\,.\]  
Together with Equation (4), and since \(\sigma\) permutes columns with each fixed sum \(x_{i}\)_independently_, we get  
\[Id(M)\stackrel{{ Equation(4)}}{{=}}\min_{\sigma\in\Sigma}\sum_{i= 1}^{k}\left(\sum_{j:x_{j}=x_{i}}(F_{j}-M_{j}^{\sigma_{i}})\right)=\sum_{i=1}^ {k}\left(\min_{\sigma_{i}\in\Sigma_{i}}\sum_{j:x_{j}=x_{i}}(F_{j}-M_{j}^{ \sigma_{i}})\right)\,.\]  
Proposition 2 states that we need to find for each sub-matrix \(M_{i}\) in \(M\) with fixed column sums \(x_{i}\) a column order (a permutation \(\sigma_{i}\)) that minimizes the following sum:  
\[w(\sigma_{i}):=\sum_{j:c_{j}=x_{i}}(F_{j}-M_{j}^{\sigma_{i}}). \tag{5}\]  
We transform the calculation of \(Id(M)\)_for each sub-matrix \(M^{i}\)_(\(i\in\{1,\ldots,k\}\)) of \(M\) to the determination of _minimum weighted perfect matching problem_ in a labelled _weighted complete bipartite graph_ (A bipartite graph \(G=(U,V,E)\) is called _complete_ if and only if each pair of vertices \(u,v\) with \(u\in U\) and \(v\in V\) is connected by an edge, i.e., \(\{u,v\}\in E\). If we have a weight function \(w:E\mapsto\mathbb{R}\) which assigns to every edge in \(G\) a weight, then \(G\) is called _weighted_\(G_{i}=(U_{M^{i}},V_{F^{i}},E_{i})\).). In \(G_{i}\), each vertex \(u_{j}\in U_{M^{i}}\) corresponds to a column \(M_{j}^{i}\) of \(M^{i}\) where \(j\in\{s_{1}+s_{2}+\cdots+s_{i-1}+1,\ldots,s_{1}+s_{2}+\cdots+s_{i-1}+s_{i}\}\). Moreover, each vertex \(v_{j}\in V_{F^{i}}\) corresponds to a column \(F_{j}\) of the Ferrers matrix \(F\) of \(M\) where \(j\in\{s_{1}+s_{2}+\cdots+s_{i-1}+1,\ldots,s_{1}+s_{2}+\cdots+s_{i-1}+s_{i}\}\), i.e., we consider the exactly same indices of columns in \(F\) as in sub-matrix \(M^{i}\). For simplicity we denote vertices \(u_{j}\) by \(M_{j^{\prime}}^{i}\), or, \(v_{j}\) by \(F_{j}\), respectively. We assign each edge \(\{M_{j^{\prime}}^{i},F_{j^{\prime}}\}\in E_{i}\) the weight \(w(M_{j^{\prime}}^{i},F_{j^{\prime}}):=(F_{j}-M_{j^{\prime}}^{i})\). Now, we calculate a minimum weighted perfect matching \(P^{i}=\{\{M_{i}^{i},F_{j_{1}}\},\ldots,\{M_{i^{\prime}}^{i},F_{j_{i}}\}\}\) in each \(G_{i}\). Hence, \(P^{i}\) minimizes Equation (5). Moreover, an edge \(\{M_{\ell^{\prime}}^{i},F_{j_{\ell}}\}\) in \(P^{i}\) tells us that we have to put column \(\ell\) in \(M\) on position \(j_{\ell}\). That is, \(P^{i}\) calculates how to permute the columns in \(M^{i}\) such that the discrepancy is minimal. Consider Example 6. **Example 6**. : _For the \(3\times 5\)-matrix \(M:= \begin{pmatrix}1&1&0&1&0\\ 0&1&1&0&0\\ 1&0&0&0&1\end{pmatrix} \) with \(disc(M)=3\), we get \(3\times 2\)-sub-matrix \(M^{1}:= \begin{pmatrix}1&1\\ 0&1\\ 1&0\end{pmatrix} \) with column sums \(2\), and \(3\times 3\)-matrix \(M^{2}:= \begin{pmatrix}0&1&0\\ 1&0&0\\ 0&0&1\end{pmatrix} \) with column sums \(1\). Hence, we have to construct two complete bipartite graphs \(G_{1}=(U_{M^{1}},V_{F^{1}},E_{1})\) and \(G_{2}=(U_{M^{2}},V_{F^{2}},E_{2})\). The Ferrers matrix for \(M\) is \(F= \begin{pmatrix}1&1&1&0&0\\ 1&1&0&0&0\\ 1&1&0&0&0\end{pmatrix} \).