CONVEX POLYTOPES OF GENERALIZED DOUBLY STOCHASTIC MATRICES
Soo‐Jin Cho, Yunsun Nam · Communications of the Korean Mathematical Society · 2001
Doubly stochastic matrices are nn nonnegative ma-trices whose row and column sums are all 1. Convex polytope of doubly stochastic matrices and more generally (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 , and extremal matrices of transporta-tion polytopes (R,S) were all classified combinatorially. In this article, we consider signed version of and (R.S), obtain signed Birkhoff theorem; we define a new class of convex polytopes (R,S), calculate their dimensions, and classify their extremal matrices, Moreover, we suggest an algorithm to express a matrix in (R,S) as a convex combination of txtremal matrices. We also give an example that a polytope of signed matrices is used as a domain for a decision problem. In this context of finite reflection(Coxeter) group theory, our generalization may also be considered as a generalization from type n/ to type B D. n/.