Jinchuan HOU Haili ZHAO

School of Mathematics,Taiyuan University of Technology,Taiyuan 030024,China

E-mail:jinchuanhou@aliyun.com;zhaohaili927@aliyun.com

Abstract A property(C)for permutation pairs is introduced.It is shown that if a pair{π1,π2}of permutations of(1,2,···,n)has property(C),then the D-type map Φπ1,π2on n × n complex matrices constructed from{π1,π2}is positive.A necessary and sufficient condition is obtained for a pair{π1,π2}to have property(C),and an easily checked necessary and sufficient condition for the pairs of the form{πp,πq}to have property(C)is given,where π is the permutation de fi ned by π(i)=i+1 mod n and 1≤ p

Key words matrix algebras;positive linear maps;permutations;quantum information

1 Introduction

Denote by Mm,nthe set of all m×n complex matrices,and write Mn,n=Mnandthe set of all positive semi-de fi nite matrices in Mn.A linear map L:Mn→Mnis positive if?.Not like the completely positive maps,characterizing positive maps is a very difficult task.The study of positive maps were the central theme for many pure and applied topics.For example,see[1–5].In particular,the study was pertinent in quantum information science research(see[6–13]).Due to the positive map criterion of entanglement,constructing as many as possible positive maps on matrix algebras is signi fi cant[10,14–17].

Suppose ΦD:Mn→ Mnis a linear map of the form

with(f1,f2,···,fn)=(a11,a22,···,ann)D for an n × n nonnegative matrix D=(dij)(i.e.,dij≥ 0 for all i,j).The map ΦDof the form eq.(1.1)de fi ned 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,construct entanglement witnesses and get new lower bound of the concurrence(see,for instance[3,15,16,18,19]and the references therein).

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

Assume that π is a permutation of(1,2,···,n).Recall that the permutation matrix Pπ=(pij)of π is a n× n matrix determined by

Recall also that a subset{i1,···,il} ? {1,2,···,n}is an l-cycle of the permutation π if π(ij)=ij+1for j=1,···,l? 1 and π(il)=i1.Note that every permutation π of(1,···,n)has a disjoint cycle decomposition π =(π1)(π2)···(πr),that is,there exists a set{Fs}of disjoint cycles of π withFs={1,2,···,n}such that πs= π|Fsand π(i)= πs(i)whenever i∈Fs.The positivity of D-type maps induced by a permutation were discussed in[3]recently.Let π be a permutation of(1,2,···,n)with disjoint cycle decomposition(π1)···(πr)such that the maximum length of πhs is equal to l>1 and Pπis the permutation matrix associated with π.For t ≥ 0,let Φt,π:Mn→ Mnbe the D-type map of the form in eq.(1.1)with D=(n ? t)In+tPπ.It is shown in[3]that Φt,πis positive if and only if 0 ≤ t ≤Particularly,Φπ= Φ1,πis always positive.The results in[3]then be used to construct new entanglement witnesses and the optimal entanglement witnesses in[20,21],and also be used to get some new lower bound of the concurrence of quantum states in[19].

Motivated by the above result,one may consider the question when the D-type maps constructed from several permutations are positive.Not like the one permutation case,generally,ΦDπ1,···,πkis not positive,where

with 11.For the permutation π de fi ned by π(i)=i+1 mod n,and for any 1≤ k ≤ n?1,it is known that ΦD:Mn→ Mnis positive,where D=(n?k)In+Pπ+Pπ2+···+Pπk(ref.[22]).

So it is an natural and interesting topic to study the D-type linear maps ΦDwith D=Dπ1,···,πkof the form(1.2)and establish positivity criteria for them.The purpose of this paper is to establish some positivity criteria for Φπ1,π2.To do this,we introduce a property(C)for the pairs of permutations and show that if{π1,π2}has property(C),then the D-type map Φπ1,π2= ΦDπ1,π2is positive.A necessary and sufficient condition is obtained for a pair{π1,π2}to have property(C),and an easily checked necessary and sufficient condition for the pairs of the form{πp,πq}to have property(C)is given,where π is the permutation de fi ned by π(i)=i+1 mod n and 1≤p

