Integral matrices with given row and column sums. (English) Zbl 0773.05027
Let \(P\) and \(Q\) be \(m\times n\) integral matrices and let \(R\) and \(S\) be integral vectors. For a wide variety of sets \((P,Q,R,S)\) the author obtains two necessary and sufficient conditions for there to exist an \(m\times n\) integral matrix \(A\) with row and column sum vectors \(R\) and \(S\) and such that \(P\leq A\leq Q\); these results unify earlier results on \((0,1)\)-matrices. Certain results involving decomposability or invariant elements are also derived, among other things.
Reviewer: J.W.Moon (Edmonton)
MSC:
| 05B20 | Combinatorial aspects of matrices (incidence, Hadamard, etc.) |
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 05C20 | Directed graphs (digraphs), tournaments |
| 05C40 | Connectivity |
References:
| [1] | Anstee, R. P., Properties of a class of (0, 1)-matrices covering a given matrix, Canad. J. Math., 34, 438-453 (1982) · Zbl 0442.05012 |
| [2] | Anstee, R. P., The network flows approach for matrices with given row and column sums, Discrete Math., 44, 125-138 (1983) · Zbl 0516.05036 |
| [3] | Anstee, R. P., Invariant sets of arcs in network flow problems, Discrete Appl. Math., 13, 1-7 (1986) · Zbl 0585.90029 |
| [4] | L. W. Beinekein; L. W. Beinekein |
| [5] | Beineke, L. W.; Harary, F., Local restrictions for various class of directed graphs, J. London Math. Soc., 40, 87-95 (1965) · Zbl 0125.11803 |
| [6] | L. W. Beineke and J. W. Moonin; L. W. Beineke and J. W. Moonin |
| [7] | Berge, C., Graphs and Hypergraphs (1973), North-Holland: North-Holland New York · Zbl 0483.05029 |
| [8] | Brualdi, R. A., Matrices of 0’s and 1’s with total support, J. Combin. Theory Ser. A, 28, 249-256 (1980) · Zbl 0475.05018 |
| [9] | Brualdi, R. A., Matrices of zeros and ones with fixed row and column sum vectors, Linear Algebra Appl., 33, 159-231 (1980) · Zbl 0448.05047 |
| [10] | Brualdi, R. A.; Michael, T. S., The class of matrices of zeros, ones, and twos with prescribed row and column sums, Linear Algebra Appl., 114/115, 181-198 (1989) · Zbl 0727.05012 |
| [11] | Brualdi, R. A.; Ross, J. A., Invariant sets for classes of matrices of zeros and ones, (Proc. Amer. Math. Soc., 80 (1980)), 706-710 · Zbl 0448.05012 |
| [12] | Chen, W. K., Applied Graph Theory (1976), North-Holland: North-Holland Amsterdam · Zbl 0325.05102 |
| [13] | Chen, W. Y.C; Shastri, A., On joint realization of (0, 1)-matrices, Linear Algebra Appl., 112, 75-85 (1989) · Zbl 0664.15006 |
| [14] | Ford, L. R.; Fulkerson, D. R., Flows in Networks (1962), Princeton Univ. Press: Princeton Univ. Press Princeton, NJ · Zbl 0139.13701 |
| [15] | Fulkerson, D. R., Zero-one matrices with zero trace, Pacific J. Math., 10, 831-836 (1960) · Zbl 0096.00703 |
| [16] | Gale, D., A theorem on flows in networks, Pacific J. Math., 7, 1073-1082 (1957) · Zbl 0087.16303 |
| [17] | Gibson, P. M., A bound for the number of tournaments with specified scores, J. Combin. Theory Ser. B, 36, 240-243 (1984) · Zbl 0541.05031 |
| [18] | Greene, C.; Kleitman, D. J., Longest chains in the lattice of integer partitions ordered by majorization, European J. Combin., 7, 1-10 (1986) · Zbl 0605.05003 |
| [19] | Harary, F., Graph Theory (1969), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0797.05064 |
| [20] | Hardy, G. H.; Littlewood, J. E.; Pólya, G., Inequalities (1952), Cambridge Univ. Press: Cambridge Univ. Press London · Zbl 0047.05302 |
| [21] | Knuth, D. E., (The Art of Computer Programming, Vol. 1 (1973), Addison-Wesley: Addison-Wesley Reading, MA) · Zbl 0302.68010 |
| [22] | Landau, H. G., On dominance relations and the structure of animal societies, III: The condition for a score structure, Bull. Math. Biophys., 15, 143-148 (1953) |
| [23] | Li, J. S.; Huang, G. X., The pairs of score lists of \(t\)-reducible bipartite tournaments, Acta Math. Appl. Sinica, 10, 418-427 (1987), [Chinese] · Zbl 0639.05025 |
| [24] | Lih, K. W., Majorization on finite partially ordered sets, SIAM J. Algebraic Discrete Math., 3, 495-503 (1982) · Zbl 0503.06001 |
| [25] | Lin, Y. C.; Huang, G. X.; Li, J. S., Score vectors of Kotzig tournaments, J. Combin. Theory Ser. B, 42, 328-336 (1987) · Zbl 0584.05039 |
| [26] | Moon, J. W., Topics on Tournaments (1968), Holt, Rinehart, and Winston: Holt, Rinehart, and Winston New York · Zbl 0191.22701 |
| [27] | Ryser, H. J., Combinatorial properties of matrices of zeros and ones, Canad. J. Math., 9, 371-377 (1957) · Zbl 0079.01102 |
| [28] | Ryser, H. J., Matrices of zeros and ones in combinatorial mathematics, (Recent Advances in Matrix Theory (1964), Univ. of Wisconsin Press: Univ. of Wisconsin Press Madison), 103-124 · Zbl 0129.00802 |
| [29] | Snapper, E., Group characters and nonnegative matrices, J. Algebra, 19, 520-535 (1971) · Zbl 0226.20008 |
| [30] | Wang, D. L.; Kleitman, D. J., On the existence of \(n\)-connected graphs with prescribed degrees \((n\) ⩾ 2), Networks, 3, 225-239 (1973) · Zbl 0258.05130 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
