# Matrix majorization in large samples
with varying support restrictions

Frits Verhagen  Centre for Quantum Technologies, National University of
Singapore, Singapore  ,  Marco Tomamichel  Centre for Quantum Technologies,
National University of Singapore, Singapore  Department of Electrical and
Computer Engineering, National University of Singapore, Singapore  and  Erkka
Haapasalo  Centre for Quantum Technologies, National University of Singapore,
Singapore

###### Abstract.

We say that a matrix $P$ with non-negative entries majorizes another such
matrix $Q$ if there is a stochastic matrix $T$ such that $Q=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 multi-partite 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.

##  1\. Introduction

Statistical experiments are a mathematical description of the distributions of
outcomes from an experiment on some physical system. They are described by a
family $P=\\{p^{\vartheta}\\}_{\vartheta\in\Theta}$ of probability measures or
vectors $p^{\vartheta}$ on the space of outcomes of the experiment, where the
index set $\Theta$ represents the different states the system can be in. To
avoid redundancy, it is important to characterize when one experiment is more
informative than another, i.e., we need to be able to compare experiments. Due
to results by Blackwell [2, 3], the information order of experiments can be
characterized in an intuitive way: An experiment
$P=\\{p^{\vartheta}\\}_{\vartheta\in\Theta}$ is more informative than an
experiment $Q=\\{q^{\vartheta}\\}_{\vartheta\in\Theta}$, or $P$ majorizes $Q$,
if and only if there is a stochastic map $T$ such that
$q^{\vartheta}=Tp^{\vartheta}$ for all $\vartheta\in\Theta$. In this case, we
also denote $P\succeq Q$.

Majorization of one experiment $P=\\{p^{\vartheta}\\}_{\vartheta\in\Theta}$
over another experiment $Q=\\{q^{\vartheta}\\}_{\vartheta\in\Theta}$ can also
be aided by having many copies of the experiments or by catalysis. The former
situation means that

(1) $\left\\{\big{(}p^{\vartheta}\big{)}^{\otimes
n}\right\\}_{\vartheta\in\Theta}\succeq\left\\{\big{(}q^{\vartheta}\big{)}^{\otimes
n}\right\\}_{\vartheta\in\Theta}$

for sufficiently large $n\in\mathbb{N}$. Note that $p^{\otimes n}$ denotes the
$n$-th Kronecker product power of $p$. We call this majorization in large
samples. The latter situation means that there exists a third experiment
$R=\\{r^{\vartheta}\\}_{\vartheta\in\Theta}$ (a catalyst) such that

(2) $\big{\\{}p^{\vartheta}\otimes
r^{\vartheta}\big{\\}}_{\vartheta\in\Theta}\succeq\big{\\{}q^{\vartheta}\otimes
r^{\vartheta}\big{\\}}_{\vartheta\in\Theta}.$

This is called catalytic majorization. In this work, we are particularly
interested in large-sample and catalytic majorization of finite experiments
[11] where $\Theta=\\{1,\ldots,d\\}$ is a finite set and the probability
measures of all experiments are finite probability vectors. Majorization in
this case is also called matrix majorization [6]. When we identify a finite
experiment $P=\big{(}p^{(1)},\ldots,p^{(d)}\big{)}$ with a matrix with columns
$p^{(k)}$, majorization $P\succeq Q$ is equivalent to the existance of a
stochastic matrix $T$ such that $Q=TP$. Note that a stochastic matrix is a
matrix with non-negative entries where all the columns are probability
vectors.

In the case $\Theta=\\{1,2\\}$, majorization in large samples (under certain
regularity conditions) is characterized by inequalities involving the Rényi
divergences [16]. In [7], this result was extended to the general case
$\Theta=\\{1,\ldots,d\\}$ for any $d\in\mathbb{N}$ in the case of finite
experiments. According to [7], matrix majorization in large samples is
characterized by multi-party generalizations of the Rényi divergences: For any
$\underline{\alpha}=(\alpha_{1},\ldots,\alpha_{d})\in\mathbb{R}^{d}$ such that
$\max_{1\leq k\leq d}\alpha_{k}\neq 1$, we define the quantity
$D_{\underline{\alpha}}(P)$,

(3) $D_{\underline{\alpha}}(P)=\frac{1}{\max_{1\leq k\leq
d}\alpha_{k}-1}\log\sum_{i=1}^{n}\big{(}p^{(1)}_{i}\big{)}^{\alpha_{1}}\cdots\big{(}p^{(d)}_{i}\big{)}^{\alpha_{d}}$

where $P=\big{(}p^{(1)},\ldots,p^{(d)}\big{)}$ and
$p^{(k)}=\big{(}p^{(k)}_{1},\ldots,p^{(k)}_{n}\big{)}$ for $k=1,\ldots,d$. The
relevant quantities are those $\underline{\alpha}\in\mathbb{R}^{d}$ with

(4) $\underline{\alpha}\in
A_{+}:=\\{(\alpha_{1},\ldots,\alpha_{d})\in\mathbb{R}^{d}\,|\,\alpha_{1}+\cdots+\alpha_{d}=1,\
\alpha_{k}\geq 0,\ k=1,\ldots,d\\}$

or

(5) $\underline{\alpha}\in
A_{-}:=\bigcup_{k=1}^{d}\\{(\alpha_{1},\ldots,\alpha_{d})\in\mathbb{R}^{d}\,|\,\alpha_{1}+\cdots+\alpha_{d}=1,\
\alpha_{k}>0,\ \alpha_{\ell}\leq 0,\ \ell\neq k\\}$

and not equal to one of the basis vectors $e_{k}$, $k=1,\ldots,d$. Also, one
has to consider certain pointwise limits of $D_{\underline{\alpha}}$ in the
$\underline{\alpha}$-parameter space. Roughly speaking, if $P$ attains a
higher value than $Q$ in all these quantities, $P$ majorizes $Q$ in large
samples. For illustration of the quantities in (3) and their pointwise limits
in the case $d=3$, see Figure 1.

\begin{overpic}[scale={0.45},unit=1mm]{Restricted.png} \put(45.0,30.0){\Huge
${\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}A_{+}}$
} \put(17.0,12.0){\Large
${\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}A_{-}}$
} \put(77.0,12.0){\Large
${\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}A_{-}}$
} \put(47.0,62.0){\Large
${\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}A_{-}}$
} \put(31.0,37.0){\Large
{\color[rgb]{0.0078125,0.390625,0.078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.0078125,0.390625,0.078125}$D_{\underline{\alpha}}$}
} \put(25.0,7.0){\Large
{\color[rgb]{0.0078125,0.390625,0.078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.0078125,0.390625,0.078125}$D_{\underline{\alpha}}$}
} \put(68.0,7.0){\Large
{\color[rgb]{0.0078125,0.390625,0.078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.0078125,0.390625,0.078125}$D_{\underline{\alpha}}$}
} \put(37.0,60.0){\Large
{\color[rgb]{0.0078125,0.390625,0.078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.0078125,0.390625,0.078125}$D_{\underline{\alpha}}$}
} \put(25.0,25.0){\large
{\color[rgb]{0.349609375,0.39765625,0.933984375}\definecolor[named]{pgfstrokecolor}{rgb}{0.349609375,0.39765625,0.933984375}$\Delta^{(1)}_{\underline{\gamma}}$}
} \put(68.0,25.0){\large
{\color[rgb]{0.349609375,0.39765625,0.933984375}\definecolor[named]{pgfstrokecolor}{rgb}{0.349609375,0.39765625,0.933984375}$\Delta^{(2)}_{\underline{\gamma}}$}
} \put(52.0,52.0){\large
{\color[rgb]{0.349609375,0.39765625,0.933984375}\definecolor[named]{pgfstrokecolor}{rgb}{0.349609375,0.39765625,0.933984375}$\Delta^{(3)}_{\underline{\gamma}}$}
} \put(5.0,8.0){\Large
{\color[rgb]{0.890625,0.046875,0.046875}\definecolor[named]{pgfstrokecolor}{rgb}{0.890625,0.046875,0.046875}$D^{\mathbb{T}}_{\underline{\beta}}$}
} \put(86.0,8.0){\Large
{\color[rgb]{0.890625,0.046875,0.046875}\definecolor[named]{pgfstrokecolor}{rgb}{0.890625,0.046875,0.046875}$D^{\mathbb{T}}_{\underline{\beta}}$}
} \put(62.0,70.0){\Large
{\color[rgb]{0.890625,0.046875,0.046875}\definecolor[named]{pgfstrokecolor}{rgb}{0.890625,0.046875,0.046875}$D^{\mathbb{T}}_{\underline{\beta}}$}
} \end{overpic} Figure 1.  The functions of (3) together with their pointwise
limits depicted in the case $d=3$. The figure is contained in the affine plane
of $\mathbb{R}^{3}$ of those points whose coordinates sum up to 1. The maps of
(3) are associated with the areas $A_{+}$ and $A_{-}$ and are depicted in
green. Note that, e.g., in the lower-left part of $A_{-}$, we have
$\alpha_{1}>1$ and $\alpha_{2},\alpha_{3}\leq 0$. The red arcs represent
points at the infinity and they correspond to the functions introduced later
in (33). The blue points are $e_{1}=(1,0,0)$, $e_{2}=(0,1,0)$, and
$e_{3}=(0,0,1)$. The pointwise limits of the maps in (3) as
$\underline{\alpha}\to e_{1}$ are
$\Delta^{(1)}_{\underline{\gamma}}(P)=\gamma_{2}D_{1}\big{(}p^{(1)}\big{\|}p^{(2)}\big{)}+\gamma_{3}D_{1}\big{(}p^{(1)}\big{\|}p^{(3)}\big{)}$
with $\gamma_{2},\gamma_{3}\geq 0$ which depend on the angle of approach.
Similar limits exist for $\underline{\alpha}\to e_{2}$ or $e_{3}$. Here
$D_{1}$ is the Kullback-Leibler divergence. The situation depicted here
generalizes to the general $d\in\mathbb{N}$ case in a straightforward manner:
the parameter area $A_{+}$ corresponds to the $d$-dimensional probability
simplex and $A_{-}$ extends from the extreme points of the probability simplex
as cones reaching to infinity.

Both in [16] and [7] it was assumed that, within each statistical experiment,
all the probability measures or vectors share the same support. In the finite
case this means that, for an experiment
$P=\big{(}p^{(1)},\ldots,p^{(d)}\big{)}$ consisting of probability vectors
$p^{(k)}$, we have

(6) ${\rm supp}\,p^{(1)}=\cdots={\rm supp}\,p^{(d)}$

where ${\rm supp}\,p$ is set of entries where $p$ is non-zero (the support of
$p$). In this work, we consider more general support conditions. We first
study the case where there are no support conditions except for the baseline

(7) $\bigcap_{k=1}^{d}{\rm supp}\,p^{(k)}\neq\emptyset$

within each experiment $P=\big{(}p^{(1)},\ldots,p^{(d)}\big{)}$. We call this
the _minimal restrictions_ case and analyze it in Section 3. This culminates
in the main results Theorem 10 for exact large-sample or catalytic
majorization, and Theorem 11 for the asymptotic case where we consider
approximate large-sample or catalytic majorization with vanishing error.

In the second case, we study the case where the support of one of the columns,
say the final one, dominates the others, i.e., in addition to (7), we require

(8) ${\rm supp}\,p^{(k)}\subseteq{\rm supp}\,p^{(d)}$

for $k=1,\ldots,d-1$. We call this the _dominating column_ case and discuss it
in Section 4. The main results here are Theorem 17 for exact large-sample or
catalytic majorization, and Theorem 19 for asymptotic large-sample or
catalytic majorization for $d=2$.

In both of the above cases, matrix majorization in large samples is
characterized by inequalities involving subsets of the functions
$D_{\underline{\alpha}}$. In the first case, only those
$D_{\underline{\alpha}}$ where $\underline{\alpha}\in A_{+}$ appear in the
sufficient conditions for majorization in large samples. However, on the
boundary of $A_{+}$ some additional quantities surface. Simply put, in each
smaller facet of the simplex $A_{+}$, a set of additional quantities have to
be considered. Note that the facets of $A_{+}$ are of the form

(9) $\displaystyle A_{C}:=\\{(\alpha_{1},\ldots,\alpha_{d})\in
A_{+}\,|\,\alpha_{k}=0,\ k\in\\{1,\ldots,d\\}\setminus C\\}$

for some $C\subseteq\\{1,\ldots,d\\}$. With $C\subsetneq\\{1,\ldots,d\\}$, the
new quantities arising from $A_{C}$ are essentially the original quantities
when we restrict the vectors of the experiment
$P=\big{(}p^{(1)},\ldots,p^{(d)}\big{)}$ onto $\bigcap_{k\in C}{\rm
supp}\,p^{(k)}$. The occurrence of new quantities can be seen as a consequence
of the non-commutativity of the limits $x\downarrow 0$ and $\alpha\rightarrow
0$

(10) $\lim_{x\downarrow 0}x^{\alpha}=0\quad\text{for fixed
}\alpha>0,\quad\quad\quad\lim_{\alpha\rightarrow 0}x^{\alpha}=1\quad\text{for
fixed }x>0.$

To be exact, the new quantities arise when ${\rm
supp}\,\underline{\alpha}\subsetneq\\{1,\ldots,d\\}$, in which case we
consider all ${\rm supp}\,\underline{\alpha}\subseteq
C\subseteq\\{1,\ldots,d\\}$ and the new quantities are given by essentially
the same formula as 3 with the exception that the $i$-sum runs over only the
set $\bigcap_{c\in C}{\rm supp}\,p^{(c)}$. In the case of one dominating
column, the set of relevant $\underline{\alpha}$ is extended as the one-
parameter families

(11)
$D_{\underline{\alpha}(\lambda)},\quad\underline{\alpha}(\lambda)=(0,\ldots,0,\underbrace{1+\lambda}_{k{\rm
th\ entry}},0,\ldots,0,-\lambda),\qquad\lambda\geq 0,\quad k=1,\ldots,d-1,$

including the points at infinity where $\lambda\to\infty$.

This work complements earlier work particularly in [7] by filling in the
missing cases that could not be dealt with in [7] because of the support
assumptions we had to impose there. The simplest complete results we obtain
deals with dichotomies. By dichotomy, we mean a pair
$\big{(}p^{(1)},p^{(2)}\big{)}$ of probability vectors where the second
dominates the first, i.e., ${\rm supp}\,p^{(1)}\subseteq{\rm supp}\,p^{(2)}$.
Given dichotomies $\big{(}p^{(1)},p^{(2)}\big{)}$ and
$\big{(}q^{(1)},q^{(2)}\big{)}$ with the innocuous assumption that
$p^{(1)}\neq p^{(2)}$, we have that $\big{(}p^{(1)},p^{(2)}\big{)}$ majorizes
$\big{(}q^{(1)},q^{(2)}\big{)}$ in large samples approximately with vanishing
error (similarly in the catalytic regime) if and only if

(12) $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{)}$

for all $\alpha\geq 1/2$ where $D_{\alpha}(\cdot\|\cdot)$ are the Rényi
divergences (see (25) for a definition of the Rényi divergences). See also
Corollary 20 for an exact formulation of this result. We have similar results
for general finite statistical experiments for $d\in\mathbb{N}$ (dichotomies
being an example of the $d=2$ case) involving the multipartite generalizations
$D_{\underline{\alpha}}$ of the Rényi divergences in addition to the new
quantities arising in the case where ${\rm
supp}\,\underline{\alpha}\subsetneq\\{1,\ldots,d\\}$ as described earlier.

The simplest case where both the multipartite divergences and these new
quantities come into play is when we consider majorization of tuples of three
probability vectors $P=(p^{(1)},p^{(2)},p^{(3)})$. In the following, we will
illustrate the conditions for _exact_ large-sample or catalytic majorization
of $P$ over another tuple $Q=(q^{(1)},q^{(2)},q^{(3)})$ in the setting of one
dominating column, say the last, i.e. ${\rm supp}\,p^{(1)},{\rm
supp}\,p^{(2)}\subseteq{\rm supp}\,p^{(3)}$. This is the case $d=3$ in Theorem
17. The majorization conditions can be formulated in terms of the divergences
$D_{\underline{\alpha}}$ and the Rényi divergences $D_{\alpha}$. Figure 2
gives a depiction of the parameter vectors $\underline{\alpha}$ and parameters
$\alpha$ that are applicable. The precise conditions for large-sample and
catalytic majorization are:

(13) $\displaystyle D_{\underline{\alpha}}(P)>D_{\underline{\alpha}}(Q)$
$\displaystyle\forall\underline{\alpha}\in{\rm int}\,A_{+},$ (14)
$\displaystyle
D_{\alpha}\big{(}p^{(1)}\|p^{(3)}\big{)}>D_{\alpha}\big{(}q^{(1)}\|q^{(3)}\big{)}$
$\displaystyle\forall\alpha\in[0,\infty],$ (15) $\displaystyle
D_{\alpha}\big{(}p^{(1)}|_{{\rm supp}\,p^{(2)}}\|p^{(3)}|_{{\rm
supp}\,p^{(2)}}\big{)}>D_{\alpha}\big{(}q^{(1)}|_{{\rm
supp}\,q^{(2)}}\|q^{(3)}|_{{\rm supp}\,q^{(2)}}\big{)}$
$\displaystyle\forall\alpha\in[0,1),$ (16) $\displaystyle
D_{\alpha}\big{(}p^{(2)}\|p^{(3)}\big{)}>D_{\alpha}\big{(}q^{(2)}\|q^{(3)}\big{)}$
$\displaystyle\forall\alpha\in[0,\infty],$ (17) $\displaystyle
D_{\alpha}\big{(}p^{(2)}|_{{\rm supp}\,p^{(1)}}\|p^{(3)}|_{{\rm
supp}\,p^{(1)}}\big{)}>D_{\alpha}\big{(}q^{(2)}|_{{\rm
supp}\,q^{(1)}}\|q^{(3)}|_{{\rm supp}\,q^{(1)}}\big{)}$
$\displaystyle\forall\alpha\in[0,1),$ (18) $\displaystyle
D_{\alpha}\big{(}p^{(1)}\|p^{(2)}\big{)}>D_{\alpha}\big{(}q^{(1)}\|q^{(2)}\big{)},\quad
D_{\alpha}\big{(}p^{(2)}\|p^{(1)}\big{)}>D_{\alpha}\big{(}q^{(2)}\|q^{(1)}\big{)}$
$\displaystyle\forall\alpha\in[0,1/2],$

For the first condition (13) we consider $D_{\underline{\alpha}}$ for all
parameter vectors $\underline{\alpha}$ in ${\rm int}\,A_{+}$, the interior of
$A_{+}$ (defined in (4)), i.e. all
$\underline{\alpha}=(\alpha_{1},\alpha_{2},\alpha_{3})\in\mathbb{R}^{3}$ such
that $\alpha_{1}+\alpha_{2}+\alpha_{3}=1$ and $0<\alpha_{k}<1$ for $k=1,2,3$.
Condition (14) is in terms of the Rényi divergence for $\alpha\in[0,\infty]$
between the first and third vectors. This coincides with the half-line
parameterized by $(\alpha,0,1-\alpha)$ in Figure 2 starting from the top
vertex of the triangle (corresponding to $\alpha=0$) and passing through the
lower left vertex (corresponding to $\alpha=1$, i.e. the Kullback-Leibler
divergence). In the limit $\alpha\rightarrow\infty$ this gives the max-
divergence $D_{\infty}$. In condition (15), we denote by $r|_{{\rm supp}\,s}$
the restriction of the vector $r$ to the support of $s$, i.e. $\big{(}r|_{{\rm
supp}\,s}\big{)}_{i}=r_{i}$ if $i\in{\rm supp}\,s$ and $r|_{{\rm supp}\,s}=0$
otherwise. These derivations can be seen as point-wise limits of
$D_{(\alpha_{1},\alpha_{2},\alpha_{3})}$ when $\alpha_{2}\rightarrow 0$,
similarly as the Rényi divergence $D_{0}$ is the point-wise limit of
$D_{\alpha}$ when $\alpha\rightarrow 0$. Conditions (16) and (17) are similar
to the preceding two, and correspond to the other half-line in Figure 2.
Finally, (18) corresponds to the lower line segment of the triangle
parameterized by $(\alpha,1-\alpha,0)$ for $\alpha\in[0,1]$.