2 Two Cyclic Like Inequalities

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

Lemma 2.1Let s,M be positive numbers and f(u1,u2,···,um)be a function in m-variables de fi ned by

(2.3)implies that,there exists a positive integer≤ r ≤ m such that r of{u1,u2,···,um}are the same,denoted by u,and other m?r of them are the same,denoted by v,with uv=s2.Note that

Solving this system,one obtains that

3 A Positivity Criterion for D-Type Maps Induced by Two Permutations

In[3],the authors established a positivity criterion for D-type maps constructed from one permutation,and proved that ΦD:Mn→ Mnis positive if D=(n?1)In+Pπ,where π is any permutation of{1,2,···,n}.In this section we give some positivity criteria for D-type linear maps constructed from two general permutations.

The following lemma comes from[3].

admits a permutation of{1,···,i?1,i+1,···,n};namely,for any j 6=i,there exists πhj(j) ∈{π1(j),π2(j)}with hj∈ {1,2}such that the map σ de fi ned by σ(j)= πhj(j),j=1,2,···,i?1,i+1,···,n,is a permutation of(1,2,···,i? 1,i+1,···,n).

It is clear,if π1=id,then for any permutation π,{π1,π2}has property(C).

Let n=3,π1=(3,1,2)and π2=(2,3,1);then{π1,π2}has property(C)since,for i=1,the sequence{{π1(2),π2(2)},{π1(3),π2(3)}}={{1,3},{2,1}}admits a permutation σ1of(2,3)with σ1=(3,2);for i=2,the sequence{{π1(1),π2(1)},{π1(3),π2(3)}}={{3,2},{2,1}}admits a permutation σ2=(3,1)of(1,3);for i=3,the sequence{{π1(1),π2(1)},{π1(2),π2(2)}}={{3,2},{1,3}}admits a permutation σ3=(2,1)of(1,2).So,{π1,π2}has property(C).However,the pair of permutations{π2,π3}={(2,3,1),(2,1,3)}has no property(C)because,for i=1,the sequence{{π2(2),π3(2)},{π2(3),π3(3)}={{3,1},{1,3}}admits no permutation of(2,3).Clearly,the pair of permutations{π2,π4}={(2,3,1),(3,2,1)}has no property(C),either.

For n ≥ 4,let π be the permutation of(1,2,···,n)de fi ned by π(i)=i+1 mod n.It is easily checked that,for any 1 ≤ p ≤ n?1,{πp,πp+1}has property(C);{π,π4}has property(C)if n=5 and 7,but does not have property(C)if n=6.Let us check it for n=6.It follows from π =(2,3,4,5,6,1)and π4=(5,6,1,2,3,4)that,for i=1,one has

which admits no permutation of(2,3,4,5,6)since one can not pick out 2 or 5.

The following is our main result.

Theorem 3.3For any two permutations π1and π2of(1,2,···,n)with n ≥ 3,let Φπ1,π2:Mn→Mnbe the D-type map of the form

where(f1,f2,···,fn)=(a11,a22,···,ann)D and D=(n ? 2)In+Pπ1+Pπ2with Pπhthe permutation matrix of πh,h=1,2.If{π1,π2}has the property(C),then Φπ1,π2is positive.

ProofFor any unit vector x=(x1,x2,···,xn)t∈ Cn,as D=(dij)=(n ? 2)In+Pπ1+Pπ2,we have

Clearly,fj(x)6=0 whenever xj6=0.Thus,by Lemma 3.1,we only need to prove that the following inequality

holds for any unit vector x=(x1,x2,···,xn)t∈ C(n).

Let us consider fi rst the case that n ≥ 4.Assume that all xi6=0.Let uhi=|xπh(i)|2|xi|2,i=1,2,···,n;h=1,2.Then,uh1uh2···uhn=1 for each h=1,2,and thus,by Lemma 2.2,we have

ψ(4)=2,ψ(5)≈1.9793,ψ(6)≈ 1.9230,ψ(7)≈1.8575,ψ(8)≈ 1.7944,ψ(9)≈1.7373,from which we see that the inequality in(3.3)is still true and hence δn?1≤ 1,as desired.

Therefore,for any n ≥ 4,1 is the maximum extremum value of f(x1,x2,···,xn)achieving at f.

In the following we show that the supremum of f on the boundary of its domain|x1|2+|x2|2+ ···+|xn|2=1 is not greater than 1,either.Assume that(x1,x2,···,xn)tlies in the boundary of the region|x1|2+|x2|2+ ···+|xn|2=1;then at least one of xiis zero.With no loss of generality,say xi6=0 for i=1,2,···,r,but xr+1= ···=xn=0,where 1

The inequalities in(3.4)and(3.5)ensure us that f is upper bounded by 1 on the boundary of its domain,and hence(3.2)is true for any unit vectors.Applying Lemma 3.1,Φπ1,π2is a positive linear map for the case n≥4.

Finally,assume n=3.If one of π1and π2is the identity,then the question reduce to the case that the D-type map is introduced by one permutation,and hence the corresponding D-type map is positive by[3].So we may assume that both π1and π2are not the identity.It is easily checked that{π1,π2}has the property(C)if and only if either there is a common fi xed point;or π1(i)6= π2(i)for any i∈ {1,2,3}.

If π1,π2have a common fi xed point i1,then with{i2,i3}={1,2,3}{i1},we have π1(i2)=i3, π1(i3)=i2,which forces that π2(i2)=i2and π2(i3)=i3,contradicting to π26=id.

So,{π1,π2}has property(C)if and only if they have no common fi xed points and π1(i)6=π2(i)for any i.Thus,we have four possible cases:

The fact that Φπ1,π2is positive in case{(2,3,1),(3,1,2)}is implied by the result in[22].In fact,for this case,we have

and by Lemma 3.1, Φπ1,π2≥ 0.Again,by Lemma 3.1,for the rest three cases,proving of positivity of Φπ1,π2is induced to prove the following inequality

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

by 2uv≤u2+v2.So the theorem is also true for the case n=3, fi nishing the proof. ?

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

For a nonempty proper subset F of{1,2,···,n},if πh(F)=F holds for all h=1,2,we say that F is an invariant subsets of{π1,π2}.Obvious,there exist disjoint minimal invariant subsets F1,F2,···,Flof{π1,π2}such thatFs={1,2,···,n}).We say{F1,F2,···,Fl}is the complete set of minimal invariant subsets of{π1,π2}.Thus one can reduce the pair{π1,π2}of permutations into l pairs{π1s,π2s}ls=1of small ones,where πhs= πh|Fs.It is easily checked that{π1,π2}has property(C)if and only if each pair{π1s,π2s}of the sub-permutations has property(C).

