# The Isomorphic Version of [PERSON]'s and [PERSON]'s Nestedness
## 2 The Discrepancy Problem for Isomorphic Matrices
However, the minimum discrepancy under all isomorphic matrices of \(M\) is \(4\), i.e., \(Id(M)=4\). This is true because each permutation \(\sigma\) of the last three columns of \(M\) leads to a matrix \(M^{\sigma}\) with \(disc(M^{\sigma})=4\). A discrepancy of \(3\) cannot be achieved by a permutation of columns from \(M\)._  
The set of all matrices with row sums \((r_{1},\ldots,r_{m})\) and column sums \((c_{1},\ldots,c_{n})\) can be partitioned in isomorphic matrix sets \(\mathcal{M}_{i}\). Example 5 shows that not all sets possess a matrix \(A\) with minimum possible discrepancy. If this had been the case, we would already know the value \(Id(M)\) for each matrix. Unfortunately, it is not the case. We want to develop a simple formula to calculate the discrepancy of a given matrix. We need this formula later to devise an approach for the isomorphic version. Notice that a shift in a matrix \(M\) will always be applied when \(F_{i,j}=1\) and \(M_{i,j}=0\). Since \(M\) and \(F\) have identical row sums, and due to the construction of \(F\), there must always be an index \(j^{\prime}>j\) with \(F_{i,j^{\prime}}=0\) and \(M_{i,j^{\prime}}=1\). In matrices of our Examples 4 and 5, we marked these \(0\) s and \(1\) s. This means that the number of absences of \(1\) s in \(M\), when they are present in \(F\), correspond to the number of minimum shifts \(disc(M)\). We define the difference of the \(j\)th columns \(A_{j}\) and \(A_{j}^{\prime}\) of \(m\times n\)\(0,1\)-matrices \(A\) and \(A^{\prime}\) by  
\[(A_{j}-A_{j}^{\prime}):=\sum_{i=1}^{m}(A_{i,j}-A_{i,j}^{\prime})^{+}. \tag{3}\]  
Back to our problem, we find \((F_{j}-M_{j})\geq c_{j}^{\prime}-c_{j}\) for all \(j\). The reason is that a column \(F_{j}\) has \(c_{j}^{\prime}\)\(1\) s and a column \(M_{j}\) has \(c_{j}\)\(1\) s. This means that the minimum difference of both columns happens if all \(1\) s in \(M_{j}\) also occur in \(F_{j}\). Then, \((F_{j}-M_{j})=c_{j}^{\prime}-c_{j}\). Consider in Example 4 the third columns of \(M\), \(M^{\prime}\) and \(F\). \(M^{\prime}\) has all \(1\) s of \(F\), whereas \(M\) has only two of them. Hence, \(F_{3}-M_{3}=1>0=c_{3}^{\prime}-c_{3}\) but \(F_{3}-M_{3}^{\prime}=0=c_{3}^{\prime}-c_{3}\). In cases where you find a \(1\) in \(M_{j}\), which does not occur in \(F_{j}\), this \(1\) needs to be shifted to a 'left' column \(j^{\prime}\) where \(F\) has a \(1\) and \(M\) a \(0\). A \(1\) from a 'right' column \(j^{\prime\prime}\) in \(M\) has to be shifted to \(M_{j}\) to achieve the \(c_{j}^{\prime}\)\(1\) s in \(F\). In Example 4, this is the case for \(M_{6,3}\). We put this connection in another formula for the discrepancy. **Proposition 1**. : _Let \(M\) be an \(m\times n\)\(0,1\)-matrix with non-increasing row sums \((r_{1},\ldots,r_{m})\) and non-increasing column sums \((c_{1},\ldots,c_{n})\). Let \(F\) be the corresponding Ferrers matrix. Then, the minimum number of shifts \(disc(M)\) to achieve \(F\) from \(M\) can be calculated by \(disc(M)=\sum_{j=1}^{n}(F_{j}-M_{j})\)._  
Proof. : The proof is by induction on the number \(n\) of columns. For one column, we have \(M=F\) and so \(disc(M)=0\) and \((F_{1}-M_{1})=0\). We assume that \(disc(M)=\sum_{j=1}^{k}(F_{j}-M_{j})\) holds for all matrices with \(m\) rows and \(k\leq n-1\) columns (induction hypothesis IH). Let us now consider a matrix an \(m\times n\) matrix \(M\). Notice that \((F_{n}-M_{n})=0\) for each matrix \(M\) and its corresponding Ferrers matrix \(F\) due to the construction of \(F\). In column \(n-1\) of \(M\), we consider the set \(I\) of all indices \(i\) where \(F_{i,n-1}=1\) and \(M_{i,n-1}=0\). Due to the construction of a Ferrers matrix, and since \(F\) and \(M\) have equal row sums, we find for all \(i\in I\) that \(F_{i,n}=0\) and \(M_{i,n}=1\). We construct matrix \(B\) by exchanging, for all indices \(i\in I\), all entries \(M_{i,n-1}=0\) to \(1\), and all corresponding entries \(M_{i,n}=1\) to \(0\). Basically, we apply \(|I|\) shifts from the \(n\)th column to the \((n-1)\)th column.