© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

arXiv:2301.07353 · IEEE Transactions on Information Theory

Matrix Majorization in Large Samples

Muhammad Usman Farooq, Tobias Fritz, Erkka Haapasalo, Marco Tomamichel

Published Jan 10, 2024• 6 citations

Abstract

One tuple of probability vectors is more informative than another tuple when there exists a single stochastic matrix transforming the probability vectors of the first tuple into the probability vectors of the other. This is called matrix majorization. Solving an open problem raised by Muet al, we show that if certain monotones—namely multivariate extensions of Rényi divergences—are strictly ordered between the two tuples, then for sufficiently largen, there exists a stochastic matrix taking then-fold Kronecker power of each input distribution to then-fold Kronecker power of the corresponding output distribution. The same conditions, with non-strict ordering for the monotones, are also necessary for such matrix majorization in large samples. Our result also gives conditions for the existence of a sequence of statistical maps that asymptotically (with vanishing error) convert 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 majorization in large samples and in the catalytic regime as well as relative majorization in a unified manner.

DOI: 10.1109/tit.2024.3352088

Related papers

Classical and Quantum Information Measures Characterizing Convertibility: An Axiomatic Approach

Frits Verhagen

In this PhD thesis, we take an axiomatic approach to studying multivariate divergences, which are measures of the information content of a tuple of classical or quantum states. These divergences are studied in the context of large-sample and catalytic convertibility of tuples of states. This type of convertibility is characterized by the ordering of an axiomatically defined family of divergences. In this thesis, we identify this family of divergences explicitly for two scenarios, one classical and one quantum. In the classical setting, we show that the relevant divergences are certain generalizations of the bivariate Rényi divergences. Unlike previous studies, we do not require the distributions to have the same support, yielding interesting new divergences. In the quantum setting, we consider pairs of classical-quantum states with pure component states, and find that majorization is characterized by all $α$-$z$ relative entropies for $α<1$. This demonstrates the first operational interpretation of these relative entropies.

quant-pharXiv:2610.16267•Oct 13, 2026•0 citations

Matrix Majorization in Large Samples With Varying Support Restrictions

Frits Verhagen, Marco Tomamichel, Erkka Haapasalo

We say that a matrixPwith non-negative entries majorizes another such matrixQif there is a stochastic matrixTsuch thatQ=TP. We study matrix majorization in large samples and in the catalytic regime in the case where the columns of the matrices need not have equal support, as has been assumed in earlier works. We focus on two cases: either there are no support restrictions (except for requiring a non-empty intersection for the supports) or the final column dominates the others. Using real-algebraic methods, we identify sufficient and almost necessary conditions for majorization in large samples or when using catalytic states under these support conditions. These conditions are given in terms of multivariate divergences that generalize the Rényi divergences. We notice that varying support conditions dramatically affect the relevant set of divergences. Our results find an application in the theory of catalytic state transformation in quantum thermodynamics.

arXiv:2407.16581•IEEE Transactions on Information Theory•Jul 2, 2025•2 citations

Correlations in typicality and an affirmative solution to the exact catalytic entropy conjecture

Henrik Wilming

I show that if a finite-dimensional density matrix has strictly smaller von Neumann entropy than a second one of the same dimension (and the rank is not bigger), then sufficiently (but finitely) many tensor-copies of the first density matrix majorize a density matrix whose single-body marginals are all exactly equal to the second density matrix. This implies an affirmative solution of the exact catalytic entropy conjecture (CEC) introduced by Boes et al. [PRL 122, 210402 (2019)]. Both the Lemma and the solution to the CEC transfer to the classical setting of finite-dimensional probability vectors (with permutations of entries instead of unitary transformations for the CEC).

arXiv:2205.08915•Quantum•Nov 10, 2022•16 citations

Majorization

Gilad Gour

