×

Enumerating extreme points of the polytopes of stochastic tensors: an optimization approach. (English) Zbl 1471.52010

Summary: This paper is concerned with the extreme points of the polytopes of stochastic tensors. By a tensor we mean a multi-dimensional array over the real number field. A line-stochastic tensor is a nonnegative tensor in which the sum of all entries on each line (i.e. one free index) is equal to 1; a plane-stochastic tensor is a nonnegative tensor in which the sum of all entries on each plane (i.e. two free indices) is equal to 1. In enumerating extreme points of the polytopes of line- and plane-stochastic tensors of order 3 and dimension \(n\), we consider the approach by linear optimization and present new lower and upper bounds. We also study the coefficient matrices that define the polytopes.

MSC:

52B11 \(n\)-dimensional polytopes
52B05 Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.)
60B20 Random matrices (probabilistic aspects)
90C05 Linear programming

Software:

birkhoff faces
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Webster, R., Convexity (1994), New York: Oxford University Press, New York · Zbl 0835.52001
[2] Marlow, WH., Mathematics for operations research (2013), New York: Dover Books on Mathematics, New York
[3] Barvinok, A.A course in convexity. Providence (RI): American Mathematical Society; 2002. (Graduate studies in mathematics; 54). · Zbl 1014.52001
[4] Ziegler, GM., Lectures on polytopes (1995), New York: Springer, New York · Zbl 0823.52002
[5] Zhang, F., Matrix theory: basic results and techniques (2011), New York: Springer, New York · Zbl 1229.15002
[6] Brualdi, RA; Cao, L., Symmetric, Hankel-symmetric, and centrosymmetric doubly stochastic matrices, Acta Math Vietnam, 43, 675-700 (2018) · Zbl 1400.15036 · doi:10.1007/s40306-018-0266-z
[7] Brualdi, RA; Csima, J., Stochastic patterns, J Combin Theory Ser A, 19, 1-12 (1975) · Zbl 0304.05011 · doi:10.1016/0097-3165(75)90088-6
[8] Cui, L.; Li, W.; Ng, M-K., Birkhoff-von Neumann theorem for multistochastic tensors, SIAM J Matrix Anal Appl, 35, 956-973 (2014) · Zbl 1309.15040 · doi:10.1137/120896499
[9] Paffenholz, A., Faces of Birkhoff polytopes, Electron J Combin, 22, 1 (2015) · Zbl 1311.52015
[10] Marshall, AW; Olkin, I.; Arnold, B., Inequalities: theory of majorization and its applications (2011), New York: Springer, New York · Zbl 1219.26003
[11] Brondsted, A., An introduction to convex polytopes (1983), New York: Springer, New York · Zbl 0509.52001
[12] Wang, Q-W; Zhang, F., The permanent functions of tensors, Acta Math Vietnam, 43, 4, 701-713 (2018) · Zbl 1400.15013 · doi:10.1007/s40306-018-0268-x
[13] Fischer, P.; Swart, ER., Three dimensional line stochastic matrices and extreme points, Linear Algebra Appl, 69, 179-203 (1985) · Zbl 0574.15013 · doi:10.1016/0024-3795(85)90075-8
[14] Brualdi, RA; Csima, J., Extremal plane stochastic matrices of dimension three, Linear Algebra Appl, 11, 105-133 (1975) · Zbl 0312.15010 · doi:10.1016/0024-3795(75)90053-1
[15] Brualdi, RA; Csima, J., Small matrices of large dimension, Linear Algebra Appl, 150, 227-241 (1991) · Zbl 0761.05021 · doi:10.1016/0024-3795(91)90171-R
[16] Li, Z.; Zhang, F.; Zhang, X-D., On the number of vertices of the stochastic tensor polytope, Linear Multilinear Algebra, 65, 2064-2075 (2017) · Zbl 1382.15050 · doi:10.1080/03081087.2017.1310178
[17] Ding, W.; Wei, Y., Theory and computation of tensors: multi-dimensional arrays (2016), London: Elsevier, London · Zbl 1380.15004
[18] Qi, L.; Luo, Z., Tensor analysis: spectral theory and special tensors (2017), Philadelphia: SIAM, Philadelphia · Zbl 1370.15001
[19] Ke, R.; Li, W.; Xiao, M., Characterization of extreme points of multi-stochastic tensors, Comput Methods Appl Math, 16, 459-274 (2016) · Zbl 1360.15032 · doi:10.1515/cmam-2016-0005
[20] Jurkat, WB; Ryser, HJ., Extremal configurations and decomposition theorems, J Algebra, 8, 194-222 (1968) · Zbl 0162.03102 · doi:10.1016/0021-8693(68)90045-8
[21] Burkard, R.; Dell’Amico, M.; Martello, S., Assignment problems: revised reprint (2009), Philadelphia: SIAM, Philadelphia · Zbl 1196.90002
[22] Ahmed, M.Algebraic combinatorics of magic squares [Ph.D. Thesis]. Davis: University of Califorina; 2004.
[23] Ahmed, M, De Loera, J, Hemmecke, R.Polyhedral cones of magic cubes and squares. In Aronov B, et al., editors. Discrete and computational geometry algorithms and combinatorics. Vol. 25. Berlin: Springer; 2003. p. 25-41. · Zbl 1077.52506
[24] van Lint, JH; Wilson, RM., A course in combinatorics (1992), Berlin: Cambridge University Press, Berlin · Zbl 0769.05001
[25] Chang, H.; Paksoy, VE; Zhang, F., Polytopes of stochastic tensors, Ann Funct Anal, 7, 3, 386-393 (2016) · Zbl 1347.15040 · doi:10.1215/20088752-3605195
[26] Gass, SI., Linear programming: methods and applications (2003), New York: Dover Books on Computer Science, New York
[27] Burger, E., Introduction to the theory of games (1963), New York: Prentice-Hall, New York · Zbl 0112.12502
[28] Linial, N.; Luria, Z., On the vertices of the d-dimensional Birkhoff polytope, Discrete Comput Geom, 51, 1, 161-170 (2014) · Zbl 1284.05045 · doi:10.1007/s00454-013-9554-5
[29] McMullen, P., The maximum numbers of faces of a convex polytope, Mathematika, 17, 179-184 (1970) · Zbl 0217.46703 · doi:10.1112/S0025579300002850
[30] McKay, BD; Wanless, IM., On the number of latin squares, Ann Comb, 9, 3, 335-344 (2005) · Zbl 1073.05013 · doi:10.1007/s00026-005-0261-7
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.