# The Isomorphic Version of [PERSON]'s and [PERSON]'s Nestedness
## 1 Introduction
**Example 2**. : _Exchanging columns 2 and 3 in matrix \(N\) of Figure 1 leads to matrix \(N^{\prime}= \begin{array}{cccc}A&C&B\\ b&\left(\begin{array}{cccc}1&1&1\\ 1&0&1\\ 1&0&1\\ 1&0&0\end{array}\right),\\ d&\left(\begin{array}{cccc}1&1&1\\ 1&0&1\\ 1&0&0\end{array}\right),\end{array} \) which does not fulfill the property of non-increasing column sums. Moreover, in this matrix, it is more difficult to recognize nestedness because rows 2, 3 and 4 do not consist of consecutive \(1\)s followed by consecutive \(0\)s._  
However, if columns and rows are ordered in regards to non-increasing row and column sums, it is easy to decide whether a given matrix is nested or not. We give a mathematical definition for nestedness. **Definition 1** (nestedness). : _Let \(M\) be an \(m\times n\)\(0,1\)-matrix where the columns \(1,\ldots,n\) and rows \(1,\ldots,m\) are sorted such that we find for the column sums \(c_{1}\geq c_{2}\geq\cdots\geq c_{n}\), and for the row sums \(s_{1}\geq s_{2}\geq\cdots\geq s_{m}\). Then, matrix \(M\) is called nested if and only if each of the \(m\) rows start with consecutive \(1\)s followed by consecutive \(0\)s._  
In graph theory, a nested matrix is usually referred to as _Ferrers matrix_[7]. We will use equivalently the two terms. Moreover, a whole theory around Ferrers matrices exists, and it is worth reconsidering theoretical insights regarding the nestedness metrics. 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})\). The corresponding _Ferrers matrix \(F\) is the matrix where each row \(i\) of \(F\) starts with \(r_{i}\)\(1\) s followed by \(n-r_{i}\)\(0\) s. It can be achieved in several _shifts_. A shift is the movement of a \(1\) in a row from a right to a left column with entry \(0\), i.e., it is an exchange of entries \(M_{i,j}=1\) and \(M_{i,j^{\prime}}=0\) for \(j>j^{\prime}\) leading to the matrix \(M^{\prime}\) with \(M^{\prime}_{i,j}=0\), \(M^{\prime}_{i,j^{\prime}}=1\) and \(M^{\prime}_{k,\ell}=M_{k,\ell}\) for all index pairs of \(M\) with \((k,\ell)\
eq(i,j)\) or \((k,\ell)\
eq(i,j^{\prime})\). The corresponding Ferrers matrix of matrix \(M\) in Example 1 can be seen in Example 3. **Example 3**. : _Matrix \(F= \begin{array}{cccc}A&B&C&D\\ b&\left(\begin{array}{cccc}1&1&0&0\\ 1&0&0&0\\ 1&0&0&0\\ 1&0&0&0\\ \end{array}\right)\end{array} \) is the corresponding Ferrers matrix of matrix \(M\) in Example 1. It can be achieved by shifting \(1\) s to the left. Matrix \(F\) has the same row sums like \(M\) but different column sums._  
Example 3 shows that Ferrers matrix \(F\) has the same row sums as \(M\) but different column sums. They can be calculated in counting for each row \(i\) in \(M\) the number of rows which have at least row sum \(i\). **Remark 1**. : _Let \(M\) be an \(m\times n\)\(0,1\)-matrix \(M\) where the columns \(1,\ldots,n\) and rows \(1,\ldots,m\) are sorted such that we find for the column sums \(c_{1}\geq c_{2}\geq\cdots\geq c_{n}\), and for the row sums \(s_{1}\geq s_{2}\geq\cdots\geq s_{m}\). Furthermore, let \(F\) be its corresponding Ferrers matrix. Then, Matrix \(F\) also has row sums \((r_{1},\ldots,r_{n})\) but different column sums, i.e., \((c^{\prime}_{1},\ldots,c^{\prime}_{n})\), where \(c^{\prime}_{i}=|\{j\mid j\text{ is row in M with }r_{j}\geq i\}|\)._  
Remark 1 gives row and column sums for a corresponding Ferrers matrix \(F\) of \(M\). The vector \((c^{\prime}_{1},\ldots,c^{\prime}_{n})\) of column sums is also known as _conjugate vector_ of \((r_{1},\ldots,r_{n})\). Furthermore, it is a classical result that there is exactly one matrix with these column and row sums [8] (Section 2). **Remark 2**. : _The corresponding Ferrers matrix \(F\) of a matrix \(M\) is unique._  
Ferrers matrices together with _majorisation theory_ are classical concepts for deciding the question: whether a matrix \(M\) (or its bipartite graph) exists with given row and column sums.