Possible line sums for a qualitative matrix (Q5935360): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3056948 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Convex Sets of Non-Negative Matrices / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3943082 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The diagonal equivalence of a nonnegative matrix to a stochastic matrix / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3274170 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Patterns that allow given row and column sums / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Matrix Links, An Extremization Problem, and the Reduction of a Non-Negative Matrix to One With Prescribed Row and Column Sums / rank | |||
Normal rank |
Latest revision as of 17:39, 3 June 2024
scientific article; zbMATH DE number 1610097
Language | Label | Description | Also known as |
---|---|---|---|
English | Possible line sums for a qualitative matrix |
scientific article; zbMATH DE number 1610097 |
Statements
Possible line sums for a qualitative matrix (English)
0 references
18 January 2002
0 references
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.
0 references
qualitative matrix
0 references
line sums
0 references
sign pattern matrix
0 references
network flows
0 references