Partitions of the polytope of doubly substochastic matrices. (English) Zbl 1405.15041
Summary: In this paper, we provide three different ways to partition the polytope of doubly substochastic matrices into subpolytopes via the prescribed row and column sums, the sum of all elements and the sub-defect respectively. Then we characterize the extreme points of each type of convex subpolytopes. The relations of the extreme points of the subpolytopes in the three partitions are also given.
MSC:
| 15B51 | Stochastic matrices |
| 52B05 | Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) |
| 05A18 | Partitions of sets |
References:
| [1] | Balasubramanian, K., Diagonal sums of doubly stochastic matrices, Sankhya, Ser. B, 39, 1, 89-91 (1977) · Zbl 0414.15014 |
| [2] | Bolker, Ethan D., Transportation polytopes, J. Combin. Theory Ser. B, 13, 3, 251-262 (1972) · Zbl 0241.90033 |
| [3] | Brualdi, Richard A., Convex sets of non-negative matrices, Canad. J. Math., 20, 1, 144-157 (1968) · Zbl 0155.06501 |
| [4] | Brualdi, Richard A., Some applications of doubly stochastic matrices, Linear Algebra Appl., 107, Supplement C, 77-100 (1988) · Zbl 0657.15016 |
| [5] | Brualdi, Richard A.; Gibson, Peter M., Convex polyhedra of doubly stochastic matrices. I. Applications of the permanent function, J. Combin. Theory Ser. A, 2, 22, 194-230 (1977) · Zbl 0355.15013 |
| [6] | Birkhoff, Garrett, Tres observaciones sobre el algebra lineal, Univ. Nac. Tucumán, Revista, Ser. A, vol. 5, 147-151 (1946) · Zbl 0060.07906 |
| [7] | Cao, Lei, A short note on doubly substochastic analogue of Birkhoff’s theorem, Electron. J. Linear Algebra (2018), in press. Available from |
| [8] | Cao, Lei; Koyuncu, Selcuk, Sub-defect of product of doubly substochastic matrices, Linear Multilinear Algebra, 65, 4, 653-657 (2017) · Zbl 1367.15052 |
| [9] | Cao, Lei; Koyuncu, Selcuk; Parmer, Timmothy, A minimal completion of doubly substochastic matrix, Linear Multilinear Algebra, 64, 11, 2313-2334 (2016) · Zbl 1358.15025 |
| [10] | Lei Cao, Zhi Chen, Xuefeng Duan, Selcuk Koyuncu, Huilan Li, Diagonal sums of doubly substochastic matrices, submitted for publication.; Lei Cao, Zhi Chen, Xuefeng Duan, Selcuk Koyuncu, Huilan Li, Diagonal sums of doubly substochastic matrices, submitted for publication. |
| [11] | Cao, Lei; Chen, Zhi; Koyuncu, Selcuk; Li, Huilan, Permanents of doubly substochastic matrices, Linear Multilinear Algebra (2018), in press · Zbl 1432.15034 |
| [12] | Chen, Zhi; Cao, Lei, On the maximum of permanent of \((I - A)\), Linear Algebra Appl., 555, 412-431 (2018) · Zbl 1396.15006 |
| [13] | Cho, Soo-Jin; Nam, Yun-Sun, Convex polytopes of generalized doubly stochastic matrices, Commun. Korean Math. Soc., 4, 16, 679-690 (2001) · Zbl 1101.15301 |
| [14] | Egorychev, Georgy P., A Solution of the van der Waerden’s Permanent Problem (1980), Academy of Sciences SSSR: Academy of Sciences SSSR Krasnoyarsk, Preprint IFSO-L3 M · Zbl 0438.15010 |
| [15] | Falikman, Dmitry, Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix, Math. Notes Acad. Sci. USSR, 29, 6, 475-479 (1981) · Zbl 0475.15007 |
| [16] | Gibson, Peter M., A short proof of an inequality for the permanent function, Proc. Amer. Math. Soc., 17, 2, 535-536 (1966) · Zbl 0143.05004 |
| [17] | Johnson, Charles R., Row stochastic matrices similar to doubly stochastic matrices, Linear Multilinear Algebra, 10, 2, 113-130 (1981) · Zbl 0455.15019 |
| [18] | Jurkat, W. B.; Ryser, H. J., Term ranks and permanents of nonnegative matrices, J. Algebra, 5, 3, 342-357 (1967) · Zbl 0178.03302 |
| [19] | Katz, M., On the extreme points of a certain convex polytope, J. Combin. Theory, 8, 4, 417-423 (1970) · Zbl 0194.34102 |
| [20] | Katz, M., On the extreme points of the set of substochastic and symmetric matrices, J. Math. Anal. Appl., 37, 3, 576-579 (1972) · Zbl 0235.15007 |
| [21] | Klee, V.; Witzgall, C., Facets and Vertices of Transportation Polytope, 277-282 (1968), Amer. Math. Soc.: Amer. Math. Soc. Providence |
| [22] | Malek, Massoud, On the maximum of \(Per(I - A)\), Linear Multilinear Algebra, 19, 4, 347-355 (1986) · Zbl 0604.15009 |
| [23] | Marcus, Marvin; Minc, Henryk, Some results on doubly stochastic matrices, Proc. Amer. Math. Soc., 13, 4, 571-579 (1962) · Zbl 0107.01403 |
| [24] | Marcus, Marvin; Minc, Henryk, Inequalities for general matrix functions, Bull. Amer. Math. Soc., 70, 70, 308-313 (1964) · Zbl 0122.01607 |
| [25] | Marshall, A.; Olkin, I., Inequalities: Theory of Majorization and Its Applications (1979), Academic Press · Zbl 0437.26007 |
| [26] | Mirsky, L., On a convex set of matrices, Arch. Math., 10, 1, 88-92 (1959) · Zbl 0088.25105 |
| [27] | von Neumann, John, A certain zero-sum two-person game equivalent to the optimal assignment problem, Contrib. Theory Games, 2, 28, 5-12 (1953) · Zbl 0050.14105 |
| [28] | Sinkhorn, Richard, A relationship between arbitrary positive matrices and doubly stochastic matrices, Ann. Math. Stat., 35, 2, 876-879 (1964) · Zbl 0134.25302 |
| [29] | Sinkhorn, Richard; Knopp, Paul, Concerning nonnegative matrices and doubly stochastic matrices, Pacific J. Math., 21, 2, 343-348 (1967) · Zbl 0152.01403 |
| [30] | van der Waerden, B. L., Aufgabe 45, Jber. Deut. Math.-Verein., 35, 117 (1926) |
| [31] | Wang, Edward Tzu-Hsia, Maximum and minimum diagonal sums of doubly stochastic matrices, Linear Algebra Appl., 8, 6, 483-505 (1974) · Zbl 0294.15017 |
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.
