$P\succeq Q$. A simple calculation shows that

(226) $\Delta(P)=\gamma_{\ell}\left(2-\frac{3}{4}\log
3\right)\leq\gamma_{\ell}=\Delta(Q),$

with strict inequality if $\gamma_{\ell}>0$. This would imply that $\Delta$ is
not monotone. Hence, we find that $\gamma_{\ell}=0$ for all
$\ell\in[d-1]\setminus\\{k\\}$. Therefore, if $k\neq d$,

(227) $\Delta(P)=\gamma_{d}\sum_{i\in{\rm
supp}\,p^{(k)}}p_{i}^{(k)}\log\left(\frac{p_{i}^{(k)}}{\widetilde{p_{i}^{(d)}}}\right)=\gamma_{d}D_{1}\left(p^{(k)}\|p^{(d)}\right),$

where we used that ${\rm supp}\,p^{(k)}\subseteq{\rm supp}\,p^{(d)}$ to
identify the sum as the Kullback-Leibler divergence $D_{1}$. Note that the
monotonicity of $\Delta$ follows from the data-processing inequality satisfied
by $D_{1}$. For the case $k=d$, we have $\gamma_{\ell}=0$ for all $\ell\neq
d$, hence $\Delta(P)=0$ for every $P\in S_{\rm d.c.}^{d}$.

∎

###  4.3. Power universal elements

The following Proposition characterizes the power universal elements in
$S_{\rm d.c.}^{d}$.

######  Proposition 16.

Let $U=(u^{(1)},\ldots,u^{(d)})\in S_{\rm d.c.}^{d}$ with all $u^{(k)}$ for
$k\in[d]$, probability distributions. Then the following are equivalent

  1. (i)

$U$ is power universal;

  2. (ii)

It holds that ${\rm supp}\,u^{(k)}\subsetneq{\rm supp}\,u^{(d)}$ for all
$k\in[d-1]$, and ${\rm supp}\,u^{(k)}\nsubseteq{\rm supp}\,u^{(k^{\prime})}$
for all $k,k^{\prime}\in[d-1]$, $k\neq k^{\prime}$;

  3. (iii)

Any nondegenerate homomorphism $\Phi\in\mathcal{H}^{\rm n.d.}(S^{d}_{\rm
d.c.},\mathbb{R}_{+})\cup\mathcal{H}^{\rm n.d.}(S^{d}_{\rm
d.c.},\mathbb{R}_{+}^{\rm op})\cup\mathcal{H}^{\rm n.d.}(S^{d}_{\rm
d.c.},\mathbb{T}\mathbb{R}_{+})$ satisfies $\Phi(U)\neq 1$.

###### Proof.

(iii) $\Rightarrow$ (ii): Note that for a monotone homomorphism
$\Phi:S^{d}_{\rm d.c.}\to\mathbb{\mathbb{R}^{\rm op}}$, $\Phi(U)\neq 1$
implies $\Phi(U)<1$. Since $\Phi_{e_{d},\\{k,d\\}}(U)<1$ for $k\in[d-1]$,
there is a row with a vanishing entry at $k$ and a positive value at $d$.
Similarly, since $\Phi_{e_{k},\\{k,k^{\prime},d\\}}(U)<1$ for
$k,k^{\prime}\in[d-1]$, $k\neq k^{\prime}$, there is a row with a vanishing
entry at $k^{\prime}$ and a positive value at $k$. Hence, the conditions in
(ii) are satisfied.

(ii) $\Rightarrow$ (i): From (ii), it follows that for each $k=2,\ldots,d-1$,
$U$ has a row with positive entries at positions $1$ and $d$, and $0$ at
position $k$. Then $U^{\boxtimes(d-2)}$ will contain the $\boxtimes$-product
of these $d-2$ rows, which is a row with positive entries at positions $1$ and
$d$, and $0$ everywhere else. Similarly, for the other columns
$k^{\prime}=2,\ldots,d-2$, $U^{\boxtimes(d-2)}$ will contain a row with
positive entries at positions $k^{\prime}$ and $d$ and $0$ everywhere else.
Note that $U^{\boxtimes(d-1)}=U^{\boxtimes(d-2)}\boxtimes U$ will also contain
rows of these specific types. From (ii) it also follows that for each
$k=1,\ldots,d-1$, $U$ contains a row with a positive entry at position $d$ and
$0$ at position $k$. Then $U^{\boxtimes(d-1)}$ will contain the
$\boxtimes$-product of these $d-1$ rows, which is a row with a positive entry
at position $d$ and $0$ everywhere else. One sees that it is possible to the
sum rows in $U^{\boxtimes(d-1)}$ in such a way that

(228)
$U^{\boxtimes(d-1)}\succeq\left(\begin{array}[]{cccc}a_{1}&\cdots&a_{d-1}&b_{0}\\\
1-a_{1}&\cdots&0&b_{1}\\\ 0&\ddots&\vdots&\vdots\\\
0&\cdots&1-a_{d-1}&b_{d-1}\\\ 0&\cdots&0&1-b\end{array}\right):=\tilde{U},$

where $b:=\sum_{i=0}^{d-1}b_{i}$, and $a_{k},b_{i},b\in(0,1)$ for
$k=1,\ldots,d-1$ and $i=0,\ldots,d-1$. Define the stochastic map (matrix) $T$
mapping probability vectors on $\\{0,1,\ldots,d\\}^{2}$ into probability
vectors on $\\{0,1.\ldots,d\\}$ through

(229) $(Tp)_{m}=p_{m,m}+\sum_{j=0}^{m-1}\big{(}p_{j,m}+p_{m,j}\big{)},\qquad
m=0,\ldots,d,$

for all $p=(p_{j,k})_{i,j=0}^{d}$ where empty sums $\sum_{j=0}^{-1}(\cdots)$
vanish. Also define matrices $U_{\ell}$ through $U_{1}=\tilde{U}$ and
$U_{\ell+1}=T(\tilde{U}\boxtimes U_{\ell})$ for all $\ell=1,2,\ldots$. One
easily sees that $\tilde{U}^{\boxtimes\ell}\succeq U_{\ell}$ and a
straightforward calculation combined with an induction argument shows that,
for all $\ell\in\mathbb{N}$, there are $b^{(\ell)}_{i}$, $i=0,\ldots,d-1$ such
that $b^{(\ell)}_{0}+\cdots+b^{(\ell)}_{d-1}=b^{\ell}$ and

(230)
$U_{\ell}=\left(\begin{array}[]{cccc}a_{1}^{\ell}&\cdots&a_{d-1}^{\ell}&b_{0}^{(\ell)}\\\
1-a_{1}^{\ell}&\cdots&0&b_{1}^{(\ell)}\\\ 0&\ddots&\vdots&\vdots\\\
0&\cdots&1-a_{d-1}^{\ell}&b_{d-1}^{(\ell)}\\\
0&\cdots&0&1-b^{\ell}\end{array}\right).$

Hence, by choosing $\ell$ sufficiently large, we can make $a_{k}^{\ell}$ for
$k=1,\ldots,d-1$ and $b_{i}^{(\ell)}$ for $i=0,\ldots,d-1$ arbitrarily small.

Let $P=\big{(}p^{(1)},\ldots,p^{(d)}\big{)}\in\mathcal{V}_{\rm d.c.}^{d}$ with
columns of unit $1$-norm, where
$p^{(k)}=\big{(}p^{(k)}_{1},\ldots,p^{(k)}_{n}\big{)}$. We may assume WLOG
that $p^{(k)}_{1}>0$ for $k=1,\ldots,d$. Let us denote $p_{1}:=\min_{1\leq
k\leq d-1}p^{(k)}_{1}>0$. Let $t^{(0)}:=(1,0,\ldots,0)$ (with $n$ entries).
Let us denote

(231) $t^{(k)}_{v}:=\frac{1}{1-v}\big{(}p^{(k)}-vt^{(0)}\big{)}$

for $v\in(0,p_{1})$ and $k=1,\ldots,d-1$. For any
$v=(v_{1},\ldots,v_{d-1})\in(0,p_{1})^{d-1}$ and
$w=(w_{0},\ldots,w_{d-1})\in\mathbb{R}_{>0}^{d}$ such that
$w_{0}+\cdots+w_{d-1}<1$, let us also define

(232) $t^{(d)}_{v,w}:=\frac{1}{1-w_{0}-\cdots-
w_{d-1}}\big{(}p^{(d)}-w_{0}t^{(0)}-w_{1}t^{(1)}_{v_{1}}-\cdots-
w_{d-1}t^{(d-1)}_{v_{d-1}}\big{)}.$

A sufficient condition for $t^{(d)}_{v,w}$ to be a probability vector is

(233) $\displaystyle
p^{(d)}_{1}-w_{0}-\sum_{k=1}^{d-1}w_{k}\frac{p^{(k)}_{1}}{1-p_{1}}$
$\displaystyle\geq 0,$ (234) $\displaystyle
p^{(d)}_{i}-\sum_{k=1}^{d-1}w_{k}\frac{p^{(k)}_{i}}{1-p_{1}}$
$\displaystyle\geq 0,\qquad i=2,\ldots,n,$

