Possible line sums for a qualitative matrix
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. NEWLINENEWLINENEWLINEIn 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\). NEWLINENEWLINENEWLINEThe 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.
- Convex Sets of Non-Negative Matrices
- scientific article; zbMATH DE number 3156381 (Why is no real title available?)
- scientific article; zbMATH DE number 3760340 (Why is no real title available?)
- Matrix Links, An Extremization Problem, and the Reduction of a Non-Negative Matrix to One With Prescribed Row and Column Sums
- Network flows. Theory, algorithms, and applications.
- Patterns that allow given row and column sums
- The diagonal equivalence of a nonnegative matrix to a stochastic matrix
- Sum decompositions of symmetric matrices
- On the existence of sequences and matrices with prescribed partial sums of elements
- Scaling symmetric positive definite matrices to prescribed row sums.
- Patterns that allow given row and column sums
- Patterns, linesums, and symmetry
- Integral matrices with given row and column sums
- scientific article; zbMATH DE number 4177072 (Why is no real title available?)
- Low Rank Matrices with a Given Sign Pattern
- Rational solutions of certain matrix equations
This page was built for publication: Possible line sums for a qualitative matrix
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5935360)
