# Criteria of positivity for linear maps constructed from permutation pairs

Haili Zhao, Jinchuan Hou  Faculty of Mathematics, Taiyuan University of
Technology, Taiyuan 030024, P. R. of China<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

In this paper, we show that a $D$-type map $\Phi_{D}:M_{n}\rightarrow M_{n}$
with $D=(n-2)I_{n}+P_{\pi_{1}}+P_{\pi_{2}}$ induced by a pair
$\\{\pi_{1},\pi_{2}\\}$ of permutations of $(1,2,\ldots,n)$ is positive if
$\\{\pi_{1},\pi_{2}\\}$ has property (C). The property (C) is characterized
for $\\{\pi_{1},\pi_{2}\\}$, and an easy criterion is given for the case that
$\pi_{1}=\pi^{p}$ and $\pi_{2}=\pi^{q}$, where $\pi$ is the permutation
defined by $\pi(i)=i+1$ mod $n$ and $1\leq p<q\leq n$.

2010 Mathematics Subject Classification. 15A86; 47B49; 47N50.

Key words and phrases. matrix algebras, positive linear maps, permutations,
inequalities

This work is partially supported by Natural Science Foundation of China
(11171249, 11271217)

##  1\. Introduction

Denote by $M_{m,n}$ the set of all $m\times n$ complex matrices, and write
$M_{n,n}=M_{n}$ and $M_{n}^{+}$ the set of all positive semi-definite matrices
in $M_{n}$. A linear map $L:M_{n}\rightarrow M_{n}$ is positive if
$L(M_{n}^{+})\subseteq M_{n}^{+}$. The study of positive maps have been the
central theme for many pure and applied topics. For example, see [3, 6, 9, 10,
11]. In particular, the study is pertinent in quantum information science
research; see [1, 2, 4, 7, 8, 12, 13]. So, the study of positive maps is
significant.

Suppose $\Phi_{D}:{M_{n}}\rightarrow{M_{n}}$ is a linear map of the form

$None$ $(a_{ij})\longmapsto{{\rm diag}(f_{1},f_{2},...,f_{n})-(a_{ij})}$

with $(f_{1},f_{2},...,f_{n})=(a_{11},a_{22},...,a_{nn})D$ for an $n\times n$
nonnegative matrix $D=(d_{ij})$ (i.e., $d_{ij}\geq 0$ for all $i,j$). The map
$\Phi_{D}$ of the form Eq.(1.1) defined by a nonnegative matrix $D$ is called
a $D$-type map. The question of when a $D$-type map is positive was studied
intensively by many authors and applied in quantum information theory to
detect entangled states and construct entanglement witnesses (ref., for
instance, [9, 14] and the references therein).

A very interesting class of $D$-type maps is the class of maps constructed
from permutations.

Assume that $\pi$ is a permutation of $(1,2,\ldots,n)$. Recall that the
permutation matrix $P_{\pi}=(p_{ij})$ of $\pi$ is a $n\times n$ matrix
determined by

$p_{ij}=\begin{cases}1\ \ \ \ \ \ {\rm if}\ \ i=\pi(j)\ ({\rm mod}\ n),\\\ 0\
\ \ \ \ \ {\rm if}\ \ i\neq{\pi(j)}\ ({\rm mod}\ n).\end{cases}$

Recall also that a subset $\\{i_{1},\dots,i_{l}\\}\subseteq\\{1,2,\ldots,n\\}$
is an $l$-cycle of the permutation $\pi$ if $\pi(i_{j})=i_{j+1}$ for
$j=1,\dots,l-1$ and $\pi(i_{l})=i_{1}$. Note that every permutation $\pi$ of
$(1,\dots,n)$ has a disjoint cycle decomposition
$\pi=(\pi_{1})(\pi_{2})\cdots(\pi_{r})$, that is, there exists a set
$\\{F_{s}\\}_{s=1}^{r}$ of disjoint cycles of $\pi$ with
$\cup_{s=1}^{r}F_{s}=\\{1,2,\ldots,n\\}$ such that $\pi_{s}=\pi|_{F_{s}}$ and
$\pi(i)=\pi_{s}(i)$ whenever $i\in F_{s}$.

The positivity of $D$-type maps generated by one permutation were discussed in
[9] recently. Let $\pi$ be a permutation of $(1,2,\ldots,n)$ with disjoint
cycle decomposition $(\pi_{1})\cdots(\pi_{r})$ such that the maximum length of
$\pi_{h}$s is equal to $l>1$ and $P_{\pi}=(\delta_{i\pi(j)})$ is the
permutation matrix associated with $\pi$. For $t\geq 0$, let
$\Phi_{t,\pi}:M_{n}\rightarrow M_{n}$ be the $D$-type map of the form in
Eq.(1.1) with $D=(n-t)I_{n}+tP_{\pi}$. It is shown in [9] that $\Phi_{t,\pi}$
is positive if and only if $0\leq t\leq\frac{n}{l}$. Particularly,
$\Phi_{\pi}=\Phi_{1,\pi}$ is always positive.

Motivated by the above result, let us consider the $D$-type maps constructed
from several permutations. Generally speaking,
$\Phi_{D_{\pi_{1},\ldots,\pi_{k}}}$ is not positive if

$None$
$D_{\pi_{1},\ldots,\pi_{k}}=(n-k)I_{n}+P_{\pi_{1}}+P_{\pi_{2}}+\cdots+P_{\pi_{k}}$

with $1<k\leq n-1$. For example, take $\pi$ defined by $\pi(i)=i+1$ mod $n$
and let $D=(n-2)I_{n}+2P_{\pi}$,; then $\Phi_{D}$ is not positive by the
result in [9] mentioned above. However there do exist $D$-type positive linear
maps of the form $\Phi_{D_{\pi_{1},\ldots,\pi_{k}}}$ with $k>1$. For the
permutation $\pi$ defined by $\pi(i)=i+1$ mod $n$, and for any $1\leq k\leq
n-1$, it is known that $\Phi_{D}:M_{n}\rightarrow M_{n}$ is positive, where
$D=(n-k)I_{n}+P_{\pi}+P_{\pi^{2}}+\cdots+P_{\pi^{k}}$ (ref. [15]).

So it is an natural and interesting topic to study the $D$-type linear maps
$\Phi_{D}$ with $D={D_{\pi_{1},\ldots,\pi_{k}}}$ of the form Eq.(1.2) and
establish positivity criteria for them.

The purpose of this paper is to start the discussion of this topic. We
introduce a concept of property (C) for a pair of permutations (Definition
3.2), and show that, if $\\{\pi_{1},\pi_{2}\\}$ has the property (C), then the
$D$-type map $\Phi_{D_{\pi_{1},\pi_{2}}}$ is positive (Theorem 3.3 and Theorem
3.4). To do this, we develop some inequalities (Lemma 2.1, Lemma 2.2), which
are interesting themselves. Furthermore, we give a necessary and sufficient
condition for two permutations to have property (C) (Proposition 3.5). This
results then applied to give some criteria of positivity of $D$-type maps
induced by pair of permutations and to construct some new positive $D$-type
maps, especially from pair of permutations $\\{\pi^{p},\pi^{q}\\}$, where
$\pi$ is the cyclic permutation defined by $\pi(i)=i+1$ mod $n$. Some examples
are also presented to illustrate how to use the criteria.

##  2\. Preliminary inequalities

In this section, we first establish two cyclic like inequalities, which are
needed to establish the criteria for a $D$-type linear maps induced from a
pair of permutations to be positive.

Lemma 2.1. Let $s,M$ be positive numbers and $f(u_{1},u_{2},...,u_{m})$ be a
function in $m$-variable defined by

$f(u_{1},u_{2},...,u_{m})=\frac{1}{s+u_{1}}+\frac{1}{s+u_{2}}+...+\frac{1}{s+u_{m}}$

on the region $u_{i}>0$ with $u_{1}u_{2}...u_{m}=M^{m}$, $i=1,2,...,m$. Then
we have

(1) $f$ has extremum values
$\frac{rs^{\frac{m}{2r-m}}+(m-r)M^{\frac{m}{2r-m}}}{s(s^{\frac{m}{2r-m}}+M^{\frac{m}{2r-m}})}$
with $\frac{m}{2}<r\leq m$ at the points that $r$ of $u_{i}$s are
$(\frac{M^{m}}{s^{2m-2r}})^{\frac{1}{2r-m}}$ and others are
$(\frac{s^{2r}}{M^{m}})^{\frac{1}{2r-m}}$;

(2) $f$ may also achieve the extremum $\frac{m}{s+M}$ when $m$ is even, at
points $\frac{m}{2}$ of $u_{i}$s are $u$ and others are $\frac{s^{2}}{u}$, in
this case we must have $s=M$;

(3) $\sup f(u_{1},u_{2},...,u_{m})=\max\\{\frac{m-1}{s},\frac{m}{s+M}\\}.$

Proof. The case $m=1$ is obvious. For the case that $m=2$, we have
$u_{2}=\frac{M^{2}}{u_{1}}$ and
$f(u_{1},u_{2})=\frac{1}{s+u_{1}}+\frac{1}{s+\frac{M^{2}}{u_{1}}}=\frac{1}{s+u_{1}}+\frac{u_{1}}{su_{1}+M^{2}}=g(u_{1})$.
Letting
$g^{\prime}(u_{1})=\frac{M^{2}}{(su_{1}+M^{2})^{2}}-\frac{1}{(s+u_{1})^{2}}=0$,
we get $(M^{2}-s^{2})(u_{1}^{2}-M^{2})=0$. If $M\not=s$, we must have
$u_{1}=M$ and $g$ has an extremum at $u_{1}=M$ with $g(M)=\frac{2}{s+M}$; if
$s=M$, then $g(u_{1})=\frac{1}{s+u_{1}}+\frac{u_{1}}{s(s+u_{1})}=\frac{1}{s}$.
Also note that $\lim_{u_{1}\rightarrow 0}g(u_{1})=\frac{1}{s}$. So, $\max
f(u_{1},u_{2})\leq\max\\{\frac{1}{s},\frac{2}{s+M}\\}$.

Assume that $m\geq 3$. $f$ approximates its supremum at the singular boundary
of its domain or at some of its extremum values. It is obvious that if
$(u_{1j},u_{2j},\ldots,u_{mj})$ converges to the boundary of the domain
$\\{\Pi_{i=1}^{m}u_{i}=M^{m}\\}$, then some $u_{i}$ tend to 0 and some tend to
$\infty$. Say $k$ of them tend to 0 and $m-k-r$ of them tend to $\infty$. Thus
there are $r$ nonnegative numbers $t_{h}$ so that
$\overline{\lim}_{j\rightarrow\infty}f(u_{1j},u_{2j},\ldots,u_{mj})=\frac{k}{s}+\sum_{h=1}^{r}\frac{1}{s+t_{h}}\leq\frac{k+r}{s}\leq\frac{m-1}{s}$.

Next let us consider the extremum values of $f$. Let
$\varphi(u_{1},u_{2},...,u_{m})=u_{1}u_{2}...u_{m}-M^{m},$ and

$\begin{array}[]{rl}L(u_{1},u_{2},...,u_{m},\lambda)=&f(u_{1},u_{2},...,u_{m})+\lambda\varphi(u_{1},u_{2},...,u_{m})\\\
=&\sum_{i=1}^{m}\frac{1}{s+u_{i}}+\lambda(u_{1}u_{2}...u_{m}-M^{m}).\end{array}$

By the method of Lagrange multipliers, we have the system

$None$
$L_{u_{i}}^{\prime}=\frac{-1}{(s+u_{i})^{2}}+\lambda{u_{1}u_{2}...u_{i-1}u_{i+1}...u_{m}}=\frac{-1}{(s+u_{i})^{2}}+\frac{\lambda
M^{m}}{u_{i}}=0,$

$i=1,2\ldots,m$. Solving this system gives

$None$ ${\lambda M^{m}}=\frac{u_{i}}{(s+u_{i})^{2}}$

for $i=1,2,...,m.$ Thus, for any $i,j$ with $i\not=j$,
$\frac{u_{i}}{(s+u_{i})^{2}}={\lambda M^{m}}=\frac{u_{j}}{(s+u_{j})^{2}}$
which yields

$u_{i}[s+u_{j}]^{2}=u_{j}[s+u_{i}]^{2}.$

It follows that

${s^{2}}{u_{i}}+2{u_{i}}{u_{j}}{s}+{u_{i}}{u_{j}}^{2}={s^{2}}{u_{j}}+{2u_{i}u_{j}s}+{u_{j}}{u_{i}^{2}},$
${s^{2}}(u_{i}-u_{j})+u_{i}u_{j}(u_{j}-u_{i})=0,$
$(u_{i}-u_{j})[s^{2}-u_{i}u_{j}]=0.$

Hence we get

$None$ ${u_{i}=u_{j}}\ \ \ {\rm or}\ \ \ {u_{i}u_{j}=s^{2}}.$

Eq.(2.3) implies that, there exists a positive integer $\frac{m}{2}\leq r\leq
m$ such that $r$ of $u_{1},u_{2},\ldots,u_{m}$ are the same, denoted by $u$,
and other $m-r$ of them are the same, denoted by $v$, with $uv=s^{2}$. Note
that

$None$ $u^{(2r-m)}s^{2(m-r)}=u^{r}v^{m-r}=u_{1}u_{2}\cdots u_{m}=M^{m}.$

If $2r=m$ (in this case $m$ is even), then we get $s^{m}=M^{m}$ and hence
$s=M$. Consequently, $f$ has a possible extremum value

$\frac{m}{2(s+u)}+\frac{m}{2(s+\frac{s^{2}}{u})}=\frac{m}{2(s+u)}+\frac{mu}{2s(s+u)}=\frac{m}{2s}=\frac{m}{s+M}$

at each point $(u_{1},u_{2},\ldots,u_{m})$ satisfying that $\frac{m}{2}$ of
$u_{i}$s are $u$ for some $u>0$ and other $\frac{m}{2}$ of them are
$\frac{s^{2}}{u}$.

If $m<2r\leq 2m$, we get by Eq.(2.4) that

$None$ $u=\left(\frac{M^{m}}{s^{2(m-r)}}\right)^{\frac{1}{2r-m}}\quad{\rm
and}\quad v=\left(\frac{s^{2r}}{M^{m}}\right)^{\frac{1}{2r-m}},$

and hence $f$ has an extremum value

$None$
$\begin{array}[]{rl}\frac{r}{s+u}+\frac{m-r}{s+v}=&\frac{r}{s+\left(\frac{M^{m}}{s^{2(m-r)}}\right)^{\frac{1}{2r-m}}}+\frac{m-r}{s+\left(\frac{s^{2r}}{M^{m}}\right)^{\frac{1}{2r-m}}}\\\
=&\frac{rs^{\frac{2m-2r}{2r-m}}+\frac{m-r}{s}M^{\frac{m}{2r-m}}}{s^{\frac{m}{2r-m}}+M^{\frac{m}{2r-m}}}=\frac{rs^{\frac{m}{2r-m}}+(m-r)M^{\frac{m}{2r-m}}}{s(s^{\frac{m}{2r-m}}+M^{\frac{m}{2r-m}})}\end{array}$

at those points $(u_{1},u_{2},\ldots,u_{m})$ that $r$ of $u_{i}$s equal
$\left(\frac{M^{m}}{s^{2(m-r)}}\right)^{\frac{1}{2r-m}}$ and other $m-r$ of
$u_{i}$s equal $\left(\frac{s^{2r}}{M^{m}}\right)^{\frac{1}{2r-m}}$.

