Convex polytopes of generalized doubly stochastic matrices. (English) Zbl 1101.15301
Summary: Doubly stochastic matrices are \(n\times n\) nonnegative matrices whose row and column sums are all \(1\). Convex polytope \(\Omega_n\) of doubly stochastic matrices and more generally \({\mathfrak A}(R,S)\), so called transportation polytopes, are important since they form the domains for the transportation problems. A theorem by Birkhoff classifies the extremal matrices of \(\Omega_n\), and extremal matrices of transportation polytopes \({\mathfrak A}(R,S)\) were all classified combinatorially.
We consider signed version of \(\Omega_n\) and \({\mathfrak A}(R,S)\), obtain ‘signed’ Birkhoff theorem; we define a new class of convex polytopes \({\mathfrak A}(R,S)\), calculate their dimensions, and classify their extremal matrices. Moreover, we suggest an algorithm to express a matrix in \(|{\mathfrak A}|(R,S)\) as a convex combination of extremal matrices. We also give an example that a polytope of signed matrices is used as a domain for a decision problem. In the context of finite reflection(Coxeter) group theory, our generalization may also be considered as a generalization from type \(A_n\) to type \(B_n\) and \(D_n\).
We consider signed version of \(\Omega_n\) and \({\mathfrak A}(R,S)\), obtain ‘signed’ Birkhoff theorem; we define a new class of convex polytopes \({\mathfrak A}(R,S)\), calculate their dimensions, and classify their extremal matrices. Moreover, we suggest an algorithm to express a matrix in \(|{\mathfrak A}|(R,S)\) as a convex combination of extremal matrices. We also give an example that a polytope of signed matrices is used as a domain for a decision problem. In the context of finite reflection(Coxeter) group theory, our generalization may also be considered as a generalization from type \(A_n\) to type \(B_n\) and \(D_n\).
MSC:
15B51 | Stochastic matrices |
52B05 | Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) |