Chapter 4 delves into the concept of majorization, an essential mathematical framework critical for understanding the intricate structures within quantum resource theories. At its core, majorization establishes a preorder relationship between probability vectors, revealing a structured approach to compare the dispersion or concentration of probabilistic distributions. The chapter systematically deconstructs majorization into comprehensible segments, incorporating axiomatic, constructive, and operational perspectives. It further explores the mathematical foundations of majorization through an in-depth look at doubly stochastic matrices and T-transforms. Additionally, the chapter examines various forms of majorization, including approximate, relative, trumping, catalytic, and conditional majorization. This exploration not only encompasses the theoretical facets but also offers practical insights derived from games of chance.

Cambridge University Press eBooks•Apr 10, 2025•0 citations

Limits of Stochastic Semigroups and Block-Triangular Majorisation

Fabio Deelan Cunden, Jakub Czartowski, Giovanni Gramegna +1 more

We investigate limits of semigroups of stochastic matrices defined by their invariant distribution. Given probability vectors $γ(β)$ depending on a parameter $β$, we introduce a notion of convergence as $β\to\infty$ for the corresponding semigroups of $γ(β)$-preserving stochastic matrices and investigate the structure of the resulting limit. In general, the limiting semigroup differs from the semigroup preserving the limiting distribution, showing that these two operations do not commute. We develop a general framework for such limiting semigroups and study in detail the case in which the invariant distributions are Gibbs vectors at the inverse temperature $β$. We show that the limiting semigroup consists of block-upper-triangular stochastic matrices subject to additional substochasticity constraints. We characterise and enumerate their extremal elements and determine the preorder on probability vectors induced by the action of the semigroup. The resulting notion of Block-Triangular majorisation interpolates between ordinary majorisation and upper triangular (aka unordered) majorisation. We show that it is completely characterised by a finite family of monotones and analyse the corresponding behaviour of Rényi $α$-entropies as $β\to\infty$.

math-phCross-listedarXiv:2609.04057•Sep 4, 2026

Asymptotic Majorization of Finite Probability Distributions

Asger Kjaerulff Jensen

This paper studies the majorization of high tensor powers of finitely supported probability distributions. Taking two probability distributions$P$and$Q$to the$n$’th and$m$’th tensor power, respectively, in such a way that the power of$Q$majorizes the power of$P$, we ask how large the ratio$m/n$can become. It is shown that the supremum of such ratios is equal to the minimal ratio of the$\alpha $-Rényi entropies of$P$and$Q$for$\alpha \in [0,\infty]$. Consideration of this ratio of tensor powers is motivated, to the author, by the resource theory of quantum entanglement, where the supremum of these ratios corresponds to the asymptotic conversion rate of bipartite pure quantum states under exact, deterministic LOCC transformations.

arXiv:1808.05157•IEEE Transactions on Information Theory•Jun 12, 2019•8 citations

One tuple of probability vectors is more informative than another tuple when there exists a single stochastic matrix transforming the probability vectors of the first tuple into the probability vectors of the other. This is called matrix majorization. Solving an open problem raised by Muet al, we show that if certain monotones—namely multivariate extensions of Rényi divergences—are strictly ordered between the two tuples, then for sufficiently largen, there exists a stochastic matrix taking then-fold Kronecker power of each input distribution to then-fold Kronecker power of the corresponding output distribution. The same conditions, with non-strict ordering for the monotones, are also necessary for such matrix majorization in large samples. Our result also gives conditions for the existence of a sequence of statistical maps that asymptotically (with vanishing error) convert 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 majorization in large samples and in the catalytic regime as well as relative majorization in a unified manner.

In this PhD thesis, we take an axiomatic approach to studying multivariate divergences, which are measures of the information content of a tuple of classical or quantum states. These divergences are studied in the context of large-sample and catalytic convertibility of tuples of states. This type of convertibility is characterized by the ordering of an axiomatically defined family of divergences. In this thesis, we identify this family of divergences explicitly for two scenarios, one classical and one quantum. In the classical setting, we show that the relevant divergences are certain generalizations of the bivariate Rényi divergences. Unlike previous studies, we do not require the distributions to have the same support, yielding interesting new divergences. In the quantum setting, we consider pairs of classical-quantum states with pure component states, and find that majorization is characterized by all