independent of $v_{1},\ldots,v_{d-1}$. Thus, there is
$w=(w_{0},\ldots,w_{d-1})\in\mathbb{R}_{>0}^{d}$ such that
$t^{(d)}_{v,w^{\prime}}$ is a probability vector for all $v\in(0,p_{1})^{d-1}$
and $w^{\prime}\in\mathbb{R}_{>0}^{d}$ whose entries are upper-bounded by
those of $w$. Suppose then that $\ell\in\mathbb{N}$ is large enough so that
$a_{k}^{\ell}<p_{1}$ for $k=1,\ldots,d-1$ and $b^{\ell}<w_{i}$ (so that
$b^{(\ell)}_{i}\leq b^{\ell}<w_{i}$) for $i=0,\ldots,d-1$ where $a_{k}$,
$b_{i}$, and $b^{(\ell)}_{i}$ are as in (228) and (230). Setting
$v:=\big{(}a_{1}^{\ell},\ldots,a_{d-1}^{\ell}\big{)}$ and
$w^{\prime}:=\big{(}b_{0}^{(\ell)},\ldots,b_{d-1}^{(\ell)}\big{)}$ and
$t^{(k)}:=t^{(k)}_{v}$ for $k=1,\ldots,d-1$ and
$t^{(d)}:=t^{(d)}_{v,w^{\prime}}$, we may set up the stochastic matrix
$T=\big{(}t^{(0)},\ldots,t^{(d)}\big{)}$. It follows that we may write
$TU_{\ell}=P$, i.e.,
$U^{\boxtimes\ell(d-1)}\succeq\tilde{U}^{\boxtimes\ell}\succeq U_{\ell}\succeq
P$.

We now have shown that, for all $P\in\mathcal{V}^{d}_{\rm d.c.}$ with columns
of unit $1$-norm, there is $\ell\in\mathbb{N}$ such that
$U^{\boxtimes\ell}\succeq P$. Let us assume next that $P,Q\in\mathcal{V}_{\rm
d.c.}^{d}$ are such that $P\succeq Q$. WLOG we may assume that the columns of
$P$ and $Q$ have unit 1-norm. Thus, there is $\ell\in\mathbb{N}$ such that

(235) $Q\boxtimes U^{\boxtimes\ell}\succeq(1\,\cdots\,1)\boxtimes
U^{\boxtimes\ell}=U^{\boxtimes\ell}\succeq P,$

showing that $U$ is a power universal.

(i) $\Rightarrow$ (iii): Let $P\in\mathcal{V}^{d}_{\rm d.c.}$ be such that all
the columns of $P$ have unit 1-norm and $\Phi(P)\neq 1$ for all the
nondegenerate monotone homomorphisms of $S^{d}_{\rm d.c.}$ into
$\mathbb{K}\in\\{\mathbb{R}_{+},\mathbb{R}_{+}^{\rm
op},\mathbb{T}\mathbb{R}_{+},\mathbb{T}\mathbb{R}_{+}^{\rm op}\\}$. We may
choose, e.g.,

(236) $P=\left(\begin{array}[]{cccc}1/2&\cdots&1/2&1/d\\\ 1/2&\cdots&0&1/d\\\
\vdots&\ddots&\vdots&\vdots\\\ 0&\cdots&1/2&1/d\end{array}\right)$

for which $\Phi(P)>1$ when $\Phi\in\mathcal{H}^{\rm n.d.}(S^{d}_{\rm
d.c.},\mathbb{R}_{+})\cup\mathcal{H}^{\rm d.c.}(S^{d}_{\rm
d.c.},\mathbb{T}\mathbb{R}_{+})$ and $\Phi(P)<1$ otherwise. According to (i),
there is $\ell\in\mathbb{N}$ such that $U^{\boxtimes\ell}\succeq P$, so that
$\Phi(U)^{\ell}\geq\Phi(P)>1$ for $\Phi\in\mathcal{H}^{\rm n.d.}(S^{d}_{\rm
d.c.},\mathbb{R}_{+})\cup\mathcal{H}^{\rm d.c.}(S^{d}_{\rm
d.c.},\mathbb{T}\mathbb{R}_{+})$ and $\Phi(U)^{\ell}\leq\Phi(P)<1$ otherwise.
All in all, $\Phi(U)\neq 1$ for all the monotone homomorphisms.

∎

######  Remark 4.

Note that for the implication (iii) $\Rightarrow$ (ii) above, we do not need
all non-degenerate monotone homomorphisms to be unequal to $1$. It is
sufficient that this holds for the homomorphisms $\Phi_{e_{d},\\{k,d\\}}$ for
$k\in[d-1]$, and $\Phi_{e_{k},\\{k,k^{\prime},d\\}}$ for
$k,k^{\prime}\in[d-1]$, $k\neq k^{\prime}$.

######  Remark 5.

Note that, according to item (ii) of Proposition 16 and item (iii) of
Proposition 9, $U=\big{(}u^{(1)},\ldots,u^{(d)}\big{)}$ is a power universal
of $S^{d}_{\rm d.c.}$ if and only if $\big{(}u^{(1)},\ldots,u^{(d-1)}\big{)}$
is a power universal of $S^{d-1}$ (n.b., not of $S^{d-1}_{\rm d.c.}$) and
${\rm supp}\,u^{(k)}\subsetneq{\rm supp}\,u^{(d)}$ for $k=1,\ldots,d-1$.

For $d=2$, $U=\big{(}u^{(1)},u^{(2)}\big{)}$ is a power universal of
$S^{d}_{\rm d.c.}$ if and only if ${\rm supp}\,u^{(1)}\subsetneq{\rm
supp}\,u^{(2)}$. For $d=3$, the general form of a power universal, up to the
$\approx$-equivalence, is

(237) $U=\left(\begin{array}[]{ccc}*&*&*\\\ &0&*\\\ 0&*&*\end{array}\right)$

where the asterisques represent positive entries (or vectors with positive
entries).

###  4.4. Results: applying the Vergleichsstellensatz

Applying the Vergleichsstellensatz in the form of Theorem 1, we can use the
results from the previous sections to find the conditions for large sample and
catalytic majorization in the semiring $S^{d}_{\rm d.c.}$, as given in the
following Theorem. Note that just like the analogous result for the semiring
$S^{d}$, the strict inequalities in (238) and (239) already imply that $P$ is
power universal by Proposition 16, hence we do not need to require this
explicitly in the conditions of the Theorem.

The conditions on the monotones and derivations for asymptotic and catalytic
majorization of input $P\in\mathcal{V}^{d}$ and output $Q\in\mathcal{V}^{d}$
can be expressed as

(238)
$\displaystyle\Phi_{\underline{\alpha},C}(P)<\Phi_{\underline{\alpha},C}(Q)$
$\displaystyle\forall\;\Phi_{\underline{\alpha},C}\in\mathcal{H}^{\rm
n.d.}(S^{d}_{\rm d.c.},\mathbb{R}_{+}^{\rm op}),$ (239)
$\displaystyle\Phi_{\alpha,c}(P)>\Phi_{\alpha,c}(Q)$
$\displaystyle\forall\;\Phi_{\alpha,c}\in\mathcal{H}^{\rm n.d.}(S^{d}_{\rm
d.c.},\mathbb{R}_{+}),$ (240) $\displaystyle
D_{1}(p^{(k)}\|p^{(d)})>D_{1}(q^{(k)}\|q^{(d)}),\,D_{\infty}(p^{(k)}\|p^{(d)})>D_{\infty}(q^{(k)}\|q^{(d)})$
$\displaystyle\forall k=1,\ldots,d-1.$

Recall that $D_{1}$ is the Kullback-Leibler divergence and $D_{\infty}$ the
max-divergence between two columns. The homomorphisms
$\Phi_{\underline{\alpha},C}\in\mathcal{H}^{\rm n.d.}(S^{d}_{\rm
d.c.},\mathbb{R}_{+}^{\rm op})$ are exactly as in (163), where we again
exclude all degenerate homomorphisms $\Phi^{(k)}$, $k\in[d]$ (i.e. those with
either $\underline{\alpha}=e_{k}$ and $C=\\{k\\}$ for some $k\in[d]$, or
$\underline{\alpha}=e_{k}$ and $C=\\{k,d\\}$ for some $k\in[d-1]$). The
homomorphisms $\Phi_{\alpha,c}\in\mathcal{H}^{\rm n.d.}(S^{d}_{\rm
d.c.},\mathbb{R}_{+})$ were defined in (181) and can be conveniently written
as

(241)
$\Phi_{\alpha,c}(P)=\sum_{i=1}^{n}\big{(}p^{(c)}\big{)}^{\alpha}\big{(}p^{(d)}\big{)}^{1-\alpha},$

where $c\in[d-1]$ and $\alpha>1$.

######  Theorem 17.

Let $P=(p^{(1)},\ldots,p^{(d)})$, $Q=(q^{(1)},\ldots,q^{(d)})$ be tuples of
probability vectors such that $\bigcap_{k=1}^{d}{\rm
supp}\,p^{(k)}\neq\emptyset$ and ${\rm supp}\,p^{(k)}\subseteq{\rm
supp}\,p^{(d)}$ for $k\in[d-1]$, and similarly for $Q$. If the inequalities in
(238), (239) and (240) hold, then we have the following:

  1. (a)