The following is a version of Theorem 3.3.

Theorem 3.4Let{Fs}ls=1be the complete set of minimal invariant subsets of a pair{π1,π2}of permutations of(1,2,···,n)with n ≥ 3.Let πis= πi|Fs.If{π1s,π2s}has Property(C)for every s=1,2,···,l,then the D-type map Φπ1,π2de fi ned as in Theorem 3.3 is positive.

Theorem 3.3 and Theorem 3.4 give a possible way to construct new positive maps and,in general,it is not difficult to judge whether or not a given pair of permutations possesses property(C).In the following,we give a characterization for a pair of permutations to have property(C),which will be helpful to construct new positive maps.

By the discussion before the statement of Theorem 3.4,to give a necessary and sufficient condition for{π1,π2}to have property(C),we may assume that π1and π2have no common proper invariant subsets and n ≥ 1.It is clear that,if n=1,{π1,π2}always has property(C);if n=2,{π1,π2}has property(C)if and only if one of π1,π2is the identity and other is(2,1).Generally,we have

Proposition 3.5Let π1,π2be two permutations of(1,2,···,n)with n ≥ 2 having no proper common invariant subsets.Then{π1,π2}has property(C)if and only if the following conditions are satis fi ed:

(1)For any distinct i,j,π1(i)6= π2(i)and{π1(i),π2(i)}6={π1(j),π2(j)};

