Majorization polytopes

AbstractWe study polytopes related to the concept of matrix majorization: for two real matrices A and B having m rows we say that A majorizes B if there is a row-stochastic matrix X with AX=B. In that case we write A≻B and the associated majorization polytope M(A≻B) is the set of row stochastic matrices X such that AX=B. We investigate some properties of M(A≻B) and obtain e.g., generalizations of some results known for vector majorization. Relations to transportation polytopes and network flow theory are discussed. A complete description of the vertices of majorization polytopes is found for some special cases