there exist a stochastic map $T$ and a tuple of probability vectors
$(r^{(1)},\ldots,r^{(d)})$, satisfying $\bigcap_{k=1}^{d}{\rm
supp}\,r^{(k)}\neq\emptyset$ and ${\rm supp}\,r^{(k)}\subseteq{\rm
supp}\,r^{(d)}$ for $k\in[d-1]$, such that

(242) $T(r^{(k)}\otimes p^{(k)})=r^{(k)}\otimes q^{(k)}\quad\text{for
}k\in[d],$

and we may choose, for $n$ sufficiently large:

(243)
$r^{(k)}=\frac{1}{n+1}\bigoplus_{\ell=0}^{n}\left(q^{(k)}\right)^{\otimes\ell}\otimes\left(p^{(k)}\right)^{\otimes(n-\ell)}\quad\text{
for }k\in[d],$

  2. (b)

for $n$ sufficiently large there exists a stochastic map $T_{n}$ such that

(244) $T_{n}(p^{(k)})^{\otimes n}=(q^{(k)})^{\otimes n}\quad\text{for
}k\in[d].$

Conversely, if either one of these holds, then the inequalities (238), (239)
and (240) hold non-strictly.

######  Remark 6.

We may derive an asymptotic version of this result, analogous to Theorem 11.
However, we would have to require the input $P$ to be power universal, which
according to the characterization in (ii) of Proposition 16 is quite
restrictive. Nevertheless, for the case $d=2$, the situation is manageable,
since there are essentially three interesting cases: either both columns have
the same support and are different, or both columns have part of the support
outside of the support of the other column, or one column has support strictly
contained in the other. Majorization results (both for the exact and
asymptotic setting) for the first case were derived in [7], and the second
case is covered by the results in Section 3.5. The third case is covered by
Theorem 17 (for the exact setting) above and by Theorem 19 (for the asymptotic
setting) in the next section, where we will derive an analogue of Theorem 11
for the case $d=2$.

Note that for $d>2$ there are many possibilities for the relationships of the
supports of the columns, and each would require a different semiring to be
studied. We will discuss this issue further in our concluding remarks.

###  4.5. The two-column case: dichotomies

Here we specify to the case $d=2$. In this context, any pair
$\big{(}p^{(1)},p^{(2)}\big{)}$, where $p^{(1)}$ and $p^{(2)}$ are probability
vectors (i.e., $\big{\|}p^{(1)}\big{\|}_{1}=1=\big{\|}p^{(2)}\big{\|}_{1}$)
and satisfy ${\rm supp}\,p^{(1)}\subseteq{\rm supp}\,p^{(2)}$, is called a
_dichotomy_. This special case will turn out to be particularly interesting in
the theory of thermal state transformations in the next section. We derive
sufficient conditions for exact large-sample and catalytic majorization in
this setting and sufficient and necessary conditions for approximate large-
sample and catalytic majorization with asymptotically vanishing error in
Corollary 18 and Theorem 19. We describe the conditions in the form of
inequalities involving the traditional Rényi divergences. We also complete the
picture of asymptotic majorization in large samples and catalytically in
Corollary 20 to obtain a full characterization without having to make any
support restrictions.

For all dichotomies $\big{(}p^{(1)},p^{(2)}\big{)}$, we have

(245)
$\frac{1}{\alpha-1}\log{\Phi_{(\alpha,1-\alpha),\\{1,2\\}}\big{(}p^{(1)}\|p^{(2)}\big{)}}=D_{\alpha}\big{(}p^{(1)}\big{\|}p^{(2)}\big{)},$

when $\alpha\in[0,1)$, corresponding to the homomorphisms in $\mathcal{H}^{\rm
n.d.}(S^{d}_{\rm d.c.},\mathbb{R}_{+}^{\rm op})$, and

(246)
$\frac{1}{\alpha-1}\log{\Phi_{\alpha,1}\big{(}p^{(1)}\|p^{(2)}\big{)}}=D_{\alpha}\big{(}p^{(1)}\big{\|}p^{(2)}\big{)},$

when $\alpha\in(0,\infty)$, corresponding to the homomorphisms in
$\mathcal{H}^{\rm n.d.}(S^{d}_{\rm d.c.},\mathbb{R}_{+})$. We have the two
degenerate homomorphisms
$\Phi^{(1)}=\Phi_{(1,0),\\{1\\}}=\Phi_{(1,0),\\{1,2\\}}$ and
$\Phi^{(2)}=\Phi_{(0,1),\\{2\\}}$. Up to a positive multiplier (and
interchangeability), we have only one monotone derivation at $\Phi^{(1)}$,
which is simply the Kullback-Leibler divergence, and none at $\Phi^{(2)}$. We
also have essentially only one nondegenerate tropical homomorphism
$\Phi^{\mathbb{T}}_{1}$ and

(247)
$\log{\Phi^{\mathbb{T}}_{1}\big{(}p^{(1)},p^{(2)}\big{)}}=D_{\infty}\big{(}p^{(1)}\big{\|}p^{(2)}\big{)}$

for all dichotomies $\big{(}p^{(1)},p^{(2)}\big{)}$. Thus, we may unify the
nondegenerate monotone homomorphisms and derivations of $S^{2}_{\rm d.c.}$
within the family $D_{\alpha}$, $0\leq\alpha\leq\infty$, of Rényi divergences;
see Figure 4 for a depiction. The monotonicity of the homomorphisms and
derivation is now encapsulated by the data processing inequality

(248) $D_{\alpha}\big{(}p^{(1)}\big{\|}p^{(2)}\big{)}\geq
D_{\alpha}\big{(}Tp^{(1)}\big{\|}Tp^{(2)}\big{)},\qquad\forall\alpha\in[0,\infty],$

for all dichotomies $\big{(}p^{(1)},p^{(2)}\big{)}$ and stochastic matrices
$T$.

We reformulate Theorem 17 specified to the case of dichotomies and in terms of
inequalities of Rényi divergences.

######  Corollary 18.

Let $\big{(}p^{(1)},p^{(2)}\big{)}$ and $\big{(}q^{(1)},q^{(2)}\big{)}$ be
dichotomies. If

(249)
$D_{\alpha}\big{(}p^{(1)}\big{\|}p^{(2)}\big{)}>D_{\alpha}\big{(}q^{(1)}\big{\|}q^{(2)}\big{)},\qquad\forall\alpha\in[0,\infty],$

then we have the following:

  * (a)

There is a stochastic matrix $T$ and a dichotomy
$\big{(}r^{(1)},r^{(2)}\big{)}$ such that

(250) $T\big{(}r^{(k)}\otimes p^{(k)}\big{)},\qquad k=1,2.$

There is $n\in\mathbb{N}$ such that we may choose

(251)
$r^{(k)}=\frac{1}{n+1}\bigoplus_{\ell=0}^{n}\big{(}q^{(k)}\big{)}^{\otimes\ell}\otimes\big{(}p^{(k)}\big{)}^{\otimes(n-\ell)},\quad
k=1,2.$

  * (b)

For any $n\in\mathbb{N}$ sufficiently large, there is a stochastic matrix
$T_{n}$ such that

(252) $T_{n}\big{(}p^{(k)}\big{)}^{\otimes n}=\big{(}q^{(k)}\big{)}^{\otimes
n},\qquad k=1,2.$

Conversely, if item (a) or (b) above holds, then (249) holds with non-strict
inequalities.

\begin{overpic}[scale={0.65},unit=1mm]{2d.png} \put(0.0,9.0){\large
$\Phi^{(2)}$ } \put(49.0,9.0){\large $\Phi^{(1)}$ } \put(0.0,20.0){\Large
{\color[rgb]{0.0078125,0.390625,0.078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.0078125,0.390625,0.078125}$D_{0}$}
} \put(0.0,28.0){
{\color[rgb]{0.0078125,0.390625,0.078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.0078125,0.390625,0.078125}$\Phi_{e_{2},\\{1,2\\}}$}
} \put(18.0,9.0){\large
{\color[rgb]{0.0078125,0.390625,0.078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.0078125,0.390625,0.078125}$0<\alpha<1$}
} \put(18.0,20.0){\Large
{\color[rgb]{0.0078125,0.390625,0.078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.0078125,0.390625,0.078125}$D_{\alpha}$}
} \put(18.0,28.0){
{\color[rgb]{0.0078125,0.390625,0.078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.0078125,0.390625,0.078125}$\Phi_{(\alpha,1-\alpha),\\{1,2\\}}$}
} \put(90.0,9.0){\large
{\color[rgb]{0.0078125,0.390625,0.078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.0078125,0.390625,0.078125}$1<\alpha<\infty$}
} \put(90.0,20.0){\Large
{\color[rgb]{0.0078125,0.390625,0.078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.0078125,0.390625,0.078125}$D_{\alpha}$}
} \put(90.0,28.0){
{\color[rgb]{0.0078125,0.390625,0.078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.0078125,0.390625,0.078125}$\Phi_{(\alpha,1-\alpha),\\{1,2\\}}$}
} \put(49.0,20.0){\Large
{\color[rgb]{0.349609375,0.39765625,0.933984375}\definecolor[named]{pgfstrokecolor}{rgb}{0.349609375,0.39765625,0.933984375}$D_{1}$}
} \put(135.0,9.0){\large
{\color[rgb]{0.890625,0.046875,0.046875}\definecolor[named]{pgfstrokecolor}{rgb}{0.890625,0.046875,0.046875}$\alpha=\infty$}
} \put(140.0,20.0){\Large
{\color[rgb]{0.890625,0.046875,0.046875}\definecolor[named]{pgfstrokecolor}{rgb}{0.890625,0.046875,0.046875}$D_{\infty}$}
} \put(140.0,28.0){
{\color[rgb]{0.890625,0.046875,0.046875}\definecolor[named]{pgfstrokecolor}{rgb}{0.890625,0.046875,0.046875}$\Phi^{\mathbb{T}}_{1}$}
} \end{overpic} Figure 4.  The monotone homomorphisms and derivations depicted
for $S^{2}_{\rm d.c.}$: The line is the compactification of the half line
$[0,\infty]$. Nondegenerate temperate homomorphisms are in green in the area
$\alpha\in[0,1)\cup(1,\infty)$. These correspond to the Rényi divergences
$D_{\alpha}$. At points $\alpha=0$ and $\alpha=1$ we also have the degenerate
homomorphisms $\Phi^{(2)}$ and $\Phi^{(1)}$, the latter of which is associated
with the non-zero derivation $D_{1}$, the Kullback-Leibler divergence. At the
infinity (in red) we have the tropical homomorphism corresponding to the max-
divergence $D_{\infty}$.

