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\).