α

-

z

relative entropies for

α<1

. This demonstrates the first operational interpretation of these relative entropies.

We say that a matrixPwith non-negative entries majorizes another such matrixQif there is a stochastic matrixTsuch thatQ=TP. We study matrix majorization in large samples and in the catalytic regime in the case where the columns of the matrices need not have equal support, as has been assumed in earlier works. We focus on two cases: either there are no support restrictions (except for requiring a non-empty intersection for the supports) or the final column dominates the others. Using real-algebraic methods, we identify sufficient and almost necessary conditions for majorization in large samples or when using catalytic states under these support conditions. These conditions are given in terms of multivariate divergences that generalize the Rényi divergences. We notice that varying support conditions dramatically affect the relevant set of divergences. Our results find an application in the theory of catalytic state transformation in quantum thermodynamics.

I show that if a finite-dimensional density matrix has strictly smaller von Neumann entropy than a second one of the same dimension (and the rank is not bigger), then sufficiently (but finitely) many tensor-copies of the first density matrix majorize a density matrix whose single-body marginals are all exactly equal to the second density matrix. This implies an affirmative solution of the exact catalytic entropy conjecture (CEC) introduced by Boes et al. [PRL 122, 210402 (2019)]. Both the Lemma and the solution to the CEC transfer to the classical setting of finite-dimensional probability vectors (with permutations of entries instead of unitary transformations for the CEC).

Chapter 4 delves into the concept of majorization, an essential mathematical framework critical for understanding the intricate structures within quantum resource theories. At its core, majorization establishes a preorder relationship between probability vectors, revealing a structured approach to compare the dispersion or concentration of probabilistic distributions. The chapter systematically deconstructs majorization into comprehensible segments, incorporating axiomatic, constructive, and operational perspectives. It further explores the mathematical foundations of majorization through an in-depth look at doubly stochastic matrices and T-transforms. Additionally, the chapter examines various forms of majorization, including approximate, relative, trumping, catalytic, and conditional majorization. This exploration not only encompasses the theoretical facets but also offers practical insights derived from games of chance.

We investigate limits of semigroups of stochastic matrices defined by their invariant distribution. Given probability vectors

γ(β)

depending on a parameter

β

, we introduce a notion of convergence as

β\to\infty

for the corresponding semigroups of

γ(β)

-preserving stochastic matrices and investigate the structure of the resulting limit. In general, the limiting semigroup differs from the semigroup preserving the limiting distribution, showing that these two operations do not commute. We develop a general framework for such limiting semigroups and study in detail the case in which the invariant distributions are Gibbs vectors at the inverse temperature

β

. We show that the limiting semigroup consists of block-upper-triangular stochastic matrices subject to additional substochasticity constraints. We characterise and enumerate their extremal elements and determine the preorder on probability vectors induced by the action of the semigroup. The resulting notion of Block-Triangular majorisation interpolates between ordinary majorisation and upper triangular (aka unordered) majorisation. We show that it is completely characterised by a finite family of monotones and analyse the corresponding behaviour of Rényi

α

-entropies as

β\to\infty

.

This paper studies the majorization of high tensor powers of finitely supported probability distributions. Taking two probability distributions

P

and

Q

to the

n

’th and

m

’th tensor power, respectively, in such a way that the power of

Q

majorizes the power of

P

, we ask how large the ratio

m/n

can become. It is shown that the supremum of such ratios is equal to the minimal ratio of the$\alpha

-Rényi entropies of

P

and

Q

for

\alpha \in [0,\infty]$. Consideration of this ratio of tensor powers is motivated, to the author, by the resource theory of quantum entanglement, where the supremum of these ratios corresponds to the asymptotic conversion rate of bipartite pure quantum states under exact, deterministic LOCC transformations.