We may also derive an asymptotic version of the above result using largely the
same methods as in the proof of Theorem 11. However, since the second
probability vector dominates the first one in a dichotomy, we may remove the
vanishing error completely on the second probability vector as stated at the
end of the following result.

######  Theorem 19.

Consider dichotomies $\big{(}p^{(1)},p^{(2)}\big{)}$ and
$\big{(}q^{(1)},q^{(2)}\big{)}$ and assume ${\rm supp}\,p^{(1)}\subsetneq{\rm
supp}\,p^{(2)}$. The following conditions are equivalent:

  * (i)

For all $\alpha\in(0,\infty]$,

(253) $D_{\alpha}\big{(}p^{(1)}\big{\|}p^{(2)}\big{)}\geq
D_{\alpha}\big{(}q^{(1)}\big{\|}q^{(2)}\big{)}.$

  * (ii)

For all $\varepsilon>0$, there is a stochastic matrix $T_{\varepsilon}$ and
dichotomies $\big{(}q_{\varepsilon}^{(1)},q_{\varepsilon}^{(2)}\big{)}$ and
$\big{(}r_{\varepsilon}^{(1)},r_{\varepsilon}^{(2)}\big{)}$ such that

(254) $\big{\|}q^{(k)}-q^{(k)}_{\varepsilon}\big{\|}_{1}\leq\varepsilon,\qquad
k=1,2,$

and

(255) $T_{\varepsilon}\big{(}r_{\varepsilon}^{(k)}\otimes
p^{(k)}\big{)}=r_{\varepsilon}^{(k)}\otimes q_{\varepsilon}^{(k)},\qquad
k=1,2.$

Again, we may choose $r_{\varepsilon}^{(k)}$ as in (251) (with
$q_{\varepsilon}^{(k)}$ substituted for $q^{(k)}$) for sufficiently large
$n\in\mathbb{N}$.

  * (iii)

For all $\varepsilon>0$, there is a dichotomy
$\big{(}q_{\varepsilon}^{(1)},q_{\varepsilon}^{(2)}\big{)}$ such that

(256) $\big{\|}q^{(k)}-q_{\varepsilon}^{(k)}\big{\|}_{1}\leq\varepsilon,\qquad
k=1,2,$

and for $n\in\mathbb{N}$ sufficiently large there is a stochastic matrix
$T_{\varepsilon,n}$ such that

(257) $T_{\varepsilon,n}\big{(}p^{(k)}\big{)}^{\otimes
n}=\big{(}q_{\varepsilon}^{(k)}\big{)}^{\otimes n},\qquad k=1,2.$

In statements (ii) and (iii) above, we may assume that
$q_{\varepsilon}^{(2)}=q^{(2)}$ for all $\varepsilon>0$.

###### Proof.

Let us assume condition (i). Let us choose $w\in\mathcal{P}_{n}$ which
dominates $q^{(2)}$ (and, hence, automatically $q^{(1)}$). Naturally, we may
choose $w=q^{(2)}$; this choice yields the final claim of the statement of the
theorem, as one clearly subsequently sees. Let us denote, for brevity,
$\big{(}p^{(1)},p^{(2)}\big{)}=:P$, $\big{(}q^{(1)},q^{(2)}\big{)}=:Q$, and
$W:=(w,w)$ and define, for all $\varepsilon\in(0,2]$,

(258)
$q^{(k)}_{\varepsilon}:=\left(1-\frac{\varepsilon}{2}\right)q^{(1)}+\frac{\varepsilon}{2}w,\qquad
k=1,2,$

and

(259)
$Q_{\varepsilon}:=\big{(}q^{(1)}_{\varepsilon},q^{(2)}_{\varepsilon}\big{)}=\left(1-\frac{\varepsilon}{2}\right)Q+\frac{\varepsilon}{2}W.$

Clearly, $Q_{\varepsilon}$ is a dichotomy with mutually supporting columns for
all $\varepsilon\in(0,2]$. Moreover,
$\big{\|}q^{(k)}-q^{(k)}_{\varepsilon}\big{\|}_{1}\leq\varepsilon$, as one
easily verifies. We may show that
$D_{\alpha}\big{(}p^{(1)}\big{\|}p^{(2)}\big{)}>D_{\alpha}\big{(}q^{(1)}_{\varepsilon}\big{\|}q^{(2)}_{\varepsilon}\big{)}$
for all $\alpha\in[0,1)$ in the same way as in the proof of Theorem 11.

Using the joint convexity of the Kullback-Leibler divergence, we have, for all
$\varepsilon\in(0,2]$,

(260)
$D_{1}\big{(}q^{(1)}_{\varepsilon}\big{\|}q^{(2)}_{\varepsilon}\big{)}\leq\left(1-\frac{\varepsilon}{2}\right)D_{1}\big{(}q^{(1)}\big{\|}q^{(2)}\big{)}+\frac{\varepsilon}{2}\underbrace{D_{1}(w\|w)}_{=0}\leq
D_{1}\big{(}q^{(1)}\big{\|}q^{(2)}\big{)}\leq
D_{1}\big{(}p^{(1)}\big{\|}p^{(2)}\big{)}.$

If $D_{1}\big{(}q^{(1)}\big{\|}q^{(2)}\big{)}=0$, then
$D_{1}\big{(}q^{(1)}\big{\|}q^{(2)}\big{)}=0<D_{1}\big{(}p^{(1)}\big{\|}p^{(2)}\big{)}$
since $p^{(1)}\neq p^{(2)}$. If, on the other hand,
$D_{1}\big{(}q^{(1)}\big{\|}q^{(2)}\big{)}>0$, then the penultimate inequality
in the above calculation is strict. Thus, we have

(261)
$D_{1}\big{(}q^{(1)}_{\varepsilon}\big{\|}q^{(2)}_{\varepsilon}\big{)}<D_{1}\big{(}p^{(1)}\big{\|}p^{(2)}\big{)},\qquad\forall\varepsilon\in(0,2].$

Let now $\alpha\in(1,\infty)$ and denote
$\Phi_{\alpha}:=\Phi_{(\alpha,1-\alpha),\\{1,2\\}}$. Similarly as in the proof
of Theorem 11, we may evaluate, for all $\varepsilon\in(0,2]$,

(262) $\displaystyle
D_{\alpha}\big{(}q^{(1)}_{\varepsilon}\big{\|}q^{(2)}_{\varepsilon}\big{)}$
$\displaystyle\leq\frac{1}{\alpha-1}\log{\bigg{(}Q_{\alpha}(Q)-\frac{\varepsilon}{2}\underbrace{\big{(}\Phi_{\alpha}(Q)-1\big{)}}_{\geq
0}\bigg{)}}$ (263)
$\displaystyle\leq\frac{1}{\alpha-1}\log{\Phi_{\alpha}(Q)}=D_{\alpha}\big{(}q^{(1)}\big{\|}q^{(2)}\big{)}\leq
D_{\alpha}\big{(}p^{(1)}\big{\|}p^{(2)}\big{)}.$

If $\Phi_{\alpha}(Q)=1$, then $\Phi_{\alpha}(Q)=1<\Phi_{\alpha}(P)$ and the
final inequality above is strict. If $\Phi_{\alpha}(Q)>1$, then the
penultimate inequality above is strict. Thus,

(264)
$D_{\alpha}\big{(}q^{(1)}_{\varepsilon}\big{\|}q^{(2)}_{\varepsilon}\big{)}<D_{\alpha}\big{(}p^{(1)}\big{\|}p^{(2)}\big{)},\qquad\forall\varepsilon\in(0,2].$

Let us then look at the tropical homomorphism $\Phi^{\mathbb{T}}_{1}$. Using
monotonicity, we have, for all $\varepsilon\in(0,2]$,

