×

Symmetric and Hankel-symmetric transportation polytopes. (English) Zbl 1489.15044

Summary: In this paper, we consider the symmetric and Hankel-symmetric transportation polytope \(\mathcal U^{t \& h}(R,S)\), which is the convex set of all symmetric and Hankel-symmetric non-negative matrices with prescribed row sum vector \(R\) and prescribed column sum vector \(S\). We characterize all extreme points of \(\mathcal U^{t \& h}(R,S)\). Moreover, we show that the extreme points of \(\Omega_n^{t \& h}\) the polytope of symmetric and Hankel-symmetric doubly stochastic matrices, can be obtained from the extreme points of \(\mathcal U^{t \& h}(R,S)\) by specializing to the case that \(R=S=(1,1,\ldots,1) \in \mathbb R^n\).

MSC:

15B51 Stochastic matrices
52B05 Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)
05A18 Partitions of sets
Full Text: DOI

References:

[1] Bolker, ED., Transportation polytopes, J Combin Theory Ser B, 13, 3, 251-262 (1972) · Zbl 0241.90033 · doi:10.1016/0095-8956(72)90060-3
[2] Brualdi, RA., Convex sets of non-negative matrices, Canad J Math, 20, 1, 144-157 (1968) · Zbl 0155.06501 · doi:10.4153/CJM-1968-016-9
[3] Cho, S-J; Nam, Y-S., Convex polytopes of generalized doubly stochastic matrices, Commun Korean Math Soc, 4, 16, 679-690 (2001) · Zbl 1101.15301
[4] Dantzig, GB., Linear programming and extensions (1962), Princeton (NJ): Princeton University Press, Princeton (NJ)
[5] Fulkerson, DR.Hitchcock transportation problem; 1956 (Rand. Corp. Report, P-890).
[6] Jurkat, WB; Ryser, HJ., Term ranks and permanents of nonnegative matrices, J Algebra, 5, 3, 342-357 (1967) · Zbl 0178.03302 · doi:10.1016/0021-8693(67)90044-0
[7] Klee, V, Witzgall, C.Facets and vertices of transportation polytope. Mathematics of the Decision Sciences, Part I (Seminar, Stanford, Calif., 1967). Providence (RI): American Mathematical Society; 1968. p. 257-282. · Zbl 0184.44601
[8] Brualdi, RA.Combinatorial matrix classes. Cambridge: Cambridge University Press; 2006. (Encyclopedia of Mathematics and its Applications; 108). · Zbl 1106.05001
[9] Gregory, DA; Kirkland, SJ; Pullman, NJ., Row-stochastic matrices with a common left fixed vector, Linear Algebra Appl, 169, 131-149 (1992) · Zbl 0758.15015 · doi:10.1016/0024-3795(92)90175-A
[10] Brualdi, RA.Combinatorial properties of symmetric non-negative matrices. In: Colloquio Internazionale sulle Theorie Combinatorie, Roma, 1973, Acad. Naz. Lincei, Tomo II(17), Rome; 1976. p. 99-120. · Zbl 0358.05013
[11] Cao, L, Chen, Z, Koyuncu, S, et al. The extreme points of centrosymmetric transportation polytopes. Linear Multilinear Algebra. Forthcoming. doi:. · Zbl 1457.15034
[12] Cruse, AB., Some combinatorial properties of centrosymmetric matrices, Linear Algebra Appl, 16, 65-77 (1977) · Zbl 0348.15011 · doi:10.1016/0024-3795(77)90020-9
[13] Brualdi, RA; Cao, L., Symmetric, Hankel-symmetric, and centrosymmetric doubly stochastic matrices, Acta Math Vietnam, 43, 4, 675-700 (2018) · Zbl 1400.15036 · doi:10.1007/s40306-018-0266-z
[14] Birkhoff, G., Tres observaciones sobre el algebra lineal, Univ Nac Tucumán Rev Ser A, 5, 147-151 (1946) · Zbl 0060.07906
[15] Katz, M., On the extreme points of a certain convex polytope, J Comb Theory, 8, 4, 417-423 (1970) · Zbl 0194.34102 · doi:10.1016/S0021-9800(70)80034-5
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.