(2)For any i and j1,j2with π1(j2)= π2(j1)=i,if distinct j3,···,jm6∈ {i,j1,j2}satisfy that π2(j3)= π1(j1),π2(j4)= π1(j3),···,π2(jm)= π1(jm?1),then π1(jm)6= π2(j2).

ProofAssume that{π1,π2}satisfy conditions(1)–(2).For any i,we have to show that we can choose one element πhj(j) ∈ {π1(j),π2(j)}for each j 6=i so that{πhj(j),j 6=i}={1,2,···,i? 1,i+1,···,n}.We do this by considering two cases.

Case(i)i ∈ {π1(i),π2(i)}.Say π1(i)=i;then obviously the choice{π1(j):j 6=i}={1,2,···,i? 1,i+1,···,n}.

Case(ii)i 6∈ {π1(i),π2(i)}.

Take j1,j2so that π1(j2)=i= π2(j1).By condition(1),we must have π1(j1)6= π2(j2).In fact,if π1(j1)= π2(j2),then{π1(j1),π2(j1)}={π1(j2),π2(j2)},which contradicts to condition(1). If{π1(j1),π2(j2)}={π1(i),π2(i)},then{π1(j1),π2(j2)} ∪ {π1(j):j 6∈ {i,j1,j2}}={1,···,i? 1,i+1,···,n}and we fi nish the proof.

Assume that{π1(j1),π2(j2)}6={π1(i),π2(i)}.

If π1(j1)= π2(i)or π2(j2)= π1(i),saying π2(j2)= π1(i),then we have{π2(j2)} ∪ {π1(j):j 6∈ {i,j2}}={π1(j):j 6=j2}={1,2,···,i? 1,i+1,···,n}, fi nishing the proof.

Thus we may assume in the sequel that{π1(j1),π2(j2)} ∩ {π1(i),π2(i)}= ?.Take j3so that π2(j3)= π1(j1).As π1(j1)6= π2(j2),we have j36=j2.Also π2(j3)= π1(j1)6= π2(i)and π2(j3)= π1(j1)6= π2(j1)(=i)ensure that j36∈ {i,j1}.So we have j36∈ {i,j1,j2}and by condition(2),we see that π1(j3)6= π2(j2).Thus we get a set{π1(j1),π2(j2),π1(j3)}of distinct elements.If π1(j3)= π2(i),then

{π1(j1),π1(j3)} ∪ {π2(j):j 6∈ {i,j1,j3}}={π2(j):j 6=j1}={1,2,···,i? 1,i+1,···,n}and we fi nish the proof.If π1(j3)6= π2(i),take j4so that π2(j4)= π1(j3).Then j46=i and j46=j3by the previous proof.In fact,π2(j3)= π1(j1)6= π1(j3)implies that π2(j3)6= π1(j3),and j46=j3.As π2(j4)= π1(j3)6= π2(j2),we have j46=j2.Also π1(j3)6= π1(j2)implies that j46=j1.So j46∈ {i,j1,j2,j3}and by the condition(2),π1(j4)6= π2(j2).Therefore,we have π1(j4)6∈ {π1(j1),π2(j2),π1(j3)}.Again,if π1(j4)= π2(i),then

and the proof is fi nished.If π1(j4)6= π2(i),then,by condition(2), π1(j4)6= π2(j2)and π1(j4)6= π2(j1)=i.It follows that we can take j56∈ {i,j1,j2,j3,j4}such that π2(j5)= π1(j4),and π1(j5)6∈ {π1(j1),π2(j2),π1(j3),π1(j4)}.Continue this process and fi nally,one can get jmso that π2(jm)= π1(jm?1)and π1(jm)= π2(i).Then we have

and complete the proof.Hence,conditions(1)and(2)imply{π1,π2}has property(C).

By checking the arguments above,it is easily seen that,if any one of conditions(1)and(2)is broken,then{π1,π2}does not have property(C).Therefore,the conditions are also necessary. ?

By the symmetry of π1and π2,condition(2)in Proposition 3.5 may be replaced by the following