(265) $\displaystyle\Phi^{\mathbb{T}}_{1}(Q_{\varepsilon})$
$\displaystyle=\Phi^{\mathbb{T}}_{1}\left(\left(1-\frac{\varepsilon}{2}\right)Q+\frac{\varepsilon}{2}W\right)\leq\Phi^{\mathbb{T}}_{1}\left(\left(1-\frac{\varepsilon}{2}\right)Q\boxplus\frac{\varepsilon}{2}W\right)$
(266)
$\displaystyle=\max\big{\\{}\Phi^{\mathbb{T}}_{1}(Q),1\big{\\}}=\Phi^{\mathbb{T}}_{1}(Q)\leq\Phi^{\mathbb{T}}_{1}(P).$

Especially,
$\Phi^{\mathbb{T}}_{1}(Q_{\varepsilon})\leq\Phi^{\mathbb{T}}_{1}(Q)$, i.e.,

(267) $\max_{1\leq i\leq
n}\frac{\left(1-\frac{\varepsilon}{2}\right)q^{(1)}_{i}+\frac{\varepsilon}{2}w_{i}}{\left(1-\frac{\varepsilon}{2}\right)q^{(2)}_{i}+\frac{\varepsilon}{2}w_{i}}\leq\max_{1\leq
i\leq n}\frac{q^{(1)}_{i}}{q^{(2)}_{i}}$

for all $\varepsilon\in(0,2]$. When $0<\varepsilon\leq\varepsilon^{\prime}\leq
2$, then $Q_{\varepsilon}\succeq Q_{\varepsilon^{\prime}}$, implying that the
LHS above is non-increasing in $\varepsilon$ and coincides with the RHS when
$\varepsilon\to 0$. Thus, if we have equality with some
$\varepsilon_{0}\in(0,2]$, then we have equality for all
$\varepsilon\in[0,\varepsilon_{0}]$. Let us assume this. Since the LHS is a
pointwise maximum of a finite set of real-analytic functions, the maximum is
reached with the same index $i$ for all $\varepsilon\in[0,\varepsilon_{0}]$.
The real-analyticity of the LHS now implies that the LHS is constant for all
$\varepsilon\in[0,2]$, i.e.,
$\Phi^{\mathbb{T}}_{1}(Q)=1=\Phi^{\mathbb{T}}_{1}(W)$. Thus, if
$\Phi^{\mathbb{T}}_{1}(Q_{\varepsilon})=\Phi^{\mathbb{T}}_{1}(Q)$ for some
$\varepsilon\in(0,2]$, this is the case for all $\varepsilon\in[0,2]$ and
$\Phi^{\mathbb{T}}_{1}(Q)=1<\Phi^{\mathbb{T}}_{1}(P)$. On the other hand, if
$\Phi^{\mathbb{T}}_{1}(Q)>1$ then
$\Phi^{\mathbb{T}}(Q_{\varepsilon})<\Phi^{\mathbb{T}}(Q)$, so that
$\Phi^{\mathbb{T}}_{1}(Q_{\varepsilon})<\Phi^{\mathbb{T}}_{1}(Q)\leq\Phi^{\mathbb{T}}_{1}(P)$.
All in all,

(268)
$D_{\infty}\big{(}q^{(1)}_{\varepsilon}\big{\|}q^{(2)}_{\varepsilon}\big{)}<D_{\infty}\big{(}p^{(1)}\big{\|}p^{(2)}\big{)},\qquad\forall\varepsilon\in(0,2].$

Thus, the conditions of Corollary 18 are satisfied for $Q_{\varepsilon}$ and
$P$, and conditions (ii) and (iii) of the claim follow.

Let us then assume that (ii) or (iii) holds. The proof that
$D_{\alpha}\big{(}p^{(1)}\big{\|}p^{(2)}\big{)}\geq
D_{\alpha}\big{(}q^{(1)}\big{\|}q^{(2)}\big{)}$ for $\alpha\in(0,1)$ follows
from the same argument as in the end of the proof of Theorem 11. To show the
inequality for $\alpha\in(1,\infty)$, we use almost the same argument:
consider any $D_{\alpha}$ with $\alpha\in(1,\infty)$, which corresponds to the
monotone homomorphism $\Phi_{\alpha,1}$. Then we use similar notation and
reasoning as in the proof of Theorem 11, except that $\Phi=\Phi_{\alpha,1}$
and the direction of the inequalities is reversed, and we note that

(269)
$\Phi_{\alpha,1}(Q_{\varepsilon}^{1}\boxplus(1\,\cdots\,1))\geq(1+\varepsilon)^{1-\alpha},$

where we used monotonicity of $\Phi_{\alpha,1}$ and that the sum of each
column in $Q_{\varepsilon}^{1}\boxplus(1\,\cdots\,1)$ is between $1$ and
$1+\varepsilon$. Finally, the inequalities
$D_{\alpha}\big{(}p^{(1)}\big{\|}p^{(2)}\big{)}\geq
D_{\alpha}\big{(}q^{(1)}\big{\|}q^{(2)}\big{)}$ for $\alpha\in\\{1,\infty\\}$
follow from the same inequalities for $\alpha\in(0,1)\cup(1,\infty)$ and the
continuity of $D_{\alpha}$ in $\alpha$.

∎

Combining the above result with Theorem 22 in [7] gives immediately the
following corollary.

######  Corollary 20.

Denote by $\mathcal{P}_{n}$ the set of probability vectors with $n$ components
and consider probability vectors $p^{(2)},q^{(2)}\in\mathcal{P}_{n}$ of full
support and some additional $p^{(1)},q^{(1)}\in\mathcal{P}_{n}$. Also assume
that $p^{(1)}\neq p^{(2)}$. The following conditions are equivalent:

  * (i)

For all $\alpha\geq 1/2$,

(270) $D_{\alpha}\big{(}p^{(1)}\big{\|}p^{(2)}\big{)}\geq
D_{\alpha}\big{(}q^{(1)}\big{\|}q^{(2)}\big{)},\qquad
D_{\alpha}\big{(}p^{(2)}\big{\|}p^{(1)}\big{)}\geq
D_{\alpha}\big{(}q^{(2)}\big{\|}q^{(1)}\big{)}.$

  * (ii)

For all $\varepsilon>0$, there is a stochastic matrix $T_{\varepsilon}$ and
dichotomies $\big{(}q_{\varepsilon}^{(1)},q_{\varepsilon}^{(2)}\big{)}$ and
$\big{(}r_{\varepsilon}^{(1)},r_{\varepsilon}^{(2)}\big{)}$ such that

(271) $\big{\|}q^{(k)}-q^{(k)}_{\varepsilon}\big{\|}_{1}\leq\varepsilon,\qquad
k=1,2,$

and

(272) $T_{\varepsilon}\big{(}r_{\varepsilon}^{(k)}\otimes
p^{(k)}\big{)}=r_{\varepsilon}^{(k)}\otimes q_{\varepsilon}^{(k)},\qquad
k=1,2.$

Again, we may choose $r_{\varepsilon}^{(k)}$ as in (251) (with
$q_{\varepsilon}^{(k)}$ substituted for $q^{(k)}$) for sufficiently large
$n\in\mathbb{N}$.

  * (iii)

For all $\varepsilon>0$, there is a dichotomy
$\big{(}q_{\varepsilon}^{(1)},q_{\varepsilon}^{(2)}\big{)}$ with probability
vectors in $\mathcal{P}_{n}$ such that

(273) $\big{\|}q^{(k)}-q_{\varepsilon}^{(k)}\big{\|}_{1}\leq\varepsilon,\qquad
k=1,2,$

and for $n\in\mathbb{N}$ sufficiently large there is a stochastic matrix
$T_{\varepsilon,n}$ such that

(274) $T_{\varepsilon,n}\big{(}p^{(k)}\big{)}^{\otimes
n}=\big{(}q_{\varepsilon}^{(k)}\big{)}^{\otimes n},\qquad k=1,2.$

In statements (i) and (ii), we may assume that $q_{\varepsilon}^{(2)}=q^{(2)}$
for all $\varepsilon>0$.

###### Proof.

Let us first assume that ${\rm supp}\,p^{(1)}={\rm
supp}\,p^{(2)}=\\{1,\ldots,n\\}$ and ${\rm supp}\,q^{(1)}={\rm
supp}\,q^{(2)}=\\{1,\ldots,n\\}$. In this case, the desired result is given by
Theorem 22 in [7]. Strictly speaking, only the equivalence of statements (i)
and (ii) is shown there, but adding (iii) can be done in the same way that we
have already employed earlier.

Let us now assume that ${\rm supp}\,p^{(1)}\subsetneq{\rm supp}\,p^{(2)}$ or
${\rm supp}\,q^{(1)}\subsetneq{\rm supp}\,q^{(2)}$. Let us first show that the
latter case is out of the question if the first one does not hold. So, assume
that ${\rm supp}\,p^{(1)}={\rm supp}\,p^{(2)}$ while ${\rm
supp}\,q^{(1)}\subsetneq{\rm supp}\,q{(2)}$. If we assume (i), we obtain from
the second set of inequalities that

(275) $1=\sum_{i\in{\rm supp}\,p^{(1)}}p^{(2)}_{i}\leq\sum_{i\in{\rm
supp}\,q^{(1)}}q^{(2)}_{i}<1$