\begin{overpic}[scale={0.4},unit=1mm]{DominatingColumn.png}
\put(42.0,60.0){\Huge $A_{+}$ } \put(-3.0,86.0){
{\color[rgb]{0.0390625,0.57421875,0.13671875}\definecolor[named]{pgfstrokecolor}{rgb}{0.0390625,0.57421875,0.13671875}$D_{0}\big{(}p^{(1)}|_{{\rm
supp}\,p^{(2)}}\|p^{(3)}|_{{\rm supp}\,p^{(2)}}\big{)},$}
{\color[rgb]{0.0078125,0.390625,0.078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.0078125,0.390625,0.078125}$D_{0}\big{(}p^{(2)}\big{\|}p^{(3)}\big{)}$,
$D_{0}\big{(}p^{(1)}\big{\|}p^{(3)}\big{)}$} } \put(29.0,67.0){ {(a1)} }
\put(59.0,67.0){ {(b1)} } \put(8.0,30.0){ {(a2)} } \put(80.0,30.0){ {(b2)} }
\put(2.0,53.0){
{\color[rgb]{0.349609375,0.39765625,0.933984375}\definecolor[named]{pgfstrokecolor}{rgb}{0.349609375,0.39765625,0.933984375}$D_{1}\big{(}p^{(1)}\big{\|}p^{(3)}\big{)}$}
} \put(2.0,47.0){
{\color[rgb]{0.0078125,0.390625,0.078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.0078125,0.390625,0.078125}$D_{0}\big{(}p^{(2)}\big{\|}p^{(1)}\big{)}$}
} \put(70.0,53.0){
{\color[rgb]{0.349609375,0.39765625,0.933984375}\definecolor[named]{pgfstrokecolor}{rgb}{0.349609375,0.39765625,0.933984375}$D_{1}\big{(}p^{(2)}\big{\|}p^{(3)}\big{)}$}
} \put(70.0,47.0){
{\color[rgb]{0.0078125,0.390625,0.078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.0078125,0.390625,0.078125}$D_{0}\big{(}p^{(1)}\big{\|}p^{(2)}\big{)}$}
} \put(-12.0,1.0){
{\color[rgb]{0.890625,0.046875,0.046875}\definecolor[named]{pgfstrokecolor}{rgb}{0.890625,0.046875,0.046875}$D_{\infty}\big{(}p^{(1)}\big{\|}p^{(3)}\big{)}$}
} \put(78.0,1.0){
{\color[rgb]{0.890625,0.046875,0.046875}\definecolor[named]{pgfstrokecolor}{rgb}{0.890625,0.046875,0.046875}$D_{\infty}\big{(}p^{(2)}\big{\|}p^{(3)}\big{)}$}
} \put(0.0,67.0){
{\color[rgb]{0.0390625,0.57421875,0.13671875}\definecolor[named]{pgfstrokecolor}{rgb}{0.0390625,0.57421875,0.13671875}$D_{\underline{\alpha},\\{1,2,3\\}}(P)$}
} \put(24.0,68.0){\vector(1,0){17.0}} \put(35.0,46.0){ {(c1)} }
\put(53.0,46.0){ {(c2)} } \end{overpic} Figure 2.  A subset of the set of
parameter vectors that are depicted in Figure 3. These represent the family of
monotones that appear in the conditions for exact large-sample and catalytic
majorization for matrices $P=(p^{(1)},p^{(2)},p^{(3)})$ where the support of
the last column dominates the support of the other two. The interior of the
triangle $A_{+}$ corresponds to the tri-partite monotones
$D_{\underline{\alpha}}(P)$ given by (3). The two half lines beginning at
$e_{3}$, going through $e_{1}$, respectively $e_{2}$, and extending to
infinity represent the Rényi divergences
$D_{\alpha}\big{(}p^{(1)}\|p^{(3)}\big{)}$ ((a1), (a2)), respectively
$D_{\alpha}\big{(}p^{(2)}\|p^{(3)}\big{)}$ ((b1), (b2)), for
$\alpha\in[0,\infty]$. The side of the triangle between $e_{1}$ and $e_{2}$ is
split in half at $\underline{\alpha}=(1/2,1/2,0)$: the left half (c1)
represents $D_{\alpha}\big{(}p^{(2)}\|p^{(1)}\big{)}$ for $\alpha\in[0,1/2]$
and the right half (c2) represents $D_{\alpha}\big{(}p^{(1)}\|p^{(2}\big{)}$
for $\alpha\in[0,1/2]$. Additionally, on the two sides of the triangle between
$e_{3}$ and $e_{1}$, respectively $e_{2}$, we have the Rényi divergences
between two columns when restricted to the support of the remaining column:
$D_{\alpha}\big{(}p^{(1)}|_{{\rm supp}\,p^{(2)}}\|p^{(3)}|_{{\rm
supp}\,p^{(2)}}\big{)}$ (a1), respectively $D_{\alpha}\big{(}p^{(2)}|_{{\rm
supp}\,p^{(1)}}\|p^{(3)}|_{{\rm supp}\,p^{(1)}}\big{)}$ (b1).

At first glance, Theorems 10 and 17 for the minimal restrictions and
dominating column case, respectively, are very similar and the former seems to
apply to a larger set of matrices than the latter. On top of that, the former
theorem requires less conditions in terms of inequalities of monotones to be
satisfied. Therefore, one may wonder why we would need the latter theorem at
all. The important thing to note here is that the strict inequalities in the
conditions that the input matrix $P$ and output matrix $Q$ have to satisfy
forces $P$ to be of a very specific form, it has to be _power universal_ (more
on this later). In the case of Theorem 10, these conditions require the
support of $P=(p^{(1)},\ldots,p^{(d)})$ to satisfy the following:

(19) ${\rm supp}\,p^{(k)}\nsubseteq{\rm supp}\,p^{(k^{\prime})}\text{ for all
}k,k^{\prime}\in\\{1,\ldots,d\\}\text{ with }k\neq k^{\prime}.$

However, for Theorem 17, $P$ has to satisfy

(20) ${\rm supp}\,p^{(k)}\subsetneq{\rm supp}\,p^{(d)}\text{ for all
}k\in\\{1,\ldots,k-1\\},$

and

(21) ${\rm supp}\,p^{(k)}\nsubseteq{\rm supp}\,p^{(k^{\prime})}\text{ for all
}k,k^{\prime}\in\\{1,\ldots,k-1\\}\text{ with }k\neq k^{\prime}.$

Therefore, both theorems apply to two disjunct types of matrices, depending on
their support structure. In principle, one could derive similar theorems for
matrices with different kinds of support structures, where the family of
monotones that appear in the conditions of the theorem are different for each
type of support structure. We will discuss this point in more detail in the
Conclusion and outlook section. To understand why the type of matrices in
Theorem 10 require less conditions in terms of inequalities of monotones than
those in Theorem 17, one can consider the catalytic case: both theorems
guarantee the existence of a catalyst that is taken from the same set of
matrices that $P$ and $Q$ are from. Hence, when this set is larger (which it
is for Theorem 10 compared to Theorem 17), it intuitively makes sense that we
require less conditions on $P$ and $Q$.

Our results are based on earlier work done in [7] and on the theory developed
in [9, 8]. The methods used are real algebraic in nature. We build different
preordered semirings based on matrix majorization and use the
Vergleichsstellensätze developed in [9, 8] which associates ordering in large
samples and in the catalytic setting with inequalities involving certain
monotone homomorphisms of the semiring. Recall that a semiring is an algebraic
structure with an addition and multiplication, but the elements of the
semiring are not required to have inverses with respect to either the
multiplication or even the addition. Preordered semirings additionally possess
a preorder (a reflexive and transitive binary relation) which is required to
fit with the algebraic structure of the semiring. Semiring methods have proven
to be highly useful in statistics and information theory [19] and they have
also been applied in comparison of quantum statistical experiments [18, 5].
Multivariate divergences similar to the ones we study find an operational
interpretation in the task of (quantum) hypothesis exclusion, where they
appear in the error exponents [14].

One immediate application of the results obtained in this work is in the field
of quantum thermodynamics. In thermodynamical equilibrium, the system is in a
stable or thermal state $\gamma_{\beta}$ which is typically the Gibbs state of
inverse temperature $\beta$ (or a KMS-state in general). A quantum channel
$\Phi$ (a completely positive trace-preserving affine map on the states) is
thermal if $\Phi(\gamma_{\beta})=\gamma_{\beta}$. We denote
$\rho\succeq_{\beta}\sigma$ for quantum states $\rho$ and $\sigma$ if there is
a thermal channel $\Phi$ such that $\Phi(\rho)=\sigma$. When we require the
states $\rho$ and $\sigma$ to be diagonalizable in the eigenbasis of the
thermal state $\gamma_{\beta}$, $\rho\succeq_{\beta}\sigma$ means that

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

where $\lambda^{\rho}$ and $\lambda^{\sigma}$ are the vectors of eigenvalues
of $\rho$ and $\sigma$ where the eigenvalues appear in the order fixed by the
thermal eigenbasis and $\lambda^{\beta}:=\lambda^{\gamma_{\beta}}$. This
thermal majorization was characterized in large samples in [4]. However, our
method bypasses some of the technical uncertainties of this work and finally
resolves the problem of large-sample thermal majorization also in the case
when the states are not of full support. We may also now investigate multiple
thermal majorization
$(\rho_{1},\ldots\rho_{m})\succeq_{T}(\sigma_{1},\ldots,\sigma_{m})$ i.e., the
existence of a thermal channel $\Phi$ such that $\Phi(\rho_{i})=\sigma_{i}$
for $i=1,\ldots,m$.

This paper is organized as follows. In Section 2, we set up basic notation and
definitions, review previous results in majorization in its various forms and
introduce the theoretical results of [9] that we will be utilizing in this
work. We derive the preordered semiring for matrix majorization with minimal
support conditions, its monotone homomorphisms and derivations relevant for
large-sample and catalytic majorization, in Section 3. We partially build on
earlier work in [7] but see that lifting the assumption of mutually supporting
columns in each matrix requires a dramatically different approach. In Section
4, we study the case where the final column supports the others and in
subsections 4.5 and 4.6 concentrate on the two-column case whose results we
apply to the problem of thermal majorization briefly presented above.

##  2\. Background

###  2.1. Basic definitions

We follow the convention $\mathbb{N}=\\{1,2,\ldots\\}$. When $d\in\mathbb{N}$,
we define $[d]:=\\{1,\ldots,d\\}$. For any $n\in\mathbb{N}$, we define the
1-norm in $\mathbb{R}^{n}$ as

(23) $\|(x_{1},\ldots,x_{n})\|_{1}=|x_{1}|+\cdots+|x_{n}|.$

Instead of full $\mathbb{R}$, we usually concentrate on the half-line
$\mathbb{R}_{+}:=[0,\infty)$ or $\mathbb{R}_{>0}:=(0,\infty)$.

For any $n\in\mathbb{N}$, we say that
$p=(p_{1},\ldots,p_{n})\in\mathbb{R}_{+}^{n}$ is a probability vector when
$p_{1}+\cdots+p_{n}=1$, i.e., $\|p\|_{1}=1$. Let us denote the set of all
$n$-component probability vectors by $\mathcal{P}_{n}$. This set is convex,
i.e., when $p,q\in\mathcal{P}_{n}$ and $t\in[0,1]$, then
$tp+(1-t)q\in\mathcal{P}_{n}$. Fix $m,n\in\mathbb{N}$. We say that
$T:\mathcal{P}_{m}\to\mathcal{P}_{n}$ is a stochastic map if it is affine,
i.e., $T\big{(}tp+(1-t)q\big{)}=tTp+(1-t)Tq$ for all $p,q\in\mathcal{P}_{m}$
and $t\in[0,1]$. Equivalently, we may view $T$ as a linear map
$T:\mathbb{R}^{m}\to\mathbb{R}^{n}$ such that
$T\mathbb{R}_{+}^{m}\subseteq\mathbb{R}_{+}^{n}$ and $\|Tx\|_{1}=\|x\|_{1}$
for all $x\in\mathbb{R}^{m}$. This means that we may view $T$ as an $(n\times
m)$-matrix $T=(T_{i,j})_{i,j}$ with entries in $\mathbb{R}_{+}$ such that
$T_{1,j}+\cdots+T_{n,j}=1$ for all $j=1,\ldots,m$. We say that $T$ is
bistochastic if also $T_{i,1}+\cdots+T_{i,m}=1$ for all $i=1,\ldots,n$.

###  2.2. Majorization

Majorization is a word commonly used when an object (often a probability
measure or vector or a collection of them) can be reached from another object
using a map of a relevant type (often a stochastic map). The arguably simplest
notion of majorization deals with finite probability vectors. This is why we
call this type of majorization as vector majorization. In this mode of
majorization, we say that a probability vector $p=(p_{1},\ldots,p_{m})$
majorizes another probability vector $q=(q_{1},\ldots,q_{n})$ if

(24)
$\sum_{i=1}^{k}p_{i}^{\downarrow}\geq\sum_{i=1}^{k}q_{i}^{\downarrow},\qquad
k=1,2,\ldots,$

where $p^{\downarrow}=(p_{1}^{\downarrow},\ldots,p_{m}^{\downarrow})$ and
$q^{\downarrow}=(q_{1}^{\downarrow},\ldots,q_{m}^{\downarrow})$ are $p$ and
$q$ with their entries ordered in a non-increasing order. We also denote
$p\succeq q$ in this situation. This is equivalent with the existence of a
stochastic map $T$ such that $Tp=q$ such that, for a uniform probability
vector $u$ dominating both $p$ and $q$, $Tu=u$. This means that $T$ is
bistochastic. We subsequently generalize this notion in a straightforward
manner.

######  Definition 1.

Fix $d\in\mathbb{N}$ and consider collections
$P=\left(p^{(1)},\ldots,p^{(d)}\right)$ and
$Q=\left(q^{(1)},\ldots,q^{(d)}\right)$ of probability vectors. We say that
$P$ majorizes $Q$ and denote $P\succeq Q$ if there is a stochastic map $T$
such that $Tp^{(k)}=q^{(k)}$ for $k=1,\ldots,d$. We call this form of
majorization matrix majorization.

We immediately notice that the preceding vector majorization is an example of
this matrix majorization by noting that a probability vector $p$ majorizes
another probability vector $q$ if $(p,u)\succeq(q,u)$ where $u$ is a uniform
vector dominating both $p$ and $q$. Just like matrix majorization, also vector
majorization can be studied in the large-sample and catalytic regimes.

Also the special case $d=2$ of matrix majorization is of particular interest.
This is called relative majorization. Relative majorization is often
restricted to the case of dichotomies, i.e., pairs $(p,q)$ of probability
measures or vectors where $q$ dominates $p$ (${\rm supp}\,p\subseteq{\rm
supp}\,q$), or, symbolically, $p\ll q$.

###  2.3. Earlier results

The field of vector majorization is probably the best known mode of
majorization. In [13], necessary and sufficient conditions for catalytic
vector majorization were derived. These conditions can be written using the
Rényi divergences $D_{\alpha}(\cdot\|\cdot)$, $0\leq\alpha\leq\infty$, defined
on any pair $(p,q)$ of probability measures with supports ${\rm supp}\,p=:I$
and ${\rm supp}\,q=:J$,

(25) $D_{\alpha}(p\|q)=\left\\{\begin{array}[]{ll}-\log{\sum_{i\in I\cap
J}q_{i}},&\alpha=0,\ {\rm and}\ I\cap J\neq\emptyset,\\\
\frac{1}{\alpha-1}\log{\sum_{i\in I\cap
J}p_{i}^{\alpha}q_{i}^{1-\alpha}},&\alpha\in(0,1),\ {\rm and}\ I\cap
J\neq\emptyset,\\\ \sum_{i\in I}p_{i}\log{\frac{p_{i}}{q_{i}}},&\alpha=1,\
{\rm and}\ I\subseteq J,\\\ \frac{1}{\alpha-1}\log{\sum_{i\in
I}p_{i}^{\alpha}q_{i}^{1-\alpha}},&\alpha\in(1,\infty),\ {\rm and}\ I\subseteq
J,\\\ \max_{i\in I}\log{\frac{p_{i}}{q_{i}}},&\alpha=\infty\ {\rm and}\
I\subseteq J,\ {\rm and}\\\ \infty&{\rm otherwise,}\end{array}\right.,$

in the following way: For probability vectors $p$ and $q$ such that $p\neq q$,
there is a catalytic probability vector $r$ such that $p\otimes r\succeq
q\otimes r$ if and only if, denoting the uniform distribution on ${\rm
supp}\,p\cup{\rm supp}\,q$ by $u$,

(26) $D_{\alpha}(p\|u)>D_{\alpha}(q\|u),\quad
D_{\alpha}(u\|p)>D_{\alpha}(u\|q),\qquad\forall\alpha\in[1/2,\infty).$

Conditions for vector majorization in large samples were derived in [12] which
were further extended in [7]. The latter extended result can be stated as
follows: given probability vectors $p$ and $q$, there is $n\in\mathbb{N}$ such
that $p^{\otimes n}\succeq q^{\otimes n}$ if conditions (26) hold including
the case $\alpha=\infty$.

In [1], asymptotic large-sample and catalytic vector majorization were
studied. It was found that, given again probability vectors $p$ and $q$, the
following conditions are equivalent

  * (i)

For all $\varepsilon>0$, there is $n_{\varepsilon}\in\mathbb{N}$ and a
probability vector $q_{\varepsilon}$ such that
$\|q-q_{\varepsilon}\|_{1}\leq\varepsilon$ and $p^{\otimes n}\succeq
q_{\varepsilon}^{\otimes n}$ for all $n\geq n_{\varepsilon}$.

  * (ii)

For all $\varepsilon>0$, there are probability vectors $q_{\varepsilon}$ and
$r_{\varepsilon}$ such that $\|q-q_{\varepsilon}\|_{1}\leq\varepsilon$ and
$p\otimes r_{\varepsilon}\succeq q_{\varepsilon}\otimes r_{\varepsilon}$.

  * (iii)

$\|p\|_{\alpha}\geq\|q\|_{\alpha}$ for all $\alpha\geq 1$ where

(27)
$\|(p_{1},\ldots,p_{n})\|_{\alpha}=\left(p_{1}^{\alpha}+\cdots+p_{n}^{\alpha}\right)^{1/\alpha}.$

Also this result was derived using real-algebraic methods in [7].

The problem of relative majorization in large samples was studied in [16].
This work studied dichotomies $(p,q)$ of probability measures over a standard
Borel space $(X,\mathcal{A})$ where $p\sim q$, i.e., $p\ll q$ and $q\ll p$. In
this case, the relevant Rényi divergences $D_{\alpha}$,
$\alpha\in[1/2,\infty]$ are given by

(28)
$D_{\alpha}(p\|q)=\left\\{\begin{array}[]{ll}\frac{1}{\alpha-1}\int_{X}\frac{dp}{dq}(x)^{\alpha}\,dq(x),&\alpha\in[1/2,\infty)\setminus\\{1\\},\\\
\int_{X}\log{\frac{dp}{dq}(x)}\,dq(x),&\alpha=1,\ {\rm and}\\\
q-\operatorname*{ess\,sup}_{x\in
X}\log{\frac{dp}{dq}(x)},&\alpha=\infty.\end{array}\right.$

It was found in [16] that, a dichotomy $\big{(}p^{(1)},p^{(2)}\big{)}$, where
$p^{(1)}\sim p^{(2)}$, majorizes $\big{(}q^{(1)},q^{(2)}\big{)}$, where and
$q^{(1)}\sim q^{(2)}$, if

(29)
$D_{\alpha}\big{(}p^{(1)}\big{\|}p^{(2)}\big{)}>D_{\alpha}\big{(}q^{(1)}\big{\|}q^{(2)}\big{)},\quad
D_{\alpha}\big{(}p^{(2)}\big{\|}p^{(1)}\big{)}>D_{\alpha}\big{(}q^{(2)}\big{\|}q^{(1)}\big{)},\qquad\forall\alpha\in[1/2,\infty].$

Large-sample and catalytic matrix majorization in the case of matrices (finite
experiments) $P=\big{(}p^{(1)},\ldots,p^{(d)}\big{)}$ where the supports ${\rm
supp}\,p^{(k)}$, $k=1,\ldots,d$, coincide was characterized in [7]. For these
results, let us define $A_{+}$ and $A_{-}$ as in (4) and (5), and

(30) $\displaystyle
B:=\\{(\beta_{1},\ldots,\beta_{d})\in\mathbb{R}^{d}\,|\,\beta_{1}+\cdots+\beta_{d}=0\\},$
(31) $\displaystyle B_{-}:=\bigcup_{k=1}^{d}\\{(\beta_{1},\ldots,\beta_{d})\in
B\,|\,\beta_{k}>0,\ \beta_{\ell}\leq 0,\ \ell\neq k\\}.$

We also define the natural basis vectors
$e_{k}:=(\delta_{\ell,k})_{\ell=1}^{d}$. We define the maps
$D_{\underline{\alpha}}$ and $D_{\underline{\beta}}$ through

(32) $\displaystyle D_{\underline{\alpha}}(P)$
$\displaystyle=\frac{1}{\max_{1\leq k\leq
d}\alpha_{k}-1}\log{\sum_{i=1}^{n}\prod_{k=1}^{d}\big{(}p^{(k)}_{i}\big{)}^{\alpha_{k}}},$
(33) $\displaystyle D_{\underline{\beta}}^{\mathbb{T}}(P)$
$\displaystyle=\frac{1}{\max_{1\leq k\leq d}\beta_{k}}\log{\max_{1\leq i\leq
n}\prod_{i=1}^{n}\big{(}p^{(k)}_{i}\big{)}^{\beta_{k}}},$

for all for $P=\big{(}p^{(1)},\ldots,p^{(d)}\big{)}$ where
$p^{(k)}=\big{(}p^{(k)}_{1},\ldots,p^{(k)}_{n}\big{)}$, $k=1,\ldots,d$. The
areas $A_{+}$ and $A_{-}$ together with the functions $D_{\underline{\alpha}}$
and $D^{\mathbb{T}}_{\underline{\beta}}$ are depicted in Figure 1. It follows
that, if

(34)
$\begin{array}[]{rcll}D_{\underline{\alpha}}(P)&>&D_{\underline{\alpha}}(Q),&\forall\underline{\alpha}\in
A_{+}\cup A_{-}\setminus\\{e_{1},\ldots,e_{d}\\},\\\
D_{\underline{\beta}}^{\mathbb{T}}(P)&>&D_{\underline{\beta}}^{\mathbb{T}}(Q),&\forall\underline{\beta}\in
B_{-},\\\
D_{1}\big{(}p^{(k)}\big{\|}p^{(\ell)}\big{)}&>&D_{1}\big{(}q^{(k)}\big{\|}q^{(\ell)}\big{)},&\forall
k,\ell\in\\{1,\ldots,d\\},\ k\neq\ell,\end{array}$

then $P=\big{(}p^{(1)},\ldots,p^{(d)}\big{)}$ majorizes
$Q=\big{(}q^{(1)},\ldots,q^{(d)}\big{)}$ in large samples. We also recover the
earlier result of [16] for dichotomies of probability vectors as a special
case. Also asymptotic large-sample and catalytic majorization can be
characterized with similar non-strict inequalities involving
$D_{\underline{\alpha}}$ with $\underline{\alpha}\in A_{+}\cup
A_{-}\setminus\\{e_{1},\ldots,e_{d}\\}$.

The above result crucially assumes that the columns of each matrix share a
common support. In this work, we remove this condition and open the
possibility for different support restrictions. This requires modifying the
methodology used in [7]. For this, we first have to introduce the real-
algebraic machinery required for the Vergleichstellensätze of [9] that give
the sufficient and almost necessary conditions for large-sample and catalytic
matrix majorization.

###  2.4. Preordered semirings and a Vergleichsstellensatz

We only study commutative algebraic structures in this work. We say that a
tuple $(S,+,\cdot,0,1,\preceq)$ is a preordered semiring if $(S,+,0)$ and
$(S,1,\cdot)$ are commutative semigroups where the multiplication distributes
over the addition and $\preceq$ is a preorder (a binary relation which is
reflexive and transitive) satisfying

(35) $x\preceq y\ \Rightarrow\ \left\\{\begin{array}[]{rcl}x+a&\preceq&y+a,\\\
xa&\preceq&ya\end{array}\right.$

for all $a\in S$. As above, we usually omit the multiplication dot between
elements in the semiring. We denote $x\sim y$ if there are
$z_{1},\ldots,z_{n}\in S$ such that

(36) $x\preceq z_{1}\succeq z_{2}\preceq\cdots\succeq z_{n}\preceq y.$

The preordered semiring $S$ is of polynomial growth if it has a power
universal $u\in S$, i.e.

(37) $x\preceq y\quad\Rightarrow\quad\exists k\in\mathbb{N}:\ y\preceq
xu^{k}.$

A preordered semiring $S$ is a preordered semidomain if

(38) $\begin{array}[]{rcl}xy=0&\Rightarrow&x=0\ {\rm or}\ y=0,\\\ 0\preceq
x\preceq 0&\Rightarrow&x=0.\end{array}$

Moreover, $S$ is zerosumfree if $x+y=0$ implies $x=0=y$.

Given preordered semirings $S$ and $T$, we say that a map $\Phi:S\to T$ is a
monotone homomorphism if

  * •

$\Phi(x+y)=\Phi(x)+\Phi(y)$ for all $x,y\in S$ (additivity),

  * •

$\Phi(xy)=\Phi(x)\Phi(y)$ for all $x,y\in S$ (multiplicativity),

  * •

$x\preceq y$ $\Rightarrow$ $\Phi(x)\preceq\Phi(y)$ (monotonicity), and

  * •

$\Phi(0)=0$ and $\Phi(1)=1$.

We say that such a monotone homomorphism is degenerate if $x\preceq y$ implies
$\Phi(x)=\Phi(y)$. Otherwise $\Phi$ is nondegenerate. For our results we need
monotone homomorphisms with values in special semirings. These are the
following:

  * •

$\mathbb{R}_{+}$: The half-line $[0,\infty)$ equipped with the natural
addition, multiplication, and total order.

  * •

$\mathbb{R}_{+}^{\rm op}$: The same as above but with the reversed order.
Together $\mathbb{R}_{+}$ and $\mathbb{R}_{+}^{\rm op}$ are often called as
temperate reals.

  * •

$\mathbb{T}\mathbb{R}_{+}$: The half-line $[0,\infty)$ equipped with the
natural multiplication, total order, and the tropical sum $x+y=\max\\{x,y\\}$.

  * •

$\mathbb{T}\mathbb{R}_{+}^{\rm op}$: The same as above but with the reversed
order. Together $\mathbb{T}\mathbb{R}_{+}$ and $\mathbb{T}\mathbb{R}_{+}^{\rm
op}$ are often called as tropical reals.

Suppose that $S$ is a preordered semiring and that $\Phi:S\to\mathbb{R}_{+}$
or $\Phi:S\to\mathbb{R}_{+}^{\rm op}$ is a monotone homomorphism. We say that
an additive map $\Delta:S\to\mathbb{R}$ is a derivation at $\Phi$ or a
$\Phi$-derivation if it satisfies the Leibniz rule

(39) $\Delta(xy)=\Delta(x)\Phi(y)+\Phi(x)\Delta(y)$

for all $x,y\in S$. We are usually interested in monotone derivations at
degenerate homomorphisms (in which case we may always view $\mathbb{R}_{+}$ as
the value space for $\Phi$).

Not all derivations are relevant though for the following results. Given a
degenerate homomorphism $\Phi:S\to\mathbb{R}_{+}$, we only need to consider
derivations at $\Phi$ modulo interchangeability: we say that derivations
$\Delta,\Delta^{\prime}:S\to\mathbb{R}$ at $\Phi$ are interchangeable if there
exists an additive derivation $\delta:\mathbb{R}_{+}\to\mathbb{R}$, i.e.,
$\delta(x+y)=\delta(x)+\delta(y)$ and $\delta(xy)=\delta(x)y+x\delta(y)$ for
all $x,y\in\mathbb{R}$, such that

(40) $\Delta^{\prime}(x)=\Delta(x)+\delta\big{(}\Phi(x)\big{)}$

for all $x\in S$. On the other hand, assume that $\Delta:S\to\mathbb{R}$ is an
additive monotone derivation at a degenerate homomorphism
$\Phi:S\to\mathbb{R}_{+}$ and that $\delta:\mathbb{R}_{+}\to\mathbb{R}$ is an
additive derivation. Then (40) defines an additive monotone derivation
$\Delta^{\prime}:S\to\mathbb{R}$ at $\Phi$. Let us quickly prove this. For the
additivity, consider $x,y\in S$:

(41) $\displaystyle\Delta^{\prime}(x+y)$
$\displaystyle=\Delta(x+y)+\delta\big{(}\Phi(x+y)\big{)}=\Delta(x)+\Delta(y)+\delta\big{(}\Phi(x)+\Phi(y)\big{)}$
(42)
$\displaystyle=\Delta(x)+\delta\big{(}\Phi(x)\big{)}+\Delta(y)+\delta\big{(}\Phi(y)\big{)}=\Delta^{\prime}(x)+\Delta^{\prime}(y).$

For monotonicity, consider $x,y\in S$, $x\succeq y$:

(43) $\displaystyle\Delta^{\prime}(y)$
$\displaystyle=\underbrace{\Delta(y)}_{\leq\Delta(x)}+\delta\big{(}\underbrace{\Phi(y)}_{=\Phi(x)}\big{)}\leq\Delta(x)+\delta\big{(}\Phi(x)\big{)}=\Delta^{\prime}(x).$

for the Leibnitz property, consider $x,y\in S$:

(44) $\displaystyle\Delta^{\prime}(xy)$
$\displaystyle=\Delta(xy)+\delta\big{(}\underbrace{\Phi(xy)}_{=\Phi(x)\Phi(y)}\big{)}=\Delta(x)\Phi(y)+\Phi(x)\Delta(y)+\delta\big{(}\Phi(x)\big{)}\Phi(y)+\Phi(x)\delta\big{(}\Phi(y)\big{)}$
(45)
$\displaystyle=\Big{(}\Delta(x)+\delta\big{(}\Phi(x)\big{)}\Big{)}\Phi(y)+\Phi(x)\Big{(}\Delta(y)+\delta\big{(}\Phi(y)\big{)}\Big{)}=\Delta^{\prime}(x)\Phi(y)+\Phi(x)\Delta^{\prime}(y).$

Several results called ‘Vergleichstellensätze’ have been derived in [8]. Of
all of them, we particularly need the following:

######  Theorem 1 (Theorem 8.6 in [8]).

Let $S$ be a zerosumfree preordered semidomain with a power universal element
$u$. Assume that for some $d\in\mathbb{N}$ there is a surjective homomorphism
$\|\cdot\|:S\to\mathbb{R}_{>0}^{d}\cup\\{(0,\ldots,0)\\}$ with trivial kernel
and such that

(46) $a\preceq b\ \Rightarrow\ \|a\|=\|b\|\quad{\rm and}\quad\|a\|=\|b\|\
\Rightarrow\ a\sim b.$

Denote the component homomorphisms of $\|\cdot\|$ by $\|\cdot\|_{(j)}$,
$j=1,\ldots,d$. Let $x,y\in S\setminus\\{0\\}$ with $\|x\|=\|y\|$ and where
$y$ is power universal. If,

  * (i)

for every $\mathbb{K}\in\\{\mathbb{R}_{+},\mathbb{R}_{+}^{\rm
op},\mathbb{T}\mathbb{R}_{+},\mathbb{T}\mathbb{R}_{+}^{\rm op}\\}$ and every
nondegenerate monotone homomorphism $\Phi:S\to\mathbb{K}$ with trivial kernel,
we have $\Phi(x)<\Phi(y)$ and

  * (ii)

$\Delta(x)<\Delta(y)$ for every monotone $\|\cdot\|_{(j)}$-derivation
$\Delta:S\to\mathbb{R}$ with $\Delta(u)=1$ (modulo interchangeability) for all
component indices $j=1,\ldots,d$,

then

  * (a)

$x^{n}\preceq y^{n}$ for all sufficiently large $n\in\mathbb{N}$, and

  * (b)

$ax\preceq ay$ for a catalyst of the form
$a=\sum_{\ell=0}^{n}x^{\ell}y^{n-\ell}$ for all sufficiently large
$n\in\mathbb{N}$.

Conversely if either of these properties holds for any $n$ or $a$, then the
above inequalities hold non-strictly.

##  3\. The minimal restrictions case

In order to derive conditions for large-sample majorization with varying
support conditions for the columns of the matrices, we apply Theorem 1. To
this end, we need to define semirings preordered by the extension of the
matrix majorization ordering $\succeq$ defined in Definition 1 and find their
monotone homomorphisms and derivations into each of $\mathbb{R}_{+}$,
$\mathbb{R}_{+}^{\rm op}$, $\mathbb{T}\mathbb{R}_{+}$, and
$\mathbb{T}\mathbb{R}_{+}^{\rm op}$. We look at two particular cases: the case
where the only condition for the columns of the matrices is that either they
are all zero columns or they share some common support and the case where the
final column dominates all the other columns. We start with the first case.

###  3.1. Minimal restrictions semiring

We now define the semiring to which we will apply the Vergleichsstellensatz in
Theorem 1 to in order to obtain large-sample majorization results for matrices
whose columns need not be mutually dominating. Fix an integer $d\geq 2$, which
is the number of probability distributions in a tuple. For any integer $n\geq
1$, write

(47) $\displaystyle\mathcal{V}_{n}^{d}$
$\displaystyle:=\left\\{\,\left(p^{(1)},\ldots,p^{(d)}\right)\in\left(\mathbb{R}_{+}^{n}\right)^{d}\;\middle|\;\bigcap_{k=1}^{d}{\rm
supp}\,p^{(k)}\neq\emptyset\textrm{ or }p^{(k)}=(0,\ldots,0)\;\forall
k\in[d]\,\right\\},$ (48) $\displaystyle\mathcal{V}^{d}$
$\displaystyle:=\bigcup_{n=1}^{\infty}\mathcal{V}_{n}^{d}.$

For any $P=(p^{(1)},\ldots,p^{(d)})\in\mathcal{V}_{n}^{d}$ we write
$p^{(k)}=(p_{1}^{(k)},\ldots,p_{n}^{(k)})$ for $k\in[d]$ and view $P$ as an
$n\times d$-matrix.

We define two binary operations $\boxplus,\boxtimes$ on matrices in
$\mathcal{V}^{d}$. Let $P,Q\in\mathcal{V}^{d}$. Then

(49) $P\boxplus Q:=(p^{(1)}\oplus q^{(1)},\ldots,p^{(d)}\oplus q^{(d)}),$

where $\oplus$ denotes the concatenation of two vectors. One can view this as
stacking the matrices $P$ and $Q$:

(50) $P\boxplus Q=\left(\frac{P}{Q}\right).$

Also, we define

(51) $P\boxtimes Q:=(p^{(1)}\otimes q^{(1)},\ldots,p^{(d)}\otimes q^{(d)}),$

where $\otimes$ is the Kronecker product of two vectors.

Next, we define a preorder $\succeq$ on $\mathcal{V}$ as follows: for
$P,Q\in\mathcal{V}^{d}$, we declare $P\succeq Q$ if there exists a stochastic
matrix $T$ such that $TP=Q$.

The set $\mathcal{V}^{d}$ together with the operations $\boxplus$, $\boxtimes$
and the preorder $\succeq$ do not yet form a preordered semiring. For
instance, $P\boxplus Q$ and $Q\boxplus P$ have the same rows, but possibly in
a different order. We now define an equivalence relation $\approx$ on
$\mathcal{V}^{d}$ such that it becomes a preordered semiring together with the
induced operations and preorder. Write $P\approx Q$ when one matrix can be
obtained from the other by permuting the rows and adding rows of zeros
$(0,\ldots,0)$. Denote by $[P]$ the equivalence class of
$P\in\mathcal{V}^{d}$. The operations $\boxplus$ and $\boxtimes$ induce well-
defined operations on $\mathcal{V}^{d}/\approx$ that are also commutative and
transitive. The preorder $\succeq$ on $\mathcal{V}^{d}$ induces a well-defined
preorder on $\mathcal{V}^{d}/\approx$ which we still denote by $\succeq$.
Defining $0:=[(0,\ldots,0)]$, $1:=[(1,\ldots,1)]$, one checks that
$S^{d}:=(\mathcal{V}^{d}/\approx,\boxplus,\boxtimes,0,1,\succeq)$ is a
preordered semiring, which we call the _minimal restrictions matrix
majorization semiring of length_ $d$.

In the rest of this paper, we will mostly denote any element
$[P]\in\mathcal{V}^{d}/\approx$ by just one representative matrix
$P\in\mathcal{V}^{d}$, and do calculations with this matrix while freely
changing the ordering of the rows and adding or removing rows of zeros.

Let
$P=(p^{(1)},\ldots,p^{(d)}),Q=(q^{(1)},\ldots,q^{(d)})\in\mathcal{V}_{n}^{d}$.
Since a stochastic map preserves the $1$-norm of vectors, one sees that
$P\preceq Q$ implies $\|p^{(k)}\|_{1}=\|q^{(k)}\|_{1}$ for all $k\in[d]$.
Next, assume $\|p^{(k)}\|_{1}=\|q^{(k)}\|_{1}$ for all $k\in[d]$, and let $T$
be the stochastic map that takes the $1$-norm of every column. Then
$TP=(\|p^{(1)}\|_{1},\ldots,\|p^{(d)}\|_{1})=TQ$, hence $P\sim Q$. We conclude
that the conditions on
$\|\cdot\|:S^{d}\rightarrow\mathbb{R}_{>0}^{d}\cup\\{0\\}$ in Theorem 1 are
met when we choose $\|P\|:=(\|p^{(1)}\|_{1},\ldots,\|p^{(d)}\|_{1})$ for
$P\in\mathcal{V}^{d}$, which is clearly a surjective homomorphism. We will
later in Subsection 3.4 show that $S^{d}$ is of polynomial growth by
characterizing the power universals of $S^{d}$.

###  3.2. Monotone homomorphisms

In this section, we characterize all monotone homomorphisms
$\Phi:S^{d}\to\mathbb{K}$, where
$\mathbb{K}\in\\{\mathbb{R}_{+},\mathbb{R}_{+}^{\rm
op},\mathbb{T}\mathbb{R}_{+},\mathbb{T}\mathbb{R}_{+}^{\rm op}\\}$. It will
turn out that only for $\mathbb{K}=\mathbb{R}_{+}^{\rm op}$ there exist non-
degenerate $\Phi$.

Define the one-row function
$\varphi:\mathbb{R}_{>0}^{d}\cup\\{(0,\ldots,0)\\}\to\mathbb{R}_{+}$, where
$\varphi(x_{1},\ldots,x_{d}):=\Phi(x_{1}\,\cdots\,x_{d})$. Note that $\varphi$
is only defined on those rows of a matrix $P\in S^{d}$ that contain only
positive entries, and the row containing only zeros. Exactly as in the proof
of Proposition 13 in [7], we can show that

(52) $\varphi(x_{1},\ldots,x_{d})=x_{1}^{\alpha_{1}}\cdots
x_{d}^{\alpha_{d}},$

where

(53)
$\underline{\alpha}=(\alpha_{1},\ldots,\alpha_{d})\in\left\\{\begin{array}[]{ll}A_{-},&\mathbb{K}=\mathbb{R}_{+}\\\
A_{+},&\mathbb{K}=\mathbb{R}_{+}^{\rm op}\\\
B_{-},&\mathbb{K}=\mathbb{T}\mathbb{R}_{+}\\\
B,&\mathbb{K}=\mathbb{T}\mathbb{R}_{+}^{\rm op}\end{array}\right..$

Here, the sets $A_{+},A_{-},B,B_{-}$ are as in (4), (5), (30), (31),
respectively. Note that any $P\in S^{d}$ has at least one row with all
positive entries, since the columns must have some common support. We will say
that $\Phi$ _is associated with_ $\underline{\alpha}$.

In [7], where only matrices $P$ with common support were considered, it was
possible to break down $P$ into a $\boxtimes$-sum of its rows which can all be
viewed as elements of the semiring because each row contains only positive
entries, or contains only zeros. In that case, denoting the rows of a matrix
$P$ by $p_{i}$, we may write, for any monotone homomorphism $\Phi$ with
codomain $\mathbb{K}$,

(54)
$\Phi(P)=\left\\{\begin{array}[]{ll}\sum_{i}\varphi(p_{i}),&\mathbb{K}\in\\{\mathbb{R}_{+},\mathbb{R}_{+}^{\rm
op}\\}\\\
\max_{i}\varphi(p_{i}),&\mathbb{K}\in\\{\mathbb{T}\mathbb{R}_{+},\mathbb{T}\mathbb{R}_{+}^{\rm
op}\\}\end{array}\right..$

Thus, it is enough to characterize this one-row function $\varphi$ in the
common-support case. In the semiring we are considering now, this no longer
works because a row with both vanishing and positive entries cannot be seen as
an element of our semiring; recall that the columns of any matrix in our
semiring must have some common support. This is why we have to consider the
value of a homomorphism at matrices with a full-support row and different
types of rows with vanishing entries. However, it turns out that we may
characterize the monotone homomorphisms considering its values at only two-row
matrices where the first row has full support and the second has some
vanishing entries.

We first prove a useful result for the monotone homomorphisms. For any
$B\subseteq[d]$ we denote by $(\;B\;)$ the row of length $d$ whose $k$-th
entry is 1 if $k\in B$ and otherwise the entry is 0. For any monotone
homomorphism $\Phi:S^{d}\to\mathbb{K}$ for
$\mathbb{K}\in\\{\mathbb{R}_{+},\mathbb{R}_{+}^{\rm
op},\mathbb{T}\mathbb{R}_{+},\mathbb{T}\mathbb{R}_{+}^{\rm op}\\}$ denote

(55) $\Phi[B]:=\Phi\left(\begin{array}[]{ccc}1&\cdots&1\\\
&B&\end{array}\right).$

######  Lemma 2.

Let $B\subsetneq[d]$, $B\neq\emptyset$, and $\Phi:S^{d}\to\mathbb{K}$ a
monotone homomorphism for some
$\mathbb{K}\in\\{\mathbb{R}_{+},\mathbb{R}_{+}^{\rm
op},\mathbb{T}\mathbb{R}_{+},\mathbb{T}\mathbb{R}_{+}^{\rm op}\\}$. Then

  1. (i)

We have

(56) $\Phi[B]=\left\\{\begin{array}[]{ll}1\text{ or
}2,&\mathbb{K}\in\\{\mathbb{R}_{+},\mathbb{R}_{+}^{\rm op}\\}\\\
1,&\mathbb{K}\in\\{\mathbb{T}\mathbb{R}_{+},\mathbb{T}\mathbb{R}_{+}^{\rm
op}\\}\end{array}\right..$

  2. (ii)

Suppose that $\mathbb{K}\in\\{\mathbb{R}_{+},\mathbb{R}_{+}^{\rm op}\\}$ and
that $\Phi$ is associated with
$\underline{\alpha}=(\alpha_{1},\ldots,\alpha_{d})\in A_{+}\cup A_{-}$. If
$\Phi[B]$ equals $2$, then $\alpha_{k}=0$ for all $k\notin B$.

###### Proof.

To prove (i), notice

(57) $\left(\begin{array}[]{ccc}1&\cdots&1\\\ &B&\end{array}\right)^{\boxtimes
2}\boxplus\left(\begin{array}[]{ccc}1&\cdots&1\\\
1&\cdots&1\end{array}\right)=\left(\begin{array}[]{ccc}1&\cdots&1\\\
&B&\end{array}\right)\boxplus\left(\begin{array}[]{ccc}1&\cdots&1\\\
&B&\end{array}\right)\boxplus\left(\begin{array}[]{ccc}1&\cdots&1\\\
&B&\end{array}\right).$

Using additivity and multiplicativity of $\Phi$, and the fact that we know
that $\Phi$ evaluated on single rows with only positive entries is given by
(52), the above equality, for
$\mathbb{K}\in\\{\mathbb{R}_{+},\mathbb{R}_{+}^{\rm op}\\}$, yields the
equation

(58) $\left(\Phi[B]\right)^{2}+2=3\Phi[B],$

and for
$\mathbb{K}\in\\{\mathbb{T}\mathbb{R}_{+},\mathbb{T}\mathbb{R}_{+}^{\rm
op}\\}$, yields the equation

(59) $\max\left\\{\left(\Phi[B]\right)^{2},1\right\\}=\Phi[B].$

The solutions to the first equation are $1$ and $2$, and to the second the
unique solution is $1$, proving (56).

To prove (ii), define the numbers $x_{k}$ coinciding with $2$ when $k\in B$
and otherwise $x_{k}=1$ and $y_{k}$ coinciding with $2$ when $k\in B$ and
otherwise $y_{k}=0$. Denoting by $\begin{subarray}{c}\succeq\\\
\preceq\end{subarray}$ majorization in both directions simultaneously, we have

(60) $\left(\begin{array}[]{ccc}1&\cdots&1\\\
&B&\end{array}\right)\boxplus\left(\begin{array}[]{ccc}1&\cdots&1\\\
&B&\end{array}\right)\boxplus(x_{1}\,\cdots\,x_{d})\,\begin{subarray}{c}\succeq\\\
\preceq\end{subarray}\left(\begin{array}[]{ccc}x_{1}&\cdots&x_{d}\\\
y_{1}&\cdots&y_{d}\end{array}\right)\boxplus\left(\begin{array}[]{ccc}1&\cdots&1\\\
1&\cdots&1\end{array}\right),$

where the LHS majorizes the RHS because there is a stochastic matrix that adds
the two rows $(\;B\;)$ to obtain the row $(y_{1}\,\cdots\,y_{d})$, and the RHS
majorizes the LHS because there is a stochastic matrix that splits the row
$(y_{1}\,\cdots\,y_{d})$ into two copies of the row $(\;B\;)$. Next, notice
that the RHS is equal to

(61) $(x_{1}\,\cdots\,x_{d})\boxtimes\left(\begin{array}[]{ccc}1&\cdots&1\\\
&B&\end{array}\right)\boxplus\left(\begin{array}[]{ccc}1&\cdots&1\\\
1&\cdots&1\end{array}\right).$

Using the monotonicity, additivity and multiplicativity of $\Phi$, and the
single-row function given by (52), the two equations (60) and (61) above yield
the equation

(62) $2+2+2^{\sum_{k\in B}\alpha_{k}}=2^{\sum_{k\in B}\alpha_{k}}\cdot 2+2,$

hence $\sum_{k\in B}\alpha_{k}=1$. This implies $\alpha_{k}=0$ for all
$k\notin B$, where for the case $\mathbb{K}=\mathbb{R}_{+}$ we use the fact
that $\underline{\alpha}\in A_{-}$ and therefore only one of the coordinates
$\alpha_{k}$ is positive. ∎

Consider a monotone homomorphism $\Phi:S^{d}\to\mathbb{K}$ for
$\mathbb{K}\in\\{\mathbb{R}_{+},\mathbb{R}_{+}^{\rm
op},\mathbb{T}\mathbb{R}_{+},\mathbb{T}\mathbb{R}_{+}^{\rm op}\\}$. We call
$B$ _$\Phi$ -trivial_ if $\Phi[B]=1$ and _$\Phi$ -nontrivial_ if $\Phi[B]=2$.
Note that if
$\mathbb{K}\in\\{\mathbb{T}\mathbb{R}_{+},\mathbb{T}\mathbb{R}_{+}^{\rm
op}\\}$, all sets $B$ are $\Phi$-trivial.

######  Lemma 3.

Fix a monotone homomorphism $\Phi:S^{d}\to\mathbb{K}$ for
$\mathbb{K}\in\\{\mathbb{R}_{+},\mathbb{R}_{+}^{\rm op}\\}$. Let
$B_{1},B_{2}\subsetneq[d]$, with $B_{1},B_{2}\neq\emptyset$. The following
holds:

  1. (i)

If $B_{1}$ and $B_{2}$ are $\Phi$-nontrivial, then $B_{1}\cap B_{2}$ is also
$\Phi$-nontrivial.

  2. (ii)

If $B_{1}\subseteq B_{2}$ and $B_{1}$ is $\Phi$-nontrivial, then $B_{2}$ is
also $\Phi$-nontrivial.

###### Proof.

For the proof of (i), assume that $B_{1}$ and $B_{2}$ are $\Phi$-nontrivial.
Notice

(63) $\left(\begin{array}[]{ccc}1&\cdots&1\\\
1&\cdots&1\end{array}\right)\boxplus\left(\begin{array}[]{ccc}1&\cdots&1\\\
&B_{1}&\end{array}\right)\boxtimes\left(\begin{array}[]{ccc}1&\cdots&1\\\
&B_{2}&\end{array}\right)=\left(\begin{array}[]{ccc}1&\cdots&1\\\
1&\cdots&1\\\ 1&\cdots&1\\\ &B_{1}&\\\ &B_{2}&\\\ &B_{1}\cap
B_{2}&\end{array}\right)$

This yields

(64) $2+\Phi[B_{1}]\Phi[B_{2}]=\Phi[B_{1}]+\Phi[B_{2}]+\Phi[B_{1}\cap B_{2}].$

Since $\Phi[B_{1}]=2=\Phi[B_{2}]$, we conclude that $\Phi[B_{1}\cap B_{2}]=2$,
hence $B_{1}\cap B_{2}$ is $\Phi$-nontrivial.

Next, for the proof of (ii), assume that $B_{1}$ is $\Phi$-nontrivial. Notice

(65) $\left(\begin{array}[]{ccc}1&\cdots&1\\\
1&\cdots&1\end{array}\right)\boxplus\left(\begin{array}[]{ccc}1&\cdots&1\\\
&B_{1}&\end{array}\right)\boxtimes\left(\begin{array}[]{ccc}1&\cdots&1\\\
&B_{2}&\end{array}\right)=\left(\begin{array}[]{ccc}1&\cdots&1\\\
1&\cdots&1\\\ 1&\cdots&1\\\ &B_{1}&\\\ &B_{2}&\\\ &B_{1}&\end{array}\right)$

This yields

(66) $2+\Phi[B_{1}]\Phi[B_{2}]=2\Phi[B_{1}]+\Phi[B_{2}].$

Since $\Phi[B_{1}]=2$, we conclude that $\Phi[B_{2}]=2$, hence $B_{2}$ is
$\Phi$-nontrivial. ∎

For any homomorphism
$\Phi:S^{d}\to\mathbb{K}\in\\{\mathbb{R}_{+},\mathbb{R}_{+}^{\rm op}\\}$, we
define the character $C\subseteq[d]$ as the intersection of all
$\Phi$-nontrivial subsets of $[d]$. According to Lemma 3, $C$ is
$\Phi$-nontrivial and, by construction, it is the smallest $\Phi$-nontrivial
subset of $[d]$. Moreover, $B\subseteq[d]$ is $\Phi$-nontrivial if and only if
$C\subseteq B$. Indeed, if $B\subseteq[d]$ were a $\Phi$-nontrivial set such
that $C$ is not a subset of $B$, then also $B\cap C$ would be
$\Phi$-nontrivial and thus nonempty. But now $B\cap C\subsetneq C$ is a
$\Phi$-nontrivial set genuinely smaller than $C$, a contradiction.

Let $\underline{\alpha}=(\alpha_{1},\ldots,\alpha_{d})\in\mathbb{R}_{+}^{d}$
with $\alpha_{1}+\ldots+\alpha_{d}=1$, and
$C=\\{c_{1},\ldots,c_{\ell}\\}\subseteq[d]$, $C\neq\emptyset$, such that $C$
contains (at least) all columns $c$ with $\alpha_{c}\neq 0$. Denote by
$C^{\prime}:=\\{c^{\prime}_{1},\ldots,c^{\prime}_{\ell^{\prime}}\\}\subseteq
C$ the subset of columns $c\in C$ that satisfy $\alpha_{c}\neq 0$. Define
$\varphi_{\underline{\alpha},C}:\mathbb{R}_{+}^{\ell^{\prime}}\to\mathbb{R}$
by

(67)
$\varphi_{\underline{\alpha},C}(x_{c^{\prime}_{1}},\ldots,x_{c^{\prime}_{\ell^{\prime}}}):=x_{c^{\prime}_{1}}^{\alpha_{c^{\prime}_{1}}}\cdots
x_{c^{\prime}_{\ell^{\prime}}}^{\alpha_{c^{\prime}_{\ell^{\prime}}}}.$

One can show that $\varphi_{\underline{\alpha},C}$ is concave on
$\mathbb{R}_{>0}^{\ell^{\prime}}$ (see the proof of Proposition 13 in [7]).
Then, by continuity of $\varphi_{\underline{\alpha},C}$ and the fact that all
powers $\alpha_{c^{\prime}}>0$ for $c^{\prime}\in C^{\prime}$111Here we use
that $\lim_{x\downarrow 0}x^{\alpha}=0$ for $\alpha>0$., one concludes that
$\varphi_{\underline{\alpha},C}$ is concave on its entire domain
$\mathbb{R}_{+}^{\ell^{\prime}}$. In the following, we will abuse notation by
writing $\varphi_{\underline{\alpha},C}(x)$ for $x\in\mathbb{R}_{+}^{d}$
instead of $x\in\mathbb{R}_{+}^{\ell^{\prime}}$, where it is understood that
we ignore the coordinates not in $C^{\prime}$.

We now define the homomorphism
$\Phi_{\underline{\alpha},C}:S^{d}\to\mathbb{R}_{+}^{\rm op}$ by

(68) $\Phi_{\underline{\alpha},C}(P):=\sum_{i\in
I(P,C)}\varphi_{\underline{\alpha},C}\left(p_{i}^{(1)},\ldots,p_{i}^{(d)}\right),\quad\quad
P=(p^{(1)},\ldots,p^{(d)})\in\mathcal{V}_{n}^{d},$

where

(69) $I(P,C):=\left\\{\,i\in[n]\,\middle|\,p_{i}^{(c)}>0\quad\forall c\in
C\,\right\\}=\bigcap_{c\in C}{\rm supp}\,p^{(c)}.$

These are, indeed, easily seen to be homomorphisms and we will later see that
they are also monotone. The degenerate ones among these homomorphisms are
exactly all $\Phi_{\underline{\alpha},C}=:\Phi^{(k)}$ with $\alpha_{k}=1$ for
some $k$ and $\alpha_{k^{\prime}}=0$ for all $k^{\prime}\neq k$, and
$C=\\{k\\}$; indeed, these give the same value for $P$ and $Q$ whenever $P\sim
Q$. Denote all the non-degenerate homomorphisms $\Phi_{\underline{\alpha},C}$
by $\mathcal{H}^{\rm n.d.}(S^{d},\mathbb{R}_{+}^{\rm op})$, i.e., denoting by
${\rm supp}\,\underline{\alpha}$ for all
$\underline{\alpha}=(\alpha_{1},\ldots,\alpha_{d})\in A_{+}$ (where
$A_{+}\subset\mathbb{R}^{d}$ is given in (4)) the subset of those $k\in[d]$
such that $\alpha_{k}>0$,

(70) $\mathcal{H}^{\rm n.d.}(S^{d},\mathbb{R}_{+}^{\rm
op})=\left\\{\Phi_{\underline{\alpha},C}\,\middle|\,\underline{\alpha}\in
A_{+},\ {\rm supp}\,\underline{\alpha}\subseteq
C\subseteq[d]\right\\}\setminus\big{\\{}\Phi^{(k)}\big{\\}}_{k=1}^{d}.$

Note that if $C$ consists of all $c\in[d]$ that satisfy $\alpha_{c}>0$, and no
other $c\in[d]$, then $\Phi_{\underline{\alpha},C}$ essentially sums over all
rows of any matrix in $S^{d}$. Hence a homomorphism with this property is
continuous in its argument. From now on, we simply call elements of
$\mathcal{H}^{\rm n.d.}(S^{d},\mathbb{R}_{+}^{\rm op})$ with this property
continuous, i.e,

(71) $\Phi_{\underline{\alpha},C}\ {\rm continuous}\quad\iff\quad C={\rm
supp}\,\underline{\alpha}.$

A homomorphism not satisfying this property is always discontinuous. For
example in the case $d=2$ and for the homomorphism $\Phi_{(0,1),\\{1,2\\}}$,
this can be seen by considering

(72) $P_{\varepsilon}:=\left(\begin{array}[]{ccc}1-\varepsilon&1/2\\\
\varepsilon&1/2\end{array}\right),$

where $\varepsilon\geq 0$, and noting that there is a gap between
$\Phi_{(0,1),\\{1,2\\}}(P_{0})=1/2$ and
$\Phi_{(0,1),\\{1,2\\}}(P_{\varepsilon})=1$ for $\varepsilon>0$, although
$\lim_{\varepsilon\rightarrow 0}P_{\varepsilon}=P_{0}$.

We first show that all homomorphisms in $\mathcal{H}^{\rm
n.d.}(S^{d},\mathbb{R}_{+}^{\rm op})$ are monotone, and then prove that these
are in fact all non-degenerate monotone homomorphisms.

######  Proposition 4.

All homomorphisms in $\mathcal{H}^{\rm n.d.}(S^{d},\mathbb{R}_{+}^{\rm op})$
are monotone.

###### Proof.

Let $\underline{\alpha}\in\mathbb{R}_{+}^{d}$ such that
$\alpha_{1}+\ldots+\alpha_{d}=1$, and $C\in\mathcal{P}([d])\setminus\emptyset$
such that $C$ contains all columns $c$ with $\alpha_{c}\neq 0$. Consider
$P\in\mathcal{V}_{n}^{d}$ with rows $p_{1},\ldots,p_{n}\in\mathbb{R}_{+}^{d}$
and a stochastic $m\times n$-matrix $T$, and write
$Q:=TP\in\mathcal{V}_{m}^{d}$ with rows
$q_{1},\ldots,q_{m}\in\mathbb{R}_{+}^{d}$, and
$T_{i}:=\sum_{j=1}^{n}T_{i,j}>0$. Using the concavity of
$\varphi_{\underline{\alpha},C}$ in the first inequality, we find

(73) $\displaystyle\Phi_{\underline{\alpha},C}(Q)$ $\displaystyle=\sum_{i\in
I(Q,C)}\varphi_{\underline{\alpha},C}(q_{i})=\sum_{i\in
I(Q,C)}\varphi_{\underline{\alpha},C}\left(\sum_{j=1}^{n}T_{i,j}p_{j}\right)=\sum_{i\in
I(Q,C)}T_{i}\varphi_{\underline{\alpha},C}\left(\sum_{j=1}^{n}\frac{T_{i,j}}{T_{i}}p_{j}\right)$
(74) $\displaystyle\geq\sum_{i\in
I(Q,C)}T_{i}\sum_{j=1}^{n}\frac{T_{i,j}}{T_{i}}\varphi_{\underline{\alpha},C}(p_{j})=\sum_{j=1}^{n}\varphi_{\underline{\alpha},C}(p_{j})\sum_{i\in
I(Q,C)}T_{i,j}$ (75) $\displaystyle=\sum_{j\in
I(P,C)}\varphi_{\underline{\alpha},C}(p_{j})\underbrace{\sum_{i\in
I(Q,C)}T_{i,j}}_{=1}+\sum_{j\notin
I(P,C)}\varphi_{\underline{\alpha},C}(p_{j})\sum_{i\in I(Q,C)}T_{i,j}$ (76)
$\displaystyle\geq\sum_{j\in
I(P,C)}\varphi_{\underline{\alpha},C}(p_{j})=\Phi_{\underline{\alpha},C}(P).$

For the second inequality, consider any $j\in I(P,C)$ and $i\notin I(Q,C)$.
Then there exists a column $k\in C$ such that
$\sum_{j^{\prime}=1}^{n}T_{i,j^{\prime}}(p_{j^{\prime}})_{k}=0$, hence
$T_{i,j}(p_{j})_{k}=0$. Since $j\in I(P,C)$ implies that $(p_{j})_{k}>0$, we
conclude that $T_{i,j}=0$. This means that $\sum_{i\in
I(Q,C)}T_{i,j}=\sum_{i=1}^{m}T_{i,j}=1$ for all $j\in I(P,C)$. ∎

######  Proposition 5.

The non-degenerate monotone homomorphisms $S^{d}\rightarrow\mathbb{R}_{+}^{\rm
op}$ are exactly those in $\mathcal{H}^{\rm n.d.}(S^{d},\mathbb{R}_{+}^{\rm
op})$. For $\mathbb{K}$ equal to $\mathbb{R}_{+}$, $\mathbb{T}\mathbb{R}_{+}$
or $\mathbb{T}\mathbb{R}_{+}^{\rm op}$, there are no non-degenerate monotone
homomorphisms $S^{d}\rightarrow\mathbb{K}$.

###### Proof.

Let us first consider the case
$\mathbb{K}\in\\{\mathbb{R}_{+},\mathbb{R}_{+}^{\rm op}\\}$ and fix a monotone
homomorphism $\Phi:S^{d}\to\mathbb{K}$. Let
$\underline{\alpha}=(\alpha_{1},\ldots,\alpha_{d})\in A$ be the parameter
vector which $\Phi$ is associated with and $C\subseteq[d]$ be the character of
$\Phi$. For any $x\in\mathbb{R}_{+}^{d}$, denote by
$\tilde{x}\in\mathbb{R}_{>0}^{d}$ the vector obtained from $x$ by replacing
all vanishing entries with $1$. We now define
$\varphi:\mathbb{R}_{+}\to\mathbb{K}$ through

(77) $\varphi(x):=\Phi\big{(}\tilde{x}^{T}\boxplus
x^{T}\big{)}-\varphi(\tilde{x})$

for all $x\in\mathbb{R}_{+}^{d}$. Note that for
$x=(x_{1},\ldots,x_{d})\in\mathbb{R}_{+}^{d}$, we have

(78) $\varphi(\tilde{x})=\prod_{k\in{\rm supp}\,x}x_{k}^{\alpha_{k}}.$

We now have, for all $x=(x_{1},\ldots,x_{k})\in\mathbb{R}_{+}^{d}$,

(81) $\displaystyle\varphi(x)$ $\displaystyle=\Phi\big{(}\tilde{x}^{T}\boxplus
x^{T}\big{)}-\varphi(\tilde{x})=\Phi\left(\tilde{x}^{T}\boxtimes\left(\begin{array}[]{ccc}1&\cdots&1\\\
&{\rm supp}\,x&\end{array}\right)\right)-\varphi(\tilde{x})$ (86)
$\displaystyle=\varphi(\tilde{x})\left(\Phi\left(\begin{array}[]{ccc}1&\cdots&1\\\
&{\rm supp}\,x&\end{array}\right)-1\right)=\varphi(\tilde{x})\big{(}\Phi[{\rm
supp}\,x]-1\big{)}=\left\\{\begin{array}[]{ll}\varphi(\tilde{x}),&C\subseteq{\rm
supp}\,x,\\\ 0&{\rm otherwise}\end{array}\right.$

where the last equality is due to the fact that $\Phi[B]=2$ if and only if
$C\subseteq B$ and $\Phi[B]=1$ otherwise.

Let $P=\big{(}p^{(1)},\ldots,p^{(d)}\big{)}\in\mathcal{V}^{d}$,
$p^{(k)}=\big{(}p^{(k)}_{1},\ldots,p^{(k)}_{n}\big{)}$ for $k=1,\ldots,d$.
Define $p_{i}:=\big{(}p^{(1)}_{i},\ldots,p^{(d)}_{i}\big{)}$ for
$i=1,\ldots,n$. We may write

(87) $\displaystyle\Phi(P)$
$\displaystyle=\Phi\left(\mathop{\vphantom{\sum}\mathchoice{\vbox{\hbox{\leavevmode\resizebox{9.00005pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{10.00012pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{7.00009pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{5.00006pt}{}{$\boxplus$}}}}}\slimits@_{i=1}^{n}p_{i}^{T}\right)=\Phi\left(\mathop{\vphantom{\sum}\mathchoice{\vbox{\hbox{\leavevmode\resizebox{9.00005pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{10.00012pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{7.00009pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{5.00006pt}{}{$\boxplus$}}}}}\slimits@_{i=1}^{n}\big{(}\tilde{p}_{i}^{T}\boxplus
p_{i}^{T}\big{)}\right)-\sum_{i=1}^{n}\varphi(\tilde{p}_{i})$ (88)
$\displaystyle=\sum_{i=1}^{n}\left(\Phi\big{(}\tilde{p}_{i}^{T}\boxplus
p_{i}^{T}\big{)}-\varphi(\tilde{p}_{i})\right)=\sum_{i=1}^{n}\varphi(p_{i})=\sum_{i:\,C\subseteq{\rm
supp}\,p_{i}}\prod_{k\in{\rm
supp}\,p_{i}}\big{(}p^{(k)}_{i}\big{)}^{\alpha_{k}}.$

It follows from Lemma 2(ii) that if $k\notin C$, then $\alpha_{k}=0$.

Thus, the form of $\Phi$ is the same as those in $\mathcal{H}^{\rm
n.d.}(S^{d},\mathbb{R}^{\rm op}_{+})$ but with $\underline{\alpha}$ not
necessarily in $A_{+}$. We already know that those within $\mathcal{H}^{\rm
n.d.}(S^{d},\mathbb{R}_{+}^{\rm op})$ are monotone in the case
$\mathbb{K}=\mathbb{R}_{+}^{\rm op}$. We know from [7] that, if
$\underline{\alpha}\in A_{-}\setminus\\{e_{1},\ldots,e_{d}\\}$, then $\Phi$ is
monotone in the case $\mathbb{K}=\mathbb{R}_{+}$ when restricted on matrices
whose columns have common support. Thus, in the case
$\mathbb{K}=\mathbb{R}_{+}^{\rm op}$, the nondegenerate monotone homomorphisms
are exactly those in $\mathcal{H}^{\rm n.d.}(S^{d},\mathbb{R}^{\rm op})$. We
next show that there are actually no nondegenerate monotone homomorphisms in
the case $\mathbb{K}=\mathbb{R}_{+}$.

Next, we consider the case $\mathbb{K}=\mathbb{R}_{+}$. We show that

(89) $\Phi\left(\begin{array}[]{ccccccc}1&\cdots&1&1&1&\cdots&1\\\
0&\cdots&0&\smash{\underbrace{x}_{k\text{-th
entry}}}&0&\cdots&0\end{array}\right)\vspace{0.5cm}$

equals $1+x$ for at most one column $k\in[d]$ and equals $1$ for all other
columns. Recall from the previous analysis that the above equals either $1$ or
$1+x$. Assume (89) equals $1+x$ for some $k$. For any $k^{\prime}$ such that
$k^{\prime}\neq k$ note that

(94) $\displaystyle\left(\begin{array}[]{ccccccc}1&\cdots&1&1&1&\cdots&1\\\
0&\cdots&0&\smash{\underbrace{x}_{k\text{-th
entry}}}&0&\cdots&0\end{array}\right)$
$\displaystyle\boxtimes\left(\begin{array}[]{ccccccc}1&\cdots&1&1&1&\cdots&1\\\
0&\cdots&0&\smash{\underbrace{y}_{k^{\prime}\text{-th
entry}}}&0&\cdots&0\end{array}\right)$ (99)
$\displaystyle\overset{\rm(a)}{=}\left(\begin{array}[]{ccccccccc}1&\cdots&1&1&1&\cdots&1&\cdots&1\\\
0&\cdots&0&x&0&\cdots&0&\cdots&0\\\ 0&\cdots&0&0&0&\cdots&y&\cdots&0\\\
\end{array}\right)$ (101)
$\displaystyle\overset{\rm(b)}{\succeq}(1\;\cdots\;1\;1+x\;1\;\cdots\;1\;1+y\;1\;\cdots\;1).$

If (89) also equals $1+x$ for some $k^{\prime}\neq k$, then equality (a) above
implies

(102) $(1+x)(1+y)=1+x+y,$

for all $x,y>0$, which is clearly not possible. Hence (89) equals $1$ for all
$k^{\prime}$ except $k$. The inequality (b) above implies

(103) $1+x\geq(1+x)^{\alpha_{k}}(1+y)^{\alpha_{k^{\prime}}},$

for any $k^{\prime}\neq k$. Since $y$ can be chosen arbitrarily large, it
follows from the above inequality that $\alpha_{k^{\prime}}\leq 0$ for all
$k^{\prime}\neq k$. Hence, since $\alpha_{1}+\ldots+\alpha_{d}=1$, we find
that $\alpha_{k}\geq 1$. But $\alpha_{k}>1$ violates the above inequality for
sufficiently large $x$. Hence $\alpha_{k}=1$ and $\alpha_{k^{\prime}}=0$ for
all $k^{\prime}\neq k$.

Let $P=(p^{(1)},\ldots,p^{(d)})\in\mathcal{V}_{n}^{d}$. Notice the following
inequalities, which follow from monotonicity, and for the second inequality by
inserting a row of $1$’s for every non-zero entry in $P$ and putting every
entry on its own row:

(104)
$\Phi(\|p^{(1)}\|_{1}\;\cdots\;\|p^{(d)}\|_{1})\leq\Phi(P)\leq\sum_{i=1}^{n}\sum_{k=1}^{d}\left(\Phi\left(\begin{array}[]{ccccccc}1&\cdots&1&1&1&\cdots&1\\\
0&\cdots&0&\smash{\underbrace{p_{i}^{(k)}}_{k\text{-th
entry}}}&0&\cdots&0\end{array}\right)-1\right).\vspace{0.5cm}$

Since $\alpha_{k}=1$, the LHS is equal to $\|p^{(k)}\|_{1}$. If (89) equals
$1+x$ for some $k$, then it equals $1$ for all $k^{\prime}\neq k$, and the RHS
equals $\|p^{(k)}\|_{1}$. Hence $\Phi(P)=\|p^{(k)}\|_{1}$ for all $P$, meaning
that $\Phi$ is degenerate. If (89) equals $1$ for all $k$, then it follows
from the right inequality in (104) that $\Phi(P)=0$ for all $P$, which is not
possible. In conclusion, no non-degenerate monotone homomorphism
$S^{d}\to\mathbb{R}_{+}$ exists.

Next, we consider the cases $\mathbb{K}$ equal to $\mathbb{T}\mathbb{R}_{+}$
or $\mathbb{T}\mathbb{R}_{+}^{\rm op}$. Let $\Phi:S^{d}\to\mathbb{K}$, where
$\mathbb{K}\in\\{\mathbb{T}\mathbb{R}_{+},\mathbb{T}\mathbb{R}_{+}^{\rm
op}\\}$, be a non-degenerate monotone homomorphism, and
$\underline{\beta}=(\beta_{1},\ldots,\beta_{d})\in B$ the parameter vector
which $\Phi$ is associated with.

Let $\ell\in[d]$ and define $B_{\ell}:=\\{\ell\\}$ and
$x^{(\ell)}:=(0,\ldots,x,\ldots,0)$ for some $x>0$. Then it follows from Lemma
2(i) that

(105)
$\Phi\big{(}\big{(}\widetilde{x^{(\ell)}}\big{)}^{T}\boxplus\big{(}x^{(\ell)}\big{)}^{T}\big{)}=\Phi\left(\big{(}\widetilde{x^{(\ell)}}\big{)}^{T}\boxtimes\left(\begin{array}[]{ccc}1&\cdots&1\\\
&B_{\ell}&\end{array}\right)\right)=\Phi\big{(}(\widetilde{x^{(\ell)}}\big{)}^{T})\Phi[B_{\ell}]=\Phi\big{(}(\widetilde{x^{(\ell)}}\big{)}^{T}).$

Consider now the case $\mathbb{K}=\mathbb{T}\mathbb{R}_{+}$. Let
$P\in\mathcal{V}_{n}^{d}$, $P\neq 0$. By inserting rows of $1$’s and placing
each non-zero entry in $P$ on its own row, we have

(106)
$P\boxplus\mathop{\vphantom{\sum}\mathchoice{\vbox{\hbox{\leavevmode\resizebox{9.00005pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{10.00012pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{7.00009pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{5.00006pt}{}{$\boxplus$}}}}}\slimits@_{i,k\,:\,p_{i}^{(k)}>0}(1\,\cdots\,1\,p_{i}^{(k)}\,1\,\cdots\,1)\preceq\mathop{\vphantom{\sum}\mathchoice{\vbox{\hbox{\leavevmode\resizebox{9.00005pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{10.00012pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{7.00009pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{5.00006pt}{}{$\boxplus$}}}}}\slimits@_{i,k\,:\,p_{i}^{(k)}>0}\left(\begin{array}[]{ccccccc}1&\cdots&1&p_{i}^{(k)}&1&\cdots&1\\\\[2.84544pt]
0&\cdots&0&\smash{\underbrace{p_{i}^{(k)}}_{k\text{-th
entry}}}&0&\cdots&0\end{array}\right).\vspace{0.5cm}$

Assume all $\beta_{k}=0$. Then from the majorization above and the fact that
we know the value of $\Phi$ on single rows (52) it follows that

(107) $\Phi(P)\leq\max\\{\Phi(P),1\\}\leq 1.$

Since also $1=\Phi(\|p^{(1)}\|_{1}\;\cdots\;\|p^{(d)}\|_{1})\leq\Phi(P)$, we
find that $\Phi(P)=1$. Hence $\Phi$ is degenerate, which leads to a
contradiction. Thus there exists $k$ such that $\beta_{k}>0$. Note that

(108) $\left(\begin{array}[]{cc}1&\frac{1}{2}\\\\[2.84544pt]
0&\frac{1}{2}\end{array}\right)\left(\begin{array}[]{ccccccc}\frac{3}{2}&\cdots&\frac{3}{2}&1&\frac{3}{2}&\cdots&\frac{3}{2}\\\\[2.84544pt]
0&\cdots&0&\smash{\underbrace{1}_{k\text{-th
entry}}}&0&\cdots&0\end{array}\right)=\left(\begin{array}[]{ccccccc}\frac{3}{2}&\cdots&\frac{3}{2}&\frac{3}{2}&\frac{3}{2}&\cdots&\frac{3}{2}\\\\[2.84544pt]
0&\cdots&0&\smash{\underbrace{\textstyle\frac{1}{2}}_{k\text{-th
entry}}}&0&\cdots&0\end{array}\right).\vspace{0.5cm}$

Using this and the fact that $\sum_{k^{\prime}\neq k}\beta_{k^{\prime}}<0$ it
follows that

(111) $\displaystyle 1>\left(\frac{3}{2}\right)^{\sum_{k^{\prime}\neq
k}\beta_{k^{\prime}}}$
$\displaystyle=\Phi\left(\left(\frac{3}{2}\;\cdots\;\frac{3}{2}\;\smash{\underbrace{1}_{k\text{-th
entry}}}\;\frac{3}{2}\;\cdots\;\frac{3}{2}\right)\boxtimes\left(\begin{array}[]{ccccccc}1&\cdots&1&1&1&\cdots&1\\\\[2.84544pt]
0&\cdots&0&\smash{\underbrace{1}_{k\text{-th
entry}}}&0&\cdots&0\end{array}\right)\right)$ (114)
$\displaystyle=\Phi\left(\begin{array}[]{ccccccc}\frac{3}{2}&\cdots&\frac{3}{2}&1&\frac{3}{2}&\cdots&\frac{3}{2}\\\\[2.84544pt]
0&\cdots&0&\smash{\underbrace{1}_{k\text{-th
entry}}}&0&\cdots&0\end{array}\right)$ (117)
$\displaystyle\geq\Phi\left(\begin{array}[]{ccccccc}\frac{3}{2}&\cdots&\frac{3}{2}&\frac{3}{2}&\frac{3}{2}&\cdots&\frac{3}{2}\\\\[2.84544pt]
0&\cdots&0&\smash{\underbrace{\textstyle\frac{1}{2}}_{k\text{-th
entry}}}&0&\cdots&0\end{array}\right)$ (120)
$\displaystyle=\Phi\left(\left(\frac{3}{2}\;\cdots\;\frac{3}{2}\right)\boxtimes\left(\begin{array}[]{ccccccc}1&\cdots&1&1&1&\cdots&1\\\\[2.84544pt]
0&\cdots&0&\smash{\underbrace{\textstyle\frac{1}{3}}_{k\text{-th
entry}}}&0&\cdots&0\end{array}\right)\right)$ (121)
$\displaystyle\geq\Phi\left(\frac{3}{2}\;\cdots\;\frac{3}{2}\right)\Phi\left(1\;\cdots\;1\;\smash{\underbrace{\textstyle\frac{4}{3}}_{k\text{-th
entry}}}\;1\;\cdots\;1\right)=\left(\frac{4}{3}\right)^{\beta_{k}}>1,$

which leads to a contradiction. We conclude that no non-degenerate monotone
homomorphism $S^{d}\to\mathbb{T}\mathbb{R}_{+}$ exists.

Finally, consider the case $\mathbb{K}=\mathbb{T}\mathbb{R}_{+}^{\rm op}$. Let
$P\in\mathcal{V}_{n}^{d}$, $P\neq 0$. $P$ has at least one row not containing
any $0$. Assume WLOG it is the first row. Then

(122) $P\preceq\left(\begin{array}[]{ccc}p_{1}^{(1)}/2&\cdots&p_{1}^{(d)}/2\\\
p_{1}^{(1)}/2&\cdots&p_{1}^{(d)}/2\\\ p_{2}^{(1)}&\cdots&p_{2}^{(d)}\\\
\vdots&\vdots&\vdots\\\ p_{n}^{(1)}&\cdots&p_{n}^{(d)}\end{array}\right),$

hence

(123)
$\Phi(P)\geq\max\left\\{\Phi\left(p_{1}^{(1)}/2\;\cdots\;p_{1}^{(d)}/2\right),\Phi\left(\begin{array}[]{ccc}p_{1}^{(1)}/2&\cdots&p_{1}^{(d)}/2\\\
p_{2}^{(1)}&\cdots&p_{2}^{(d)}\\\ \vdots&\vdots&\vdots\\\
p_{n}^{(1)}&\cdots&p_{n}^{(d)}\end{array}\right)\right\\}$

Assume all $\beta_{k}=0$. Then it follows from the above and (52) that
$\Phi(P)\geq 1$. Since also
$1=\Phi(\|p^{(1)}\|_{1}\;\cdots\;\|p^{(d)}\|_{1})\geq\Phi(P)$, we find that
$\Phi(P)=1$. Hence $\Phi$ is degenerate, which leads to a contradiction. Thus
there exists $k$ such that $\beta_{k}<0$. Then we can perform the same
calculations as in (111) but now with $\beta_{k}<0$ and all the inequalities
reversed. This leads to a contradiction. Hence there exists no non-degenerate
monotone homomorphism $S^{d}\to\mathbb{T}\mathbb{R}_{+}^{\rm op}$. ∎

###  3.3. Monotone derivations

In this section, we identify the monotone derivations of the degenerate
monotone homomorphisms on $S^{d}$, up to _interchangeability_ : if the
difference between two $\Phi$-derivations factors through $S^{d}/\sim$, then
they are called _interchangeable_ and we only need to consider one of these
derivations in the Vergleichsstellensatz (see Definition 8.1 and the
subsequent discussion in [8]).

Recall that the degenerate monotone homomorphisms are exactly the $d$
$1$-norms of the columns $P\mapsto\|p^{(k)}\|_{1}$ for every $k\in[d]$. It
will turn out that up to interchangeability, the only monotone derivation
$\Delta$ is $\Delta(P)=0$ for all $P\in S^{d}$.

######  Proposition 6.

There is a unique monotone derivation $\Delta$, up to interchangeability, for
any degenerate monotone homomorphism $S^{d}\rightarrow\mathbb{R}_{+}$, and
satisfies $\Delta(P)=0$ for all $P\in S^{d}$.

Before proving this Proposition, we will use interchangeability to show that
we only need to consider a certain type of derivations. This result also
applies to the derivations of the semirings studied in [7] and, thus,
simplifies their definition. In [7], it was shown that the derivations
$\Delta^{(k)}$ had $\Delta$ the vanishing property $\Delta(x,\ldots,x)=0$ only
for $x\in\mathbb{Q}_{+}$.

######  Lemma 7.

Up to interchangeability, we may assume that any monotone derivation $\Delta$
of a degenerate monotone homomorphism satisfies

(124) $\Delta(x\,\cdots\,x)=0,$

for any $x\geq 0$.

###### Proof.

Let $\Delta$ be a monotone derivation of the degenerate monotone homomorphism
$\Phi^{(k)}:P\mapsto\|p^{(k)}\|_{1}$ for some $k\in[d]$. Define the function
$\delta:\mathbb{R}_{+}\to\mathbb{R}$ through
$\delta(x)=-\Delta(x\,\cdots\,x)$. This function is an additive derivation.
Let us prove this. For the additivity and the Leibniz property, consider
$x,y\in\mathbb{R}_{+}$. Note that

(125) $\left(\begin{array}[]{ccc}x&\cdots&x\\\
y&\cdots&y\end{array}\right)\succeq\big{(}x+y\,\cdots\,x+y\big{)}\succeq\left(\begin{array}[]{ccc}x&\cdots&x\\\
y&\cdots&y\end{array}\right).$

Thus,

(128) $\displaystyle\delta(x+y)$
$\displaystyle=-\Delta\left(\begin{array}[]{ccc}x&\cdots&x\\\
y&\cdots&y\end{array}\right)=-\Delta(x\,\cdots\,x)-\Delta(y\,\cdots\,y)=\delta(x)+\delta(y).$

Moreover,

(129) $\displaystyle\delta(xy)$
$\displaystyle=-\Delta\big{(}(x\,\cdots\,x)\boxtimes(y\,\cdots\,y)\big{)}=-\Delta(x\,\cdots\,x)y-x\Delta(y\,\cdots\,y)=\delta(x)y+x\delta(y).$

Let us define the additive monotone derivation $\Delta^{\prime}$ at
$\Phi^{(k)}$ as in 40, i.e.,

(130) $\Delta^{\prime}(P)=\Delta(P)+\delta\big{(}\|p^{(k)}\|_{1}\big{)}.$

Since $\Delta$ and $\Delta^{\prime}$ are interchangeable, we may replace
$\Delta$ with $\Delta^{\prime}$. We now have, for all $x\geq 0$,

(131)
$\Delta^{\prime}(x\,\cdots\,x)=\Delta(x\,\cdots\,x)+\delta(x)=\Delta(x\,\cdots\,x)-\Delta(x\,\cdots\,x)=0.$

∎

######  Remark 1.

According to Lemma 7, up to interchangeability, any monotone additive
derivation $\Delta:S^{d}\to\mathbb{R}$ has the vanishing property
$\Delta(p,\ldots,p)=0$ for any $p\in\mathbb{R}_{+}^{n}$, $n\in\mathbb{N}$.
Indeed, denoting $p=(p_{1},\ldots,p_{n})$, we have

(132) $\Delta(p,\ldots,p)=\sum_{i=1}^{n}\Delta(p_{i}\,\cdots\,p_{i})=0.$

This same result also applies to the results of [7] where the assumption that
$\|p\|_{1}\in\mathbb{Q}_{+}$ was made to guarantee this vanishing property.

Recall that the degenerate monotone homomorphisms are all $\Phi^{(k)}$ for
$k\in[d]$. Let $\Delta:S^{d}\to\mathbb{\mathbb{R}}$ be a monotone
$\Phi^{(k)}$-derivation for some $k\in[d]$. For any $B\subseteq[d]$ we write

(133) $\Delta[B]:=\Delta\left(\begin{array}[]{ccc}1&\cdots&1\\\
&B&\end{array}\right).$

The following Lemma will be used in the proof op Proposition 6.

######  Lemma 8.

Let $B\subseteq[d]$ and $\Delta:S^{d}\to\mathbb{\mathbb{R}}$ be a monotone
$\Phi^{(k)}$-derivation for some $k\in[d]$. Then $\Delta[B]=0$.

###### Proof.

Recall the equality of matrices given in (57). Using the Leibniz rule and
additivity of $\Delta$, and Lemma 7, we find

(134) $2\Phi^{(k)}[B]\Delta[B]=3\Delta[B],$

where $\Phi^{(k)}[B]=2$, respectively $1$, depending on whether $k\in B$,
respectively $k\notin B$. In both cases, the only solution is $\Delta[B]=0$. ∎

We now prove Proposition 6.

###### Proof of Proposition 6.

Fix $k\in[d]$ and assume $\Delta:S^{d}\to\mathbb{R}$ is a monotone
$\Phi^{(k)}$-derivation. For $\ell=1,\ldots,d$ define

(135)
$C_{\ell}:=\left(\begin{array}[]{ccccccc}1&\cdots&1&1&1&\cdots&1\\\\[2.84544pt]
0&\cdots&0&\smash{\underbrace{1}_{\ell\text{-th
entry}}}&0&\cdots&0\end{array}\right).\vspace{0.5cm}$

According to Lemma 8, $\Delta(C_{\ell})=0$ for $\ell=1,\ldots,d$. Let us
consider $P=\big{(}p^{(1)},\ldots,p^{(d)}\big{)}\in\mathcal{V}^{d}$ with
$p^{(\ell)}=\big{(}p^{(\ell)}_{1},\ldots,p^{(\ell)}_{n}\big{)}$. Define the
matrix

(136)
$P^{\prime}:=\mathop{\vphantom{\sum}\mathchoice{\vbox{\hbox{\leavevmode\resizebox{9.00005pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{10.00012pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{7.00009pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{5.00006pt}{}{$\boxplus$}}}}}\slimits@_{i=1}^{n}\mathop{\vphantom{\sum}\mathchoice{\vbox{\hbox{\leavevmode\resizebox{9.00005pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{10.00012pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{7.00009pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{5.00006pt}{}{$\boxplus$}}}}}\slimits@_{\ell=1}^{d}\big{(}p^{(\ell)}_{i}\,\cdots\,p^{(\ell)}_{i}\big{)}\boxtimes
C_{\ell}.$

One easily sees that

(137) $P^{\prime}\succeq
P^{\prime\prime}=:P\boxplus\mathop{\vphantom{\sum}\mathchoice{\vbox{\hbox{\leavevmode\resizebox{9.00005pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{10.00012pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{7.00009pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{5.00006pt}{}{$\boxplus$}}}}}\slimits@_{i=1}^{n}\mathop{\vphantom{\sum}\mathchoice{\vbox{\hbox{\leavevmode\resizebox{9.00005pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{10.00012pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{7.00009pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{5.00006pt}{}{$\boxplus$}}}}}\slimits@_{\ell=1}^{d}\big{(}p^{(\ell)}_{i}\,\cdots\,p^{(\ell)}_{i}\big{)}.$

Since $\Delta(x\,\cdots\,x)=0$ for all $x\geq 0$, we notice that
$\Delta(P^{\prime\prime})=\Delta(P)$ and, hence

(138) $\displaystyle\Delta(P)$
$\displaystyle=\Delta(P^{\prime\prime})\leq\Delta(P^{\prime})=\sum_{i=1}^{n}\sum_{\ell=1}^{d}\Delta\left(\big{(}p^{(\ell)}_{i}\,\cdots\,p^{(\ell)}_{i}\big{)}\boxtimes
C_{\ell}\right)$ (139)
$\displaystyle=\sum_{i=1}^{n}\sum_{\ell=1}^{d}\Big{(}\underbrace{\Delta\big{(}p^{(\ell)}_{i}\,\cdots\,p^{(\ell)}_{i}\big{)}}_{=0}\Phi^{(k)}(C_{\ell})+\Phi^{(k)}\big{(}p^{(\ell)}_{i}\,\cdots\,p^{(\ell)}_{i}\big{)}\underbrace{\Delta(C_{\ell})}_{=0}\Big{)}=0.$

Thus, $\Delta$ is nonpositive.

We finish the proof by showing that $\Delta$ is also nonnegative. Define
$M:=\max_{1\leq\ell\leq d}\|p^{(\ell)}\|_{1}$,
$m_{\ell}:=M-\|p^{(\ell)}\|_{1}$ for $\ell=1,\ldots,d$, and
$m:=m_{1}+\cdots+m_{d}$. Consider

(140)
$\tilde{P}:=P\boxplus\mathop{\vphantom{\sum}\mathchoice{\vbox{\hbox{\leavevmode\resizebox{9.00005pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{10.00012pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{7.00009pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{5.00006pt}{}{$\boxplus$}}}}}\slimits@_{\ell=1}^{d}\big{(}m_{\ell}\,\cdots\,m_{\ell}\big{)}\boxtimes
C_{\ell}$

which has columns that have the same $1$-norm $M+m$ as one easily verifies. By
monotonicity, we find

(141) $\displaystyle 0$
$\displaystyle=\Delta(M+m\,\cdots\,M+m)\leq\Delta(\tilde{P})=\Delta(P)+\sum_{\ell=1}^{d}\underbrace{\Delta\Big{(}\big{(}m_{\ell}\,\cdots\,m_{\ell}\big{)}\boxtimes
C_{\ell}\Big{)}}_{=0}=\Delta(P),$

where the terms in the sum vanish according to the same calculation that was
done in the first half of this proof. ∎

\begin{overpic}[scale={0.43},unit=1mm]{NoRestrictions.png}
\put(60.0,30.0){\Huge $A_{+}$ } \put(32.0,11.0){\Large $e_{1}$ }
\put(65.0,65.0){\Large $e_{3}$ } \put(95.0,13.0){\Large $e_{2}$ }
\put(75.0,47.0){\Large
${\color[rgb]{0.0390625,0.57421875,0.13671875}\definecolor[named]{pgfstrokecolor}{rgb}{0.0390625,0.57421875,0.13671875}\Phi_{\underline{\alpha},\\{1,2,3\\}}}$
} \put(23.0,46.0){
${\color[rgb]{0.0390625,0.57421875,0.13671875}\definecolor[named]{pgfstrokecolor}{rgb}{0.0390625,0.57421875,0.13671875}\Phi_{(\alpha,0,1-\alpha),\\{1,2,3\\}}}$
} \put(12.0,13.0){
${\color[rgb]{0.0390625,0.57421875,0.13671875}\definecolor[named]{pgfstrokecolor}{rgb}{0.0390625,0.57421875,0.13671875}\Phi_{e_{1},\\{1,2,3\\}}}$
} \put(20.0,42.0){
${\color[rgb]{0.0078125,0.390625,0.078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.0078125,0.390625,0.078125}\Phi_{(\alpha,0,1-\alpha),\\{1,3\\}}}$
} \put(17.0,18.0){
${\color[rgb]{0.0078125,0.390625,0.078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.0078125,0.390625,0.078125}\Phi_{e_{1},\\{1,3\\}}}$
} \put(27.0,7.0){
${\color[rgb]{0.0078125,0.390625,0.078125}\definecolor[named]{pgfstrokecolor}{rgb}{0.0078125,0.390625,0.078125}\Phi_{e_{1},\\{1,2\\}}}$
} \put(0.0,6.0){ $\Phi_{e_{1},\\{1\\}}=\Phi^{(1)}$ } \end{overpic} Figure 3.
Illustration of the monotone homomorphisms of $S^{3}$, where the figure
concentrates on the line segment from $e_{1}$ to $e_{3}$ and the vertex
$e_{1}$: The monotone homomorphisms associated with $\underline{\alpha}$ in
the interior of $A_{+}$ are $\Phi_{\underline{\alpha},\\{1,2,3\\}}$, depicted
in lighter green. The smaller facets of $A_{+}$, i.e., the three line segments
and the singletons $\\{e_{1}\\}$, $\\{e_{2}\\}$, and $\\{e_{3}\\}$ inherit
similar homomorphisms still with $C=\\{1,2,3\\}$, also depicted in lighter
green. These homomorphisms can be seen as pointwise limits from the interior
of $A_{+}$, when $\alpha_{2}\to 0$. Additionally, the extreme point $e_{1}$
inherits the homomorphisms $\Phi_{e_{1},\\{1,3\\}}$ and
$\Phi_{e_{1},\\{1,2\\}}$, depicted in darker green, as limits from the two
line segments it connects, and similarly for $e_{2}$ and $e_{3}$. We also have
the homomorphisms $\Phi_{(\alpha,0,1-\alpha),\\{1,3\\}}$, $\alpha\in[0,1]$, on
the line segment between $e_{1}$ and $e_{3}$, depicted in darker green, and
similarly for the other two line segments. At $e_{1}$, the degenerate
homomorphism with $C=\\{1\\}$, i.e., $\Phi^{(1)}$, is also present, depicted
in black, and similarly for $e_{2}$ and $e_{3}$. There are no non-zero
derivations at the three extreme points.

###  3.4. Power universal elements

We determine which matrices in $\mathcal{V}^{d}$ with columns that sum to $1$
are power universal, which is a requirement for the input matrix in the
Vergleichsstellensatz for the case of majorization in large samples.

######  Proposition 9.

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

  1. (i)

$U$ is power universal;

  2. (ii)

There exists $m\in\mathbb{N}$ such that for all $k\in[d]$, $U^{\boxtimes m}$
has a row $(0\,\cdots\,0\underbrace{x_{k}}_{k\text{-th entry}}0\,\cdots\,0)$
for some $x_{k}>0$;

  3. (iii)

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

  4. (iv)

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

###### Proof.

We show the implications (iii) $\Rightarrow$ (ii) $\Rightarrow$ (i)
$\Rightarrow$ (iv) $\Rightarrow$ (iii).

(iii) $\Rightarrow$ (ii): Let $k\in[d]$. The matrix $U^{\boxtimes(d-1)}$
contains a row which is the element-wise product of the $d-1$ rows
$(u^{(1)}_{i_{k^{\prime}}}\;\cdots\;u^{(d)}_{i_{k^{\prime}}})$ with
$u^{(k)}_{i_{k^{\prime}}}>0,u^{(k^{\prime})}_{i_{k^{\prime}}}=0$ for
$k^{\prime}\in[d]\setminus\\{k\\}$, which exist according to (iii). This row
in $U^{\boxtimes(d-1)}$ is clearly of the form
$(0\,\cdots\,0\underbrace{x_{k}}_{k\text{-th entry}}0\,\cdots\,0)$ for some
$x_{k}>0$. We conclude that (ii) holds for $m=d-1$.

(ii) $\Rightarrow$ (i): Assume $U\in\mathcal{V}_{n}^{d}$ satisfies (ii), and
let $P,Q\in\mathcal{V}_{n}^{d}$, $Q\preceq P$. We may assume WLOG that $P,Q$
have columns of unit $1$-norm. By (ii) there exists $m_{0}\in\mathbb{N}$ such
that $\tilde{U}:=U^{\boxtimes m_{0}}$ has a row
$(0\,\cdots\,0\underbrace{x_{k}}_{k\text{-th entry}}0\,\cdots\,0)$ with
$x_{k}>0$ for every $k\in[d]$. We then have

(142)
$\tilde{U}=\left(\begin{array}[]{ccc}\tilde{u}^{(1)}_{0}&\cdots&\tilde{u}^{(d)}_{0}\\\
1-\|\tilde{u}^{(1)}_{0}\|_{1}&\cdots&0\\\ 0&\ddots&0\\\
0&\cdots&1-\|\tilde{u}^{(d)}_{0}\|_{1}\end{array}\right)\succeq\left(\begin{array}[]{ccc}\|\tilde{u}^{(1)}_{0}\|_{1}&\cdots&\|\tilde{u}^{(d)}_{0}\|_{1}\\\
1-\|\tilde{u}^{(1)}_{0}\|_{1}&\cdots&0\\\ 0&\ddots&0\\\
0&\cdots&1-\|\tilde{u}^{(d)}_{0}\|_{1}\end{array}\right),$

for some vectors $\tilde{u}_{0}^{(k)}\in\mathbb{R}_{+}^{l}$, $k\in[d]$, where
$l\in\mathbb{N}$, and such that $1-\|\tilde{u}_{0}^{(k)}\|_{1}>0$ for all
$k\in[d]$. Then for any $m\geq 1$

(147) $\displaystyle\tilde{U}^{\boxtimes m}$
$\displaystyle\succeq\left(\begin{array}[]{ccc}\|\tilde{u}^{(1)}_{0}\|_{1}&\cdots&\|\tilde{u}^{(d)}_{0}\|_{1}\\\
1-\|\tilde{u}^{(1)}_{0}\|_{1}&\cdots&0\\\ 0&\ddots&0\\\
0&\cdots&1-\|\tilde{u}^{(d)}_{0}\|_{1}\end{array}\right)^{\boxtimes m}$ (152)
$\displaystyle\succeq\left(\begin{array}[]{ccc}\|\tilde{u}^{(1)}_{0}\|_{1}^{m}&\cdots&\|\tilde{u}^{(d)}_{0}\|_{1}^{m}\\\
1-\|\tilde{u}^{(1)}_{0}\|_{1}^{m}&\cdots&0\\\ 0&\ddots&0\\\
0&\cdots&1-\|\tilde{u}^{(d)}_{0}\|_{1}^{m}\end{array}\right)=:\tilde{U}_{m}.$

Denote the stochastic matrix that maps $\tilde{U}^{\boxtimes m}$ to
$\tilde{U}_{m}$ as $T_{m}$. Write

(153) $P=\left(\begin{array}[]{ccc}p_{0}^{(1)}&\cdots&p_{0}^{(d)}\\\
p_{1}^{(1)}&\cdots&p_{1}^{(d)}\end{array}\right),$

where for $k\in[d]$ the vectors $p_{0}^{(k)}\in\mathbb{R}_{>0}^{n_{0}}$ form
the part of common support of $P$ and $p_{1}^{(k)}\in\mathbb{R}_{+}^{n_{1}}$,
and $n_{0}+n_{1}=n$. Also, define
$v_{0}:=(1/n_{0},\ldots,1/n_{0})\in\mathbb{R}_{+}^{n_{0}}$. Next, consider

(154)
$S_{m}:=\left(\begin{array}[]{cccc}v_{0}&\frac{p_{0}^{(1)}}{1-\|\tilde{u}_{0}^{(1)}\|_{1}^{m}}-\frac{\|\tilde{u}_{0}^{(1)}\|_{1}^{m}}{1-\|\tilde{u}_{0}^{(1)}\|_{1}^{m}}v_{0}&\cdots&\frac{p_{0}^{(d)}}{1-\|\tilde{u}_{0}^{(d)}\|_{1}^{m}}-\frac{\|\tilde{u}_{0}^{(d)}\|_{1}^{m}}{1-\|\tilde{u}_{0}^{(d)}\|_{1}^{m}}v_{0}\\\
0&\frac{1-\|p_{0}^{(1)}\|_{1}}{1-\|\tilde{u}_{0}^{(1)}\|_{1}^{m}}&\cdots&0\\\
\vdots&0&\ddots&0\\\
0&0&\cdots&\frac{1-\|p_{0}^{(d)}\|_{1}}{1-\|\tilde{u}_{0}^{(d)}\|_{1}^{m}}\end{array}\right),$

which has columns that sum to $1$ and non-negative entries for sufficiently
large $m$ because $\|\tilde{u}_{0}^{(k)}\|_{1}<1$ and $p_{0}^{(k)}$ has
positive entries for all $k\in[d]$. Then

(159) $\displaystyle P$
$\displaystyle\preceq\left(\begin{array}[]{ccc}p_{0}^{(1)}&\cdots&p_{0}^{(d)}\\\
1-\|p_{0}^{(1)}\|_{1}&\cdots&0\\\ 0&\ddots&0\\\
0&\cdots&1-\|p_{0}^{(d)}\|_{1}\end{array}\right)=S_{m}\tilde{U}_{m}=S_{m}T_{m}\tilde{U}^{\boxtimes
m}$ (160) $\displaystyle\preceq\tilde{U}^{\boxtimes m}=(1\,\cdots\,1)\boxtimes
U^{\boxtimes(m_{0}m)}\preceq Q\boxtimes U^{\boxtimes(m_{0}m)},$

which is what we aimed to prove.

(i) $\Rightarrow$ (iv): Let $\Phi_{\underline{\alpha},C}\in\mathcal{H}^{\rm
n.d.}(S^{d},\mathbb{R}_{+}^{\rm op})$, and $P,Q\in\mathcal{V}^{d}$ such that
$Q\preceq P$. Since $U$ is power universal, there exists $m\in\mathbb{N}$ such
that $P\preceq Q\boxtimes U^{\boxtimes m}$. Using monotonicity and
multiplicativity:

(161)
$\Phi_{\underline{\alpha},C}(P)\geq\Phi_{\underline{\alpha},C}(Q\boxtimes
U^{\boxtimes
m})=\Phi_{\underline{\alpha},C}(Q)\Phi_{\underline{\alpha},C}(U)^{m}\geq\Phi_{\underline{\alpha},C}(P)\Phi_{\underline{\alpha},C}(U)^{m}.$

If $\Phi_{\underline{\alpha},C}(U)=1$, then
$\Phi_{\underline{\alpha},C}(P)=\Phi_{\underline{\alpha},C}(Q)$. This implies
that $\Phi_{\underline{\alpha},C}$ is degenerate, leading to a contradiction.
Therefore, $\Phi_{\underline{\alpha},C}(U)<1$.

(iv) $\Rightarrow$ (iii): Let $k,k^{\prime}\in[d]$, $k\neq k^{\prime}$. Since
$\Phi_{e_{k},\\{k,k^{\prime}\\}}(U)<1$ and the columns in $U$ sum to $1$,
$I(U,\\{k,k^{\prime}\\})$ cannot contain all rows $i$ in $U$ where
$u^{(k)}_{i}>0$. Hence there exists a row $i$ such that $u^{(k)}_{i}>0$, but
$u^{(k^{\prime})}_{i}=0$, proving the claim. ∎

######  Remark 2.

Note that it follows from the proof of (iv) $\Rightarrow$ (iii) above that we
only have to require that monotones from a certain subset of $\mathcal{H}^{\rm
n.d.}(S^{d},\mathbb{R}_{+}^{\rm op})$ are strictly less than $1$, namely all
those of the type $\Phi_{e_{k},\\{k,k^{\prime}\\}}$, where
$k,k^{\prime}\in[d]$, $k\neq k^{\prime}$.

###  3.5. Results: applying the Vergleichsstellensatz

In the previous sections we have characterized all monotone homomorphisms,
their monotone derivations, and the power universal elements in the matrix
majorization semiring $S^{d}$. Now, we will apply the Vergleichsstellensatz in
the form of Theorem 1 to $S^{d}$ to obtain results on the asymptotic and
catalytic majorization of tuples of probability distributions. We obtain
sufficient conditions for exact majorization in large samples and
catalytically in Theorem 10 below and further derive if and only conditions
for majorization in large samples and catalytically where the majorization
only happens approximately with asymptotically vanishing error in Theorem 11.

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

(162)
$\Phi_{\underline{\alpha},C}(P)<\Phi_{\underline{\alpha},C}(Q)\quad\quad\forall\;\Phi_{\underline{\alpha},C}\in\mathcal{H}^{\rm
n.d.}(S^{d},\mathbb{R}_{+}^{\rm op})$

These homomorphisms $\Phi_{\underline{\alpha},C}$ are defined in (68) and if
we adopt the convention $0^{0}=1$, we can rewrite these more conveniently as
follows:

(163) $\Phi_{\underline{\alpha},C}(P)=\sum_{i\in
I(P,C)}\big{(}p^{(1)}_{i}\big{)}^{\alpha_{1}}\cdots\big{(}p^{(d)}_{i}\big{)}^{\alpha_{d}},$

where $\underline{\alpha}\in A_{+}$ (defined in (4)), $C\subseteq[d]$ such
that ${\rm supp}\,\underline{\alpha}\subseteq C$, and the sum runs only over
the rows in $I(P,C)$ (defined in (69)). Furthermore, we exclude the degenerate
homomorphisms $\Phi^{(k)}(P)=\|p^{(k)}\|_{1}$, which equals the sum of the
entries in column $k$, for $k\in[d]$.

We note that if $P,Q\in\mathcal{V}^{d}$ have columns that sum to $1$ and
satisfy (162), then $P$ is automatically power universal. To see this, observe
that for any $\Phi_{\underline{\alpha},C}\in\mathcal{H}^{\rm
n.d.}(S^{d},\mathbb{R}_{+}^{\rm op})$ we have
$\Phi_{\underline{\alpha},C}(P)<\Phi_{\underline{\alpha},C}(Q)\leq 1$, hence
(iv) in Proposition 9 holds for $U=P$, which means $P$ is power universal.

Putting everything together, Theorem 1 yields the following result.

######  Theorem 10.

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 $\bigcap_{k=1}^{d}{\rm
supp}\,q^{(k)}\neq\emptyset$. If the inequalities in (162) 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$, such that

(164) $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:

(165)
$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

(166) $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 in (162) hold
non-strictly.

Just as in the case with equal support in [7], we have an asymptotic version
of majorization. Note that now, as opposed to the exact version of
majorization in the Theorem above, we have to require the input $P$ to be
power universal, which is also necessary for the approximate version in the
equal-support case in [7].

######  Theorem 11.

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 $\bigcap_{k=1}^{d}{\rm
supp}\,q^{(k)}\neq\emptyset$, and $P$ is power universal. The following are
equivalent:

  1. (i)

For all $\Phi_{\underline{\alpha},C}\in\mathcal{H}^{\rm
n.d.}(S^{d},\mathbb{R}_{+}^{\rm op})$ that are continuous (see (71)) it holds
that

(167) $\Phi_{\underline{\alpha},C}(P)\leq\Phi_{\underline{\alpha},C}(Q).$

  2. (ii)

For every $\varepsilon>0$ there exist two tuples of probability vectors
$(q_{\varepsilon}^{(1)},\ldots,q_{\varepsilon}^{(d)})$ and
$(r_{\varepsilon}^{(1)},\ldots,r_{\varepsilon}^{(d)})$, satisfying
$\bigcap_{k=1}^{d}{\rm supp}\,q_{\varepsilon}^{(k)}\neq\emptyset$ and
$\bigcap_{k=1}^{d}{\rm supp}\,r_{\varepsilon}^{(k)}\neq\emptyset$, and a
stochastic map $T_{\varepsilon}$ such that

(168) $\|q^{(k)}-q_{\varepsilon}^{(k)}\|_{1}\leq\varepsilon\quad\text{for
}k\in[d],$

and

(169) $T_{\varepsilon}(r_{\varepsilon}^{(k)}\otimes
p^{(k)})=r_{\varepsilon}^{(k)}\otimes q_{\varepsilon}^{(k)}\quad\text{for
}k\in[d].$

Also, we may choose, for $n$ sufficiently large

(170)
$r_{\varepsilon}^{(k)}=\frac{1}{n+1}\bigoplus_{\ell=0}^{n}\left(q_{\varepsilon}^{(k)}\right)^{\otimes\ell}\otimes\left(p^{(k)}\right)^{\otimes(n-\ell)}\quad\text{
for }k\in[d].$

  3. (iii)

For every $\varepsilon>0$ there exist a tuple of probability vectors
$(q_{\varepsilon}^{(1)},\ldots,q_{\varepsilon}^{(d)})$, satisfying
$\bigcap_{k=1}^{d}{\rm supp}\,q_{\varepsilon}^{(k)}\neq\emptyset$, such that

(171) $\|q^{(k)}-q_{\varepsilon}^{(k)}\|_{1}\leq\varepsilon\quad\text{for
}k\in[d],$

and for $n$ sufficiently large a stochastic map $T_{\varepsilon,n}$ such that

(172) $T_{\varepsilon,n}(p^{(k)})^{\otimes n}=(q_{\varepsilon}^{(k)})^{\otimes
n}\quad\text{for }k\in[d].$

###### Proof.

(i) $\Rightarrow$ (ii) and (iii): Fix any $k\in[d]$. Define $W:=(w,\ldots,w)$,
where $w:=(1/n,\ldots,1/n)\in\mathbb{R}^{n}$, and

(173)
$Q_{\varepsilon}:=\left(1-\frac{\varepsilon}{2}\right)Q+\frac{\varepsilon}{2}W,$

where $+$ means entry-wise addition of two matrices. Write
$Q_{\varepsilon}=(q_{\varepsilon}^{(1)},\ldots,q_{\varepsilon}^{(d)})$. Let
$\Phi_{\underline{\alpha},C}\in\mathcal{H}^{\rm
n.d.}(S^{d},\mathbb{R}_{+}^{\rm op})$ be continuous. Then

(174) $\displaystyle\Phi_{\underline{\alpha},C}$
$\displaystyle(Q_{\varepsilon})=\Phi_{\underline{\alpha},C}\left(\left(1-\frac{\varepsilon}{2}\right)Q+\frac{\varepsilon}{2}W\right)\geq\Phi_{\underline{\alpha},C}\left(\left(1-\frac{\varepsilon}{2}\right)Q\boxplus\frac{\varepsilon}{2}W\right)$
(175)
$\displaystyle=\left(1-\frac{\varepsilon}{2}\right)\Phi_{\underline{\alpha},C}(Q)+\frac{\varepsilon}{2}\Phi_{\underline{\alpha},C}(W)=\Phi_{\underline{\alpha},C}(Q)+\frac{\varepsilon}{2}[1-\Phi_{\underline{\alpha},C}(Q)]\geq\Phi_{\underline{\alpha},C}(Q)\geq\Phi_{\underline{\alpha},C}(P),$

where in the first inequality we used monotonicity, in the equality that
follows we used additivity and the fact that
$\Phi_{\underline{\alpha},C}(cA)=c\Phi_{\underline{\alpha},C}(A)$ for any
$c>0$ and $A\in\mathcal{V}^{d}$, in the next equality we used that
$\Phi_{\underline{\alpha},C}(W)=1$ since all the columns in $W$ are the same
and sum to $1$, in the penultimate inequality we used that
$\Phi_{\underline{\alpha},C}(Q)\leq 1$, and in the final inequality we used
the assumption in (i). If $\Phi_{\underline{\alpha},C}(Q)=1$, then the final
inequality is strict since $\Phi_{\underline{\alpha},C}(P)<1$ by Lemma 9. If
$\Phi_{\underline{\alpha},C}(Q)<1$, then the penultimate inequality is strict.
Thus, in both cases
$\Phi_{\underline{\alpha},C}(P)<\Phi_{\underline{\alpha},C}(Q_{\varepsilon})$.

Let $\Phi_{\underline{\alpha},C}\in\mathcal{H}^{\rm
n.d.}(S^{d},\mathbb{R}_{+}^{\rm op})$ be discontinuous. Since
$Q_{\varepsilon}$ has no $0$ entries,
$\Phi_{\underline{\alpha},C}(Q_{\varepsilon})=\Phi_{\underline{\alpha},D}(Q_{\varepsilon})$,
where $D\subseteq C$ consists of all $c\in C$ that satisfy $\alpha_{c}>0$. If
$\Phi_{\underline{\alpha},D}$ is one of the degenerate homomorphisms (i.e. the
$1$-norm of one of the columns), then

(176)
$\Phi_{\underline{\alpha},C}(P)<1=\Phi_{\underline{\alpha},D}(Q_{\varepsilon})=\Phi_{\underline{\alpha},C}(Q_{\varepsilon}),$

where the inequality follows from Lemma 9. If $\Phi_{\underline{\alpha},D}$ is
nondegenerate, then we find

(177)
$\Phi_{\underline{\alpha},C}(P)\leq\Phi_{\underline{\alpha},D}(P)<\Phi_{\underline{\alpha},D}(Q_{\varepsilon})=\Phi_{\underline{\alpha},C}(Q_{\varepsilon}),$

where the first inequality is due to the fact that
$\Phi_{\underline{\alpha},C}$ sums over all or a subset of the rows that
$\Phi_{\underline{\alpha},D}$ sums over, and the second inequality is due to
the fact that $\Phi_{\underline{\alpha},D}$ is continuous and nondegenerate.

We conclude that
$\Phi_{\underline{\alpha},C}(P)<\Phi_{\underline{\alpha},C}(Q_{\varepsilon})$
for all $\Phi_{\underline{\alpha},C}\in\mathcal{H}^{\rm
n.d.}(S^{d},\mathbb{R}_{+}^{\rm op})$, hence Theorem 10 yields (ii) and (iii).
Note that one easily sees that $\bigcap_{k=1}^{d}{\rm
supp}\,q_{\varepsilon}^{(k)}\neq\emptyset$ and the fact that
$\bigcap_{k=1}^{d}{\rm supp}\,r_{\varepsilon}^{(k)}\neq\emptyset$ in (ii)
follows from the possible choice of the $r_{\varepsilon}^{(k)}$ in (165).

(ii) or (iii) $\Rightarrow$ (i): The fact that $\bigcap_{k=1}^{d}{\rm
supp}\,q_{\varepsilon}^{(k)}\neq\emptyset$, respectively
$\bigcap_{k=1}^{d}{\rm supp}\,r_{\varepsilon}^{(k)}\neq\emptyset$, implies
that $(q_{\varepsilon}^{(1)},\ldots,q_{\varepsilon}^{(d)})\in S^{d}$,
respectively $(r_{\varepsilon}^{(1)},\ldots,r_{\varepsilon}^{(d)})\in S^{d}$.
Then, for any continuous $\Phi\in\mathcal{H}^{\rm
n.d.}(S^{d},\mathbb{R}_{+}^{\rm op})$ we find for any $\varepsilon>0$, using
monotonicity and multiplicativity, that $\Phi(P)\leq\Phi(Q_{\varepsilon})$,
where $Q_{\varepsilon}:=(q_{\varepsilon}^{(1)},\ldots,q_{\varepsilon}^{(d)})$.
For any $\varepsilon>0$, write $Q_{\varepsilon}=Q_{\varepsilon}^{0}\boxplus
Q_{\varepsilon}^{1}$, where $Q_{\varepsilon}^{0}$ consists of the first
$n_{Q}$ rows of $Q_{\varepsilon}$ and $n_{Q}$ is the number of rows in $Q$ (if
$Q_{\varepsilon}$ has less than $n_{Q}$ rows, then we add rows of zeros to
form $Q_{\varepsilon}^{0}$). Note that $\lim_{\varepsilon\rightarrow
0}Q_{\varepsilon}^{0}=Q$ and the sum of every column in $Q_{\varepsilon}^{1}$
is at most $\varepsilon$. Then

(178)
$\Phi(Q_{\varepsilon})+1=\Phi(Q_{\varepsilon}\boxplus(1\,\cdots\,1))=\Phi(Q_{\varepsilon}^{0})+\underbrace{\Phi(Q_{\varepsilon}^{1}\boxplus(1\,\cdots\,1))}_{\leq
1+\varepsilon},$

where in the inequality we used monotonicity and the fact that the rows of
$Q_{\varepsilon}^{1}\boxplus(1\,\cdots\,1)$ sum to at most $1+\varepsilon$.
Hence $\Phi(Q_{\varepsilon})\leq\Phi(Q_{\varepsilon}^{0})+\varepsilon$. This
implies that $\Phi(P)\leq\Phi(Q_{\varepsilon}^{0})+\varepsilon$. Taking the
limit $\varepsilon\rightarrow 0$ in this inequality, since $\Phi$ is a
continuous function when restricted to matrices with a fixed number of rows,
we deduce that $\Phi(P)\leq\Phi(Q_{\varepsilon})$, completing the proof.

∎

##  4\. One dominating column case

In this section we will consider tuples of probability vectors where the
support of one vector contains the support of all other vectors. Such tuples
have applications in quantum thermodynamics, as we will see later. Similarly
as for $S^{d}$, we will use the Vergleichsstellensatz given by Theorem 1 to
derive conditions for asymptotic and catalytic majorization.

We define the _dominating column matrix majorization semiring_ $S^{d}_{\rm
d.c.}$ as the subset of all (equivalence classes of) matrices in $S^{d}$ where
the support of the last column contains all others:

(179) $S^{d}_{\rm
d.c.}:=\left\\{\,\left[\left(p^{(1)},\ldots,p^{(d)}\right)\right]\in
S^{d}\;\middle|\;{\rm supp}\,p^{(k)}\subseteq{\rm supp}\,p^{(d)}\quad\forall
k\in[d-1]\,\right\\}$

The set of individual matrices (i.e., lifting the projection into equivalence
classes) generating $S^{d}_{\rm d.c.}$ is denoted by $\mathcal{V}^{d}_{\rm
d.c.}$. The subset of matrices in $\mathcal{V}^{d}_{\rm d.c.}$ with columns of
length $n\in\mathbb{N}$ is denoted by $(\mathcal{V}_{\rm d.c.})^{d}_{n}$. In
subsection 4.3, we identify the power universals of $S^{d}_{\rm d.c.}$ thus
showing that $S^{d}_{\rm d.c.}$ is of polynomial growth.

###  4.1. Monotone homomorphisms

Since $S^{d}_{\rm d.c.}$ is a subset of $S^{d}$, all monotone homomorphisms of
$S^{d}$, when restricted to $S^{d}_{\rm d.c.}$, are also monotone
homomorphisms of $S^{d}_{\rm d.c.}$. Thus, especially functions in
$\mathcal{H}^{\rm n.d.}(S^{d}_{\rm d.c.},\mathbb{R}_{+}^{\rm op})$, which is
defined in exactly the same way as in (70), are non-degenerate monotone
homomorphisms $S^{d}_{\rm d.c.}\to\mathbb{R}_{+}^{\rm op}$. Note that in this
case some homomorphisms that are different on $S^{d}$ coincide on $S^{d}_{\rm
d.c.}$, since column $d$ always has a non-zero entry and therefore
$\Phi_{\underline{\alpha},C}=\Phi_{\underline{\alpha},C\cup\\{d\\}}$ for any
$\underline{\alpha}\in A_{+}$ and ${\rm supp}\,\underline{\alpha}\subseteq
C\subseteq[d]$. This also means that the homomorphisms
$\Phi_{e_{k},\\{k,d\\}}$ for $k\in[d-1]$, which are nondegenerate on $S^{d}$,
are degenerate on $S^{d}_{\rm d.c.}$.

Let $\alpha>1$ and $c\in[d-1]$. Define
$\varphi_{\alpha,c}:\mathbb{R}_{+}\times\mathbb{R}_{>0}\to\mathbb{R}$ by

(180) $\varphi_{\alpha,c}(x_{c},x_{d}):=x_{c}^{\alpha}x_{d}^{1-\alpha}.$

It follows from the proof of Proposition 13 in [7] that $\varphi_{\alpha,c}$
is convex on $\mathbb{R}_{>0}^{2}$. Using the fact that $\alpha>0$ and the
continuity of $\varphi_{\alpha,c}$, we find that $\varphi_{\alpha,c}$ is
convex on its entire domain $\mathbb{R}_{+}\times\mathbb{R}_{>0}$. In the
following, we will abuse notation by writing $\varphi_{\alpha,c}(x)$ for $x$
in a higher dimensional space $\mathbb{R}^{d}$ instead of
$x\in\mathbb{R}_{+}\times\mathbb{R}_{>0}$, where it is understood that we
ignore the coordinates not equal to $c$ or $d$.

We now define the homomorphism $\Phi_{\alpha,c}:S^{d}\to\mathbb{R}_{+}$ (where
we assume WLOG that $p^{(d)}_{i}>0$ for all $i=1,\ldots,n$) by

(181)
$\Phi_{\alpha,c}(P):=\sum_{i=1}^{n}\varphi_{\alpha,c}\left(p_{i}^{(c)},p_{i}^{(d)}\right),\quad\quad
P=(p^{(1)},\ldots,p^{(d)})\in(\mathcal{V}_{\rm d.c.})_{n}^{d}.$

We denote all these homomorphisms $\Phi_{\alpha,c}$ that are non-degenerate by
$\mathcal{H}^{\rm n.d.}(S^{d}_{\rm d.c.},\mathbb{R}_{+})$, i.e.,

(182) $\mathcal{H}^{\rm n.d.}(S^{d}_{\rm
d.c.},\mathbb{R}_{+})=\big{\\{}\Phi_{\alpha,c}\,\big{|}\,1<\alpha<\infty,\
c=1,\ldots,d-1\big{\\}}.$

######  Proposition 12.

All homomorphisms in $\mathcal{H}^{\rm n.d.}(S^{d}_{\rm d.c.},\mathbb{R}_{+})$
are monotone.

###### Proof.

Let $\alpha>1$ and $c\in[d-1]$. Consider $P\in S^{d}_{\rm d.c.}$ with rows
$p_{1},\ldots,p_{n}\in\mathbb{R}_{+}^{d}$ and a stochastic $m\times n$-matrix
$T$, and write $Q:=TP\in S^{d}_{\rm d.c.}$ with rows
$q_{1},\ldots,q_{m}\in\mathbb{R}_{+}^{d}$, and
$T_{i}:=\sum_{j=1}^{n}T_{i,j}>0$. Using the convexity of $\varphi_{\alpha,c}$
and the fact that $\left(p_{j}\right)_{d}>0$ for all $j\in[n]$, we find

(183) $\displaystyle\Phi_{\alpha,c}(Q)$
$\displaystyle=\sum_{i=1}^{m}\varphi_{\alpha,c}(q_{i})=\sum_{i=1}^{m}\varphi_{\alpha,c}\left(\sum_{j=1}^{n}T_{i,j}p_{j}\right)=\sum_{i=1}^{m}T_{i}\varphi_{\alpha,c}\left(\sum_{j=1}^{n}\frac{T_{i,j}}{T_{i}}p_{j}\right)$
(184)
$\displaystyle\leq\sum_{i=1}^{m}T_{i}\sum_{j=1}^{n}\frac{T_{i,j}}{T_{i}}\varphi_{\alpha,c}(p_{j})=\sum_{j=1}^{n}\varphi_{\alpha,c}(p_{j})\underbrace{\sum_{i=1}^{n}T_{i,j}}_{=1}=\Phi_{\alpha,c}(P),$

which completes the proof.

∎

Let us also define, for all
$P=\big{(}p^{(1)},\ldots,p^{(d)}\big{)}\in\mathcal{V}^{d}_{\rm d.c.}$ with
$p^{(k)}=\big{(}p^{(k)}_{1},\ldots,p^{(k)}_{n}\big{)}$ for $k=1,\ldots,d$
(where we assume WLOG that $p^{(d)}_{i}>0$ for all $i=1,\ldots,n$) and
$c=1,\ldots,d-1$,

(185) $\Phi^{\mathbb{T}}_{c}(P):=\max_{1\leq i\leq
n}\frac{p^{(c)}_{i}}{p^{(d)}_{i}}.$

We also define

(186) $\mathcal{H}^{\rm n.d.}(S^{d}_{\rm
d.c.},\mathbb{T}\mathbb{R}_{+}):=\big{\\{}\Phi^{\mathbb{T}}_{\beta,c}:=\big{(}\Phi^{\mathbb{T}}_{c}(\cdot)\big{)}^{\beta}\,\big{|}\,\beta>0\big{\\}}.$

The functions in $\mathcal{H}^{\rm n.d.}(S^{d}_{\rm
d.c.},\mathbb{T}\mathbb{R}_{+}\\}$ are easily seen to be homomorphisms
$S^{d}_{\rm d.c.}\to\mathbb{T}\mathbb{R}_{+}$. The conditions for large-sample
or catalytic majorization of $P$ over $Q$ require in particular that
$\Phi^{\mathbb{T}}_{\beta,c}(P)>\Phi^{\mathbb{T}}_{\beta,c}(Q)$ for all
$\Phi^{\mathbb{T}}_{\beta,c}\in\mathcal{H}^{\rm n.d.}(S^{d}_{\rm
d.c.},\mathbb{T}\mathbb{R}_{+})$. Notice that this is equivalent to
$\Phi^{\mathbb{T}}_{c}(P)>\Phi^{\mathbb{T}}_{c}(Q)$ for all $c=1,\ldots,d-1$,
and that $\Phi^{\mathbb{T}}_{c}(P)=D_{\infty}\big{(}p^{(c)}\|p^{(d)}\big{)}$,
where $D_{\infty}$ is the max-divergence. We next show that the homomorphisms
in $\mathcal{H}^{\rm n.d.}(S^{d}_{\rm d.c.},\mathbb{T}\mathbb{R}_{+})$ are
monotone.

######  Proposition 13.

All homomorphisms in $\mathcal{H}^{\rm n.d.}(S^{d}_{\rm
d.c.},\mathbb{T}\mathbb{R}_{+})$ are monotone.

###### Proof.

Let $\beta>0$ and $c\in[d-1]$. Note that, denoting the rows of
$P\in\mathcal{V}^{d}_{\rm d.c.}$ by $p_{1},\ldots,p_{n}$, we have

(187) $\Phi^{\mathbb{T}}_{\beta,c}(P)=\sup_{1\leq j\leq
n}\varphi^{\mathbb{T}}_{\beta,c}(p_{j})$

where
$\varphi^{\mathbb{T}}_{\beta,c}(x_{1},\ldots,x_{d})=(x_{c}/x_{d})^{\beta}$ for
all $x_{1},\ldots,x_{d-1}\geq 0$ and $x_{d}>0$. The sublevel sets

(188)
$\left\\{(x_{1},\ldots,x_{d})\in\mathbb{R}_{+}^{d-1}\times\mathbb{R}_{>0}\,\middle|\,\left(\frac{x_{c}}{x_{d}}\right)^{\beta}\leq
a\right\\},\qquad a>0,$

are immediately seen to be convex, implying that
$\varphi^{\mathbb{T}}_{c,\beta}$ is quasi-convex, i.e., for all
$x,y\in\mathbb{R}_{+}^{d-1}\times\mathbb{R}_{>0}$ and $t\in(0,1)$,

(189)
$\varphi^{\mathbb{T}}_{c,\beta}\big{(}tx+(1-t)y\big{)}\leq\max\\{\varphi^{\mathbb{T}}_{c,\beta}(x),\varphi^{\mathbb{T}}_{c,\beta}(y)\\}.$

Let $P,Q\in\mathcal{V}^{d}_{\rm d.c.}$, $P$ with rows $p_{1},\ldots,p_{n}$ and
$Q$ with rows $q_{1},\ldots,q_{m}$. Assume that $P\succeq Q$ and let
$T=(T_{i,j})_{i,j}$ be a stochastic matrix such that $Q=TP$. We again denote
$T_{i}=\sum_{j=1}^{m}T_{i,j}$ which we may assume to be positive WLOG. Noting
that $\varphi^{\mathbb{T}}_{c,\beta}(cx)=\varphi^{\mathbb{T}}_{c,\beta}(x)$
for all $c>0$ and $x\in\mathbb{R}_{+}^{d-1}\times\mathbb{R}_{>0}$ and using
the quasi-convexity of $\varphi^{\mathbb{T}}_{c,\beta}$, we now have

(190) $\displaystyle\Phi^{\mathbb{T}}_{c,\beta}(Q)$ $\displaystyle=\max_{1\leq
i\leq m}\varphi^{\mathbb{T}}_{c,\beta}(q_{i})=\max_{1\leq i\leq
m}\varphi^{\mathbb{T}}_{c,\beta}\left(\sum_{j=1}^{n}T_{i,j}p_{j}\right)$ (191)
$\displaystyle=\max_{1\leq i\leq
m}\varphi^{\mathbb{T}}_{c,\beta}\left(\sum_{j=1}^{n}\frac{T_{i,j}}{T_{i}}p_{j}\right)\leq\max_{1\leq
i\leq m}\max_{1\leq j\leq n}\varphi^{\mathbb{T}}_{c,\beta}(p_{j})$ (192)
$\displaystyle=\max_{1\leq j\leq
n}\varphi^{\mathbb{T}}_{c,\beta}(p_{j})=\Phi^{\mathbb{T}}_{c,\beta}(P),$

proving the claim. ∎

######  Proposition 14.

The non-degenerate monotone homomorphisms in $S_{\rm d.c.}^{d}$ are exactly
those in the union of $\mathcal{H}^{\rm n.d.}(S^{d}_{\rm
d.c.},\mathbb{R}_{+})$, $\mathcal{H}^{\rm n.d.}(S^{d}_{\rm
d.c.},\mathbb{R}_{+}^{\rm op})$, and $\mathcal{H}^{\rm n.d.}(S^{d}_{\rm
d.c.},\mathbb{T}\mathbb{R}_{+})$. There are no nondegenerate monotone
homomorphisms $S^{d}_{\rm d.c.}\to\mathbb{T}\mathbb{R}_{+}^{\rm op}$.

###### Proof.

Throughout this proof, we consider a generic matrix
$P=\big{(}p^{(1)},\ldots,p^{(d)}\big{)}\in\mathcal{V}^{d}_{\rm d.c.}$ with
$p^{(k)}=\big{(}p^{(k)}_{1},\ldots,p^{(k)}_{n}\big{)}$ for $k=1,\ldots,d$. We
also denote the rows of $P$ by $p_{1},\ldots,p_{n}$.

We first consider the case of a monotone homomorphism $\Phi:S^{d}_{\rm
d.c.}\to\mathbb{K}\in\\{\mathbb{R}_{+},\mathbb{R}_{+}^{\rm op}\\}$. As in the
minimally restricted case $S^{d}$, also now $\Phi$ is associated with
$\underline{\alpha}\in A_{+}\cup A_{-}\setminus\\{e_{1},\ldots,e_{d}\\}$.
Lemmas 2 and 3 can be proven in exactly the same way (except now we only
consider $B\subsetneq[d]$ such that $d\in B$) and we will use these results in
the following. Hence, the notion of $\Phi$-nontrivial sets can again be
defined and $\Phi$ also has a character $C\subseteq[d]$. Through the same
proof as the one for Proposition 5, we know that

(193) $\Phi(P)=\sum_{i:\,C\subseteq{\rm supp}\,p_{i}}\prod_{k\in{\rm
supp}\,p_{i}}\big{(}p_{i}^{(k)}\big{)}^{\alpha_{k}}$

and that ${\rm supp}\,\underline{\alpha}=\\{k\,|\,\alpha_{k}\neq 0\\}\subseteq
C$. As for the case $\mathbb{K}=\mathbb{R}_{+}^{\rm op}$, we already know that
$\underline{\alpha}\in A_{+}$, so this case is dealt with and the set of
nondegenerate monotone homomorphisms coincides with $\mathcal{H}^{\rm
n.d.}(S^{d}_{\rm d.c.},\mathbb{R}_{+}^{\rm op})$. Thus we may concentrate on
the case $\mathbb{K}=\mathbb{R}_{+}$.

Assume that $\mathbb{K}=\mathbb{R}_{+}$. From the results of [7], we know that
$\underline{\alpha}\in A_{-}$. Let us first concentrate on the subset of those
$\underline{\alpha}=(\alpha_{1},\ldots,\alpha_{d})$ where $\alpha_{1}>1$ and
$\alpha_{2},\ldots,\alpha_{d}\leq 0$. We show that
$\alpha_{2}=\cdots=\alpha_{d-1}=0$. Consider

(194) $P_{t}:=\left(\begin{array}[]{ccccc}1/2&1-t&1/2&\cdots&1/2\\\
1/2&t&1/2&\cdots&1/2\end{array}\right),\qquad 0\leq t\leq\frac{1}{2}.$

Assume $\alpha_{2}\neq 0$. Then by Lemma 2(ii), $2\in C$. Whenever $0\leq
s\leq t\leq 1/2$, we have $P_{s}\succeq P_{t}$. Thus,
$\Phi(P_{\varepsilon})\leq\Phi(P_{0})$, i.e.,

(195)
$2^{-\alpha_{1}-\alpha_{3}-\cdots-\alpha_{d}}\left[(1-\varepsilon)^{\alpha_{2}}+\varepsilon^{\alpha_{2}}\right]\leq
2^{-\alpha_{1}-\alpha_{3}-\cdots-\alpha_{d}}$

for all $\varepsilon\in(0,1/2]$. However, the left-hand side above diverges as
$\varepsilon\to 0$, so $\alpha_{2}=0$. Similarly,
$\alpha_{3}=\cdots=\alpha_{d-1}=0$. The same logic does not work for
$\alpha_{d}$ because

(196) $\left(\begin{array}[]{cccc}1/2&\cdots&1/2&1\\\
1/2&\cdots&1/2&0\end{array}\right)\notin\mathcal{V}^{d}_{\rm d.c.}.$

We know that $1,d\in C$ and we now show that there are no other columns in
$C$. Assume that $C$ contains another column $k\in C\setminus\\{1,d\\}$. WLOG
we assume that $k=2$. Then, (195) holds with $\alpha_{1}+\alpha_{d}=1$ and
$\alpha_{3}=\cdots=\alpha_{d-1}=0$, yielding $1\leq 1/2$, a contradiction.
Hence $C=\\{1,d\\}$. Therefore, in the part of $A_{-}$ where $\alpha_{1}>1$,
the only non-degenerate homomorphisms $S^{d}_{\rm d.c.}\to\mathbb{R}_{+}$ are
all $\Phi_{\alpha,1}$ for $\alpha_{d}>1$. In the same way, we can deal with
the parts of $A_{-}$ where $\alpha_{c}>1$, $c=2,\ldots,d-1$ to show that the
only homomorphisms are all $\Phi_{\alpha,c}$, for $\alpha_{c}>1$,
$c=2,\ldots,d-1$.

It remains to be shown what the homomorphisms are for the part of $A_{-}$
where $\alpha_{d}>1$. Assume that $\alpha_{d}\geq 1$. Considering matrices

(197) $Q_{t}:=\left(\begin{array}[]{cccc}1-t&1/2&\cdots&1/2\\\
t&1/2&\cdots&1/2\end{array}\right),\qquad 0\leq t\leq\frac{1}{2},$

we find that $Q_{s}\succeq Q_{t}$ for $0\leq s\leq t\leq 1/2$, so
$\Phi(Q_{\varepsilon})\leq\Phi(Q_{0})$ for all $\varepsilon\in(0,1/2]$.
However, for $\alpha_{1}<0$, this again leads to a contradiction, so
$\alpha_{1}=0$. Similarly, $\alpha_{2}=\cdots=\alpha_{d-1}=0$. Thus,
$\alpha_{d}=1$ since $\alpha_{1}+\cdots+\alpha_{d}=1$. However, this case
falls under the set $\mathcal{H}^{\rm n.d.}(S^{d}_{\rm
d.c.},\mathbb{R}_{+}^{\rm op})$ which is already dealt with. Thus, the set of
nondegenerate monotone homomorphisms $S^{d}_{\rm d.c.}\to\mathbb{R}_{+}$ is
eaxctly $\mathcal{H}^{\rm n.d.}(S^{d}_{\rm d.c.},\mathbb{R}_{+})$.

We now consider the case $\mathbb{K}=\mathbb{T}\mathbb{R}_{+}$. From the
results of [7], we know that there is
$\underline{\beta}=(\beta_{1},\ldots,\beta_{d})\in B_{-}$ such that, when the
columns of $P$ have full support,

(198) $\Phi(P)=\max_{1\leq i\leq
n}\prod_{k=1}^{d}\big{(}p^{(k)}_{i}\big{)}^{\beta_{k}}.$

Proceeding similarly as above for $\mathbb{K}=\mathbb{R}_{+}$ and considering
the matrices $P_{t}$ and $Q_{t}$, one can again show that $\beta_{d}<0$ and
there is there is $c\in\\{1,\ldots,d-1\\}$ such that $\beta_{c}>0$ and
$\beta_{k}=0$ for $k\in[d-1]\setminus\\{c\\}$. Thus,
$\beta:=\beta_{c}=-\beta_{d}$.

Note that we may assume $P$ to have columns that sum up to $1$ because, in the
general case,

(199)
$\Phi(P)=\Phi\left(\|p^{(1)}\|_{1}\,\cdots\,\|p^{(d)}\|_{1}\right)\Phi(P^{\prime})=.$

Thus, we assume for now that $\|p^{(k)}\|=1$ for $k=1,\ldots,d$. By
monotonity, this implies that $\Phi(P)\geq 1$.

Let $p_{1},\ldots,p_{n}\in\mathbb{R}_{+}^{d}$ denote the rows of $P$. Let
$\delta>0$, which we will fix later. If a row $p_{i}$ contains a zero, but
$(p_{i})_{k}>0$, then we denote by $\widetilde{p_{i}}$ the row $p_{i}$ with
every $0$ replaced by a $1$. If a row $p_{i}$ contains a zero, and
$(p_{i})_{k}=0$ is one of them, then we denote by $\widetilde{p_{i}}^{\delta}$
the row $p_{i}$ with $\delta$ on position $k$ and every other $0$ replaced by
a $1$. Then, notice that

(200)
$P\boxplus\mathop{\vphantom{\sum}\mathchoice{\vbox{\hbox{\leavevmode\resizebox{9.00005pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{10.00012pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{7.00009pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{5.00006pt}{}{$\boxplus$}}}}}\slimits@_{k\in{\rm
supp}\,p_{i}\neq[d]}\widetilde{p_{i}}\boxplus\mathop{\vphantom{\sum}\mathchoice{\vbox{\hbox{\leavevmode\resizebox{9.00005pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{10.00012pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{7.00009pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{5.00006pt}{}{$\boxplus$}}}}}\slimits@_{k\notin{\rm
supp}\,p_{i}\neq[d]}\widetilde{p_{i}}^{\delta}=\mathop{\vphantom{\sum}\mathchoice{\vbox{\hbox{\leavevmode\resizebox{9.00005pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{10.00012pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{7.00009pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{5.00006pt}{}{$\boxplus$}}}}}\slimits@_{{\rm
supp}\,p_{i}=[d]}p_{i}\boxplus\mathop{\vphantom{\sum}\mathchoice{\vbox{\hbox{\leavevmode\resizebox{9.00005pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{10.00012pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{7.00009pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{5.00006pt}{}{$\boxplus$}}}}}\slimits@_{k\in{\rm
supp}\,p_{i}\neq[d]}\left(\begin{array}[]{c}\widetilde{p_{i}}\\\
p_{i}\end{array}\right)\boxplus\mathop{\vphantom{\sum}\mathchoice{\vbox{\hbox{\leavevmode\resizebox{9.00005pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{10.00012pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{7.00009pt}{}{$\boxplus$}}}}{\vbox{\hbox{\leavevmode\resizebox{5.00006pt}{}{$\boxplus$}}}}}\slimits@_{k\notin{\rm
supp}\,p_{i}\neq[d]}\left(\begin{array}[]{c}\widetilde{p_{i}}^{\delta}\\\
p_{i}\end{array}\right)$

Let us note that Lemma 2 still holds (with the obvious modification that $d\in
B$), especially $\Phi[B]=1$ whenever $d\in B\subseteq[d]$. Using this, we have
for the terms in the penultimate box-sum of the RHS (200) (i.e., when $i$ is
such that $k\in{\rm supp}\,p_{i}$ or, simply, $i\in{\rm supp}\,p^{(k)}$ and
${\rm supp}\,p_{i}\neq[d]$)

(201) $\Phi\big{(}\widetilde{p_{i}}\boxplus
p_{i}\big{)}=\Phi\left(\widetilde{p_{i}}\boxtimes\left(\begin{array}[]{ccc}1&\cdots&1\\\
&{\rm supp}\,p_{i}&\end{array}\right)\right)=\Phi(\widetilde{p_{i}})\Phi[{\rm
supp}\,p_{i}]=\Phi(\widetilde{p_{i}})=\left(\frac{p^{(k)}_{i}}{p^{(d)}_{i}}\right)^{\beta}.$

Similarly, for the terms in the final box-sum of the RHS of (200), we have

(202) $\Phi(\widetilde{p_{i}}^{\delta}\boxplus
p_{i})=\left(\frac{\delta}{p^{(d)}_{i}}\right)^{\beta}.$

Then (200) implies

(203) $\displaystyle\max$
$\displaystyle\left(\\{\Phi(P)\\}\cup\left\\{\left(\frac{p^{(k)}_{i}}{p^{(d)}_{i}}\right)^{\beta}\,\middle|\,i:\
k\in{\rm
supp}\,p_{i}\neq[d]\right\\}\cup\left\\{\left(\frac{\delta}{p^{(d)}_{i}}\right)^{\beta}\,\middle|\,i:\
k\notin{\rm supp}\,p_{i}\neq[d]\right\\}\right)$ (204)
$\displaystyle=\max\left(\left\\{\left(\frac{p^{(k)}_{i}}{p^{(d)}_{i}}\right)^{\beta}\,\middle|\,i:\
k\in{\rm
supp}\,p_{i}\right\\}\cup\left\\{\left(\frac{\delta}{p^{(d)}_{i}}\right)^{\beta}\,\middle|\,i:\
k\notin{\rm supp}\,p_{i}\right\\}\right).$

By making $\delta$ suitably small, we can make sure that both maximizations
above do not have an element of the form
$\delta^{\beta}\big{(}p^{(d)}_{i}\big{)}^{-\beta}$, for some row $i$, as
largest element.

For any $\varepsilon>0$, we have

(205) $P\boxplus\left(\begin{array}[]{ccc}\varepsilon&\cdots&\varepsilon\\\
\vdots&\ddots&\vdots\\\
\varepsilon&\cdots&\varepsilon\end{array}\right)\succeq
P+\left(\begin{array}[]{ccc}\varepsilon&\cdots&\varepsilon\\\
\vdots&\ddots&\vdots\\\ \varepsilon&\cdots&\varepsilon\end{array}\right),$

where $+$ denotes the entry-wise addition of matrices. This implies

(206)
$\Phi(P)\geq\max_{i\in[n]}\left(\frac{p^{(k)}_{i}+\varepsilon}{p^{(d)}_{i}+\varepsilon}\right)^{\beta},$

where we used the assumption that $\Phi(P)\geq 1$. By continuity of the
functions
$\varepsilon\mapsto\frac{p^{(k)}_{i}+\varepsilon}{p^{(d)}_{i}+\varepsilon}$,
$i\in[n]$, there exists $\varepsilon_{\rm max}$ such that the above maximum is
obtained at the same $i_{0}$ for all $\varepsilon\leq\varepsilon_{\rm max}$.
Then, taking $\varepsilon\rightarrow 0$ on both sides of the inequality above,
we deduce

(207)
$\Phi(P)\geq\left(\frac{p^{(k)}_{i_{0}}}{p^{(d)}_{i_{0}}}\right)^{\beta}\quad\forall\,i\in[n].$

This together with (203) yields

(208)
$\Phi(P)=\max_{i\in[n]}\left(\frac{p^{(k)}_{i}}{p^{(d)}_{i}}\right)^{\beta}.$

Finally, we consider the case $\mathbb{K}=\mathbb{T}\mathbb{R}_{+}^{\rm op}$.
Exactly as in the proof of Proposition 13 in [7] (see Equations (89), (90)),
we can show that $\Phi(P)$ only depends on the supports of the columns of $P$.
More precisely, if $P,Q\in S_{\rm d.c.}^{d}$ satisfy ${\rm supp}\,p^{(k)}={\rm
supp}\,q^{(k)}$ for all $k\in[d]$, then $\Phi(P)=\Phi(Q)$. It then follows
that for any $Q\in S_{\rm d.c.}^{d}$, we have
$Q\succeq(\|q^{(1)}\|_{1}\,\cdots\,\|q^{(d)}\|_{1})$, hence
$\Phi(Q)\leq\Phi(\|q^{(1)}\|_{1}\,\cdots\,\|q^{(d)}\|_{1})=\Phi(1\,\cdots\,1)=1$.
$P$ has at least one row not containing any $0$. Assume WLOG it is the first
row. Then $P$ majorizes and is majorized by

(209) $\left(\begin{array}[]{ccc}p_{1}^{(1)}/2&\cdots&p_{1}^{(d)}/2\\\
p_{1}^{(1)}/2&\cdots&p_{1}^{(d)}/2\\\ p_{2}^{(1)}&\cdots&p_{2}^{(d)}\\\
\vdots&\vdots&\vdots\\\ p_{n}^{(1)}&\cdots&p_{n}^{(d)}\end{array}\right),$

hence

(210)
$\Phi(P)=\max\left(\underbrace{\Phi\left(p_{1}^{(1)}/2\;\cdots\;p_{1}^{(d)}/2\right)}_{=1},\underbrace{\Phi\left(\begin{array}[]{ccc}p_{1}^{(1)}/2&\cdots&p_{1}^{(d)}/2\\\
p_{2}^{(1)}&\cdots&p_{2}^{(d)}\\\ \vdots&\vdots&\vdots\\\
p_{n}^{(1)}&\cdots&p_{n}^{(d)}\end{array}\right)}_{\leq 1}\right)=1.$

Therefore, there are no non-degenerate monotone homomorphisms for
$\mathbb{K}=\mathbb{T}\mathbb{R}_{+}^{\rm op}$. ∎

######  Remark 3.

Note that, compared to the minimally restricted semiring $S^{d}$, some
elements in $\mathcal{H}^{\rm n.d.}(S^{d}_{\rm d.c.},\mathbb{R}_{+}^{\rm op})$
coincide. Since the final column dominates all the other columns in all
matrices in $\mathcal{V}^{d}_{\rm d.c.}$, it immediately follows that,
whenever $\underline{\alpha}=(\alpha_{1},\ldots,\alpha_{d-1},0)\in A_{+}$ and
${\rm supp}\,\underline{\alpha}\subseteq C\subseteq[d]$, we have
$\Phi_{\underline{\alpha},C}=\Phi_{\underline{\alpha},C\cup\\{d\\}}$. See also
Figure 2 for a depiction of the monotone homomorphisms in the case $d=3$. The
figure also shows the derivations which we study in the next subsection.

###  4.2. Monotone derivations

Recall that the degenerate monotone homomorphisms are all $\Phi^{(k)}$ for
$k\in[d]$. Note that we only need to consider monotone derivations of these
homomorphisms up to interchangeability. Similarly as for the minimal
restrictions semiring, interchangeability allows us to show a result analogous
to Lemma 7, which we will use to characterize all monotone derivations, up to
interchangeability.

######  Proposition 15.

For each $k\in[d-1]$, any monotone derivation $\Delta$ of the degenerate
homomorphism $\Phi^{(k)}$, up to interchangeability, satisfies
$\Delta(P)=\gamma D_{1}(p^{(k)}\|p^{(d)})$ for all $P\in S^{d}_{\rm d.c}$, for
some $\gamma\geq 0$. The only monotone derivation $\Delta$ of the degenerate
homomorphism $\Phi^{(d)}$, up to interchangeability, vanishes, i.e.,
$\Delta(P)=0$ for all $P\in S^{d}_{\rm d.c}$.

Let $\Delta:S^{d}_{\rm d.c}\to\mathbb{\mathbb{R}}$ be a monotone
$\Phi^{(k)}$-derivation for some $k\in[d]$. For any $B\subsetneq[d]$, $d\in
B$, we write

(211) $\Delta[B]:=\Delta\left(\begin{array}[]{ccc}1&\cdots&1\\\
&B&\end{array}\right).$

Before going on to the proof, note that, whenever $B\subseteq[d]$ is such that
$d\in B$, then $\Delta[B]=0$. The proof is essentially the same as that of
Lemma 8 and will not be repeated here.

###### Proof of Proposition 15.

Let $\Delta:S_{\rm d.c.}^{d}\to\mathbb{\mathbb{R}}$ be a monotone
$\Phi^{(k)}$-derivation for some $k\in[d]$. For any $x\in\mathbb{R}_{+}^{d}$
with $d\in{\rm supp}\,x$ we find using the above note and the Leibniz rule for
$\Delta$,

(214) $\displaystyle\Delta\big{(}\tilde{x}^{T}\boxplus x^{T}\big{)}$
$\displaystyle=\Delta\left(\tilde{x}^{T}\boxtimes\left(\begin{array}[]{ccc}1&\cdots&1\\\
&{\rm supp}\,x&\end{array}\right)\right)$ (217)
$\displaystyle=\Delta(\tilde{x}^{T})\Phi^{(k)}[{\rm
supp}\,x]+\Phi^{(k)}(\tilde{x}^{T})\underbrace{\Delta[{\rm
supp}\,x]}_{=0}=\left\\{\begin{array}[]{ll}2\Delta(\tilde{x}^{T}),&k\in{\rm
supp}\,x,\\\ \Delta(\tilde{x}^{T})&{\rm otherwise.}\end{array}\right.$

Through a similar calculation as in (86), we now find that

(218) $\Delta(P)=\sum_{i\in{\rm supp}\,p^{(k)}}\Delta(\widetilde{p_{i}}),$

for any $P=(p^{(1)},\ldots,p^{(d)})\in S_{\rm d.c.}^{d}$ with rows $p_{i}$.
Again, $\widetilde{p_{i}}$ is the row $p_{i}$ where the vanishing entries are
replaced with 1. It follows that $\Delta(P)$ can be seen as $\Delta$ evaluated
on a matrix with non-vanishing entries, more specifically the matrix resulting
from taking only the rows in $P$ corresponding to ${\rm supp}\,p^{(k)}$ and
replacing all vanishing entries with $1$. Hence, we can use the results in the
proof of Proposition 14 in [7] for the equal-support case. Combining Equations
(111) and (117) in [7], we find

(219) $\Delta(P)=\sum_{\ell\neq k}\gamma_{\ell}\sum_{i\in{\rm
supp}\,p^{(k)}}p_{i}^{(k)}\log\left(\frac{p_{i}^{(k)}}{\widetilde{p_{i}^{(\ell)}}}\right),$

for some constants $\gamma_{\ell}\geq 0$, $\ell\in[d]\setminus\\{k\\}$.

Next, we show that $\gamma_{\ell}=0$ if $\ell\neq d$. Let
$\ell\in[d-1]\setminus\\{k\\}$. Consider the following matrices in $S_{\rm
d.c.}^{d}$

(222) $\displaystyle
P:=\left(\begin{array}[]{ccccccc}1/4&\cdots&1/4&1&1/4&\cdots&1/4\\\
3/4&\cdots&3/4&0&3/4&\cdots&3/4\end{array}\right),$ (225) $\displaystyle
Q:=\left(\begin{array}[]{ccccccc}1/2&\cdots&1/2&1&1/2&\cdots&1/2\\\
1/2&\cdots&1/2&0&1/2&\cdots&1/2\end{array}\right),$

where the column containing a $0$ is the $\ell$-th column. Notice that