Note that $1<\frac{m}{2}\leq r\leq m$ and

$\frac{m-1}{s}-\frac{rs^{\frac{m}{2r-m}}+(m-r)M^{\frac{m}{2r-m}}}{s(s^{\frac{m}{2r-m}}+M^{\frac{m}{2r-m}})}=\frac{(m-1-r)s^{\frac{m}{2r-m}}+(r-1)M^{\frac{m}{2r-m}}}{s(s^{\frac{m}{2r-m}}+M^{\frac{m}{2r-m}})}.$

So, if $r\leq m-1$, then we always have
$\frac{m-1}{s}\geq\frac{rs^{\frac{m}{2r-m}}+(m-r)M^{\frac{m}{2r-m}}}{s(s^{\frac{m}{2r-m}}+M^{\frac{m}{2r-m}})}$.
If $r=m$, then
$\frac{rs^{\frac{m}{2r-m}}+(m-r)M^{\frac{m}{2r-m}}}{s(s^{\frac{m}{2r-m}}+M^{\frac{m}{2r-m}})}=\frac{m}{s+M}$.
These, together with the cases that $m$ is even and $r=\frac{m}{2}$ entails
that $\sup
f(u_{1},u_{2},\ldots,u_{m})\leq\max\\{\frac{m-1}{s},\frac{m}{s+M}\\}$,
completeing the proof. $\Box$

The following lemma is crucial for our purpose. Though we only need the
special case of $k=2$ in this paper, we present the inequality for any $k\geq
1$ because it may be useful to discussing $D$-type maps induced by $k$
permutations.

Lemma 2.2. Let $s$ be a positive number, $n,k$ be positive integers with
$s>k$. Then for any $nk$ positive real numbers
$\\{x_{hi},h=1,2,...,k;i=1,2,...,n,\\}$ satisfying $x_{h1}x_{h2}...x_{hn}=1$
for each $h$ with $1\leq h\leq k$, we have

$None$
$\begin{array}[]{rl}f(x_{11},\ldots,x_{1n},x_{21},\ldots,x_{k1},\ldots,x_{kn})=&\sum_{i=1}^{n}\frac{1}{s-k+x_{1i}+x_{2i}+...+x_{ki}}\\\
\leq&\max\\{\frac{n-1}{s-k},\frac{n}{s}\\}.\end{array}$

Moreover, the extremum values of $f$ are

$None$
$\begin{array}[]{ll}\delta_{r}=\frac{r(s-k)^{\frac{n}{2r-n}}+(n-r)k^{\frac{n}{2r-n}}}{(s-k)((s-k)^{\frac{n}{2r-n}}+k^{\frac{n}{2r-n}})},&[\frac{n}{2}]+1\leq
r<n;\\\ \delta_{\frac{n}{2}}=\frac{n}{s}&\mbox{\rm if }n\ \mbox{\rm is
even},\end{array}$

where $[t]$ stands for the integer part of real number $t$.

Proof. The question is reduced to find the supremum of the $kn$-variable
function

$f(x_{11},...,x_{1n},x_{21},...,x_{2n},...,x_{k1},...,x_{kn})=\sum_{i=1}^{n}\frac{1}{s-k+x_{1i}+x_{2i}+...+x_{ki}}$

on the region $x_{hi}>0$ with $x_{h1}x_{h2}...x_{hn}=1$, $h=1,2,\ldots,k$.
Considering the behavior of $f$ near the boundary of its domain, it is obvious
that the upper bound of $f$ near the boundary is $\frac{n-1}{s-k}$.

To find the extremum values of $f$, let

$\begin{array}[]{rl}&L(x_{11},...x_{1n},x_{21},...,x_{2n},...,x_{k1},...,x_{kn},\lambda_{1},...\lambda_{k})\\\
=&f(x_{11},...x_{1n},x_{21},...,x_{2n},...,x_{k1},...,x_{kn})+\sum_{h=1}^{k}\lambda_{h}\varphi_{h},\end{array}$

where $\varphi_{h}=x_{h1}x_{h2}...x_{hn}-1$, $h=1,2,...k.$ By the method of
Lagrange multipliers, we have the system

$None$
$\begin{cases}L_{x_{11}}^{\prime}=\frac{-1}{[(s-k)+x_{11}+x_{21}+...+x_{k1}]^{2}}+\frac{\lambda_{1}}{x_{11}}=0,\\\
\ \vdots\\\
L_{x_{k1}}^{\prime}=\frac{-1}{[(s-k)+x_{11}+x_{21}+...+x_{k1}]^{2}}+\frac{\lambda_{k}}{x_{k1}}=0,\\\
\\\
L_{x_{12}}^{\prime}=\frac{-1}{[(s-k)+x_{12}+x_{22}+...+x_{k2}]^{2}}+\frac{\lambda_{1}}{x_{12}}=0,\\\
\ \vdots\\\
L_{x_{k2}}^{\prime}=\frac{-1}{[(s-k)+x_{12}+x_{22}+...+x_{k2}]^{2}}+\frac{\lambda_{k}}{x_{k2}}=0,\\\
\ \vdots\\\
L_{x_{1n}}^{\prime}=\frac{-1}{[(s-k)+x_{1n}+x_{2n}+...+x_{kn}]^{2}}+\frac{\lambda_{1}}{x_{1n}}=0,\\\
\ \vdots\\\
L_{x_{kn}}^{\prime}=\frac{-1}{[(s-k)+x_{1n}+x_{2n}+...+x_{kn}]^{2}}+\frac{\lambda_{k}}{x_{kn}}=0.\end{cases}$

Solving this system, one obtains that

$None$
$\begin{cases}\frac{\lambda_{1}}{x_{11}}={\frac{\lambda_{2}}{x_{21}}}=\ldots={\frac{\lambda_{k}}{x_{k1}}},\\\
{\frac{\lambda_{1}}{x_{12}}}={\frac{\lambda_{2}}{x_{22}}}=\ldots={\frac{\lambda_{k}}{x_{k2}}},\\\
\vdots\\\
{\frac{\lambda_{1}}{x_{1n}}}={\frac{\lambda_{2}}{x_{2n}}}=\ldots={\frac{\lambda_{k}}{x_{kn}}},\end{cases}$

which implies that

$None$
$\frac{{\lambda_{1}}^{n}}{{x_{11}}{x_{12}}\ldots{x_{1n}}}=\frac{{\lambda_{2}}^{n}}{{x_{21}}{x_{22}}\ldots{x_{2n}}}=\ldots=\frac{{\lambda_{k}}^{n}}{{x_{k1}}{x_{k2}}\ldots{x_{kn}}}.$

Now since ${x_{h1}}{x_{h2}}\ldots{x_{hn}}=1$, for each $h=1,2,...,k$, we get

$None$ ${{\lambda_{1}}^{n}}={{\lambda_{2}}^{n}}=\ldots={{\lambda_{k}}^{n}}.$

Furthermore, by Eq.(2.8) we see that

${\lambda_{h}}={\frac{x_{h1}}{{[(s-k)+({x_{11}}+{x_{21}}+\ldots+{x_{k1}})]}^{2}}}=\ldots={\frac{x_{hn}}{{[(s-k)+({x_{1n}}+{x_{2n}}+\ldots+{x_{kn}})]}^{2}}}>0$

for each $h=1,2,...,k.$ Therefore, we must have

${\lambda_{1}}={\lambda_{2}}=\ldots={\lambda_{k}}>0,$

which forces, by the Eq.(2.9), that

$None$ $\begin{cases}{x_{11}}=x_{21}=\ldots=x_{k1},\\\
{x_{12}}=x_{22}=\ldots=x_{k2},\\\ \ \vdots\\\
{x_{1n}}=x_{2n}=\ldots=x_{kn}.\\\ \end{cases}$

Let $v_{i}=x_{1i}$, $i=1,2,...,n.$ Then, the question reduces to find the
supremum of the function in $n$-variable

$g(v_{1},v_{2},...,v_{n})=\frac{1}{s-k+kv_{1}}+\frac{1}{s-k+kv_{2}}+...+\frac{1}{s-k+kv_{n}}$

on the region $v_{i}>0$ and $v_{1}v_{2}\cdots v_{n}=1$. Applying Lemma 2.1
with $m=n$, $s$ replaced by $s-k$, $M=k$ and $u_{i}=kv_{i}$, $i=1,2,\ldots n$,
we obtain that

$\sup
g(v_{1},v_{2},...,v_{n})=\max\\{\frac{n-1}{s-k},\frac{n}{s-k+k}\\}=\max\\{\frac{n-1}{s-k},\frac{n}{s}\\}.$

Hence $\sup f=\max\\{\frac{n-1}{s-k},\frac{n}{s}\\}$. Moreover, the extremum
values of $f$ are $\\{\delta_{r}:n\leq 2r\leq 2n\\}$, where

$\delta_{n}=\frac{n}{s},\
\delta_{r}=\frac{r(s-k)^{\frac{n}{2r-n}}+(n-r)k^{\frac{n}{2r-n}}}{(s-k)((s-k)^{\frac{n}{2r-n}}+k^{\frac{n}{2r-n}})}\quad{\rm
for}\ [\frac{n}{2}]+1\leq r\leq n-1,$

and

$\delta_{\frac{n}{2}}=\frac{n}{s}\quad{\rm if}\ n\ {\rm is\ even}.$

It is easily checked by Lemma 2.1 that $f$ achieves the extremum $\delta_{n}$
at $x_{11}=x_{21}=\ldots=x_{k,n}=1$; $f$ achieves $\delta_{r}$ with
$\frac{n}{2}<r\leq n-1$ at those points that $r$ of $v_{i}$s equal
$(\frac{k}{s-k})^{\frac{2n-2r}{2r-n}}$ and other $n-r$ of $v_{i}$s equal
$(\frac{s-k}{k})^{\frac{2r}{2r-n}}$; and, if $n$ is even, $f$ achieves the
extremum $\delta_{\frac{n}{2}}$ at those points that $\frac{n}{2}$ of $v_{i}$s
are the same, denoted by $v$, and other $\frac{n}{2}$ $v_{i}$s are equal to
$\frac{(s-k)^{2}}{v}$, in this case we must have $k=\frac{n}{2}=r$. $\Box$

##  3\. Criteria of positivity of $D$-type maps induced by two permutations

In [9], the authors established a criterion of positivity for $D$-type maps
constructed from one permutation, and proved that $\Phi_{D}:M_{n}\rightarrow
M_{n}$ is positive if $D=(n-1)I_{n}+P_{\pi}$, where $\pi$ is any permutation
of $\\{1,2,...,n\\}$. For those constructed from more than one permutations,
it is known that, the $D$-type map $\Phi_{D}$ with
$D=(n-k)I_{n}+P_{\pi_{0}}+P_{{\pi_{0}}^{2}}+...+P_{{\pi_{0}}^{k}}$ is
positive, where ${\pi_{0}}(i)=i-1$ mod $n$ [2] or $\pi_{0}(i)=i+1$ mod $n$
[15]. In this section we give a criterion of positivity of $D$-type linear
maps constructed from pairs of general permutations.

The following lemma comes from [9].

Lemma 3.1. Suppose $\Phi_{D}:{M_{n}}\rightarrow{M_{n}}$ is a $D$-type linear
map of the form

$None$ $(a_{ij})\longmapsto{{\rm diag}(f_{1},f_{2},...,f_{n})-(a_{ij})}$

with $(f_{1},f_{2},...,f_{n})=(a_{11},a_{22},...,a_{nn})D$ for an $n\times n$
nonnegative matrix $D=(d_{ij})$ (i.e., $d_{ij}\geq 0$ for all $i,j$). Then,
$\Phi_{D}$ is positive if and only if, for any unit vector
$u=(u_{1},u_{2},...,u_{n})^{t}\in{\mathbb{C}}^{n}$, we have
$f_{j}(u)=\sum_{i=1}^{n}d_{ij}|u_{i}|^{2}\neq 0$ whenever $u_{j}\neq 0$, and
that $\sum_{u_{j}\neq 0}{\frac{|u_{j}|^{2}}{f_{j}(u)}}\leq 1.$

Before stating our main result, we introduce a conception of property (C) for
a pair of permutations.

Definition 3.2. A pair $\\{\pi_{1},\pi_{2}\\}$ of permutations of
$(1,2,\ldots,n)$ is said to have property (C) if, for any given
$i\in\\{1,2,\ldots,n\\}$ and for any $j\not=i$, there exists
$\pi_{h_{j}}(j)\in\\{\pi_{1}(j),\pi_{2}(j)\\}$ with $h_{j}\in\\{1,2\\}$ such
that
$\\{\pi_{h_{j}}(j):j=1,2,\ldots,i-1,i+1,\ldots,n\\}=\\{1,2,\ldots,i-1,i+1,\ldots,n\\}$.

Let $\pi$ be the permutation of $(1,2,\ldots,n)$ defined by $\pi(i)=i+1$ mod
$n$. Then it is easily checked that, for any $1\leq p\leq n-1$,
$\\{\pi^{p},\pi^{p+1}\\}$ has Property (C). There are other kinds of examples.
For instance, $\\{\pi,\pi^{4}\\}$ has the property (C) if $n=5$ and $7$, but
does not have the property (C) if $n=4$ and $6$.

The following is our main general result which gives a criterion of positivity
for $D$-type maps induced by pair of general permutations.

Theorem 3.3. For any two permutations ${\pi_{1}}$ and $\pi_{2}$ of
$(1,2,...,n)$ with $n\geq 3$, let $\Phi_{D}:M_{n}\rightarrow M_{n}$ be the
$D$-type map of the form

$(a_{ij})\longmapsto{{\rm diag}(f_{1},f_{2},...,f_{n})-(a_{ij})},$

where $(f_{1},f_{2},...,f_{n})=(a_{11},a_{22},...,a_{nn})D$ and
$D=(n-2)I_{n}+{P_{\pi_{1}}}+{P_{\pi_{2}}}$ with $P_{\pi_{h}}$ the permutation
matrix of $\pi_{h}$, $h=1,2$. If $\\{\pi_{1},\pi_{2}\\}$ has the property (C),
then $\Phi_{D}$ is positive.

Proof. For any unit vector $x=(x_{1},x_{2},...,x_{n})^{t}\in{\mathbb{C}}^{n}$,
we have

$X=xx^{*}={(x_{1},x_{2},...,x_{n})^{t}}(\bar{x_{1}},\bar{x_{2}},...\bar{x_{n}})=\left(\begin{array}[]{cccc}|x_{1}|^{2}&{x_{1}\bar{x_{2}}}&\cdots&{x_{1}\bar{x_{n}}}\\\
{x_{2}\bar{x_{1}}}&|x_{1}|^{2}&\cdots&{x_{2}\bar{x_{n}}}\\\
\vdots&\vdots&\ddots&\vdots\\\
{x_{n}\bar{x_{1}}}&{x_{n}\bar{x_{2}}}&\ldots&|x_{n}|^{2}\end{array}\right).$

As $D=(d_{ij})=(n-k)I_{n}+{P_{\pi_{1}}}+{P_{\pi_{2}}}$, we get

$f_{j}(x)=\sum_{i=1}^{n}d_{ij}|x_{i}|^{2}\\\
=(n-2)|x_{j}|^{2}+|x_{\pi_{1}(j)}|^{2}+|x_{\pi_{2}(j)}|^{2}.$