as $\alpha\to 1$, a contradiction. Thus, we only have to consider the case
where ${\rm supp}\,p^{(1)}\subsetneq{\rm supp}\,p^{(2)}$. In this case, the
second set of the inequalities in (270) are irrelevant when $\alpha\geq 1$.
Indeed, $D_{\alpha}\big{(}p^{(2)}\big{\|}p^{(1)}\big{)}=\infty$ when
$\alpha\geq 1$. Thus we may ignore this set of inequalities. For $0<\alpha\leq
1/2$, we have
$D_{\alpha}\big{(}p^{(1)}\big{\|}p^{(2)}\big{)}=\frac{1-\alpha}{\alpha}D_{1-\alpha}\big{(}p^{(2)}\big{\|}p^{(1)}\big{)}$.
This means that, if (i) holds, then
$D_{\alpha}\big{(}p^{(1)}\big{\|}p^{(2)}\big{)}\geq
D_{\alpha}\big{(}q^{(1)}\big{\|}q^{(2)}\big{)}$ for all $\alpha>0$. Naturally
this also holds for $\alpha=0$ as a pointwise limit of the above. Finally,
condition (i) is equivalent with (253), and we are in the situation of Theorem
19 providing the proof for the remainder of the claim. ∎

###  4.6. Thermal majorization

Let us consider a finite-dimensional quantum thermodynamic system. We assume
that the system’s steady state is described by the Gibbs state
$\gamma_{\beta}$ at inverse temperature $\beta>0$, i.e.,

(276) $\gamma_{\beta}=\frac{1}{Z}e^{-\beta H}$

where $Z=\mathrm{Tr}\left(e^{-\beta H}\right)$ and $H$ is the Hamiltonian of
the system. Let $\\{h_{i}\\}_{i=0}^{d-1}$ be the orthonormal basis of the
system’s Hilbert space that diagonalizes $H$, i.e.,
$H=\sum_{i=0}^{d-1}E_{i}|h_{i}\rangle\langle h_{i}|$ where $E_{i}$ are the
eigenvalues of $H$. This means

(277) $\gamma_{\beta}=\sum_{i=0}^{d-1}\lambda^{\beta}_{i}|h_{i}\rangle\langle
h_{i}|$

where $\lambda^{\beta}_{i}=e^{-\beta E_{i}}/Z$. We define the probability
vector $\lambda^{\beta}:=(\lambda^{\beta}_{0},\ldots,\lambda^{\beta}_{d-1})$.
From now on, we assume that $E_{i}>0$ for $i=0,\ldots,d-1$; we are free to
assume this as the zero energy can be shifted if necessary.

We are interested now in the question when a state of this thermodynamic
system can be transformed into another with a thermal operation. Recall that a
quantum channel (completely positive trace-preserving linear map) $\Phi$ whose
input and output systems coincide with this thermodynamic system is a thermal
operation if $\Phi(\gamma_{\beta})=\gamma_{\beta}$. When $\Phi(\rho)=\sigma$
where $\Phi$ is a thermal operation, we say that $\rho$ thermally majorizes
$\sigma$ and denote $\rho\succeq_{\beta}\sigma$. Thermal majorization of
$\rho$ over $\sigma$ in large samples means that there is $n\in\mathbb{N}$
such that $\rho^{\otimes n}\succeq_{\beta}\sigma^{\otimes n}$, i.e., there is
a channel $\Phi_{n}$ on $n$ copies of the system such that
$\Phi_{n}(\rho^{\otimes n})=\sigma^{\otimes n}$ and
$\Phi_{n}(\gamma_{\beta}^{\otimes n})=\gamma_{\beta}^{\otimes n}$. Catalytic
thermal majorization means that there are states $\tau^{(1)},\tau^{(2)}$ on
possibly another system (e.g., a heat bath), where we may interpret
$\tau^{(2)}$ as the Gibbs state of the other system, and a channel $\Phi$ such
that $\Phi(\rho\otimes\tau^{(1)})=\sigma\otimes\tau^{(1)}$ and
$\Phi(\gamma_{\beta}\otimes\tau^{(2)})=\gamma_{\beta}\otimes\tau^{(2)}$. We
are particularly interested in asymptotic catalytic thermal majorization: for
any $\varepsilon>0$, there are catalysts
$\tau_{\varepsilon}^{(1)},\tau_{\varepsilon}^{(2)}$ on some system (which may
depend on $\varepsilon$), a state $\sigma_{\varepsilon}$ on our system of
interest such that $\|\sigma-\sigma_{\varepsilon}\|_{1}<\varepsilon$, and a
channel $\Phi_{\varepsilon}$ such that
$\Phi_{\varepsilon}(\rho\otimes\tau_{\varepsilon}^{(1)})=\sigma_{\varepsilon}\otimes\tau_{\varepsilon}^{(1)}$
and
$\Phi_{\varepsilon}(\gamma_{\beta}\otimes\tau_{\varepsilon}^{(2)})=\gamma_{\beta}\otimes\tau_{\varepsilon}^{(2)}$.

We concentrate on the case where the states commute with the Gibbs state. If
the energy spectrum is nondegenerate, i.e., there are no repeating eigenvalues
$E_{i}$, then $[\rho,\gamma_{\beta}]=0$ if and only if $\rho$ diagonalizes in
the energy eigenbasis, i.e.,

(278) $\rho=\sum_{i=0}^{d-1}\lambda_{i}|h_{i}\rangle\langle h_{i}|.$

Even if the energy spectrum is degenerate, we will focus on states which are
diagonalizable in the energy eigenbasis, i.e., those $\rho$ as in (278) with
$\lambda_{i}\geq 0$, $\lambda_{0}+\cdots+\lambda_{d-1}=1$. To explicitly refer
to the state, we will associate the above $\\{h_{i}\\}_{i}$-diagonal state
$\rho$ with the probability vector
$\lambda^{\rho}=(\lambda^{\rho}_{0},\ldots,\lambda^{\rho}_{d-1})$ where

(279) $\lambda^{\rho}_{i}=\lambda_{i}=\langle h_{i}|\rho\,h_{i}\rangle,\qquad
i=0,\ldots,d-1.$

If $\rho$ and $\sigma$ are $\\{h_{i}\\}_{i}$-diagonal, then one can easily see
that $\Phi(\rho)=\sigma$ for a channel $\Phi$ if and only if
$T\lambda^{\rho}=\lambda^{\sigma}$ where $T=(T_{i,j})_{i,j=0}^{d-1}$ is a
stochastic matrix given by $T_{i,j}=\langle h_{i}|\Phi(|h_{j}\rangle\langle
h_{j}|)|h_{i}\rangle$. This means that, for $\\{h_{i}\\}_{i}$-diagonal states
$\rho$ and $\sigma$, we have $\rho\succeq_{\beta}\sigma$ if and only if there
is a stochastic matrix $T$ such that $T\lambda^{\rho}=\lambda^{\sigma}$ and
$T\lambda^{\beta}=\lambda^{\beta}$, i.e.,

(280)
$\big{(}\lambda^{\rho},\lambda^{\beta}\big{)}\succeq(\lambda^{\sigma},\lambda^{\beta}).$

Thus, we arrive at matrix majorization in the case $d=2$ where the second
column dominates the first one since we assume that the energy spectrum is
non-vanishing. Moreover, we have that $\rho$ thermally majorizes $\sigma$ in
the asymptotic catalytic regime if and only if, for all $\varepsilon>0$, there
are catalytic probability vectors
$r_{\varepsilon}^{(1)},r_{\varepsilon}^{(2)}$ (of undetermined finite length),
$\lambda_{\varepsilon}\in\mathcal{P}_{d}$ such that
$\|\lambda^{\sigma}-\lambda_{\varepsilon}\|_{1}<\varepsilon$ and a stochastic
matrix $T_{\varepsilon}$ such that $T_{\varepsilon}(\lambda^{\rho}\otimes
r_{\varepsilon}^{(1)})=\lambda_{\varepsilon}\otimes r_{\varepsilon}^{(1)}$ and
$T_{\varepsilon}(\lambda^{\beta}\otimes
r_{\varepsilon}^{(2)})=\lambda^{\beta}\otimes r_{\varepsilon}^{(2)}$. Thus,
asymptotic catalytic thermal majorization can be recast as asymptotic
catalytic matrix majorization which we have exhaustively characterized in
Section 4.5.

Consider now states $\rho$ and $\sigma$ both diagonalizable in the energy
eigenbasis $\\{h_{i}\\}_{i}$. If $\rho$ and $\sigma$ are both of full rank (as
is the Gibbs state $\gamma_{\beta}$), then, according to Corollary 24 of [7],
$\rho$ asymptotically catalytically thermally majorizes $\sigma$ if and only
if $D_{\alpha}(\lambda^{\rho}\|\lambda^{\beta})\geq
D_{\alpha}(\lambda^{\sigma}\|\lambda^{\beta})$ and
$D_{\alpha}(\lambda^{\beta}\|\lambda^{\rho})\geq
D_{\alpha}(\lambda^{\beta}\|\lambda^{\sigma})$ for all $\alpha\geq 1/2$. Now
we can also address the case of general rank. If $\rho$ is not of full rank,
then, according to Proposition 16, $(\lambda^{\rho},\lambda^{\beta})$ is a
power universal of $S^{2}_{\rm d.c.}$ and, according to Theorem 19, $\rho$
asymptotically catalytically thermally majorizes $\sigma$ if and only if only
$D_{\alpha}(\lambda^{\rho}\|\lambda^{\beta})\geq
D_{\alpha}(\lambda^{\sigma}\|\lambda^{\beta})$ for all $\alpha\geq 0$. In this
case, we have $D_{\alpha}(\lambda^{\beta}\|\lambda^{\rho})=\infty$ for
$\alpha\geq 1$. Because also

