Possible line sums for a qualitative matrix (Q5935360): Difference between revisions

For any real \(m\times n\) matrix \(B\) we can associate an \(m\times n\) matrix \(A\) called the sign pattern matrix whose \((i,j)\)th entry is \(+,-\) or \(0\) depending on whether the \((i,j)\)th entry of \(B\) is positive, negative or zero. The authors consider the following problem (P): if we are given real values \(r_{1},\dots ,r_{m}\) and \(c_{1},\dots ,c_{n}\), for which sign pattern matrices \(A\) does there exist an \(m\times n\) matrix \(B\) with these row and column sums and sign pattern \(A\)? In the special case where the entries of \(A\) are all \(+\) or \(0\) the problem (P) was solved by \textit{R. A. Brualdi} [Can. J. Math. 20, 144-157 (1968; Zbl 0155.06501)], but the general problem seems to be more subtle. In order that any matrix \(B\) have the given row and column sums it is necessary that (1): \(\sum_{i}r_{i}=\sum_{j}c_{j}\). Now let \(\{\alpha_{1}, \alpha_{2}\}\) be a partition of the set of row indices \(\{ 1,2,\dots ,m\} \) and \(\{ \beta_{1},\beta_{2}\} \) be a partition of the column indices \(\{ 1,2,\dots ,n\} \), and define \(A[\alpha_{i}|\beta_{j}]\) to be the submatrix of \(A\) with rows in \(\alpha_{i}\) and columns in \(\beta_{j}\). Suppose that \(A\) is a sign pattern matrix for some matrix \(B\) with the given row and column sums. Then it may be verified that (2): if all entries in \(A[\alpha_{1}|\beta_{1}]\) are \(+\) or \(0\) and all entries of \(A[\alpha_{2}|\beta_{2}]\) are \(-\) or \(0,\) then \(\sum_{i\in \alpha_{1}}r_{i}\geq\sum_{j\in\beta_{2}}c_{j}\) and \(\sum_{j\in\beta_{1}} c_{j}\geq\sum_{i\in\alpha_{2}}r_{i}\) with equality only when both the submatrices are \(0\). The main theorem of the paper is to prove that, conversely, if both (1) and (2) hold (for all partitions \(\{ \alpha_{1}, \alpha_{2}\} \) and \(\{ \beta_{1},\beta_{2}\} \)) then there is a matrix \(B\) with the prescribed row and column sums and sign pattern matrix \(A\). A main step in the proof consists of reducing (P) to an equivalent problem in network flows.