Then by Lemma 3.1, $\Phi_{D}$ is positive if the following inequality

$None$
$\sum_{i=1}^{n}\frac{|x_{i}|^{2}}{f_{i}(x)}=\sum_{i=1}^{n}{\frac{|x_{i}|^{2}}{(n-2)|x_{i}|^{2}+|x_{\pi_{1}(i)}|^{2}+|x_{\pi_{2}(i)}|^{2}}}\leq
1$

holds for any unit vector
$x=(x_{1},x_{2},\ldots,x_{n})^{t}\in{\mathbb{C}}^{(n)}$.

Case 1. $n\geq 4$.

Let us consider first the case that $n\geq 4$. Assume that all $x_{i}\neq 0$
and let $u_{hi}={\frac{|x_{\pi_{h}(i)}|^{2}}{|x_{i}|^{2}}}$, $i=1,2,...,n$;
$h=1,2.$ Then, $u_{h1}u_{h2}\cdots u_{hn}=1$ for each $h=1,2$, and thus, by
Lemma 2.2, we have

$\begin{array}[]{rl}&f(x_{1},x_{2},\ldots,x_{n})=\sum_{i=1}^{n}{\frac{|x_{i}|^{2}}{(n-2)|x_{i}|^{2}+|x_{\pi_{1}(i)}|^{2}+|x_{\pi_{2}(i)}|^{2}}}\\\
=&g(u_{11},u_{12},\ldots,u_{1n},u_{21},u_{22},\ldots,u_{2n})=\sum_{i=1}^{n}{\frac{1}{n-2+u_{1i}+u_{2i}}}\\\
\leq&\max\\{\frac{n-1}{n-2},1\\}.\end{array}$

and, as a restriction of $g$, the maximum of all extremum values of $f$ is
bounded by the maximum of all extremum values of $g$. Thus, by Lemma 2.2, we
have

$\max\\{\mbox{\rm extreme values of
}f\\}\leq\max\\{1,\delta_{r}:r=[\frac{n}{2}]+1,[\frac{n}{2}]+1,\ldots,n-1\\},$

where

$\delta_{r}=\frac{r(n-2)^{\frac{n}{2r-n}}+(n-r)2^{\frac{n}{2r-n}}}{(n-2)((n-2)^{\frac{n}{2r-n}}+2^{\frac{n}{2r-n}})}$

and $[t]$ is the integer part of $t$. If $[\frac{n}{2}]+1\leq r\leq n-2$, then

$\begin{array}[]{rl}\delta_{r}=&\frac{r(n-2)^{\frac{n}{2r-n}}+(n-r)2^{\frac{n}{2r-n}}}{(n-2)((n-2)^{\frac{n}{2r-n}}+2^{\frac{n}{2r-n}})}\\\
=&\frac{(2r-n)(n-2)^{\frac{n}{2r-n}}}{(n-2)((n-2)^{\frac{n}{2r-n}}+2^{\frac{n}{2r-n}})}+\frac{n-r}{n-2}\leq\frac{r}{n-2}\leq
1.\end{array}$

We claim that we also have $\delta_{n-1}\leq 1$. In fact,

$\delta_{n-1}=\frac{(n-1)(n-2)^{\frac{n}{2r-n}}+2^{\frac{n}{2r-n}}}{(n-2)((n-2)^{\frac{n}{2r-n}}+2^{\frac{n}{2r-n}})}=\frac{(n-2)^{\frac{n}{2r-n}}}{(n-2)^{\frac{n}{2r-n}}+2^{\frac{n}{2r-n}}}+\frac{1}{n-2}\leq
1$

if and only if

$None$ $\psi(n)=\frac{n-2}{(n-3)^{\frac{n-2}{n}}}\leq 2.$

Let
$\varphi(t)=\ln(\frac{t-2}{(t-3)^{\frac{t-2}{t}}})=\ln(t-2)-\frac{t-2}{t}\ln(t-3)$
for $t\geq 4$. Then

$\varphi^{\prime}(t)=\frac{t^{2}-4t-(2t^{2}-10t+12)\ln(t-3)}{t^{2}(t-2)(t-3)}.$

If $t\geq 9$, then

$t^{2}-4t-(2t^{2}-10t+12)\ln(t-3)<-(t^{2}-10t+12)\ln(t-3)<0$

and hence $\varphi(t)$ is decreasing on $[9,\infty)$. It follows that
$\psi(n)=\frac{n-2}{(n-3)^{\frac{n-2}{n}}}$ is decreasing for $n\geq 9$. Since

$\psi(4)=2,\ \psi(5)\approx 1.9793,\ \psi(6)\approx 1.9230,\ \psi(7)\approx
1.8575,\ \psi(8)\approx 1.7944,\ \psi(9)\approx 1.7373,$

we see that the inequality in Eq.(3.3) is true for all $n\geq 4$ and hence
$\delta_{n-1}\leq 1$ holds for all $n\geq 4$, as desired.

Therefore, for any $n\geq 4$, 1 is the maximum extremum value of
$f(x_{1},x_{2},\ldots,x_{n})$ achieving at
$f(\frac{1}{\sqrt{n}},\frac{1}{\sqrt{n}},\ldots,\frac{1}{\sqrt{n}})$.

In the following we show that the supremum of $f$ on the boundary of its
domain $|x_{1}|^{2}+|x_{2}|^{2}+\cdots+|x_{n}|^{2}=1$ is not greater than 1,
either. Assume that $(x_{1},x_{2},\ldots,x_{n})^{t}$ lies in the boundary of
the region $|x_{1}|^{2}+|x_{2}|^{2}+\cdots+|x_{n}|^{2}=1$; then at least one
of $x_{i}$ is zero. With no loss of generality, say $x_{i}\not=0$ for
$i=1,2,\ldots r$, but $x_{r+1}=\ldots=x_{n}=0$, where $1<r<n$. Then we have

$\begin{array}[]{rl}&\sum_{i=1}^{n}{\frac{|x_{i}|^{2}}{(n-2)|x_{i}|^{2}+|x_{\pi_{1}(i)}|^{2}+|x_{\pi_{2}(i)}|^{2}}}=\sum_{i=1}^{r}{\frac{1}{(n-2)+\frac{|x_{\pi_{1}(i)}|^{2}}{|x_{i}|^{2}}+\frac{|x_{\pi_{2}(i)}|^{2}}{|x_{i}|^{2}}}}.\end{array}$

If $r=n-1$, by the assumption that $\\{\pi_{1},\pi_{2}\\}$ has the property
(C), one can choose $\pi_{h_{i}}(i)\in\\{\pi_{1}(i),\pi_{2}(i)\\}$ so that
$\\{\pi_{h_{i}}(i)\\}_{i=1}^{n-1}=\\{1,2,\ldots,n-1\\}$. So

$\Pi_{i=1}^{n-1}\frac{|x_{\pi_{h_{i}}(i)}|^{2}}{|x_{i}|^{2}}=1,$

and thus, by Lemma 2.2 with $k=1$ and $s=n-1$, we get

$None$
$\begin{array}[]{rl}&\sum_{i=1}^{n}{\frac{|x_{i}|^{2}}{(n-2)|x_{i}|^{2}+|x_{\pi_{1}(i)}|^{2}+|x_{\pi_{2}(i)}|^{2}}}=\sum_{i=1}^{n-1}{\frac{1}{(n-2)+\frac{|x_{\pi_{1}(i)}|^{2}}{|x_{i}|^{2}}+\frac{|x_{\pi_{2}(i)}|^{2}}{|x_{i}|^{2}}}}\\\
\leq&\sum_{i=1}^{n-1}{\frac{1}{((n-1)-1)+\frac{|x_{\pi_{h_{i}}(i)}|^{2}}{|x_{i}|^{2}}}}\leq\frac{n-1}{n-1}=1.\end{array}$

If $r\leq n-2$, then we always have

$None$
$\begin{array}[]{rl}&\sum_{i=1}^{n}{\frac{|x_{i}|^{2}}{(n-2)|x_{i}|^{2}+|x_{\pi_{1}(i)}|^{2}+|x_{\pi_{2}(i)}|^{2}}}=\sum_{i=1}^{r}{\frac{1}{(n-2)+\frac{|x_{\pi_{1}(i)}|^{2}}{|x_{i}|^{2}}+\frac{|x_{\pi_{2}(i)}|^{2}}{|x_{i}|^{2}}}}\leq\frac{r}{n-2}\leq
1.\end{array}$

The inequalities in Eqs.(3.4) and (3.5) ensure us that $f$ is upper bounded by
1 on the boundary of its domain, and hence Eq.(3.2) is true for any unit
vectors. Applying Lemma 3.1, $\Phi_{D}$ is a positive linear map for the case
$n\geq 4$.

Case 2. $n=3$.

Finally, assume that $n=3$. If one of $\pi_{1}$ and $\pi_{2}$ is the identity,
then the question reduce to the case of $D$-type maps generalized by one
permutation, and hence the corresponding $D$-type map is positive by [9]. So
we may assume that both $\pi_{1}$ and $\pi_{2}$ are not the identity. It is
easily checked that we have four possible cases so that
$\\{\pi_{1},\pi_{2}\\}$ has the property (C):

$\begin{array}[]{llll}\\{(2,3,1),(3,1,2)\\};&\\{(3,2,1),(2,1,3)\\};&\\{(3,2,1),(1,3,2)\\};&\\{(1,3,2),(2,1,3)\\}.\end{array}$

The case $\\{(2,3,1),(3,1,2)\\}$ is implied by the result in [15]. By Lemma
3.1, the last three cases induce to prove the following inequality

$\frac{1}{1+u+v}+\frac{u}{2u+1}+\frac{v}{2v+1}\leq 1$

for any $u,v>0$. This is true because

$\begin{array}[]{rl}&(2u+1)(2v+1)+u(1+u+v)(2v+1)+v(1+u+v)(2u+1)\\\
\leq&(1+u+v)(2u+1)(2v+1)\end{array}$

by $2uv\leq u^{2}+v^{2}$. So the theorem is also true for the case $n=3$,
finishing the proof. $\Box$

It is clear that the less $n$ is the easier to check the property (C) of
$\\{\pi_{1},\pi_{2}\\}$. This motivates us to decompose the permutations into
small ones.

For a nonempty subset $F$ of $\\{1,2,\ldots,n\\}$, if $F$ is a common
invariant subset of $\pi_{s}$s, i.e., if $\pi_{h}(F)=F$ holds for all
$h=1,2,\ldots k$, we say that $F$ is an invariant subsets of
$\\{\pi_{1},\pi_{2},\ldots,\pi_{k}\\}$. Obvious, there exist disjoint minimal
invariant subsets $F_{1},F_{2},\ldots,F_{l}$ of
$\\{\pi_{1},\pi_{2},\ldots,\pi_{k}\\}$ such that $\sum_{s=1}^{l}\\#F_{s}=n$
(i.e., $\cup_{s=1}^{l}F_{s}=\\{1,2,\ldots,n\\}$). We say
$\\{F_{1},F_{2},\ldots,F_{l}\\}$ is the complete set of minimal invariant
subsets of $\\{\pi_{1},\ldots,\pi_{k}\\}$. Thus one can reduce the set
$\\{\pi_{1},\pi_{2},\ldots,\pi_{k}\\}$ of permutations into $l$ sets
$\\{\pi_{1s},\pi_{2s},\ldots,\pi_{ks}\\}_{s=1}^{l}$ of small ones, where
$\pi_{hs}=\pi_{h}|_{F_{s}}$. It is easily checked that $\\{\pi_{1},\pi_{2}\\}$
has the property (C) if and only if each pair $\\{\pi_{1s},\pi_{2s}\\}$ of the
sub-permutations has the property (C).

The following is a version of Theorem 3.3.

Theorem 3.4. Let $\\{F_{s}\\}_{s=1}^{l}$ be the complete set of minimal
invariant subsets of a pair $\\{\pi_{1},\pi_{2}\\}$ of permutations of
$\\{1,2,\ldots,n\\}$. Let $\pi_{is}=\pi_{i}|_{F_{s}}$. If
$\\{\pi_{1s},\pi_{2s}\\}$ has Property (C) for every $s=1,2,\ldots,l$, then
the $D$-type map $\Phi_{D}$ defined as in Theorem 3.3 is positive.

Theorem 3.3 and Theorem 3.4 give a possible way to construct new positive maps
but it is not very clear how to check whether or not a given pair of
permutations has the property (C). To get an insight of this, in the
following, we give a characterization of a pair of permutations to have
property (C), which will be used to construct new positive maps in the next
section. Note that $\\{\pi_{1},\pi_{2}\\}$ has property (C) if and only if
each pair $\\{\pi_{1s},\pi_{2s}\\}$ on the common invariant subset $F_{s}$ has
property (C). So, to check whether or not $\\{\pi_{1},\pi_{2}\\}$ has property
(C), we may assume that $\pi_{1}$ and $\pi_{2}$ has no common proper invariant
subsets. It is clear that, if $n=1$, $\\{\pi_{1},\pi_{2}\\}$ always has
property (C); if $n=2$, $\\{\pi_{1},\pi_{2}\\}$ has property (C) if and only
if one of $\pi_{1},\pi_{2}$ is the identity and other is
$(1,2)\rightarrow(2,1)$.

Proposition 3.5. Let $\pi_{1},\pi_{2}$ be two permutations of $(1,2,\ldots,n)$
with $n\geq 2$ having no proper common invariant subsets. Then
$\\{\pi_{1},\pi_{2}\\}$ has the property (C) if and only if the following
conditions are satisfied:

(1) For any distinguished $i,j$, $\pi_{1}(i)\not=\pi_{2}(i)$ and
$\\{\pi_{1}(i),\pi_{2}(i)\\}\not=\\{\pi_{1}(j),\pi_{2}(j)\\}$;

(2) For any $i$ and $j_{1},j_{2}$ with $\pi_{1}(j_{2})=\pi_{2}(j_{1})=i$, if
distinct $j_{3},\ldots,j_{m}\not\in\\{i,j_{1},j_{2}\\}$ satisfy that
$\pi_{2}(j_{3})=\pi_{1}(j_{1})$,
$\pi_{2}(j_{4})=\pi_{1}(j_{3}),\ldots,\pi_{2}(j_{m})=\pi_{1}(j_{m-1})$, then
$\pi_{1}(j_{m})\not=\pi_{2}(j_{2})$.

Proof. Assume that $\\{\pi_{1},\pi_{2}\\}$ satisfy the conditions (1)-(2). For
any $i$, we have to show that we can choose one element in
$\pi_{h_{j}}(j)\in\\{\pi_{1}(j),\pi_{2}(j)\\}$ for each $j\not=i$ so that
$\\{\pi_{h_{j}}(j),j\not=i\\}=\\{1,2,\ldots,i-1,i+1,\ldots,n\\}$.

Case (i). $i\in\\{\pi_{1}(i),\pi_{2}(i)\\}$, say $\pi_{1}(i)=i$, then
obviously the choice
$\\{\pi_{1}(j):j\not=i\\}=\\{1,2,\ldots,i-1,i+1,\ldots,n\\}$.

Case (ii). $i\not\in\\{\pi_{1}(i),\pi_{2}(i)\\}$.