(281) $\displaystyle D_{\alpha}(\lambda^{\beta}\|\lambda^{\rho})$
$\displaystyle=\frac{\alpha}{1-\alpha}D_{1-\alpha}(\lambda^{\rho}\|\lambda^{\beta})\geq\frac{\alpha}{1-\alpha}D_{1-\alpha}(\lambda^{\sigma}\|\lambda^{\beta})=D_{\alpha}(\lambda^{\beta}\|\lambda^{\sigma})$

for all $\alpha\in(0,1)$, we see that the asymptotic catalytic thermal
majorization of the state $\rho$ of not full rank over $\sigma$ is equivalent
with exactly the same inequalities as in the full-rank case. The case where
$\rho$ asymptotically catalytically thermally majorizes $\sigma$ while $\rho$
is of full support and $\sigma$ is not is impossible. We can see this as
follows: Suppose that $\rho$ asymptotically catalytically thermally majorizes
$\sigma$. Because $D_{\alpha}$ are monotones, we now have that
$D_{\alpha}(\lambda^{\rho}\|\lambda^{\beta})\geq
D_{\alpha}(\lambda^{\sigma}\|\lambda^{\beta})$ for all $\alpha\geq 0$. As
$\alpha\to 0$, it follows that

(282) $\sum_{i\in{\rm supp}\,\lambda^{\rho}}e^{-\beta E_{i}}\leq\sum_{i\in{\rm
supp}\,\lambda^{\sigma}}e^{-\beta E_{i}}.$

Because $E_{i}>0$ for all $i$, this means that $|{\rm
supp}\,\lambda^{\rho}|\leq|{\rm supp}\,\lambda^{\sigma}|$, i.e., the support
of $\rho$ cannot be larger than the support of $\sigma$.

Note that, whenever $\rho$ diagonalizes in the energy eigenbasis, then
$D(\lambda^{\rho}\|\lambda^{\beta})=\tilde{D}_{\alpha}(\rho\|\gamma_{\beta})$
where $\tilde{D}_{\alpha}$ is the ‘sandwiched’ quantum Rényi divergence, i.e.,

