Asymptotic and catalytic matrix majorization

The matrix majorization problem asks, given two tuples of probability vectors, whether there exists a single stochastic matrix transforming one tuple into the other. Solving an open problem due to Mu et al, we show that if certain monotones - namely multivariate extensions of Renyi divergences - are strictly ordered between the two tuples, then for sufficiently large $n$, there exists a stochastic matrix taking $n$ copies of each input distribution to $n$ copies of the corresponding output distribution. The same conditions, with non-strict ordering for the monotones, are also necessary for such asymptotic matrix majorization. Our result also yields a map that approximately converts a single copy of each input distribution to the corresponding output distribution with the help of a catalyst that is returned unchanged. Allowing for transformation with arbitrarily small error, we find conditions that are both necessary and sufficient for such catalytic matrix majorization. We derive our results by building on a general algebraic theory of preordered semirings recently developed by one of the authors. This also allows us to recover various existing results on asymptotic and catalytic majorization as well as relative majorization in a unified manner.