Let $j_{1},j_{2}$ such that $\pi_{1}(j_{2})=i=\pi_{2}(j_{1})$. By the
condition (1), we must gave $\pi_{1}(j_{1})\not=\pi_{2}(j_{2})$. In fact, if
$\pi_{1}(j_{1})=\pi_{2}(j_{2})$, then
$\\{\pi_{1}(j_{1}),\pi_{2}(j_{1})\\}=\\{\pi_{1}(j_{2}),\pi_{2}(j_{2})\\}$,
which contradicts to the condition (1). If
$\\{\pi_{1}(j_{1}),\pi_{2}(j_{2})\\}=\\{\pi_{1}(i),\pi_{2}(i)\\}$, then
$\\{\pi_{1}(j_{1}),\pi_{2}(j_{2})\\}\cup\\{\pi_{1}(j):j\not\in\\{i,j_{1},j_{2}\\}\\}=\\{1,\ldots,i-1,i+1,\ldots,n\\}$
and we finished the proof.

Assume that
$\\{\pi_{1}(j_{1}),\pi_{2}(j_{2})\\}\not=\\{\pi_{1}(i),\pi_{2}(i)\\}$.

If $\pi_{1}(j_{1})=\pi_{2}(i)$ or $\pi_{2}(j_{2})=\pi_{1}(i)$, saying
$\pi_{2}(j_{2})=\pi_{1}(i)$, then we have
$\\{\pi_{2}(j_{2})\\}\cup\\{\pi_{1}(j):j\not\in\\{i,j_{2}\\}\\}=\\{\pi_{1}(j):j\not=j_{2}\\}=\\{1,2,\ldots,i-1,i+1,\ldots,n\\}$,
and then the proof is finished.