(2)′For any i and j1,j2with π1(j2)= π2(j1)=i,if distinct j3,···,jm6∈ {i,j1,j2}satisfy that π1(j3)= π2(j2),π1(j4)= π2(j3),···,π1(jm)= π2(jm?1),then π2(jm)6= π1(j1).

Corollary 3.6Let π1,π2be permutations of(1,2,···,n).Then the D-type map Φπ1,π2is positive if for any minimal invariant subset F of{π1,π2}with#F ≥ 2,{π1|F,π2|F}satis fi es conditions(1)and(2)in Proposition 3.5.

4 Application:Positivity of the Maps Constructed by Pairs of Powers of a Cyclic Permutation

The class of positive linear maps in Theorem 3.3 is quite large,which contains many known positive maps of D-type such as that induced by just one permutation in[3]and that in[22]with k=2.Applying the results,especially Theorem 3.3,Proposition 3.5 in the previous section,we construct in this section some new examples of D-type positive maps induced by two permutations of a special kind.

In the sequel we denote by π the cyclic permutation of(1,2,···,n)de fi ned by π(i)=i+1 mod n.Let 1 ≤ p

Lemma 4.1Let π be the cyclic permutation of(1,2,···,n)de fi ned by π(i)=i+1(mod n).For any 1 ≤ p

(1)q?p=1.

(2)1

ProofIf q?p=1,then it is clear that{πp,πq}has property(C).

So,to prove the lemma,it suffices to show that,for any p,q with 1

Claim 1{π1= πp,π2= πq}does not satisfy condition(1)of Proposition 3.5 if and only if 2(q?p)=n and p 6=n?(q?p).

In fact,{π1,π2}does not meet condition(1)of Proposition 3.5 if and only if

and

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≤n.p can not be n?(q?p)because this would imply that q=n.

Claim 2{π1= πp,π2= πq}does not satisfy condition(2)of Proposition 3.5 if and only if m(q?p)=kn for some relatively prime positive integers k,m with 1≤k

{π1= πp,π2= πq}does not satisfy condition(2)of Proposition 3.5 if and only if for some i,there exist distinct j1,···,jm6∈ {i}such that π1(j2)= π2(j1)=i, π2(j3)= π1(j1),π2(j4)= π1(j3),···,π2(jm)= π1(jm?1)and π1(jm)= π2(j2),and in turn,if and only if for some i there exist distinct j1,···,jm6∈ {i}such that

Summing up all equations in(4.1)gives

Note that 2≤m

Moreover,jh=j1?(q?p)(h?2)=j2?(q?p)(h?1)mod n for h=3,4,···,m.Obviously,j1,j26∈ {i}.While j3,···,jm6∈ {i}implies that jh6=j1+q=j2+p mod n for any h=3,4,···,m.It is clear that jh=i=j1+q=j2+p mod n for some jh=j1?(q?p)(h?2)=j2?(q?p)(h?1)mod n if and only if j1+q=j1?(q?p)(h?2)and j2+p=j2?(q?p)(h?1),and in turn,if and only if p=n?(q?p)(h?1)=n?d(q?p)for some 2≤d≤m?1.So,j1,···,jm6∈ {i}implies that p 6=n ? d(q ? p)for any 2 ≤ d

Conversely,assume that(4.2)and(4.3)hold.Take any j1,j2so that j2?j1=q?p mod n.Then j2=j1+(q?p)mod n.If m=2,we must have 2(q?p)=n and hence j2+(q?p)=j1+2(q?p)=j1mod n,which gives j2+q=j1+p mod n.If m≥3,for 3≤h≤m,let

Then j2=jm+(q?p)(m?1)mod n and hence j2+q?p=jmmod n as(q?p)m=kn.This entails that j2+q=jm+p mod n.We claim that jh6=jswhenever t 6=s.It is clear that j16=j2,for 3≤h,s≤m,

Moreover,(4.3)and(4.4)imply that j1,···,jm6∈ {i}.Hence(4.2)and(4.3)imply that{πp,πq}does not satis fi es condition(2)of Proposition 3.5.

Now,by Proposition 3.5,Claims 1–2 ensure that the lemma is true,completing the proof.?