(283)
$\tilde{D}_{\alpha}(\rho\|\tau)=\left\\{\begin{array}[]{ll}-\log{\mathrm{Tr}\left(\sigma\,{\rm
supp}\,\rho\right)},&\alpha=0\ {\rm and}\ {\rm supp}\,\rho\cap{\rm
supp}\,\sigma\neq\\{0\\},\\\
\frac{1}{\alpha-1}\log{\mathrm{Tr}\left(\big{(}\sigma^{\frac{1-\alpha}{2\alpha}}\rho\sigma^{\frac{1-\alpha}{2\alpha}}\big{)}^{\alpha}\right)},&\alpha\in(0,1)\
{\rm and}\ {\rm supp}\,\rho\cap{\rm supp}\,\sigma\neq\\{0\\},\\\
\mathrm{Tr}\left(\rho(\log{\rho}-\log{\sigma})\right),&\alpha=1\ {\rm and}\
{\rm supp}\,\rho\subseteq{\rm supp}\,\sigma,\\\
\frac{1}{\alpha-1}\log{\mathrm{Tr}\left(\big{(}\sigma^{\frac{1-\alpha}{2\alpha}}\rho\sigma^{\frac{1-\alpha}{2\alpha}}\big{)}^{\alpha}\right)},&\alpha\in(0,1)\
{\rm and}\ {\rm supp}\,\rho\subseteq{\rm supp}\,\sigma,\\\
\big{\|}\sigma^{-1/2}\rho\sigma^{-1/2}\big{\|},&\alpha=\infty\ {\rm and}\ {\rm
supp}\,\rho\subseteq{\rm supp}\,\sigma,\\\ \infty&{\rm
otherwise}\end{array}\right.$

where $\|\cdot\|$ is the operator norm and we use ${\rm supp}\,\rho$ for both
the supporting subspace of $\rho$ and for the orthogonal projection onto this
subspace. Let us define the free energies $F^{\pm}_{\alpha,\beta}$ through

(284)
$F^{+}_{\alpha,\beta}(\rho):=\tilde{D}_{\alpha}(\rho\|\gamma_{\beta}),\quad
F^{-}_{\alpha,\beta}(\rho):=\tilde{D}_{\alpha}(\gamma_{\beta}\|\rho)$

for all $\alpha\geq 1/2$. Thus, the above considerations yield the following
result.

######  Corollary 21.

Suppose that the eigen-energies $E_{i}>0$ for all $i$, and $\rho$ and $\sigma$
diagonalize in the energy eigenbasis. Then $\rho$ asymptotically catalytically
thermally majorizes $\sigma$ if and only if

(285) $F^{\pm}_{\alpha,\beta}(\rho)\geq
F^{\pm}_{\alpha,\beta}(\sigma),\qquad\forall\alpha\geq\frac{1}{2}.$

Note that, although this result was previously claimed in [4] (see also [10]
for discussions on the proof and possible fixes), our present proof avoids
some technical issues in the original proof. We also would like to highlight
the fact that, instead of using the result on vector majorization proven in
[13], our semiring methods allow us to directly study the problem from the
matrix majorization view without having to embed the problem in the vector
majorization form as was done in [4].

Our results also allow us to study multiple thermal majorization: for
$d$-tuples $\big{(}\rho^{(1)},\ldots,\rho^{(d)}\big{)}$ and
$\big{(}\sigma^{(1)},\ldots,\sigma^{(d)}\big{)}$ of states, we denote

(286)
$\big{(}\rho^{(1)},\ldots,\rho^{(d)}\big{)}\succeq_{\beta}\big{(}\sigma^{(1)},\ldots,\sigma^{(d)}\big{)}$

if there is a thermal channel $\Phi$ (i.e.,
$\Phi(\gamma_{\beta})=\gamma_{\beta}$) such that
$\Phi\big{(}\rho^{(k)}\big{)}=\sigma^{(k)}$ for $k=1,\ldots,d$. This
majorization can naturally also be studied in the large-sample, catalytic, and
asymptotic regimes, the latter one arguably being the most physically relevant
case. If we assume that all the states $\rho^{(k)}$ and $\sigma^{(k)}$
diagonalize in the energy eigenbasis, we are naturally again back to matrix
majorization with the dominating column $\lambda^{\beta}$. We point out though
that, in order to derive necessary and sufficient conditions for asymptotic
thermal majorization in this case,
$\big{(}\lambda^{\rho^{(1)}},\ldots,\lambda^{\rho^{(d)}},\lambda^{\beta}\big{)}$
has to be a power universal of the semiring $S^{d+1}_{\rm d.c.}$. Conditions
for this are quite strict, as we have seen in Proposition 16. Thus, there
remains plenty of unanswered questions in multiple thermal majorization.

##  5\. Conclusion and outlook

We have identified sufficient conditions for matrix majorization in large
samples (i.e., having many copies of the matrices) as well as in the catalytic
regime with varying support conditions. This is in contrast to the earlier
work [7], where the columns within each matrix were assumed to have a common
support. We have seen that the conditions can be written in the form of
inequalities involving multi-party generalizations of the bivariate Rényi
divergences $D_{\underline{\alpha}}$ but, unlike in the common-support case,
the support restrictions greatly affect the set of multi-party divergences to
be considered. Moreover, additional conditions arise at the boundaries where
the $\underline{\alpha}$-parameter space is cut. We have also derived
sufficient conditions for asymptotic large-sample and catalytic matrix
majorization in the case of different support conditions. Many of these
conditions are also necessary. In particular, our results completely resolve
the problem of asymptotic catalytic thermal majorization in the field of
quantum thermodynamics also studied in [4].

One issue with our results is that the sufficient conditions for the
majorization of a matrix $P$ over another matrix $Q$ in the large-sample or
catalytic, and both exact and asymptotic regime, is that the input matrix $P$
has to be a power universal of the preordered semiring we are studying. In the
case of exact large-sample or catalytic majorization (Theorems 10 and 17), the
strict ordering of the values of the homomorphisms already imply that $P$ is
power universal. However, in the case of asymptotic large-sample or catalytic
majorization (Theorems 11 and 19), we have to require $P$ to be power
universal. Being power universal is typically quite restrictive, as
highlighted in Propositions 9 and 16. We suggest the following strategy to
overcome this: If $P$ is not a power universal with respect to either of the
semirings we are studying in this work, we should redefine the semiring so
that all the matrices in this new semiring are required to have the same
support restrictions satisfied by $P$. As an example,
$P=\big{(}p^{(1)},\ldots,p^{(d)}\big{)}$ might be such that $p^{(d)}$
dominates all other columns and ${\rm supp}\,p^{(1)}=\cdots={\rm
supp}\,p^{(d-1)}$. We now move on to the semiring where all the matrices
satisfy these support conditions. If we also remove possible repetitions of
the same columns, $P$ is now a power universal of the new semiring and we
obtain tighter conditions for majorization of $P$ over other matrices. More
generally, given any $P$, we define a new semiring $S_{\rm res}^{d}$ by
specifying for any ordered pair of columns $(k,k^{\prime})$,
$k,k^{\prime}\in[d]$, whether either ${\rm supp}\,p^{(k)}\subseteq{\rm
supp}\,p^{(k^{\prime})}$, or ${\rm supp}\,p^{(k)}\supseteq{\rm
supp}\,p^{(k^{\prime})}$, or ${\rm supp}\,p^{(k)}={\rm
supp}\,p^{(k^{\prime})}$, or there is no condition. One checks that the
resulting restricted set $S_{\rm res}^{d}$ is a semiring with the usual
operations $\boxplus,\boxtimes$ and pre-order $\preceq$. Extrapolating the
results we found for the conditions for $U$ to be power universal in
Propositions 9 and 16, and Lemma 12 in [7] (the case of minimal restrictions,
one dominating column, and equal supports, respectively), we expect that each
condition on the supports of two columns will give rise to a corresponding
condition for $U$, according to the following table.

Condition on $P\in S_{\rm res}^{d}$ | Condition on power universal $U\in S_{\rm res}^{d}$
---|---
${\rm supp}\,p^{(k)}\subseteq{\rm supp}\,p^{(k^{\prime})}$ | ${\rm supp}\,u^{(k)}\subsetneq{\rm supp}\,u^{(k^{\prime})}$
${\rm supp}\,p^{(k)}\supseteq{\rm supp}\,p^{(k^{\prime})}$ | ${\rm supp}\,u^{(k)}\supsetneq{\rm supp}\,u^{(k^{\prime})}$
${\rm supp}\,p^{(k)}={\rm supp}\,p^{(k^{\prime})}$ | $u^{(k)}\neq u^{(k^{\prime})}$
no condition |  ${\rm supp}\,u^{(k)}\nsubseteq{\rm supp}\,u^{(k^{\prime})}$ and ${\rm supp}\,u^{(k^{\prime})}\nsubseteq{\rm supp}\,u^{(k)}$

In both semirings studied in this paper, we were able to show that

(287) $U\text{ is power universal}\quad\Longleftrightarrow\quad\Phi(U)\neq
1\quad\forall\,\Phi\text{ nondegenerate homomorphism.}$

In proving this, we used conditions on $U$ similar to the ones in the table
above. Hence, we conjecture that (287) also holds for a semiring $S_{\rm
res}^{d}$ with other suppport restrictions. Going even further, (287) might be
true for more general semirings (i.e. not just the matrix semirings considered
here).

From this we can see that, given any matrix $P$ that does not have repeated
columns, we can tailor the semiring $S_{\rm res}^{d}$ such that $P$ is power
universal in that semiring. We expect that the homomorphisms and derivations
corresponding to $S_{\rm res}^{d}$ are similar to the ones found in this
paper, precisely those for parameters $\underline{\alpha}$ or
$\underline{\beta}$ that are well-defined, i.e. those where there does not
appear a factor $\left(q^{(k)}_{i}\right)^{\alpha}$ or
$\left(q^{(k)}_{i}\right)^{\beta}$ with $\alpha,\beta<0$ where $q^{(k)}_{i}$
vanishes for at least one matrix $Q$ in the semiring. In this way, we would be
able to find the conditions for large-sample and catalytic majorization, both
for the exact and asymptotic case, for an input matrix with any kind of
support structure, not just the ones that are power universal in the semirings
discussed here or in [7].

From a practical point of view, the notion of asymptotic matrix majorization
in the large-sample or catalytic regime, as characterized in Theorems 11 and
19, is the most relevant case. After all, it is often enough to know that
large-sample or catalytic majorization only holds approximately, possibly with
vanishing error. Our current methods are geared towards identifying exact
majorization in large samples or catalytically and often yield extra
conditions which are not needed in the asymptotic picture, as we have seen.
Finding conditions directly for the desired asymptotic results without having
to take a scenic route through the theory and results for exact majorization
would obviously be of high interest.

There is ever-increasing interest also in multi-party quantum divergences [15,
17]. However, although we may define various multi-party quantum divergences
and often even show that they have desirable properties, e.g., monotonicity
under operating with the same quantum channel on all the states (data
processing inequality) and additivity under tensor products, characterization
of all the quantum divergences with these (and possibly other) properties
seems to be a daunting task, even in the two-party case [20]. Despite these
difficulties, we may still define semirings of $d$-tuples
$\vec{\rho}=\big{(}\rho^{(1)},\ldots,\rho^{(d)}\big{)}$ of quantum states with
varying conditions for the supports ${\rm supp}\,\rho^{(k)}$, where the
addition and multiplication are defined through componentwise direct sum and
tensor product respectively. These semirings can be preordered by denoting

(288)
$\big{(}\rho^{(1)},\ldots,\rho^{(d)}\big{)}\succeq\big{(}\sigma^{(1)},\ldots,\sigma^{(d)}\big{)}$

when there is a quantum channel $\Phi$ such that
$\Phi\big{(}\rho^{(k)}\big{)}=\sigma^{(k)}$ for $k=1,\ldots,d$. We may still
be able to identify relevant subsets of monotone homomorphisms and derivations
on these semirings yielding conditions for large-sample quantum majorization.
This remains an interesting research question.

## Acknowledgements

This work was supported by the National Research Foundation, Singapore and
A*STAR under its CQT Bridging Grant.

## References

  * [1] G. Aubrun and I. Nechita.  “Catalytic Majorization and $\ell_{p}$ Norms”.  Communications in Mathematical Physics 278(1): 133–144 (2007).
  * [2] D. Blackwell.  “Comparison of experiments”.  In Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability, 1950, pages 93–102, (1951).
  * [3] D. Blackwell.  “Equivalent Comparisons of Experiments”.  The Annals of Mathematical Statistics 24: 265–272 (1953).
  * [4] F. G. S. L. Brandao, M. Horodecki, N. H. Y. Ng, J. Oppenheim, and S. Wehner.  “The Second Laws of Quantum Thermodynamics”.  Proceedings of the National Academy of Sciences USA 112(11): 3275–3279 (2014).
  * [5] G. Bunth and P. Vrana.  “Asymptotic relative submajorization of multiple-state boxes”.  Letters in Mathematical Physics 111(4): 1–23 (2021).
  * [6] G. Dahl.  “Matrix majorization”.  Linear Algebra and its Applications 288: 53–73 (1999).
  * [7] M. U. Farooq, T. Fritz, E. Haapasalo, and M. Tomamichel.  “Matrix Majorization in Large Samples”.  IEEE Transactions on Information Theory 70(5): 3118–3144 (2024).
  * [8] T. Fritz.  “Abstract Vergleichsstellensätze for Preordered Semifields and Semirings II”, (2022).  arXiv: 2112.05949.
  * [9] T. Fritz.  “Abstract Vergleichsstellensätze for Preordered Semifields and Semirings I”.  SIAM Journal on Applied Algebra and Geometry 7(2): 505–547 (2023).
  * [10] G. Gour and M. Tomamichel.  “Entropy and Relative Entropy From Information-Theoretic Principles”.  IEEE Trans. Inf. Theor. 67(10): 6313–6327 (2021).
  * [11] H. Heyer.  Comparison of Finite Experiments.  Springer New York (1982).
  * [12] A. K. Jensen.  “Asymptotic Majorization of Finite Probability Distributions”.  IEEE Transactions on Information Theory 65(12): 8131–8139 (2019).
  * [13] M. Klimesh.  “Inequalities that Collectively Completely Characterize the Catalytic Majorization Relation”, (2007).  arXiv: 0709.3680.
  * [14] H. K. Mishra, M. Nussbaum, and M. M. Wilde.  “On the optimal error exponents for classical and quantum antidistinguishability”.  Letters in Mathematical Physics 114(76): 1573–0530 (2024).
  * [15] M. Mosonyi, G. Bunth, and P. Vrana.  “Geometric relative entropies and barycentric Rényi divergences”.  Linear Algebra and its Applications 699: 159–276 (2024).
  * [16] X. Mu, L. Pomatto, P. Strack, and O. Tamuz.  “From Blackwell Dominance in Large Samples to Rényi Divergences and Back Again”.  Econometrica 89(1): 475–506 (2020).
  * [17] T. Nuradha, H. K. Mishra, F. Leditzky, and M. M. Wilde.  “Multivariate Fidelities”, (2024).  arXiv: 2404.16101.
  * [18] C. Perry, P. Vrana, and A. H. Werner.  “The Semiring of Dichotomies and Asymptotic Relative Submajorization”.  IEEE Transactions on Information Theory 68(1): 311–321 (2022).
  * [19] V. Strassen.  “The asymptotic spectrum of tensors and the exponent of matrix multiplication”.  27th Annual Symposium on Foundations of Computer Science (sfcs 1986) pages 49–54 (1986).
  * [20] M. Tomamichel.  Quantum Information Processing with Finite Resources — Mathematical Foundations.  volume 5 of SpringerBriefs in Mathematical Physics, Springer International Publishing (2016).