Thus we may in the sequel assume that
$\\{\pi_{1}(j_{1}),\pi_{2}(j_{2})\\}\cap\\{\pi_{1}(i),\pi_{2}(i)\\}=\emptyset$.
Take $j_{3}$ so that $\pi_{2}(j_{3})=\pi_{1}(j_{1})$. As
$\pi_{1}(j_{1})\not=\pi_{2}(j_{2})$, we have $j_{3}\not=j_{2}$. Also
$\pi_{2}(j_{3})=\pi_{1}(j_{1})\not=\pi_{2}(i)$ and
$\pi_{2}(j_{3})=\pi_{1}(j_{1})\not=\pi_{2}(j_{1})=i$ ensures that
$j_{3}\not\in\\{i,j_{1}\\}$. So have $j_{3}\not\in\\{i,j_{1},j_{2}\\}$ and by
the condition (3), we have $\pi_{1}(j_{3})\not=\pi_{2}(j_{2})$. Thus we get a
set $\\{\pi_{1}(j_{1}),\pi_{2}(j_{2}),\pi_{1}(j_{3})\\}$ of distinct elements.
If $\pi_{1}(j_{3})=\pi_{2}(i),$ then
$\\{\pi_{1}(j_{1}),\pi_{1}(j_{3})\\}\cup\\{\pi_{2}(j):j\not\in\\{i,j_{1},j_{3}\\}=\\{\pi_{2}(j):j\not=j_{1}\\}=\\{1,2,\ldots,i-1,i+1,\ldots,n\\}$
and we finish the proof. Suppose that $\pi_{1}(j_{3})\not=\pi_{2}(i)$ and take
$j_{4}$ so that $\pi_{2}(j_{4})=\pi_{1}(j_{3})$. Then $j_{4}\not=i$ and
$j_{4}\not=j_{3}$ by the previous proof. In fact, because
$\pi_{2}(j_{3})=\pi_{1}(j_{1})\not=\pi_{1}(j_{3})$, so
$\pi_{2}(j_{3})\not=\pi_{1}(j_{3})$, and $j_{4}\not=j_{3}$. As
$\pi_{2}(j_{4})=\pi_{1}(j_{3})\not=\pi_{2}(j_{2})$, thus we have
$j_{4}\not=j_{2}$. Also
$\pi_{2}(j_{4})=\pi_{1}(j_{3})\not=\pi_{1}(j_{2})=\pi_{2}(j_{1})=i$ implies
that $j_{4}\not=j_{1}$. So $j_{4}\not\in\\{i,j_{1},j_{2},j_{3}\\}$ and by the
condition (3), $\pi_{1}(j_{4})\not=\pi_{2}(j_{2})$. Therefore, we have
$\pi_{1}(j_{4})\not\in\\{\pi_{1}(j_{1}),\pi_{2}(j_{2}),\pi_{1}(j_{3})\\}$.
Again, if $\pi_{1}(j_{4})=\pi_{2}(i),$ then
$\\{\pi_{1}(j_{1}),\pi_{1}(j_{3}),\pi_{1}(j_{4})\\}\cup\\{\pi_{2}(j):j\not\in\\{i,j_{1},j_{3},j_{4}\\}=\\{\pi_{2}(j):j\not=j_{1}\\}=\\{1,2,\ldots,i-1,i+1,\ldots,n\\}$,
and the proof is finished. If $\pi_{1}(j_{4})\not=\pi_{2}(i)$, then, by the
condition (3), $\pi_{1}(j_{4})\not=\pi_{2}(j_{2})$ and
$\pi_{1}(j_{4})\not=\pi_{2}(j_{1})=i$. It follows that we can take
$j_{5}\not\in\\{i,j_{1},j_{2},j_{3},j_{4}\\}$ such that
$\pi_{2}(j_{5})=\pi_{1}(j_{4})$, and
$\pi_{1}(j_{5})\not\in\\{\pi_{1}(j_{1}),\pi_{2}(j_{2}),\pi_{1}(j_{3}),\pi_{1}(j_{4})\\}$.
We continue the above process until getting $j_{m}$ such that
$\pi_{2}(j_{m})=\pi_{1}(j_{m-1})$ and $\pi_{1}(j_{m})=\pi_{2}(i)$. Then we get
$\\{\pi_{1}(j_{1}),\pi_{1}(j_{3}),\ldots,\pi_{1}(j_{m})\\}\cup\\{\pi_{2}(j):j\not\in\\{i,j_{1},j_{3},\ldots,j_{m}\\}\\}=\\{\pi_{2}(j):j\not=j_{1}\\}=\\{1,2,\ldots,i-1,i+1,\ldots,n\\}$.
Hence, the conditions (1) and (2) imply $\\{\pi_{1},\pi_{2}\\}$ has Property
(C).

By checking the arguments above, one sees that, if any one of the conditions
(1) and (3) is broken, then $\\{\pi_{1},\pi_{2}\\}$ can not have Property (C).
Therefore, the conditions are also necessary. $\Box$

By the symmetry of $\pi_{1}$ and $\pi_{2}$, the condition (2) in Proposition
3.5 may be replaced by the following

(2′) For any $i$ and $j_{1},j_{2}$ with $\pi_{1}(j_{2})=\pi_{2}(j_{1})=i$, if
distinct $j_{3},\ldots,j_{m}\not\in\\{i,j_{1},j_{2}\\}$ satisfy that
$\pi_{1}(j_{3})=\pi_{2}(j_{2})$,
$\pi_{1}(j_{4})=\pi_{2}(j_{3}),\ldots,\pi_{1}(j_{m})=\pi_{2}(j_{m-1})$, then
$\pi_{2}(j_{m})\not=\pi_{1}(j_{1})$.

Corollary 3.6. Let $\pi_{1},\pi_{2}$ be permutations of $(1,2,\ldots,n)$ and
let $D=(n-2)I_{n}+P_{\pi_{1}}+P_{\pi_{2}}$. Then the $D$-type map $\Phi_{D}$
is positive if for any minimal invariant subset $F$ of $\\{\pi_{1},\pi_{2}\\}$
with $\\#F\geq 2$, $\\{\pi_{1}|_{F},\pi_{2}|_{F}\\}$ satisfies the conditions
(1) and (2) in Proposition 3.5.

Proof. The corollary is an immediate consequence of Proposition 3.5 and
Theorem 3.4. $\Box$

Before going to next section, we give a simple example of how to using the
results in this section to construct new positive linear maps.

Example 3.7. The map $\Phi:M_{5}\rightarrow M_{5}$ defined by

$(a_{ij})\mapsto\left(\begin{array}[]{ccccc}3a_{11}+a_{55}&-a_{12}&-a_{13}&-a_{14}&-a_{15}\\\
-a_{21}&2a_{22}+a_{11}+a_{44}&-a_{23}&-a_{24}&-a_{25}\\\
-a_{31}&-a_{32}&3a_{33}+a_{22}&-a_{34}&-a_{35}\\\
-a_{41}&-a_{42}&-a_{43}&2a_{44}+a_{33}+a_{55}&-a_{45}\\\
-a_{51}&-a_{52}&-a_{53}&-a_{54}&2a_{55}+a_{44}\end{array}\right)$

is positive. In fact, $\Phi$ is a $D$-type map with
$D=3I_{5}+P_{\pi_{1}}+P_{\pi_{2}}$, where $\pi_{1}$ and $\pi_{2}$ are
permutations of $(1,2,3,4,5)$ determined respectively by $(2,3,4,5,1)$ and
$(1,5,3,2,4)$. It is easily checked by Definition 3.2 or Proposition 3.5 that
$\\{\pi_{1},\pi_{2}\\}$ has the property (C). Hence the positivity of $\Phi$
follows from Theorem 3.3. We remark here that, this example is different from
those treated in the next section.

##  4\. Constructing positive $D$-type maps from cyclic permutations

The class of positive linear maps may detected by Theorem 3.3 is quite large,
which contains many known positive maps of $D$-type such as that induced by
just one permutation in [9] and that in [15] with $k=2$. Applying the results,
especially Theorem 3.3, Proposition 3.5 in the previous section, we construct
in this section some new classes of $D$-type positive maps induced by two
powers of the cyclic permutation.

In the sequel, for any integer $n\geq 3$, we denote $\pi$ the cyclic
permutation of $(1,2\ldots,n)$ defined by $\pi(i)=i+1$ mod $n$. Let $1\leq
p<q\leq n$ be two integers. Consider the $D$-type map induced by
$\pi^{p},\pi^{q}$ with $D=(n-2)I_{n}+P_{\pi^{p}}+P_{\pi^{q}}$. We shall give
an easily handled criterion for $\Phi_{n,p,q}=\Phi_{D}$ to be positive. Note
that $q=n$ implies $\pi^{q}={\rm id}$ and
$D=(n-2)I_{n}+P_{\pi^{p}}+P_{\pi^{n}}=(n-1)I_{n}+P_{\pi^{p}}$. So, $\Phi_{D}$
is positive by [9, 14] whenever $q=n$ and it is also clear that
$\\{\pi^{p},{\rm id}\\}$ has the property (C). Thus we may assume $q<n$ in the
following lemma.

Lemma 4.1. Let $\pi$ be the permutation of $(1,2,\ldots,n)$ defined by
$\pi(i)=i+1$ (mod $n$). For any $1\leq p<q<n$, $\\{\pi^{p},\pi^{q}\\}$ has the
property (C) if and only if one of the following conditions holds.

(1) $q-p=1$.

(2) $1<q-p<n-1$ and if there are relatively prime positive integers $k,m$ with
$m<n$ and $k<q-p$ such that $m(q-p)={kn}$, then $p=n-d(q-p)$ for some integer
$1\leq d\leq m-1$.

Proof. If $q-p=1$, then it is clear that $\\{\pi^{p},\pi^{q}\\}$ has property
(C).

So, to prove the lemma, it suffices to show that, for any $p,q$ with
$1<q-p<n-1$ and $1\leq p<q\leq n-1$, $\\{\pi^{p},\pi^{q}\\}$ does not have
property (C) if and only if there exist relatively prime integers $k,m$ with
$0<k<q-p$ and $0<m<n$ such that $m(q-p)=kn$ and $p\not=n-d(q-p)$ for any
integer $d$ with $2\leq d\leq m-1$. By Proposition 3.5, it suffices to check
the following two claims.

Claim 1. $\\{\pi_{1}=\pi^{p},\pi_{2}=\pi^{q}\\}$ does not satisfy the
condition (1) of Proposition 3.5 if and only if $2(q-p)=n$ and
$p\not=n-(q-p)$.

In fact, $\\{\pi_{1},\pi_{2}\\}$ does not meet the condition (1) of
Proposition 3.5 if and only if

$i+p\ {\rm mod}\ n=\pi_{1}(i)=\pi_{2}(j)=j+q\ {\rm mod}\ n$

and

$i+q\ {\rm mod}\ n=\pi_{2}(i)=\pi_{1}(j)=j+p\ {\rm mod}\ n$

for some distinct $i,j$. This happens if and only if $2(q-p)=0$ mod $n$, and
in turn, if and only if $n=2(q-p)$ as $q\leq n$. It is clear that $p$ can not
be $n-(q-p)$, because this would imply that $q=n$.

Claim 2. $\\{\pi_{1}=\pi^{p},\pi_{2}=\pi^{q}\\}$ does not satisfy the
condition (2) of Proposition 3.5 if and only if $m(q-p)=kn$ for some
relatively prime positive integers $k,m$ with $1\leq k<q-p$, $2<m<n$, and
$p\not=n-d(q-p)$ for any $1<d<m-1$.

$\\{\pi_{1}=\pi^{p},\pi_{2}=\pi^{q}\\}$ does not satisfy the condition (2) of
Proposition 3.5 if and only if for some $i$, there exist distinct
$j_{1},\ldots,j_{m}\not\in\\{i\\}$ such that
$\pi_{1}(j_{2})=\pi_{2}(j_{1})=i$, $\pi_{2}(j_{3})=\pi_{1}(j_{1})$,
$\pi_{2}(j_{4})=\pi_{1}(j_{3}),\ldots,\pi_{2}(j_{m})=\pi_{1}(j_{m-1})$ and
$\pi_{1}(j_{m})=\pi_{2}(j_{2})$, and in turn, if and only if for some $i$
there exist distinct $j_{1},\ldots,j_{m}\not\in\\{i\\}$ such that

$None$ $\begin{array}[]{rl}j_{1}+q=&j_{2}+p\ {\rm mod}\ n,\\\
j_{3}+q=&j_{1}+p\ {\rm mod}\ n,\\\ j_{4}+q=&j_{3}+p\ {\rm mod}\ n,\\\
\vdots&\\\ j_{m}+q=&j_{m-1}+p\ {\rm mod}\ n,\\\ j_{2}+q=&j_{m}+p\ {\rm mod}\
n.\end{array}$

Summing up all equations in Eq.(4.1) we obtain that

$m(q-p)=0\ \ {\rm mod}\ n.$

Note that $2\leq m<n$; thus there exists positive integer $k<q-p$ such that

$None$ $m(q-p)=kn.$

Moreover, $j_{h}=j_{1}-(q-p)(h-2)=j_{2}-(q-p)(h-1)$ mod $n$ for
$h=3,4,\ldots,m$. Obviously, $j_{1},j_{2}\not\in\\{i\\}$. While
$j_{3},\ldots,j_{m}\not\in\\{i\\}$ implies that $j_{h}\not=j_{1}+q=j_{2}+p$
mod $n$ for any $h=3,4,\ldots,m$. It is clear that $j_{h}=i=j_{1}+q=j_{2}+p$
mod $n$ for some $j_{h}=j_{1}-(q-p)(h-2)=j_{2}-(q-p)(h-1)$ mod $n$ if and only
if $j_{1}+q=j_{1}-(q-p)(h-2)$ and $j_{2}+p=j_{2}-(q-p)(h-1)$, and in turn, if
and only if $p=n-(q-p)(h-1)=n-d(q-p)$ for some $2\leq d\leq m-1$. So,
$j_{1},\ldots,j_{m}\not\in\\{i\\}$ implies that $p\not=n-d(q-p)$ for any
$2\leq d<m$. Thus we proved that $\\{\pi^{p},\pi^{q}\\}$ does not satisfies
Condition (2) of Proposition 3.6 implies that $m(q-p)=kn$ for some relatively
prime positive integers $m,k$ with $1\leq k<q-p$, $1\leq m<n$, and

$None$ $p\not=n-d(q-p)\quad{\rm for\ every}\ 2\leq d\leq m-1.$

Conversely, assume that Eq.(4.2) and Eq.(4.3) hold. Take any $j_{1},j_{2}$ so
that $j_{2}-j_{1}=q-p$ mod $n$. Then $j_{2}=j_{1}+(q-p)$ mod $n$. If $m=2$, we
must have $2(q-p)=n$ and hence $j_{2}+(q-p)=j_{1}+2(q-p)=j_{1}$ mod $n$, which
gives $j_{2}+q=j_{1}+p$ mod $n$. If $m\geq 3$, for $3\leq h\leq m$, let

$None$ $j_{h}=j_{1}-(q-p)(h-2)=j_{2}-(q-p)(h-1)\ \ {\rm mod}\ n.$

Then $j_{2}=j_{m}+(q-p)(m-1)$ mod $n$ and hence $j_{2}+q-p=j_{m}$ mod $n$ as
$(q-p)m=kn$. This ensures that $j_{2}+q=j_{m}+p$ mod $n$. We claim that
$j_{h}\not=j_{s}$ whenever $t\not=s$. In fact, it is clear that
$j_{1}\not=j_{2}$; for $3\leq h,s\leq m$,

$j_{h}=j_{s}\Leftrightarrow j_{1}-(q-p)(h-2)=j_{1}-(q-p)(s-2)\Leftrightarrow
h=s.$

Moreover, the Eqs.(4.3) and (4.4) imply that
$j_{1},\ldots,j_{m}\not\in\\{i\\}$. Hence Eq.(4.2) and Eq.(4.3) imply that
$\\{\pi^{p},\pi^{q}\\}$ does not satisfies the condition (2) of Proposition
3.5.

Now, by Proposition 3.5, Claims 1-2 ensure that the lemma holds, completing
the proof. $\Box$

Using Lemma 4.1, the following criterion of positivity of $\Phi_{n,p,q}$ is
immediate, which is very easily applied.

Theorem 4.2. Let $n\geq 3$ and $\pi$ be the permutation defined by
$\pi(i)=i+1$ mod $n$. For any integers $1\leq p<q\leq n$, let
$D=(n-2)I_{n}+P_{\pi^{p}}+P_{\pi^{q}}$. Then the $D$-type map
$\Phi_{n,p,q}=\Phi_{D}:M_{n}\rightarrow M_{n}$ of the form Eq.(1.1) is
positive if one of the following conditions holds.

(1) $q-p=1$ or $q=n$.

(2) $q<n$, $1<q-p<n-1$ and if there are relatively prime positive integers
$k,m$ with $m<n$ and $k<q-p$ such that $m(q-p)={kn}$, then $p=n-d(q-p)$ for
some integer $1\leq d\leq m-1$.

We remark that in general the condition $q-p=\frac{kn}{m}$ does not imply that
$q-p$ is a factor of $n$. For example, let $n=8$, $q-p=6$; then $m=3$ and
$k=4$. If $p=8-6=2,q=8$, then $\\{\pi^{2},\pi^{8}\\}$ has property (C). But,
$\\{\pi^{1},\pi^{7}\\}$ does not posses property (C).

The following corollary is immediate.

Corollary 4.3. The $D$-type map $\Phi_{n,p,q}:M_{n}\rightarrow M_{n}$ in
Theorem 4.2 is positive if any one of the following conditions holds.

(1) $q-p=1$ or $q=n$.

(2) $n$ is prime.

(3) There are no relatively prime $m,k$ with $1\leq m<n$ and $1\leq k<q-p$ so
that $m(q-p)=kn$.

(4) $q-p$ is prime and is not a factor of $n$. Particularly, if $q-p=2$ and
$n$ is odd.

(5) $q-p$ is a prime factor of $n$ and $p=d(q-p)$ for some $1\leq
d\leq\frac{n}{q-p}-2$.

Proof. The implication (1) $\Rightarrow\Phi_{D}$ is positive is clear by
Theorem 4.2.

If (2) holds, that is, if $n$ is prime, then there are no relative prime
positive integers $m<n,k<q-p$ such that $m(q-p)=kn$. Hence, for any $1\leq
p<q\leq n$, $\\{\pi^{p},\pi^{q}\\}$ has property (C).

(3) entails that $\\{\pi^{p},\pi^{q}\\}$ meets the condition (2) in Theorem
4.2 and hence $\Phi_{n,p,q}$ is positive.

If (4) holds, that is, if $q-p$ is prime and is not a factor of $n$, then
$n=\frac{m(q-p)}{k}$ implies that $m=kr$ for some integer $r$ and $n=r(q-p)$,
which is impossible. So $\\{\pi^{p},\pi^{q}\\}$ meets the condition (2) of
Theorem 4.2 and thus $\Phi_{n,p,q}$ is positive.

The condition (5) implies that $m_{1}(q-p)=kn$ and the greatest common divisor
of $m_{1}$ and $k$ is 1 if and only if $m_{1}=m$ and $k=1$ as $q-p$ is prime.
As $p=d(q-p)=n-(m-d)(q-p)$, $\\{\pi^{p},\pi^{q}\\}$ has property (C) by Lemma
4.1. $\Box$

Since, in quantum information theory, an $N$-qbit quantum system corresponds
to a complex Hilbert space of dimension $2^{N}$, the case $n=2^{N}$ is of
special importance.

Corollary 4.4. For $n=2^{N}$ with $N\geq 2$ and $1\leq p<q<n$, the $D$-type
map $\Phi_{{2^{N}},p,q}:M_{n}\rightarrow M_{n}$ in Theorem 4.2 is positive if
one of the following holds:

(1) $q-p$ is odd.

(2) $q-p=2^{b}$ with $1\leq b\leq N-1$ and $p=d2^{b}$ for some $1\leq d\leq
2^{N-b}-1$.

(3) $q-p=2^{b}r$ with $r$ odd and $p=2^{b}(2^{N-b}-dr)$ for some $1\leq
d\leq\frac{2^{N-b}-1}{r}$.

In the following we present some simple examples to illustrate how to use the
results in this section.

Example 4.5. For $n=5$ or $7$ and any $1\leq p<q\leq n$, the $D$-type maps
$\Phi_{5,p,q}:M_{5}\rightarrow M_{5}$ and $\Phi_{7,p,q}:M_{5}\rightarrow
M_{5}$ are always positive.

Observe that $\Phi_{5,1,3}$ is of the form

$\left(\begin{array}[]{ccccc}a_{11}&a_{12}&a_{13}&a_{14}&a_{15}\\\
a_{21}&a_{22}&a_{23}&a_{24}&a_{25}\\\ a_{31}&a_{32}&a_{33}&a_{34}&a_{35}\\\
a_{41}&a_{42}&a_{43}&a_{44}&a_{45}\\\
a_{51}&a_{52}&a_{53}&a_{54}&a_{55}\end{array}\right)\mapsto$
$\small\left(\begin{array}[]{ccccc}2a_{11}+a_{22}+a_{44}&-a_{12}&-a_{13}&-a_{14}&-a_{15}\\\
-a_{21}&2a_{22}+a_{33}+a_{55}&-a_{23}&-a_{24}&-a_{25}\\\
-a_{31}&-a_{32}&2a_{33}+a_{44}+a_{11}&\\-a_{34}&-a_{35}\\\
-a_{41}&-a_{42}&-a_{43}&2a_{44}+a_{55}+a_{22}&-a_{45}\\\
-a_{51}&-a_{52}&-a_{53}&a_{54}&2a_{55}+a_{11}+a_{33}\end{array}\right),$

which is positive by Corollary 4.3.

It is also obvious that when $n=4$, $\Phi_{4,p,q}$ is positive if $q-p\not=2$;
when $n=6$, $\Phi_{6,p,q}$ is positive if $q-p\not\in\\{2,3,4\\}$.

Example 4.6. For $n=8=2^{3}$, and any $1\leq p<q\leq 8$, the $D$-type map
$\Phi_{8,p,q}:M_{8}\rightarrow M_{8}$ is positive if one of the following is
true:

(i) $q-p\in\\{1,3,5,7\\}$.

(ii) $q-p=2$, $p\in\\{2,4,6\\}$.

(iii) $q-p=4$, $p=4$.

(iv) $q-p=6$, $p=2$.

Example 4.7. For $n=16=2^{4}$, and any $1\leq p<q\leq 16$, the $D$-type map
$\Phi_{16,p,q}:M_{16}\rightarrow M_{16}$ is positive if one of the following
is true:

(i) $q-p\in\\{1,3,5,7,9,11,13,15\\}$.

(ii) $q-p=2$ and $p\in\\{2,4,6,8,10,12,14\\}$.

(iii) $q-p=4$ and $p\in\\{4,8,12\\}$.

(iv) $q-p=6$ and $p\in\\{4,10\\}$.

(v) $q-p=8$ and $p=8$.

(vi) $q-p=10$ and $p=6$.

(vii) $q-p=12$ and $p=4$.

(viii) $q-p=14$ and $p=2$.

Remark 4.8. The condition that $\\{\pi^{p},\pi^{q}\\}$ has property (C) in
Theorem 4.2 is sufficient for the associated $D$-type map $\Phi_{n,p,q}$ to be
positive. The condition is not necessary, and thus, the condition in Theorem
3.3 is not necessary for $\Phi_{D}$ to be positive. For example, let us
consider the case of $n=4$. Then, $\\{\pi^{p},\pi^{q}\\}$ does not have
property (C) if and only if $p=1,q=3$. By Lemma 3.1, the $D$-type map
$\Phi_{4,1,3}=\Phi_{D}$ with $D=2I_{4}+P_{\pi}+P_{\pi^{3}}$ is positive if and
only if

$f(x_{1},x_{2},x_{3},x_{4})=\frac{x_{1}}{2x_{1}+x_{2}+x_{4}}+\frac{x_{2}}{2x_{2}+x_{3}+x_{1}}+\frac{x_{3}}{2x_{3}+x_{4}+x_{2}}+\frac{x_{4}}{2x_{4}+x_{1}+x_{3}}\leq
1$

holds for all non-negative $x_{1},\ldots,x_{4}\in{\mathbb{R}}$ with
$x_{1}+\cdots+x_{4}=1$. By Lemma 2.2, all extremum values of
$f(x_{1},x_{2},x_{3},x_{4})$ is $1$ because $s=M=2$. Consider the supremum of
$f$ on the boundary. Assume that only one of $x_{i}$ is zero, say $x_{4}=0$;
then

$f(x_{1},x_{2},x_{3},0)=\frac{x_{1}}{2x_{1}+x_{2}}+\frac{x_{2}}{2x_{2}+x_{3}+x_{1}}+\frac{x_{3}}{2x_{3}+x_{2}}$

with $x_{1},x_{2},x_{3}$ nonzero. Consider the function

$g(s,t)=\frac{1}{2+s+t}+\frac{1}{2+\frac{1}{s}}+\frac{1}{2+\frac{1}{t}}=\frac{1}{2+s+t}+\frac{s}{2s+1}+\frac{t}{2t+1},$

where $s>0$ and $t>0$. As

$\begin{array}[]{rl}&(2s+1)(2t+1)+s(s+t+2)(2t+1)+t(s+t+2)(2s+1)\\\
=&4s^{2}t+4st^{2}+14st+s^{2}+t^{2}+4s+4t+1,\end{array}$
$(2s+1)(2t+1)(s+t+2)=4s^{2}t+4st^{2}+12st+2s^{2}+2t^{2}+5s+5t+2$

and $2st<s^{2}+t^{2}+s+t+1$, it is easily checked that
$g(s,t)=1-\frac{(s-t)^{2}+s+t+1}{(2s+1)(2t+1)(s+t+2)}<1$. So we still have
$f(x_{1},x_{2},x_{3},0)<1$. If there are more than one $x_{i}=0$, it is clear
that $f(x_{1},x_{2},x_{3},x_{4})<1$. Therefore, $\sup
f(x_{1},x_{2},x_{3},x_{4})=1$ on the region $x_{1}+\cdots+x_{4}=1$ and
$\Phi_{D}$ is positive.

It is then interesting to ask

Question 4.9. What is the necessary and sufficient condition for
$\Phi_{n,p,q}=\Phi_{D}:M_{n}\rightarrow M_{n}$ with
$D=(n-1)I_{n}+P_{\pi^{p}}+P_{\pi^{q}}$ to be positive? Where $\pi$ is the
permutation defined by $\pi(i)=i+1$ mod $n$ and $1\leq p<q<n$.

## References

  * [1] P. Albert and A. Uhlmanm, A problem relating to positive linear maps on matrix algebras, Rep. Math. Phys. 18 (1980), 163.
  * [2] R. Augusiak, J. Bae, L. Czekaj, M. Lewenstein, On structural physical approximations and entanglement breaking maps, J. Phys. A: Math. Theor. 44 (2011) 185308.
  * [3] A. Chefles, R. Jozsa, and A. Winter, On the existence of physical transformations between sets of quantum states, International J. Quantum Information, 2 (2004), 11-21.
  * [4] M.-D. Choi, Completely Positive Linear Maps on Complex Matrix, Lin. Alg. Appl. 10 (1975), 285-290.
  * [5] D. Chru$\acute{s}$ci$\acute{n}$ski and A. Kossakowski, Spectral conditions for positive maps, Comm. Math. Phys. 290 (2009) 1051.
  * [6] Roger A. Horn, Charles R. Johnson, Matrix Analysis, Cambridge Univ. Press, 1985, New York.
  * [7] J.-C. Hou, A characterization of positive linear maps and criteria for entangled quantum states, J. Phys. A: Math. Theor. 43 (2010) 385201..
  * [8] J.-C. Hou, Acharacterization of positive elementary operators, J. Operator Theory, 39 (1998), 43-58.
  * [9] J.-C. Hou, C.-K.Li, Y.-T.Poon, X.F. Qi, and N.-S. Sze, Criteria of $k$-positivity of linear maps, ArXiv: 1211.0386v1[quant-ph].
  * [10] Z. Huang, C.-K. Li, E. Poon, N.-K. Sze, Physical transformation between quantum states, arXiv:1203.5547
  * [11] K. Kraus, States, Effects, and Operations: Fundamental Notions of Quantun Theory, Lecture Notes in Physics, Vol.190.Spring-Verlag,Berlin, 1983.
  * [12] C.-K. Li and Y.-T. Poon, Interpolation by Completely Positive Maps, Linear and Multilinear Algebra 59 (2011), 1159-1170.
  * [13] M. A. Nielsen and I.L. Chuang, Quantum Computation and Quantum Information ,Cambridge University Press, Cambridge, 2000
  * [14] X.-F. Qi and J.-C. Hou, Positive finite rank elementary operators and characterizing entanglement of states, J.Phys. A: Math.Theor. 44 (2011) 215305
  * [15] S. Yamagami, Cyclic inequalities, Proc. Amer. Math. Sco., 118 (1993), 521-527.


[acronym]long-short footnote []

11institutetext: Boise State University 11email:
kennyballou<EMAIL_ADDRESS>
# muRelBench: MicroBenchmarking for Zonotope Domains

Kenny Ballou  0000-0002-6032-474X Elena Sherman  0000-0003-4522-9725

###### Abstract

We present muRelBench, a suite of synthetic benchmarks for weakly-relational
abstract domains and their operations. For example, the benchmarks can support
experimental evaluations of proposed algorithms such as domain closure.

###### Keywords:

Weakly-Relational Abstract Domains Benchmarks Tests

##  1 Introduction

Zonotopes [9], relational numerical abstract domains, are widely used in
program and system verification using static analysis and model-checking
techniques and, recently, found their way into the verification of neural
networks [10]. To reason about their computations, verifiers manipulate
abstract domains through a predefined set of operations, e.g., Least-Upper
Bound (LUB), closure, or forget operators [14]. Such manipulations of abstract
states commonly dominate the computation time of a verifier. Thus, there has
been extensive research on improving the efficiency of operations of Zonotopes
such as closure [1, 3, 7, 14, 17].

While the new algorithms provide their complexity estimates, empirically
evaluating their results remains crucial to comprehensively assessing their
impact. Commonly, such evaluations are performed in the context of a verifier
and its target, e.g., a data-flow analyzer using Zones [12, 13] on a set of
programs. However, depending on program structure and semantics [2], one may
or may not detect the effect of the new operation on Zones. Thus, the question
becomes whether the set of programs is not representative or the
implementation of the new algorithm is inefficient and requires additional
tuning. Because of the complexity of Zonotope states, it is difficult to
assess whether a verifier produces states with properties that a novel
operation algorithm takes an advantage of.

This problem is known to other research communities such as software
engineering and compiler optimization community, which they solv by
establishing microbenchmarking frameworks [11]. Microbenchmarking isolates the
effects of a specific technique such as a certain optimization on
syntactically generated code with desired features. In this work, we introduce
an extensible muRelBench microbenchmarking framework for Zonotopes that is
built on top of the JMH [15, 16] profiling tool for Java programs. muRelBench
eliminates verifier and program dependencies and focuses on specific
operations of parameterized Zonotope states.

For a given type of Zonotope domain, $Z$ and its operation $ops$, muRelBench
takes as an input set of predefined parameters for each characteristic of the
corresponding $Z$ typed abstract domain. Then the framework exhaustively
generates abstract states corresponding to each element of the Cartesian
product of those parameters and applies $ops$ and correctness checks, if any,
within the JMH context. Upon the completion of experiments, muRelBench writes
the runtime results for each abstract domain to a Comma-Separated Values (CSV)
file, that researchers can use for further evaluations.

In its current version, generation of abstract states is parameterized by the
number of variables and variable connectivity for Octagon($Z$) [14]. Thus,
synthetically generated matrices that encode Octagon states vary in their size
and density. muRelBench implements two closure operations ($ops$): Full
Transitive Closure (using Floyd-Warshall all pairs shortest path [5]) and
Chawdhary [3] incremental closure. However, as we describe in the next
section, muRelBench can be easily extended to different $Z$ and $ops$ types.

Thus, this microbenchmarking framework has the following three key features:
(1) dynamic generation of parameterized abstract states, (2) application of
user defined operations on them, and (3) checks to user-defined properties,
e.g., pre/post conditions on Zonotope states before and after executing
operations. We believe that muRelBench will help rapid prototyping of abstract
operations and evaluating the efficiency of existing implementations.

In the next section 2, we describe framework details and explain how it
generates different abstract states. To demonstrate the usefulness of
muRelBench, in Section 3, we present a case study on runtime data of the two
closure operators on Octagon states. We conclude the paper with future work on
muRelBench.

##  2 muRelBench Framework

Figure 1 provides overview of muRelBench’s components. In the dashed rounded
rectangle are user-defined components of an abstract domain type $Z$,
operations, e.g., $ops1$, and property checks of the state after $ops1$
modifies the abstract state. These bindings are defined at compile-time.
_State generator_ component takes generation parameters $N$ and $C$, and $Z$
type, and randomly (up to the seed) generates $N\times C$ abstract states.

_Benchmarking_ component takes the generated states and applies $ops1$ state
operation and checks the results with $check1$. The component also takes the
runtime parameters for JMH that defines what type or runtime data to collect
and how many times to repeat the experiments. Upon completion, the data is
written to a CSV file.

$ops1$$check1$…$Z$_State generator_ $\displaystyle N$
$\displaystyle=\\{25,50,\cdots\\},$ $\displaystyle C$
$\displaystyle=\\{.1,.2,\cdots\\}$ $R=\\{\text{average},3\text{
runs}\\}$_Benchmarking_ Runtime data for each $N\times C$ Figure 1: Component
diagram of muRelBench, specifying the framework’s and user-defined components.

The framework is implemented in Java and uses interfaces and abstract classes
to extend user-defined components. JMH provides a strong foundation for
constructing and executing profiling benchmarks whilst minimizing confounding
runtime variables such as Java Virtual Machine (JVM) startup, Just-in-Time
(JIT) warmup, Garbage Collection (GC) pauses.

The framework has extension for Octagon abstract domain, i.e., $Z=Octagon$.
The implementation encodes Octagon constraints, which are constraints of the
form: $\pm{}x\pm{}y\leq c$, where $x,y\in V$ where $V$ is the set of variables
and $c\in\mathbb{I}$, where $\mathbb{I}$ is one of $\mathbb{R}$, $\mathbb{Q}$,
or $\mathbb{Z}$. Octagons are encoded as 2-dimensional array difference
bounded matrix (DBM) [6] in the OctagonDBM class.

To extend operations over Octagons, users would provide extensions to
OctagonDBM, overriding various operations with their implementation they wish
to test. Furthermore, they would provide additional instances of *Bench, e.g.,
JoinBench. Similar to JUnit [4], the naming is conventional: muRelBench
automatically includes classes containing the Bench suffix.

### User extension beyond Octagons

It is reasonably straightforward to extend muRelBench with additional abstract
domains. A user must provide three additional classes: the abstract container
type for the domain, e.g., ZoneDBM to add Zones [12]; a builder for the new
abstract type; and finally, a state type which provides the different
parameterization sets for JMH.

##  3 Octagons and Closure Operation Case Study

### Benchmark Set Up

We examine the benefits of muRelBench in a case study. The framework randomly
generates Octagons, varying the “density” of relations between variables to
create a continuum of synthetic instances of Octagons. This density
progression roughly correlates to the different instances of Octagons from
real programs. That is, early in analysis, variables have a tendency to have
few relations as only few program statements are explored. In the middle of
analysis, after exploring several assignment statements, variables become
tightly coupled with one another. Finally, after several fixed point
iterations and widening operations, islands of connectivity emerge [8, 7, 18].
Furthermore, we also vary the number of variables of the synthetic Octagons to
account for different programs sizes.

For this case study, we generate Octagons with $25$, $50$, and $100$ program
variables, i.e., $50$, $100$, and $200$ variables using the Octagon variable
encoding [14]. For each size, we generate Octagons with $10\%-90\%$ density,
in $10\%$ increments. The Cartesian product of these parameters results in
$27$ Octagon instances.

Using JMH, we default to $3$ “warmup” iterations and $5$ experimental
iterations for each benchmark. Thus, for a single benchmark, the operation
under test executes $216$ times. However, we do provide options for the user
to modify and otherwise specify their own desired warmup and experimental
iterations, among other options available via JMH.

### Case Study

In this case study we chose to evaluate different closure algorithms for
Octagon abstract domain. The closure represents a critical operation for
static program analysis and abstract interpretation because it provides
critical functions: normalization for equality comparisons for data-flow
analysis (DFA) [1] and precision benefits for other domain operations such as
LUB [13].

Canonicalizing or normalizing Octagon states is a necessary operation because
an Octagonal bounded region can be represented by infinitely many different
Octagons. The closure operation normalizes an Octagon by making explicit
implicit edges and minimizing edge weights between variables within the
Octagons. In the simplest case, this amounts to computing the all-pairs
shortest-path problem for the directed, weighted graph used to represent the
Octagon.

There exist several algorithms for computing the all-pairs-shortest-path
problem for weighted-directed graphs such as Floyd-Warshall and Bellman-Ford
algorithms [5]. While these algorithms are relatively simple and
straightforward to implement, their cost can be excessive. Floyd-Warshall, for
example has cubic time complexity, $\Theta(n^{3})$, where $n$ is the number of
variables in the abstract Octagon state.

Chawdhary et al. [3] proposed an incremental closure algorithm for Octagons
which uses code motion and hoisting to minimize the number of comparisons
required to incrementally close an Octagon. Thus, they were able to reduce the
incremental closure, a modified Floyd-Warshall, to $O(20n^{2}-4n)$.

Closure | Program | Mean (ms) | $\sigma$
---|---|---|---
Floyd-Warshall | Fibonacci | 144 | 32.2
Loop | 46.8 | 3.1
Chawdhary | Fibonacci | 117 | 5.1
Loop | 49.6 | 10.3
Table 1: Small programs used to demonstrate performance characteristics of
using different closure algorithms.

Clearly, these two algorithms should have a different runtime growth with the
increased number of variables. We first examined their result in the context
of DFA on two small programs to see if any differences can be detected. Table
1 shows the results of the full-closure algorithm Floyd-Warshall and the
Chawdhary et al’s incremental closure. The data is averaged over five
executions and includes the mean runtime for each along with their standard
deviation. As the data shows that the results are not that conclusive since on
Loop program Floyd-Warshall performed better while Chawdhary runs faster on
Fibonacci. When we analyzed the properties of two program, we discovered that
Fibonacci algorithm had the maximum of $6$ variables with density of $72\%$
and Loop program had two variables with no density, which is purely interval.

Plots in Fig. 2 show the results of the comparison of the two closure
algorithm on benchmarks that muRelBench generates and runs. Each plot presents
runtime data for different values of $N$ while varying in density of
connections between variables. Using this detailed data we can discern
instances where the algorithm proposed by Chawdhary et al. outperforms full
closure. Both algorithms are almost indistinguishable in the first two plots.
For the plot with largest $N=100$ we can see that, depending on the density
value, one algorithm performs better than the other. For lower density states,
Floyd-Warshall tends to perform better while for higher densities Chawdhary’s
incremental closure has better runtime data.

0.00.10.20.30.40.50.6

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

0.00.10.20.30.40.50.6

Average Time (ms)

DensityFloydWarshallChawdhary$N=25$

\makebox(0.0,0.0)[]{{}}

Density$N=50$

\makebox(0.0,0.0)[]{{}}

Density$N=100$ Figure 2: Plots of microbenchmark results of closure
operations, each subplot varies the number of variables, each sample varies
the connectivity of program variables.

##  4 Conclusion and Future Work

In this paper, we present the abstract interpretation research community with
muRelBench benchmarking framework that provides standardized and uniform
support for comparing different operations within Zonotope abstract domains.
When developing new algorithms or new abstract domains, a standard set of
benchmarks and a framework to easily test them helps convince the community of
their value.

Our framework of generated benchmarks invites many improvements and future
work to make it better suited for the research community and software
engineers at large. For example, we invite contributions of additional
algorithms to be added to the suite, so others can use the results in their
comparisons. Additionally, more parameters could provide a wider surface area
of study for different Zonotope operations.

## References

  * [1] Ballou, K., Sherman, E.: Incremental transitive closure for zonal abstract domain. In: Deshmukh, J.V., Havelund, K., Perez, I. (eds.) NASA Formal Methods. pp. 800–808. Springer International Publishing, Cham (5 2022). https://doi.org/10.1007/978-3-031-06773-0_43, http://dx.doi.org/10.1007/978-3-031-06773-0_43
  * [2] Brunner, R., Dyer, R., Paquin, M., Sherman, E.: Paclab: A program analysis collaboratory. In: Proceedings of the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering. ESEC/FSE ’20, ACM (11 2020). https://doi.org/10.1145/3368089.3417936, http://dx.doi.org/10.1145/3368089.3417936
  * [3] Chawdhary, A., Robbins, E., King, A.: Incrementally closing octagons. Formal Methods in System Design 54(2), 232–277 (1 2018). https://doi.org/10.1007/s10703-017-0314-7, http://dx.doi.org/10.1007/s10703-017-0314-7
  * [4] Contributors, M.: Junit (2024), https://junit.org/
  * [5] Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms. Computer science, McGraw-Hill (2009). https://doi.org/10.1.1.708.9446, https://books.google.com/books?id=aefUBQAAQBAJ
  * [6] Dill, D.L.: Timing assumptions and verification of finite-state concurrent systems. Lecture Notes in Computer Science pp. 197–212 (1990). https://doi.org/10.1007/3-540-52148-8_17, http://dx.doi.org/10.1007/3-540-52148-8_17
  * [7] Gange, G., Ma, Z., Navas, J.A., Schachte, P., Søndergaard, H., Stuckey, P.J.: A fresh look at zones and octagons. ACM Transactions on Programming Languages and Systems 43(3), 1–51 (9 2021). https://doi.org/10.1145/3457885, http://dx.doi.org/10.1145/3457885
  * [8] Gange, G., Navas, J.A., Schachte, P., Søndergaard, H., Stuckey, P.J.: Exploiting sparsity in difference-bound matrices. Lecture Notes in Computer Science pp. 189–211 (2016). https://doi.org/10.1007/978-3-662-53413-7_10, http://dx.doi.org/10.1007/978-3-662-53413-7_10
  * [9] Ghorbal, K., Goubault, E., Putot, S.: The zonotope abstract domain taylor1+. Lecture Notes in Computer Science pp. 627–633 (2009). https://doi.org/10.1007/978-3-642-02658-4_47, http://dx.doi.org/10.1007/978-3-642-02658-4_47
  * [10] Jordan, M., Hayase, J., Dimakis, A., Oh, S.: Zonotope domains for lagrangian neural network verification. Advances in Neural Information Processing Systems 35, 8400–8413 (2022)
  * [11] Laaber, C., Leitner, P.: An evaluation of open-source software microbenchmark suites for continuous performance assessment. In: Proceedings of the 15th International Conference on Mining Software Repositories. ICSE ’18, ACM (5 2018). https://doi.org/10.1145/3196398.3196407, http://dx.doi.org/10.1145/3196398.3196407
  * [12] Miné, A.: A new numerical abstract domain based on difference-bound matrices. Lecture Notes in Computer Science pp. 155–172 (2001). https://doi.org/10.1007/3-540-44978-7_10, http://dx.doi.org/10.1007/3-540-44978-7_10
  * [13] Miné, A.: Weakly Relational Numerical Abstract Domains (12 2004), https://pastel.archives-ouvertes.fr/tel-00136630
  * [14] Miné, A.: The octagon abstract domain. Higher-Order and Symbolic Computation 19(1), 31–100 (3 2006). https://doi.org/10.1007/s10990-006-8609-1, http://dx.doi.org/10.1007/s10990-006-8609-1
  * [15] Oracle: jmh (2024), https://openjdk.org/projects/code-tools/jmh/
  * [16] Oracle: openjdk/jmh (2024), https://github.com/openjdk/jmh
  * [17] Schwarz, M., Seidl, H.: Octagons revisited. Lecture Notes in Computer Science p. 485–507 (2023). https://doi.org/10.1007/978-3-031-44245-2_21, http://dx.doi.org/10.1007/978-3-031-44245-2_21
  * [18] Singh, G., Püschel, M., Vechev, M.: Making numerical program analysis fast. ACM SIGPLAN Notices 50(6), 303–313 (8 2015). https://doi.org/10.1145/2813885.2738000, http://dx.doi.org/10.1145/2813885.2738000


# Semi-supervised Clustering for Short Text via Deep Representation Learning

Zhiguo Wang  Haitao Mi  Abraham Ittycheriah
IBM T.J. Watson Research Center
Yorktown Heights, NY, USA
{zhigwang, hmi<EMAIL_ADDRESS>
###### Abstract

In this work, we propose a semi-supervised method for short text clustering,
where we represent texts as distributed vectors with neural networks, and use
a small amount of labeled data to specify our intention for clustering. We
design a novel objective to combine the representation learning process and
the k-means clustering process together, and optimize the objective with both
labeled data and unlabeled data iteratively until convergence through three
steps: (1) assign each short text to its nearest centroid based on its
representation from the current neural networks; (2) re-estimate the cluster
centroids based on cluster assignments from step (1); (3) update neural
networks according to the objective by keeping centroids and cluster
assignments fixed. Experimental results on four datasets show that our method
works significantly better than several other text clustering methods.

##  1 Introduction

Text clustering is a fundamental problem in text mining and information
retrieval. Its task is to group similar texts together such that texts within
a cluster are more similar to texts in other clusters. Usually, a text is
represented as a bag-of-words or term frequency-inverse document frequency
(TF-IDF) vector, and then the k-means algorithm [MacQueen (1967] is performed
to partition a set of texts into homogeneous groups.

However, when dealing with short texts, the characteristics of short text and
clustering task raise several issues for the conventional unsupervised
clustering algorithms. First, the number of uniqe words in each short text is
small, as a result, the lexcical sparsity issue usually leads to poor
clustering quality [Dhillon and Guan (2003]. Second, for a specific short text
clustering task, we have prior knowledge or paticular intenstions before
clustering, while fully unsupervised approaches may learn some classes the
other way around. Take the sentences in Table 1 for example, those sentences
can be clustered into different partitions based on different intentions:
_apple_ {a, b, c} and _orange_ {d, e, f} with a fruit type intension, or
_what-question_ {a, d}, _when-question_ {b, e}, and _yes/no-question_ cluster
{c, f} with a question type intension.

(a) What’s the color of apples?
---
(b) When will this apple be ripe?
(c) Do you like apples?
(d) What’s the color of oranges?
(e) When will this orange be ripe?
(f) Do you like oranges?
Table 1: Examples for short text clustering.

To address the lexical sparity issue, one direction is to enrich text
representations by extracting features and relations from Wikipedia [Banerjee
et al. (2007] or an ontology [Fodeh et al. (2011]. But this approach requires
the annotated knowlege, which is also language dependent. So the other
direction, which directly encode texts into distributed vectors with neural
networks [Hinton and Salakhutdinov (2006, Xu et al. (2015], becomes more
interesing. To tackle the second problem, semi-supervised approaches (e.g.
[Bilenko et al. (2004, Davidson and Basu (2007, Bair (2013]) have gained
significant popularity in the past decades. Our question is can we have a
unified model to integrate netural networks into the semi-supervied framework?

In this paper, we propose a unified framework for the short text clustering
task. We employ a deep neural network model to represent short sentences, and
integrate it into a semi-supervised algorithm. Concretely, we extend the
objective in the classical unsupervised k-means algorithm by adding a penalty
term from labeled data. Thus, the new objective covers three key groups of
parameters: centroids of clusters, the cluster assignment for each text, and
the parameters within deep neural networks. In the training procedure, we
start from random initialization of centroids and neural networks, and then
optimize the objective iteratively through three steps until converge:

  1. (1)

assign each short text to its nearest centroid based on its representation
from the current neural networks;

  2. (2)

re-estimate cluster centroids based on cluster assignments from step (1);

  3. (3)

update neural networks according to the objective by keeping centroids and
cluster assignments fixed.

Experimental results on four different datasets show that our method achieves
significant improvements over several other text clustering methods.

In following parts, we first describe our neural network models for text
representaion (Section 2). Then we introduce our semi-supervised clustering
method and the learning algorithm (Section 3). Finally, we evaluate our method
on four different datasets (Section 4).

##  2 Representation Learning for Short Texts

We represent each word with a dense vector $w$, so that a short text $s$ is
first represented as a matrix $S=[w_{1},...,w_{|s|}]$, which is a
concatenation of all vectors of $w$ in $s$, $|s|$ is the length of $s$. Then
we design two different types of neural networks to ingest the word vector
sequence $S$: the convolutional neural networks (CNN) and the long short-term
memory (LSTM). More formally, we define the presentation function as $x=f(s)$,
where $x$ is the represent vector of the text $s$. We test two encoding
functions (CNN and LSTM) in our experiments.

Figure 1: CNN for text representation learning.

Inspired from ?), our CNN model views the sequence of word vectors as a
matrix, and applies two sequential operations: _convolution_ and _max-
pooling_. Then, a fully connected layer is employed to convert the final
representation vector into a fixed size. Figure 1 gives the diagram of the CNN
model. In the _convolution_ operation, we define a list of filters {$w_{o}$},
where the shape of each filter is $d\times h$, $d$ is the dimension of word
vectors and $h$ is the window size. Each filter is applied to a patch (a
window size $h$ of vectors) of $S$, and generates a feature. We apply this
filter to all possible patches in $S$, and produce a series of features. The
number of features depends on the shape of the filter $w_{o}$ and the length
of the input short text. To deal with variable feature size, we perform a
_max-pooling_ operation over all the features to select the maximum value.
Therefore, after the two operations, each filter generates only one feature.
We define several filters by varying the window size and the initial values.
Thus, a vector of features is captured after the _max-pooling_ operation, and
the feature dimension is equal to the number of filters.

Figure 2: LSTM for text representation learning.

Figure 2 gives the diagram of our LSTM model. We implement the standard LSTM
block described in ?). Each word vector is fed into the LSTM model
sequentially, and the mean of the hidden states over the entire sentence is
taken as the final representation vector.

##  3 Semi-supervised Clustering for Short Texts

###  3.1 Revisiting K-means Clustering

Given a set of texts $\\{s_{1},s_{2},...,s_{N}\\}$, we represent them as a set
of data points $\\{x_{1},x_{2},...,x_{N}\\}$, where $x_{i}$ can be a bag-of-
words or TF-IDF vector in traditional approaches, or a dense vector in Section
2. The task of text clustering is to partition the data set into some number
$K$ of clusters, such that the sum of the squared distance of each data point
to its closest cluster centroid is minimized. For each data point $x_{n}$, we
define a set of binary variables $r_{nk}\in\\{0,1\\}$, where
$k\in\\{1,...,K\\}$ describing which of the K clusters $x_{n}$ is assigned to.
So that if $x_{n}$ is assigned to cluster $k$, then $r_{nk}=1$, and $r_{nj}=0$
for $j\neq k$. Let’s define $\mu_{k}$ as the centroid of the $k$-th cluster.
We can then formulate the objective function as

$J_{unsup}=\sum_{n=1}^{N}\sum_{k=1}^{K}r_{nk}\|x_{n}-\mu_{k}\|^{2}$ (1)

Our goal is the find the values of $\\{r_{nk}\\}$ and $\\{\mu_{k}\\}$ so as to
minimize $J_{unsup}$.

The k-means algorithm optimizes $J_{unsup}$ through the gradient descent
approach, and results in an iterative procedure [Bishop (2006]. Each iteration
involves two steps: _E-step_ and _M-step_. In the _E-step_ , the algorithm
minimizes $J_{unsup}$ with respect to $\\{r_{nk}\\}$ by keeping
$\\{\mu_{k}\\}$ fixed. $J_{unsup}$ is a linear function for $\\{r_{nk}\\}$, so
we can optimize for each data point separately by simply assigning the $n$-th
data point to the closest cluster centroid. In the _M-step_ , the algorithm
minimizes $J_{unsup}$ with respect to $\\{\mu_{k}\\}$ by keeping
$\\{r_{nk}\\}$ fixed. $J_{unsup}$ is a quadratic function of $\\{\mu_{k}\\}$,
and it can be minimized by setting its derivative with respect to
$\\{\mu_{k}\\}$ to zero.

$\frac{\partial
J_{unsup}}{\partial\mu_{k}}=2\sum_{n=1}^{N}r_{nk}(x_{n}-\mu_{k})=0$ (2)

Then, we can easily solve $\\{\mu_{k}\\}$ as

$\mu_{k}=\frac{\sum_{n=1}^{N}r_{nk}x_{n}}{\sum_{n=1}^{N}r_{nk}}$ (3)

In other words, $\mu_{k}$ is equal to the mean of all the data points assigned
to cluster $k$.

###  3.2 Semi-supervised K-means with Neural Networks

The classical k-means algorithm only uses unlabeled data, and solves the
clustering problem under the unsupervised learning framework. As already
mentioned, the clustering results may not be consistent to our intention. In
order to acquire useful clustering results, some supervised information should
be introduced into the learning procedure. To this end, we employ a small
amount of labeled data to guide the clustering process.

1\. Initialize $\\{\mu_{k}\\}$ and $f(\cdot)$.
---
2\. _assign_cluster_ : Assign each text to its nearest cluster centroid.
3\. _estimate_centroid_ : Estimate the cluster centroids based on the cluster
assignments from step 2.
4\. _update_parameter_ : Update parameters in neural networks.
5\. Repeat step 2 to 4 until convergence.
Table 2: Pseudocode for semi-supervised clustering

Following Section 2, we represent each text $s$ as a dense vector $x$ via
neural networks $f(s)$. Instead of training the text representation model
separately, we integrate the training process into the k-means algorithm, so
that both the labeled data and the unlabeled data can be used for
representation learning and text clustering. Let us denote the labeled data
set as {$(s_{1},y_{1}),(s_{2},y_{2}),...,(s_{L},y_{L})$}, and the unlabeled
data set as {$s_{L+1},s_{L+2},...,s_{N}$}, where $y_{i}$ is the given label
for $s_{i}$. We then define the objective function as:

$\begin{split}&J_{semi}=\alpha\sum_{n=1}^{N}\sum_{k=1}^{K}r_{nk}\|f(s_{n})-\mu_{k}\|^{2}\\\
&+(1-\alpha)\sum_{n=1}^{L}\\{\|f(s_{n})-\mu_{g_{n}}\|^{2}+\\\ &\sum_{j\neq
g_{n}}[l+\|f(s_{n})-\mu_{g_{n}}\|^{2}-\|f(s_{n})-\mu_{j}\|^{2}]_{+}\\}\end{split}$
(4)

The objective function contains two terms. The first term is adapted from the
unsupervised k-means algorithm in Eq. (1), and the second term is defined to
encourage labeled data being clustered in correlation with the given labels.
$\alpha\in[0,1]$ is used to tune the importance of unlabeled data. The second
term contains two parts. The first part penalizes large distance between each
labeled instance and its correct cluster centroid, where $g_{n}=G(y_{n})$ is
the cluster ID mapped from the given label $y_{n}$, and the mapping function
$G(\cdot)$ is implemented with the Hungarian algorithm [Munkres (1957]. The
second part is denoted as a hinge loss with a margin $l$, where
$[x]_{+}=max(x,0)$. This part incurs some loss if the distance to the correct
centroid is not shorter (by the margin $l$) than distances to any of incorrect
cluster centroids.

There are three groups of parameters in $J_{semi}$: the cluster assignment of
each text {$r_{nk}$}, the cluster centroids {$\mu_{k}$}, and the parameters
within the neural network model $f(\cdot)$. Our goal is the find the values of
$\\{r_{nk}\\}$, $\\{\mu_{k}\\}$ and parameters in $f(\cdot)$, so as to
minimize $J_{semi}$. Inspired from the k-means algorithm, we design an
algorithm to successively minimize $J_{semi}$ with respect to $\\{r_{nk}\\}$,
{$\mu_{k}$}, and parameters in $f(\cdot)$. Table 2 gives the corresponding
pseudocode. First, we initialize the cluster centroids $\\{\mu_{k}\\}$ with
the k-means++ strategy [Arthur and Vassilvitskii (2007], and randomly
initialize all the parameters in the neural network model. Then, the algorithm
iteratively goes through three steps (_assign_cluster_ , _estimate_centroid_ ,
and _update_parameter_) until $J_{semi}$ converges.

The _assign_cluster_ step minimizes $J_{semi}$ with respect to {$r_{nk}$} by
keeping $f(\cdot)$ and $\\{\mu_{k}\\}$ fixed. Its goal is to assign a cluster
ID for each data point. We can see that the second term in Eq. (4) has no
relation with $\\{r_{nk}\\}$. Thus, we only need to minimize the first term by
assigning each text to its nearest cluster centroid, which is identical to the
_E-step_ in the k-means algorithm. In this step, we also calculate the
mappings between the given labels {$y_{i}$} and the cluster IDs (with the
Hungarian algorithm) based on cluster assignments of all labeled data.

The _estimate_centroid_ step minimizes $J_{semi}$ with respect to
$\\{\mu_{k}\\}$ by keeping $\\{r_{nk}\\}$ and $f(\cdot)$ fixed, which
corresponds to the _M-step_ in the k-means algorithm. It aims to estimate the
cluster centroids {$\mu_{k}$} based on the cluster assignments $\\{r_{nk}\\}$
from the _assign_cluster_ step. The second term in Eq. (4) makes each labeled
instance involved in the estimating process of cluster centroids. By solving
$\partial J_{semi}/\partial\mu_{k}=0$, we get

$\mu_{k}=\frac{\sum_{n=1}^{N}\alpha
r_{nk}f(s_{n})+\sum_{n=1}^{L}w_{nk}f(s_{n})}{\sum_{n=1}^{N}\alpha
r_{nk}+\sum_{n=1}^{L}w_{nk}}\\\ $ (5)

$\begin{split}&w_{nk}=(1-\alpha)(I_{nk}^{{}^{\prime}}+\sum_{j\neq
g_{n}}I_{nkj}^{{}^{\prime\prime}}-\sum_{j\neq
g_{n}}I_{nkj}^{{}^{\prime\prime\prime}})\\\
&I_{nk}^{{}^{\prime}}=\delta(k,g_{n})\\\
&I_{nkj}^{{}^{\prime\prime}}=\delta(k,j)\cdot\delta_{nj}^{{}^{\prime}}\\\
&I_{nkj}^{{}^{\prime\prime\prime}}=(1-\delta(k,j))\cdot\delta_{nj}^{{}^{\prime}}\\\
&\delta_{nj}^{{}^{\prime}}=\delta(l+\|f(s_{n})-\mu_{g_{n}}\|^{2}-\|f(s_{n})-\mu_{j}\|^{2}>0)\end{split}$
(6)

where $\delta(x_{1},x_{2})$=1 if $x_{1}$ is equal to $x_{2}$, otherwise
$\delta(x_{1},x_{2})$=0, and $\delta(x)$=1 if $x$ is true, otherwise
$\delta(x)$=0. The first term in the numerator of Eq. (5) is the contributions
from all data points, and $\alpha r_{nk}$ is the weight of $s_{n}$ for
$\mu_{k}$. The second term is acquired from labeled data, and $w_{nk}$ is the
weight of a labeled instance $s_{n}$ for $\mu_{k}$.

The _update_parameter_ step minimizes $J_{semi}$ with respect to $f(\cdot)$ by
keeping $\\{r_{nk}\\}$ and $\\{\mu_{k}\\}$ fixed, which has no counterpart in
the k-means algorithm. The main goal is to update parameters for the text
representation model. We take $J_{semi}$ as the loss function, and train
neural networks with the _Adam_ algorithm [Kingma and Ba (2014].

##  4 Experiment

###  4.1 Experimental Setting

We evaluate our method on four short text datasets. (1) _question_type_ is the
TREC question dataset [Li and Roth (2002], where all the questions are
classified into 6 categories: abbreviation, description, entity, human,
location and numeric. (2) _ag_news_ dataset contains short texts extracted
from the AG’s news corpus, where all the texts are classified into 4
categories: World, Sports, Business, and Sci/Tech [Zhang and LeCun (2015]. (3)
_dbpedia_ is the DBpedia ontology dataset, which is constructed by picking 14
non-overlapping classes from DBpedia 2014 [Lehmann et al. (2014]. (4)
_yahoo_answer_ is the 10 topics classification dataset extracted from Yahoo!
Answers Comprehensive Questions and Answers version 1.0 dataset by ?). We use
all the 5,952 questions for the _question_type_ dataset. But the other three
datasets contain too many instances (e.g. 1,400,000 instances in
yahoo_answer). Running clustering experiments on such a large dataset is quite
inefficient. Following the same solution in [Xu et al. (2015], we randomly
choose 1,000 samples for each classes individually for the other three
datasets. Within each dataset, we randomly sample 10% of the instances as
labeled data, and evaluate the performance on the remaining 90% instances.
Table 3 summarizes the statistics of these datasets.

dataset | class# | total# | labeled#
---|---|---|---
question_type | 6 | 5,953 | 595
ag_news | 4 | 4,000 | 400
dbpedia | 14 | 14,000 | 1,400
yahoo_answer | 10 | 10,000 | 1,000
Table 3: Statistics for the short text datasets

In all experiments, we set the size of word vector dimension as $d$=300 111We
tuned different dimensions for word vectors. When the size is small (50 or
100), performance drops significantly. When the size is larger (300, 500 or
1000), the curve flattens out. To make our model more efficient, we fixed it
as 300., and pre-train the word vectors with the _word2vec_ toolkit [Mikolov
et al. (2013] on the English Gigaword (LDC2011T07). The number of clusters is
set to be the same number of labels in the dataset. The clustering performance
is evaluated with two metrics: Adjusted Mutual Information (AMI) [Vinh et al.
(2009] and accuracy (ACC) [Amigó et al. (2009]. In order to show the
statistical significance, the performance of each experiment is the average of
10 trials.

###  4.2 Model Properties

There are several hyper-parameters in our model, e.g., the output dimension of
the text representation models, and the $\alpha$ in Eq. (4). The choice of
these hyper-parameters may affect the final performance. In this subsection,
we present some experiments to demonstrate the properties of our model, and
find a good configuration that we use to evaluate our final model. All the
experiments in this subsection were performed on the _question_type_ dataset.

Figure 3: Influence of the short text representation model, where the x-axis
is the output dimension of the text representation models.

First, we evaluated the effectiveness of the output dimension in text
representation models. We switched the dimension size among {50, 100, 300,
500, 1000}, and fixed the other options as: $\alpha=0.5$, the filter types in
the CNN model including {unigram, bigram, trigram} and 500 filters for each
type. Figure 3 presents the AMIs from both CNN and LSTM models. We found that
100 is the best output dimension for both CNN and LSTM models. Therefore, we
set the output dimension as 100 in the following experiments.

Figure 4: Influence of unlabeled data, where the x-axis is $\alpha$ in Eq.
(4).

Second, we studied the effect of $\alpha$ in Eq. (4), which tunes the
importance of unlabeled data. We varied $\alpha$ among {0.00001, 0.0001,
0.001, 0.01, 0.1}, and remain the other options as the last experiment. Figure
4 shows the AMIs from both CNN and LSTM models. We found that the clustering
performance is not good when using a very small $\alpha$. By increasing the
value of $\alpha$, we acquired progressive improvements, and reached to the
peak point at $\alpha$=0.01. After that, the performance dropped. Therefore,
we choose $\alpha$=0.01 in the following experiments. This results also
indicate that the unlabeled data are useful for the text representation
learning process.

Figure 5: Influence of labeled data, where the x-axis is the ratio of data
with given labels.

Third, we tested the influence of the size of labeled data. We tuned the ratio
of labeled instances from the whole dataset among [1%, 10%], and kept the
other configurations as the previous experiment. The AMIs are shown in Figure
5. We can see that the more labeled data we use, the better performance we
get. Therefore, the labeled data are quite useful for the clustering process.

Figure 6: Influence of the pre-training strategy.

Fourth, we checked the effect of the pre-training strategy for our models. We
added a softmax layer on top of our CNN and LSTM models, where the size of the
output layer is equal to the number of labels in the dataset. We then trained
the model through the classification task using all labeled data. After this
process, we removed the top layer, and used the remaining parameters to
initialize our CNN and LSTM models. The performance for our models with and
without pre-training strategy are given in Figure 6. We can see that the pre-
training strategy is quite effective for our models. Therefore, we use the
pre-training strategy in the following experiments.

###  4.3 Comparing with other Models

| question_type | ag_news | dbpedia | yahoo_answer
---|---|---|---|---
| AMI | ACC | AMI | ACC | AMI | ACC | AMI | ACC
Unsup. | bow | 0.028 | 0.257 | 0.029 | 0.311 | 0.578 | 0.546 | 0.019 | 0.140
tf-idf | 0.031 | 0.259 | 0.168 | 0.449 | 0.558 | 0.527 | 0.023 | 0.145
average-vec | 0.135 | 0.356 | 0.457 | 0.737 | 0.610 | 0.619 | 0.077 | 0.222
Sup. | metric-learn-bow | 0.104 | 0.380 | 0.459 | 0.776 | 0.808 | 0.854 | 0.125 | 0.329
metric-learn-idf | 0.114 | 0.379 | 0.443 | 0.765 | 0.821 | 0.876 | 0.150 | 0.368
metric-learn-ave-vec | 0.304 | 0.553 | 0.606 | 0.851 | 0.829 | 0.879 | 0.221 | 0.400
cnn-classifier | 0.511 | 0.771 | 0.554 | 0.771 | 0.879 | 0.938 | 0.285 | 0.501
cnn-represent. | 0.442 | 0.618 | 0.604 | 0.833 | 0.864 | 0.899 | 0.210 | 0.334
lstm-classifier | 0.482 | 0.741 | 0.524 | 0.763 | 0.862 | 0.928 | 0.283 | 0.512
lstm-represent. | 0.421 | 0.618 | 0.535 | 0.771 | 0.667 | 0.706 | 0.152 | 0.272
Semisup. | semi-cnn | 0.529 | 0.739 | 0.662 | 0.876 | 0.894 | 0.945 | 0.338 | 0.554
semi-lstm | 0.492 | 0.712 | 0.599 | 0.830 | 0.788 | 0.802 | 0.187 | 0.337
Table 4: Performance of all systems on each dataset. Figure 7: t-SNE
visualizations of clustering results.

In this subsection, we compared our method with some representative systems.
We implemented a series of clustering systems. All of these systems are based
on the k-means algorithm, but they represent short texts differently:

bow

represents each text as a bag-of-words vector.

tf-idf

represents each text as a TF-IDF vector.

average-vec

represents each text with the average of all word vectors within the text.

metric-learn-bow

employs the metric learning method proposed by ?), and learns to project a
bag-of-words vector into a 300-dimensional vector based on labeled data.

metric-learn-idf

uses the same metric learning method, and learns to map a TF-IDF vector into a
300-dimensional vector based on labeled data.

metric-learn-ave-vec

also uses the metric learning method, and learns to project an averaged word
vector into a 100-dimensional vector based on labeled data.

We designed two classifiers (cnn-classifier and lstm-classifier) by adding a
softmax layer on top of our CNN and LSTM models. We trained these two
classifiers with labeled data, and utilized them to predict labels for
unlabeled data. We also built two text representation models (“cnn-represent.”
and “lstm-represent.”) by setting parameters of our CNN and LSTM models with
the corresponding parameters in cnn-classifier and lstm-classifier. Then, we
used them to represent short texts into vectors, and applied the k-means
algorithm for clustering.

Table 4 summarizes the results of all systems on each dataset, where “semi-
cnn” is our semi-supervised clustering algorithm with the CNN model, and
“semi-lstm” is our semi-supervised clustering algorithm with the LSTM model.
We grouped all the systems into three categories: unsupervised (Unsup.),
supervised (Sup.), and semi-supervised (Semisup.) 222All clustering systems
are based on the same number of instances (total# in Table 3). For the semi-
supervised and supervised systems, the labels for 1% of the instances are
given (labeled# in Table 3). And the evaluation was conducted only on the
unlabeled portion.. We found that the supervised systems worked much better
than the unsupervised counterparts, which implies that the small amount of
labeled data is necessary for better performance. We also noticed that within
the supervised systems, the systems using deep learning (CNN or LSTM) models
worked better than the systems using metric learning method, which shows the
power of deep learning models for short text modeling. Our “semi-cnn” system
got the best performance on almost all the datasets.

Figure 7 visualizes clustering results on the _question_type_ dataset from
four representative systems. In Figure 7(a), clusters severely overlap with
each other. When using the CNN sentence representation model, we can clearly
identify all clusters in Figure 7(b), but the boundaries between clusters are
still obscure. The clustering results from our semi-supervised clustering
algorithm are given in Figure 7(c) and Figure 7(d). We can see that the
boundaries between clusters become much clearer. Therefore, our algorithm is
very effective for short text clustering.

##  5 Related Work

Existing semi-supervised clustering methods fall into two categories:
_constraint-based_ and _representation-based_. In _constraint-based_ methods
[Davidson and Basu (2007], some labeled information is used to constrain the
clustering process. In _representation-based_ methods [Bair (2013], a
representation model is first trained to satisfy the labeled information, and
all data points are clustered based on representations from the representation
model. ?) proposed to integrate there two methods into a unified framework,
which shares the same idea of our proposed method. However, they only employed
the metric learning model for representation learning, which is a linear
projection. Whereas, our method utilized deep learning models to learn
representations in a more flexible non-linear space. ?) also employed deep
learning models for short text clustering. However, their method separated the
representation learning process from the clustering process, so it belongs to
the _representation-based_ method. Whereas, our method combined the
representation learning process and the clustering process together, and
utilized both labeled data and unlabeled data for representation learning and
clustering.

##  6 Conclusion

In this paper, we proposed a semi-supervised clustering algorithm for short
texts. We utilized deep learning models to learn representations for short
texts, and employed a small amount of labeled data to specify our intention
for clustering. We integrated the representation learning process and the
clustering process into a unified framework, so that both of the two processes
get some benefits from labeled data and unlabeled data. Experimental results
on four datasets show that our method is more effective than other
competitors.

## References

  * [Amigó et al. (2009]  Enrique Amigó, Julio Gonzalo, Javier Artiles, and Felisa Verdejo.  2009\.  A comparison of extrinsic clustering evaluation metrics based on formal constraints.  Information retrieval, 12(4):461–486.
  * [Arthur and Vassilvitskii (2007]  David Arthur and Sergei Vassilvitskii.  2007\.  k-means++: The advantages of careful seeding.  In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pages 1027–1035. Society for Industrial and Applied Mathematics.
  * [Bair (2013]  Eric Bair.  2013\.  Semi-supervised clustering methods.  Wiley Interdisciplinary Reviews: Computational Statistics, 5(5):349–361.
  * [Banerjee et al. (2007]  Somnath Banerjee, Krishnan Ramanathan, and Ajay Gupta.  2007\.  Clustering short texts using wikipedia.  In Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, pages 787–788. ACM.
  * [Bilenko et al. (2004]  Mikhail Bilenko, Sugato Basu, and Raymond J Mooney.  2004\.  Integrating constraints and metric learning in semi-supervised clustering.  In Proceedings of the twenty-first international conference on Machine learning, page 11. ACM.
  * [Bishop (2006]  Christopher M Bishop.  2006\.  Pattern recognition and machine learning.  springer.
  * [Davidson and Basu (2007]  Ian Davidson and Sugato Basu.  2007\.  A survey of clustering with instance level constraints.  ACM Transactions on Knowledge Discovery from Data, 1:1–41.
  * [Dhillon and Guan (2003]  Inderjit S. Dhillon and Yuqiang Guan.  2003\.  Information theoretic clustering of sparse co-occurrence data.  pages 517–520. IEEE Computer Society.
  * [Fodeh et al. (2011]  Samah Fodeh, Bill Punch, and Pang-Ning Tan.  2011\.  On ontology-driven document clustering using core semantic features.  Knowledge and information systems, 28(2):395–421.
  * [Graves (2012]  Alex Graves.  2012\.  Supervised sequence labelling with recurrent neural networks, volume 385.  Springer.
  * [Hinton and Salakhutdinov (2006]  Geoffrey E Hinton and Ruslan R Salakhutdinov.  2006\.  Reducing the dimensionality of data with neural networks.  Science, 313(5786):504–507.
  * [Kim (2014]  Yoon Kim.  2014\.  Convolutional neural networks for sentence classification.  In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing, pages 1746–1751.
  * [Kingma and Ba (2014]  Diederik Kingma and Jimmy Ba.  2014\.  Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980.
  * [Lehmann et al. (2014]  Jens Lehmann, Robert Isele, Max Jakob, Anja Jentzsch, Dimitris Kontokostas, Pablo N Mendes, Sebastian Hellmann, Mohamed Morsey, Patrick van Kleef, Sören Auer, et al.  2014\.  Dbpedia-a large-scale, multilingual knowledge base extracted from wikipedia.  Semantic Web Journal, 5:1–29.
  * [Li and Roth (2002]  Xin Li and Dan Roth.  2002\.  Learning question classifiers.  In Proceedings of the 19th international conference on Computational linguistics-Volume 1, pages 1–7. Association for Computational Linguistics.
  * [MacQueen (1967]  James MacQueen.  1967\.  Some methods for classification and analysis of multivariate observations.  In Proceedings of the fifth Berkeley symposium on mathematical statistics and probability, volume 1, pages 281–297. Oakland, CA, USA.
  * [Mikolov et al. (2013]  Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean.  2013\.  Efficient estimation of word representations in vector space.  arXiv preprint arXiv:1301.3781.
  * [Munkres (1957]  James Munkres.  1957\.  Algorithms for the assignment and transportation problems.  Journal of the Society for Industrial and Applied Mathematics, 5(1):32–38.
  * [Vinh et al. (2009]  Nguyen Xuan Vinh, Julien Epps, and James Bailey.  2009\.  Information theoretic measures for clusterings comparison: is a correction for chance necessary?  In Proceedings of the 26th Annual International Conference on Machine Learning, pages 1073–1080. ACM.
  * [Weinberger et al. (2005]  Kilian Q Weinberger, John Blitzer, and Lawrence K Saul.  2005\.  Distance metric learning for large margin nearest neighbor classification.  In Advances in neural information processing systems, pages 1473–1480.
  * [Xu et al. (2015]  Jiaming Xu, Peng Wang, Guanhua Tian, Bo Xu, Jun Zhao, Fangyuan Wang, and Hongwei Hao.  2015\.  Short text clustering via convolutional neural networks.  In Proceedings of NAACL-HLT, pages 62–69.
  * [Zhang and LeCun (2015]  Xiang Zhang and Yann LeCun.  2015\.  Text understanding from scratch.  arXiv preprint arXiv:1502.01710.