We remark that the condition m(q?p)=kn does not imply that q?p is a factor of n in general.For example,let n=8,q?p=6;then 4(q? p)=3n.Note that,{π2,π8}={π2,id}has property(C),but,by Lemma 4.1,{π1,π7}does not.

Using Lemma 4.1,the following criterion of positivity of Φn,p,qis immediate,which is quite easily checked.

Theorem 4.2Let π be the permutation de fi ned by π(i)=i+1 mod n.For any integers 1 ≤ p

(1)q?p=1 or q=n.

(2)q

The following corollary is easier to apply.

Corollary 4.3The D-type map Φn,p,q:Mn→ Mnin 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≤m

(4)q?p is prime and 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≤d≤?2.

ProofThe implication “(1)? ΦDis positive”is obvious by Theorem 4.2.

If(2)holds,that is,if n is prime,then there are no relative prime positive integers m

(3)entails that{πp,πq}meets condition(2)in Theorem 4.2 and hence Φn,p,qis positive.

If(4)holds,that is,if q?p is prime and is not a factor of n,then n=implies that m=kr for some integer r and n=r(q?p),contradicting to the assumption that q?p is not a factor of n.So{πp,πq}meets condition(2)of Theorem 4.2 and thus Φn,p,qis positive.

Condition(5)implies that m1(q?p)=kn and the greatest common divisor of m1and k is 1 if and only if m1=m and k=1 as q?p is prime.As p=d(q?p)=n?(m?d)(q?p),{πp,πq}has property(C)by Lemma 4.1. ?

Since,in quantum information theory,an N-qbit quantum system corresponds to a complex Hilbert space of dimension 2N,the case n=2Nis of special interesting.

Corollary 4.4For n=2Nwith N ≥ 2 and 1 ≤ p

(1)q?p is odd.

(2)q?p=2bwith 1≤b≤N?1 and p=d2bfor some 1≤d≤2N?b?1.

(3)q?p=2br with r odd and p=2b(2N?b?dr)for some 1≤ d≤

Example 4.5Let n=5 or 7.Then,by Corollary 4.3,for any 1≤p

More concretely,observe that Φ5,1,3is of the form

which is a positive map by Corollary 4.3.

It is also obvious that when n=4,Φ4,p,qis positive if q?p 6=2;when n=6,Φ6,p,qis positive if q ?p 6∈ {2,3,4}.

Example 4.6Let n=8=23.For any 1≤ p

(i)q?p∈{1,3,5,7}.

(ii)q?p=2,p∈{2,4,6}.

(iii)q?p=4,p=4.

(iv)q?p=6,p=2.

Example 4.7Let n=16=24.For any 1≤ p

(i)q?p∈{1,3,5,7,9,11,13,15}.

(ii)q?p=2 and p∈{2,4,6,8,10,12,14}.

(iii)q?p=4 and p∈{4,8,12}.

(iv)q?p=6 and p∈{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.8The condition that{πp,πq}has property(C)in Theorem 4.2 is sufficient for the associated D-type map Φn,p,qto be positive.The condition is not necessary,and thus,the condition in Corollary 3.6 is not necessary for ΦDto be positive.

Example 4.9Let us consider the case of n=4.In this case,{πp,πq}does not have property(C)if and only if p=1,q=3.By Lemma 3.1,the D-type map Φ4,1,3= ΦDwith D=2I4+Pπ+Pπ3is positive if and only if

holds for all non-negative x1,···,x4∈ R with x1+···+x4=1.By Lemma 2.2,all extremums of f(x1,x2,x3,x4)is 1 because s=M=2.Let us consider the supremum of f on the boundary.Assume that only one of xiis zero,say x4=0,then

with x1,x2,x3nonzero.Consider the function

where s>0 and t>0.As

and 2st

It is then interesting to ask

Question 4.10What is the necessary and sufficient condition for Φn,p,q= ΦD:Mn→Mnwith D=(n ? 1)In+Pπp+Pπqto be positive?Where π is the permutation de fi ned by π(i)=i+1 mod n and 1≤p

This question was solved for the case when n≤4 in[24].