# Optimality of a class of entanglement witnesses for $3\otimes 3$ systems

Xiaofei Qi  Department of Mathematics, Shanxi University , Taiyuan 030006, P.
R. China<EMAIL_ADDRESS>and  Jinchuan Hou  Department of
Mathematics
Taiyuan University of Technology
Taiyuan 030024, P. R. China<EMAIL_ADDRESS>
###### Abstract.

Let $\Phi_{t,\pi}:M_{3}({\mathbb{C}})\rightarrow M_{3}({\mathbb{C}})$ be a
linear map defined by
$\Phi_{t,\pi}(A)=(3-t)\sum_{i=1}^{3}E_{ii}AE_{ii}+t\sum_{i=1}^{3}E_{i,\pi(i)}AE_{i,\pi(i)}^{\dagger}-A$,
where $0\leq t\leq 3$ and $\pi$ is a permutation of $(1,2,3)$. We show that
the Hermitian matrix $W_{\Phi_{t,\pi}}$ induced by $\Phi_{t,\pi}$ is an
optimal entanglement witness if and only if $t=1$ and $\pi$ is cyclic.

PACS. 03.67.Mn, 03.65.Ud, 03.65.Db

Key words and phrases. Quantum states, optimal entanglement witness, positive
linear maps, permutations

This work is partially supported by a grant from International Cooperation
Program in Sciences and Technology of Shanxi (2011081039), Natural Science
Foundation of China (11171249, 11101250) and Youth Foundation of Shanxi
Province (2012021004).

##  1\. Introduction

Let $H$ be a separable complex Hilbert space. Recall that a quantum state on
$H$ is a density operator $\rho\in{\mathcal{B}}(H)$ which is positive and has
trace 1. Denote by ${\mathcal{S}}(H)$ the set of all states on $H$. If $H$ and
$K$ are finite dimensional, a state in the bipartite composition system
$\rho\in{\mathcal{S}}(H\otimes K)$ is said to be separable if $\rho$ can be
written as $\rho=\sum_{i=1}^{k}p_{i}\rho_{i}\otimes\sigma_{i},$ where
$\rho_{i}$ and $\sigma_{i}$ are states on $H$ and $K$ respectively, and
$p_{i}$ are positive numbers with $\sum_{i=1}^{k}p_{i}=1$. Otherwise, $\rho$
is entangled.

Entanglement is an important physical resource to realize various quantum
information and quantum communication tasks such as teleportation, dense
coding, quantum cryptography and key distribution [10, 11]. It is very
important but also difficult to determine whether or not a state in a
composite system is separable. One of the most general approaches to
characterize quantum entanglement for bipartite composition systems is based
on the notion of entanglement witnesses (see [4]). A Hermitian matrix $W$
acting on $H\otimes K$ is an entanglement witness (briefly, EW) if $W$ is not
positive and ${\rm Tr}(W\sigma)\geq 0$ holds for all separable states
$\sigma$. Thus, if $W$ is an EW, then there exists an entangled state $\rho$
such that ${\rm Tr}(W\rho)<0$ (that is, the entanglement of $\rho$ can be
detected by $W$). It was shown that, a state is entangled if and only if it is
detected by some entanglement witness [4]. Constructing entanglement witnesses
is a hard task, too. There was a considerable effort in constructing and
analyzing the structure of entanglement witnesses [1, 3, 7, 8, 15]. However,
complete characterization and classification of EWs is far from satisfactory.

Due to the Choi-Jamiołkowski isomorphism [2, 9], a Hermitian matrix
$W\in{\mathcal{B}}(H\otimes K)$ with $\dim H\otimes K<\infty$ is an EW if and
only if there exists a positive linear map which is not completely positive
(NCP) $\Phi:{\mathcal{B}}(H)\rightarrow{\mathcal{B}}(K)$ and a maximally
entangled state $P^{+}\in{\mathcal{B}}(H\otimes H)$ such that
$W=W_{\Phi}=(I_{n}\otimes\Phi)P^{+}$. Recall that a maximally entangled state
is a pure state $P^{+}=|\psi^{+}\rangle\langle\psi^{+}|$ with
$|\psi^{+}\rangle=\frac{1}{\sqrt{n}}(|11\rangle+|22\rangle+\cdots|nn\rangle)$,
where $n=\dim H$ and $\\{|i\rangle\\}_{i=1}^{n}$ is an orthonormal basis of
$H$. Thus, up to a multiple by positive scalar, $W_{\Phi}$ can be written as
the matrix $W_{\Phi}=(\Phi(E_{ij}))_{n\times n}$, where
$E_{ij}=|i\rangle\langle j|$. For a positive linear map
$\Phi:{\mathcal{B}}(H)\rightarrow{\mathcal{B}}(K)$, we always denote
$W_{\Phi}$ the Choi-Jamiołkowski matrix of $\Phi$ with respect to a given
basis of $H$, that is $W_{\Phi}=(\Phi(E_{ij}))_{n\times n}$, and we say that
$W_{\Phi}$ is the witness induced by the positive map $\Phi$. Conversely, for
an EW $W$, we denote $\Phi_{W}$ for the associated positive map so that
$W=W_{\Phi_{W}}$.

For any entanglement witness $W$, let
$\mathcal{D}_{W}=\\{\rho:\rho\in{\mathcal{S}}(H\otimes K),{\rm
Tr}(W\rho)<0\\},$ that is, ${\mathcal{D}}_{W}$ is the set of all entangled
states that detected by $W$. For entanglement witnesses $W_{1},W_{2}$, we say
that $W_{1}$ is finer than $W_{2}$ if
$\mathcal{D}_{W_{2}}\subset\mathcal{D}_{W_{1}}$, denoted by $W_{2}\prec
W_{1}$. While, an entanglement witness $W$ is optimal if there exists no other
witness finer than it. Obviously, a state $\rho$ is entangled if and only if
there is some optimal EW such that ${\rm Tr}(W\rho)<0$. In [10], Lewenstein,
Kraus, Cirac and Horodecki proved that: (1) $W$ is an optimal entanglement
witness if and only if $W-Q$ is no longer an entanglement witness for
arbitrary positive operator $Q$; (2) $W$ is optimal if
${\mathcal{P}}_{W}=\\{|e,f\rangle\in H\otimes K:\langle e,f|W|e,f\rangle=0\\}$
spans the whole $H\otimes K$ (in this case, we say that $W$ has spanning
property). However, the criterion (2) is only a sufficient condition. There
are known optimal witnesses that have no spanning property, for example, the
entanglement witnesses induced by the Choi maps. Recently, Qi and Hou in [12]
gave a necessary and sufficient condition for the optimality of entanglement
witnesses in terms of positive linear maps.

Theorem 1.1. ([12, Theorem 2.2]) Let $H$ and $K$ be finite dimensional complex
Hilbert spaces. Let $\Phi:{\mathcal{B}}(H)\rightarrow{\mathcal{B}}(K)$ be a
positive linear map. Then $W_{\Phi}$ is an optimal entanglement witness if and
only if, for any $C\in{\mathcal{B}}(H,K)$, the map
$X\mapsto\Phi(X)-CXC^{\dagger}$ is not a positive map.

This approach is practical for some situations, especially when the witnesses
have no spanning property. Applying it, Qi and Hou [12] showed that the
entanglement witnesses arising from some positive maps in [13] are
indecomposable optimal witnesses.

If $\dim H=n$, by fixing an orthonormal basis, one may identify
${\mathcal{B}}(H)$ with $M_{n}({\mathbb{C}})$, the $n\times n$ complex matrix
algebra. In this note, we will consider the linear maps $\Phi_{t,\pi}$ defined
by

$None$
$\Phi_{t,\pi}(X)={\small\left(\begin{array}[]{ccc}(2-t)x_{11}+tx_{\pi(1),\pi(1)}&-x_{12}&-x_{13}\\\
-x_{21}&(2-t)x_{22}+tx_{\pi(2),\pi(2)}&-x_{23}\\\
-x_{31}&-x_{32}&(2-t)x_{33}+tx_{\pi(3),\pi(3)}\end{array}\right)},$

where $X=(x_{ij})\in M_{3}({\mathbb{C}})$, $0\leq t\leq 3$ and $\pi$ is any
permutation of $(1,2,3)$. We will show that the necessary and sufficient
condition for the Hermitian matrix $W_{\Phi_{t,\pi}}$ to be an optimal
entanglement witness is that $t=1$ and $\pi$ is cyclic (Theorem 2.2).

##  2\. Main result and proof

In this section, we give the main result and its proof.

Let $\pi$ be a permutation of $(1,2,\ldots,n)$ and $0\leq t\leq n$. For a
subset $F$ of $\\{1,2,\ldots,n\\}$, if $\pi(F)=F$, we say $F$ is an invariant
subset of $\pi$. Let $F$ be an invariant subset of $\pi$. If both $G\subseteq
F$ and $G$ is invariant under $\pi$ imply $G=F$, we say $F$ is a minimal
invariant subset of $\pi$. It is obvious that a minimal invariant subset is a
loop of $\pi$ and $\\{1,2,\ldots,n\\}=\cup_{s=1}^{r}F_{s}$, where
$\\{F_{s}\\}_{s=1}^{r}$ is the set of all minimal invariant subsets of $\pi$.
Denote by $\\#F_{s}$ the cardinal number of $F_{s}$. Then
$\sum_{s=1}^{r}\\#F_{s}=n$. We call $\max\\{\\#F_{s}:s=1,2,\ldots,r\\}$ the
length of $\pi$, denoted by $l(\pi)$. In the case that $l(\pi)=n$, we say that
$\pi$ is cyclic.

The following lemma was shown in [14].

Lemma 2.1. For any permutation $\pi$ of $\\{1,2,3\\}$, let
$\Phi_{t,\pi}:M_{3}({\mathbb{C}})\rightarrow M_{3}({\mathbb{C}})$ be a map
defined by Eq.(1.1). Then $\Phi_{t,\pi}$ is positive if and only if $0\leq
t\leq\frac{3}{l(\pi)}$.

The following is our main result in this note, which states that
$W_{\Phi_{t,\pi}}$ is an optimal EW if and only if $t=1$ and $\pi$ is cyclic.

Theorem 2.2. For any permutation $\pi$ of $\\{1,2,3\\}$, let
$\Phi_{t,\pi}:M_{3}({\mathbb{C}})\rightarrow M_{3}({\mathbb{C}})$ be the map
defined by Eq.(1.1). Then $W_{\Phi_{t,\pi}}$ is an optimal entanglement
witness if and only if $t=1$ and $l(\pi)=3$.

Before stating the main results in this section, let us recall some notions
and give two lemmas that we needed.

Let $l$, $k\in\mathbb{N}$ (the set of all natural numbers), and let
$A_{1},\cdots,A_{k}$, and $C_{1},\cdots,C_{l}\in{\mathcal{B}}(H$, $K$). If,
for each $|\psi\rangle\in H$, there exists an $l\times k$ complex matrix
$(\alpha_{ij}(|\psi\rangle))$ (depending on $|\psi\rangle$) such that

$C_{i}|\psi\rangle=\sum_{j=1}^{k}\alpha_{ij}(|\psi\rangle)A_{j}|\psi\rangle,\qquad
i=1,2,\cdots,l,$

we say that $(C_{1},\cdots,C_{l})$ is a locally linear combination of
$(A_{1},\cdots,A_{k})$, $(\alpha_{ij}(|\psi\rangle))$ is called a local
coefficient matrix at $|\psi\rangle$. Furthermore, if a local coefficient
matrix $(\alpha_{ij}(|\psi\rangle))$ can be chosen for every $|\psi\rangle\in
H$ so that its operator norm
$\|(\alpha_{ij}(|\psi\rangle))\|=\sup\\{\|(\alpha_{ij}(|\psi\rangle)|x\rangle\|:|x\rangle\in{\mathbb{C}}^{\rm
k},\||x\rangle\|\leq 1\\}\leq 1$, we say that $(C_{1},\cdots,C_{l})$ is a
contractive locally linear combination of $(A_{1},\cdots,A_{k})$; if there is
a matrix $(\alpha_{ij})$ such that $C_{i}=\sum_{j=1}^{k}\alpha_{ij}A_{j}$ for
all $i$, we say that $(C_{1},\cdots,C_{l})$ is a linear combination of
$(A_{1},\cdots,A_{k})$ with coefficient matrix $(\alpha_{ij})$.

The following characterization of positive linear maps was obtained in [5],
also, see [6].

Lemma 2.3. Let $H$ and $K$ be complex Hilbert spaces of any dimension,
$\Phi:{\mathcal{B}}(H)\rightarrow{\mathcal{B}}(K)$ be a linear map defined by
$\Phi(X)=\sum_{i=1}^{k}C_{i}XC_{i}^{\dagger}-\sum_{j=1}^{l}D_{j}XD_{j}^{\dagger}$
for all $X$. Then $\Phi$ is positive if and only if $(D_{1},\cdots,D_{l})$ is
a contractive locally linear combination of $(C_{1},\cdots,C_{k})$.
Furthermore, $\Phi$ is completely positive if and only if
$(D_{1},\cdots,D_{l})$ is a linear combination of $(C_{1},\cdots,C_{k})$ with
a contractive coefficient matrix, and in turn, if and only if there exist
$E_{1},E_{2},\ldots,E_{r}$ in ${\rm span}\\{C_{1},\cdots,C_{k}\\}$ such that
$\Phi=\sum_{i=1}^{r}E_{i}(\cdot)E_{i}^{\dagger}.$

Lemma 2.4. Let $t$ be a fixed number with $0<t<1$ and let $x_{1},x_{2},x_{3}$
be any positive numbers with $x_{1}x_{2}x_{3}=1$ and
$(x_{1},x_{2},x_{3})\not=(1,1,1)$. Then we have

$\frac{1-\sum_{i=1}^{3}\frac{1}{(3-t)+tx_{i}}}{\sum_{i=1}^{2}\frac{1}{(3-t)+tx_{i}}-\frac{4}{(3-t+tx_{1})(3-t+tx_{2})}-\frac{1}{(3-t+tx_{1})(3-t+tx_{3})}-\frac{1}{(3-t+tx_{2})(3-t+tx_{3})}}\geq(1-t).$

Proof. Let $f$ be the function in $3$-variables defined by

$\begin{array}[]{rl}&f(x_{1},x_{2},x_{3})\\\
=&\frac{1-\sum_{i=1}^{3}\frac{1}{(3-t)+tx_{i}}}{\sum_{i=1}^{2}\frac{1}{(3-t)+tx_{i}}-\frac{4}{(3-t+tx_{1})(3-t+tx_{2})}-\frac{1}{(3-t+tx_{1})(3-t+tx_{3})}-\frac{1}{(3-t+tx_{2})(3-t+tx_{3})}},\end{array}$

where $t$ is fixed with $0<t<1$ and $x_{1},x_{2},x_{3}$ are any positive
numbers with $x_{1}x_{2}x_{3}=1$ and $(x_{1},x_{2},x_{3})\not=(1,1,1)$. Since
the denominator of $f(x_{1},x_{2},x_{3})$ is not zero whenever
$(x_{1},x_{2},x_{3})\not=(1,1,1)$, a computation shows that

$\begin{array}[]{rl}&f(x_{1},x_{2},x_{3})\geq(1-t)\\\
\Leftrightarrow&1-\sum_{i=1}^{3}\frac{1}{(3-t)+tx_{i}}\geq(\sum_{i=1}^{2}\frac{1}{(3-t)+tx_{i}}-\frac{4}{(3-t+tx_{1})(3-t+tx_{2})}\\\
&-\frac{1}{(3-t+tx_{1})(3-t+tx_{3})}-\frac{1}{(3-t+tx_{2})(3-t+tx_{3})})(1-t)\\\
\Leftrightarrow&g(x_{1},x_{2},x_{3})\geq 0,\end{array}$

where

$\begin{array}[]{rl}g(x_{1},x_{2},x_{3})=&(2t^{2}-2t-3)+(1-t)x_{1}+(1-t)x_{2}+(1-t^{2})x_{3}\\\
&+(2t-t^{2})x_{1}x_{2}+tx_{2}x_{3}+tx_{1}x_{3}.\end{array}$

Thus, to complete the proof of the lemma, we only need to check that the
minimum of the $3$-variable function $g$ is zero on the region $x_{i}>0$ with
$x_{1}x_{2}x_{3}=1$, $i=1,2,3$.

To do this, let

$L(x_{1},x_{2},x_{3},\lambda)=g(x_{1},x_{2},x_{3})+\lambda(x_{1}x_{2}x_{3}-1).$

By the method of Lagrange multipliers, we have the system

$None$ $\begin{cases}L_{x_{1}}^{\prime}=(1-t)+(2t-t^{2})x_{2}+tx_{3}+\lambda
x_{2}x_{3}=0,\\\ L_{x_{2}}^{\prime}=(1-t)+(2t-t^{2})x_{1}+tx_{3}+\lambda
x_{1}x_{3}=0,\\\ L_{x_{3}}^{\prime}=(1-t^{2})+tx_{2}+tx_{1}+\lambda
x_{1}x_{2}=0,\\\ L_{\lambda}^{\prime}=x_{1}x_{2}x_{3}-1=0.\end{cases}$

Solving this system, one obtains

$(x_{2}-x_{1})(2t-t^{2}+\lambda x_{3})=0,$

which implies that

${\rm either}\ \ \ \ x_{1}=x_{2}\ \ \ \ {\rm or}\ \ \ \ 2t-t^{2}+\lambda
x_{3}=0.$

If $2t-t^{2}+\lambda x_{3}=0$, by Eq.(2.1), one gets $x_{3}=\frac{t-1}{t}<0$,
a contradiction. Hence we must have $x_{1}=x_{2}$. Thus, by Eq.(2.1) again, we
have

$(2t-t^{2})x_{1}^{4}+(1-t)x_{1}^{3}-tx_{1}+(t^{2}-1)=0,$

that is,

$None$
$(x_{1}-1)[(2t-t^{2})x_{1}^{3}+(1+t-t^{2})x_{1}^{2}+(1+t-t^{2})x_{1}+(1-t^{2})]=0.$

Note that
$(2t-t^{2})x_{1}^{3}+(1+t-t^{2})x_{1}^{2}+(1+t-t^{2})x_{1}+(1-t^{2})>0$ for
all $x_{1}>0$ and $0<t<1$. So Eq.(2.2) holds if and only if $x_{1}=1$, which
forces $x_{2}=x_{3}=1$. It follows that the function $g(x_{1},x_{2},x_{3})$
takes its extremum at the point $(1,1,1)$. Moreover, it is easy to check that
$(1,1,1)$ is the minimal point of $g(x_{1},x_{2},x_{3})$. Hence
$g(x_{1},x_{2},x_{3})\geq g(1,1,1)=0$ for all $x_{i}>0$ with
$x_{1}x_{2}x_{3}=1$, $i=1,2,3$.

Therefore, the inequality in Lemma 2.4 holds for all $x_{i}>0$, $i=1,2,3$,
with $x_{1}x_{2}x_{3}=1$ and $(x_{1},x_{2},x_{3})\not=(1,1,1)$. The proof is
finished. $\Box$

Now we are in a position to give the proof of Theorem 2.1.

Proof of Theorem 2.1. By Lemma 2.1, $\Phi_{t,\pi}$ is positive whenever $0\leq
t\leq\frac{3}{l(\pi)}$. We will prove the theorem by considering several
cases. Note that, $\Phi_{0,\pi}$ is completely positive; so we may assume that
$t>0$.

Case 1. $l(\pi)=1$.

if $l=1$, then $\pi={\rm id}$ (the identical permutation). In this case,
$\Phi_{t,\pi}$ is a completely positive linear map for all $0<t\leq 3$ (see
[13, Proposition 2.7]), and so $W_{\Phi_{t,\pi}}\geq 0$, which is not an EW.

Case 2. $l(\pi)=2$.

If $l=2$, then $\pi^{2}={\rm id}$. Without loss of generality, assume that
$\pi(1)=2$, $\pi(2)=1$ and $\pi(3)=3$. Since
$\Phi_{t,\pi}(E_{11})=(2-t)E_{11}+tE_{22}$,
$\Phi_{t,\pi}(E_{22})=(2-t)E_{22}+tE_{11}$, $\Phi_{t,\pi}(E_{33})=2E_{33}$ and
$\Phi_{t,\pi}(E_{ij})=-E_{ij}$ with $1\leq i\not=j\leq 3$, the Choi matrix of
$\Phi_{t,\pi}$ is

$\begin{array}[]{rl}W_{\Phi_{t,\pi}}=&\sum_{i=1}^{3}(2-t)E_{ii}\otimes
E_{ii}+tE_{22}\otimes E_{11}+tE_{11}\otimes E_{22}+tE_{33}\otimes
E_{33}-\sum_{i\not=j}E_{ij}\otimes E_{ij}\\\ =&(2-t)E_{11}\otimes
E_{11}+(2-t)E_{22}\otimes E_{22}+2E_{33}\otimes E_{33}\\\ &+tE_{22}\otimes
E_{11}+tE_{11}\otimes E_{22}-\sum_{i\not=j}E_{ij}\otimes E_{ij}.\end{array}$

If $1\leq t\leq\frac{3}{2}$, then let

$C_{1}=(2-t)E_{11}\otimes E_{11}+(2-t)E_{22}\otimes E_{22}+2E_{33}\otimes
E_{33}-\sum_{i\neq j;\pi(i)\neq j}E_{ij}\otimes E_{ij}$

and

$C_{2}=tE_{22}\otimes E_{11}+tE_{11}\otimes E_{22}-E_{12}\otimes
E_{12}-E_{21}\otimes E_{21}.$

It is easily checked that $C_{1}\geq 0$. As $C_{2}^{{\rm
T}_{2}}=tE_{22}\otimes E_{11}+tE_{11}\otimes E_{22}-E_{12}\otimes
E_{21}-E_{21}\otimes E_{12}\geq 0,$ we see that $C_{2}$ is PPT. It is clear
that $C_{1}\not=0$ and $W_{\Phi_{t,\pi}}=C_{1}+C_{2}$. Hence
$W_{\Phi_{t,\pi}}$ is decomposable and not optimal.

If $0<t<1$, then let

$\begin{array}[]{rl}D_{1}=&(2-t)E_{11}\otimes E_{11}+(2-t)E_{22}\otimes
E_{22}+2E_{33}\otimes E_{33}\\\ &-\sum_{i\neq j;\pi(i)\neq j}E_{ij}\otimes
E_{ij}-(1-t)E_{12}\otimes E_{12}-(1-t)E_{21}\otimes E_{21}\end{array}$

and

$D_{2}=tE_{22}\otimes E_{11}+tE_{11}\otimes E_{22}-tE_{12}\otimes
E_{12}-tE_{21}\otimes E_{21}.$

It is also clear that $D_{2}$ is PPT and $D_{1}\geq 0$. We still have
$D_{1}\not=0$ and $W_{\Phi_{t,\pi}}=D_{1}+D_{2}$. Hence $W_{\Phi_{t,\pi}}$ is
decomposable and not optimal.

Case 3. $l(\pi)=3$, i.e., $\pi$ is cyclic.

If $l(\pi)=3$ and $t=1$, then $\pi$ is a cyclic permutation, and by [13,
Theorem 3.2], $W_{\Phi_{1,\pi}}$ is optimal.

In the sequel we always assume that $l(\pi)=3$. Our aim is to prove that
$W_{\Phi_{t,\pi}}$ is not optimal for any $0<t<1$. Without loss of generality,
let $\pi(i)=(i+1)\ {\rm mod}\ 3$, $i=1,2,3$. By Theorem 1.1, to prove that
$W_{\Phi_{t,\pi}}$ is not optimal, we have to prove that there exists a matrix
$C\in M_{3}({\mathbb{C}})$ such that the linear map
$A\mapsto\Phi_{t,\pi}(A)-CAC^{\dagger}$ is positive. Indeed, we will show
that, for any positive number $0<c\leq\sqrt{1-t}$, let $C_{0}={\rm
diag}(c,-c,0)$; then the map $A\mapsto\Phi_{t,\pi}(A)-CAC^{\dagger}$ is
positive.

To do this, let $C_{0}={\rm diag}(c,-c,0)$ with $c>0$ and let $\Psi_{C_{0}}$
be the map defined by

$\begin{array}[]{rl}\Psi_{C_{0}}(A)=&\Phi_{t,\pi}(A)-C_{0}AC_{0}^{\dagger}\\\
=&(3-t)\sum_{i=1}^{3}E_{ii}AE_{ii}^{\dagger}+\sum_{i=1}^{3}E_{i,i+1}AE_{i,i+1}^{\dagger}-A-C_{0}AC_{0}^{\dagger}\end{array}$

for all $A\in M_{3}({\mathbb{C}})$.

If $\Psi_{C_{0}}$ is positive, then by Lemma 2.3, for any unit
$|x\rangle\in{\mathbb{C}}^{3}$, there exist scalars
$\\{\alpha_{i}(|x\rangle)\\}_{i=1}^{3}$,
$\\{\beta_{i}(|x\rangle)\\}_{i=1}^{3}$,
$\\{\delta_{i}(|x\rangle)\\}_{i=1}^{3}$ and
$\\{\gamma_{i}(|x\rangle)\\}_{i=1}^{3}$ such that

$None$
$|x\rangle=I|x\rangle=\sum_{i=1}^{3}\alpha_{i}(|x\rangle)(\sqrt{3-t}E_{ii})|x\rangle+\sum_{i=1}^{3}\beta_{i}(|x\rangle)\sqrt{t}E_{i,i+1}|x\rangle,$
$None$
$C|x\rangle=\sum_{i=1}^{3}\delta_{i}(|x\rangle)(\sqrt{3-t}E_{ii})|x\rangle+\sum_{i=1}^{3}\gamma_{i}(|x\rangle)\sqrt{t}E_{i,i+1}|x\rangle,$

and the matrix

$F_{x}=\left(\begin{array}[]{cccccc}\alpha_{1}(|x\rangle)&\alpha_{2}(|x\rangle)&\alpha_{3}(|x\rangle)&\beta_{1}(|x\rangle)&\beta_{2}(|x\rangle)&\beta_{3}(|x\rangle)\\\
\delta_{1}(|x\rangle)&\delta_{2}(|x\rangle)&\delta_{3}(|x\rangle)&\gamma_{1}(|x\rangle)&\gamma_{2}(|x\rangle)&\gamma_{3}(|x\rangle)\end{array}\right)$

is contractive.

Note that $\|F_{x}\|\leq 1$ if and only if $\|F_{x}F_{x}^{\dagger}\|\leq 1$.

In the sequel, for any unit $|x\rangle\in{\mathbb{C}}^{3}$, we write
$|x\rangle=(|x_{1}|e^{i\theta_{1}},|x_{2}|e^{i\theta_{2}},|x_{3}|e^{i\theta_{3}})^{T}$.
Then $|x_{1}|^{2}+|x_{2}|^{2}+|x_{3}|^{2}=1$.

Subcase 1. $|x_{1}|=|x_{2}|=|x_{3}|=\frac{1}{\sqrt{3}}$.

In Eqs.(2.3)-(2.4), by taking

$(\alpha_{1},\alpha_{2},\alpha_{3})=(\frac{\sqrt{3-t}}{3},\frac{\sqrt{3-t}}{3},\frac{\sqrt{3-t}}{3})\
\ \ {\rm and}\ \
(\delta_{1},\delta_{2},\delta_{3})=(\frac{\sqrt{3-t}c}{3},-\frac{\sqrt{3-t}c}{3},0),$

we get

$(\beta_{1},\beta_{2},\beta_{3})=(\frac{{\sqrt{t}}x_{1}}{3x_{2}},\frac{{\sqrt{t}}x_{2}}{3x_{3}},\frac{{\sqrt{t}}x_{3}}{3x_{1}})\
\ \ {\rm and}\ \
(\gamma_{1},\gamma_{2},\gamma_{3})=(\frac{{\sqrt{t}c}x_{1}}{3x_{2}},-\frac{{\sqrt{t}}cx_{2}}{3x_{3}},0).$

So $\sum_{i=1}^{3}(|\alpha_{i}|^{2}+|\beta_{i}|^{2})=1$,
$\sum_{i=1}^{3}(|\delta_{i}|^{2}+|\gamma_{i}|^{2})=\frac{6c^{2}}{9}$ and
$\sum_{i=1}^{3}(\alpha_{i}\overline{\delta_{i}}+\beta_{i}\overline{\gamma_{i}})=0$.
It follows that

$F_{x}F_{x}^{\dagger}=\left(\begin{array}[]{cc}\sum_{i=1}^{3}(|\alpha_{i}|^{2}+|\beta_{i}|^{2})&\sum_{i=1}^{3}(\alpha_{i}\bar{\delta_{i}}+\beta_{i}\bar{\gamma_{i}})\\\
\sum_{i=1}^{3}(\bar{\alpha_{i}}\delta_{i}+\bar{\beta_{i}}\gamma_{i})&\sum_{i=1}^{3}(|\delta_{i}|^{2}+|\gamma_{i}|^{2})\end{array}\right)=\left(\begin{array}[]{cc}1&0\\\
0&\frac{6c^{2}}{9}\end{array}\right),$

which implies that $\|F_{x}F_{x}^{\dagger}\|\leq 1\Leftrightarrow
c^{2}\leq\frac{9}{6}.$ Hence

$c^{2}\leq 1-t\Rightarrow\|F_{x}F_{x}^{\dagger}\|\leq 1.$

Subcase 2. $x_{i}\not=0$ for all $i=1,2,3$ and
$(|x_{1}|,|x_{2}|,|x_{3}|)\not=(\frac{1}{\sqrt{3}},\frac{1}{\sqrt{3}},\frac{1}{\sqrt{3}})$.

Let $r_{i}=|\frac{x_{i}}{x_{i+1}}|^{2}$ for $i=1,2,3$. Then $r_{i}>0$,
$i=1,2,3$, and $r_{1}r_{2}r_{3}=1$. Take

$(\alpha_{1},\alpha_{2},\alpha_{3})=(\frac{\sqrt{3-t}r_{1}}{t+(3-t)r_{1}},\frac{\sqrt{3-t}r_{2}}{t+(3-t)r_{2}},\frac{\sqrt{3-t}r_{3}}{t+(3-t)r_{3}})$

and

$(\delta_{1},\delta_{2},\delta_{3})=(\frac{\sqrt{3-t}r_{1}c}{t+(3-t)r_{1}},-\frac{\sqrt{3-t}r_{2}c}{t+(3-t)r_{2}},0).$

By Eqs.(2.3)-(2.4), we get

$(\beta_{1},\beta_{2},\beta_{3})=(\frac{\sqrt{r_{1}}}{t+(3-t)r_{1}}e^{i(\theta_{1}-\theta_{2})},\frac{\sqrt{r_{2}}}{t+(3-t)r_{2}}e^{i(\theta_{2}-\theta_{3})},\frac{\sqrt{r_{3}}}{t+(3-t)r_{3}}e^{i(\theta_{3}-\theta_{1})})$

and

$(\gamma_{1},\gamma_{2},\gamma_{3})=(\frac{\sqrt{tr_{1}}c}{t+(3-t)r_{1}}e^{i(\theta_{1}-\theta_{2})},-\frac{\sqrt{tr_{2}}c}{t+(3-t)r_{2}}e^{i(\theta_{2}-\theta_{3})},0).$

So

$f(\alpha_{1},\alpha_{2},\alpha_{3})=\sum_{i=1}^{3}|\alpha_{i}|^{2}+\sum_{i=1}^{3}|\beta_{i}|^{2}=\sum_{i=1}^{3}\frac{r_{i}}{t+(3-t)r_{i}},$
$f_{C_{0}}(\delta_{1},\delta_{2},\delta_{3})=\sum_{i=1}^{3}|\delta_{i}|^{2}+\sum_{i=1}^{3}|\gamma_{i}|^{2}=\frac{r_{1}c^{2}}{t+(3-t)r_{1}}+\frac{r_{2}c^{2}}{t+(3-t)r_{2}}$

and

$\sum_{i=1}^{3}(\alpha_{i}\bar{\delta_{i}}+\beta_{i}\bar{\gamma_{i}})=\frac{r_{1}c}{t+(3-t)r_{1}}-\frac{r_{2}c}{t+(3-t)r_{2}}.$

It follows that

$\begin{array}[]{rl}F_{x}F_{x}^{\dagger}=&\left(\begin{array}[]{cc}\sum_{i=1}^{3}(|\alpha_{i}|^{2}+|\beta_{i}|^{2})&\sum_{i=1}^{3}(\alpha_{i}\bar{\delta_{i}}+\beta_{i}\bar{\gamma_{i}})\\\
\sum_{i=1}^{3}(\bar{\alpha_{i}}\delta_{i}+\bar{\beta_{i}}\gamma_{i})&\sum_{i=1}^{3}(|\delta_{i}|^{2}+|\gamma_{i}|^{2})\end{array}\right)\\\
=&\left(\begin{array}[]{cc}\sum_{i=1}^{3}\frac{r_{i}}{t+(3-t)r_{i}}&\frac{r_{1}c}{t+(3-t)r_{1}}-\frac{r_{2}c}{t+(3-t)r_{2}}\\\
\frac{r_{1}c}{t+(3-t)r_{1}}-\frac{r_{2}c}{t+(3-t)r_{2}}&\frac{r_{1}c^{2}}{t+(3-t)r_{1}}+\frac{r_{2}c^{2}}{t+(3-t)r_{2}}\end{array}\right).\end{array}$

Note that $\|F_{x}F_{x}^{\dagger}\|\leq 1$ if and only if its maximal
eigenvalue $\lambda_{{\rm max}}\leq 1$. By a calculation, it is easily checked
that

$\lambda_{{\rm max}}\leq 1$

holds if and only if

$None$
$c^{2}\leq\frac{1-\sum_{i=1}^{3}\frac{r_{i}}{t+(3-t)r_{i}}}{(1-\sum_{i=1}^{3}\frac{r_{i}}{t+(3-t)r_{i}})(\frac{r_{1}}{t+(3-t)r_{1}}+\frac{r_{2}}{t+(3-t)r_{2}})+(\frac{r_{1}}{t+(3-t)r_{1}}-\frac{r_{2}}{t+(3-t)r_{2}})^{2}},$

where $r_{1},r_{2},r_{3}>0$ with $r_{1}r_{2}r_{3}=1$ and
$(r_{1},r_{2},r_{3})\not=(1,1,1)$. Let

$g(r_{1},r_{2},r_{3})=\frac{1-\sum_{i=1}^{3}\frac{r_{i}}{t+(3-t)r_{i}}}{(1-\sum_{i=1}^{3}\frac{r_{i}}{t+(3-t)r_{i}})(\frac{r_{1}}{t+(3-t)r_{1}}+\frac{r_{2}}{t+(3-t)r_{2}})+(\frac{r_{1}}{t+(3-t)r_{1}}-\frac{r_{2}}{t+(3-t)r_{2}})^{2}}.$

Replacing $r_{i}$ by $\frac{1}{r_{i}}$ in the above function
$g(r_{1},r_{2},r_{3})$, we have

$g(r_{1},r_{2},r_{3})=\frac{1-\sum_{i=1}^{3}\frac{1}{(3-t)+tr_{i}}}{\sum_{i=1}^{2}\frac{1}{(3-t)+tr_{i}}-\frac{4}{(3-t+tr_{1})(3-t+tr_{2})}-\frac{1}{(3-t+tr_{1})(3-t+tr_{3})}-\frac{1}{(3-t+tr_{2})(3-t+tr_{3})}}.$

Now applying Lemma 2.4, we see that

$g(r_{1},r_{2},r_{3})\geq 1-t$

holds for all positive numbers $r_{1},r_{2},r_{3}$ with $r_{1}r_{2}r_{3}=1$
and $(r_{1},r_{2},r_{3})\not=(1,1,1)$. This and Eq.(2.5) imply

$c^{2}\leq(1-t)\Rightarrow\lambda_{{\rm max}}\leq
1\Rightarrow\|F_{x}F_{x}^{\dagger}\|\leq 1.$

Subcase 3. $x_{1}=0$ and $x_{i}\not=0$ for $i=2,3$.

In this case, by Eqs.(2.3)-(2.4), one may choose
$\beta_{1}=\delta_{3}=\gamma_{1}=0$, $\alpha_{3}=\frac{1}{\sqrt{3-t}}$,
$\beta_{2}=\frac{(1-\sqrt{3-t}\alpha_{2})x_{2}}{\sqrt{t}x_{3}}$ and
$\gamma_{2}=\frac{(-c-\sqrt{3-t}\delta_{2})x_{2}}{\sqrt{t}x_{3}}$. Write
$r_{2}=|\frac{x_{2}}{x_{3}}|^{2}=\frac{|x_{2}|^{2}}{1-|x_{2}|^{2}}$. Then by
taking

$\begin{array}[]{rl}&(\alpha_{1},\alpha_{2},\alpha_{3},\beta_{1},\beta_{2},\beta_{3})=(0,\frac{\sqrt{3-t}r_{2}}{t+(3-t)r_{2}},\frac{1}{\sqrt{3-t}},0,\frac{\sqrt{t}\sqrt{r_{2}}}{t+(3-t)r_{2}}e^{i(\theta_{2}-\theta_{3})},0)\end{array}$

and

$(\delta_{1},\delta_{2},\delta_{3},\gamma_{1},\gamma_{2},\gamma_{3})=(0,-\frac{\sqrt{t}\sqrt{r_{2}}c}{t+(3-t)r_{2}}e^{i(\theta_{2}-\theta_{3})},0),$

which meet Eqs.(2.3)-(2.4), we get

$f(\alpha_{1},\alpha_{2},\alpha_{3})=\sum_{i=1}^{3}|\alpha_{i}|^{2}+\sum_{i=1}^{3}|\beta_{i}|^{2}=\frac{r_{2}}{t+(3-t)r_{2}}+\frac{1}{3-t},$
$f_{C_{0}}(\delta_{1},\delta_{2},\delta_{3})=\sum_{i=1}^{3}|\delta_{i}|^{2}+\sum_{i=1}^{3}|\gamma_{i}|^{2}=\frac{r_{2}c^{2}}{t+(3-t)r_{2}}$

and

$\sum_{i=1}^{3}(\alpha_{i}\bar{\delta_{i}}+\beta_{i}\bar{\gamma_{i}})=-\frac{r_{2}c}{t+(3-t)r_{2}}.$

Hence

$F_{x}F_{x}^{\dagger}=\left(\begin{array}[]{cc}\frac{r_{2}}{t+(3-t)r_{2}}+\frac{1}{3-t}&-\frac{r_{2}c}{t+(3-t)r_{2}}\\\
-\frac{r_{2}c}{t+(3-t)r_{2}}&\frac{r_{2}c^{2}}{t+(3-t)r_{2}}\end{array}\right).$

Still, by a calculation, one can easily obtain

$None$ $\|F_{x}F_{x}^{\dagger}\|\leq 1\Leftrightarrow
c^{2}\leq\frac{1-\frac{r_{2}}{t+(3-t)r_{2}}-\frac{1}{3-t}}{\frac{r_{2}}{t+(3-t)r_{2}}-\frac{r_{2}}{(t+(3-t)r_{2})(3-t)}},$

where $r_{2}>0$ is any positive number. Let

$g(r_{2})=\frac{1-\frac{r_{2}}{t+(3-t)r_{2}}-\frac{1}{3-t}}{\frac{r_{2}}{t+(3-t)r_{2}}-\frac{r_{2}}{(t+(3-t)r_{2})(3-t)}}.$

A direct calculation yields that,

$None$ $g(r_{2})\geq 1-t\Leftrightarrow r_{2}\geq\frac{t(2-t)}{t-1}.$

Note that $r_{2}>0$ and $\frac{t(2-t)}{t-1}<0$ as $0<t<1$. So we always have
$r_{2}\geq\frac{t(2-t)}{t-1}$. Thus by Eq.(2.7), we have proved that
$g(r_{2})\geq 1-t$ holds for all positive numbers $r_{2}>0$. It follows from
Eq.(2.6) that

$c^{2}\leq 1-t\Rightarrow\|F_{x}F_{x}^{\dagger}\|\leq 1.$

Subcase 4. $x_{2}=0$ and $x_{i}\not=0$ for $i=1,3$.

Let $r_{3}=|\frac{x_{3}}{x_{1}}|^{2}=\frac{|x_{3}|^{2}}{1-|x_{3}|^{2}}$. By
Eqs.(2.3)-(2.4), we can choose $\beta_{2}=\gamma_{2}=0$,
$\alpha_{1}=\frac{1}{\sqrt{3-t}}$,
$\alpha_{3}=\frac{\sqrt{3-t}r_{3}}{t+(3-t)r_{3}}$,
$\beta_{3}=\frac{(1-\sqrt{3-t}\alpha_{3})x_{3}}{\sqrt{t}x_{1}}$ and
$\gamma_{3}=\frac{-\sqrt{3-t}\delta_{3}x_{3}}{\sqrt{t}x_{1}}$. Now take

$\begin{array}[]{rl}&(\alpha_{1},\alpha_{2},\alpha_{3},\beta_{1},\beta_{2},\beta_{3})=(\frac{1}{\sqrt{3-t}},0,\frac{\sqrt{3-t}r_{3}}{t+(3-t)r_{3}},0,0,\frac{\sqrt{t}\sqrt{r_{3}}}{t+(3-t)r_{3}}e^{i(\theta_{3}-\theta_{1})})\end{array}$

and

$(\delta_{1},\delta_{2},\delta_{3},\gamma_{1},\gamma_{2},\gamma_{3})=(\frac{c}{\sqrt{3-t}},0,0,0,0,0).$

It follows that

$f(\alpha_{1},\alpha_{2},\alpha_{3})=\sum_{i=1}^{3}|\alpha_{i}|^{2}+\sum_{i=1}^{3}|\beta_{i}|^{2}=\frac{r_{3}}{t+(3-t)r_{3}}+\frac{1}{3-t},$
$f_{C_{0}}(\delta_{1},\delta_{2},\delta_{3})=\sum_{i=1}^{3}|\delta_{i}|^{2}+\sum_{i=1}^{3}|\gamma_{i}|^{2}=\frac{c^{2}}{3-t}$

and

$\sum_{i=1}^{3}(\alpha_{i}\bar{\delta_{i}}+\beta_{i}\bar{\gamma_{i}})=\frac{c}{3-t}.$

Hence

$F_{x}F_{x}^{\dagger}=\left(\begin{array}[]{cc}\frac{r_{3}}{t+(3-t)r_{3}}+\frac{1}{3-t}&\frac{c}{3-t}\\\
\frac{c}{3-t}&\frac{c^{2}}{3-t}\end{array}\right).$

Still, one can easily checked that

$\|F_{x}F_{x}^{\dagger}\|\leq 1\Leftrightarrow
c^{2}\leq\frac{1-\frac{r_{3}}{t+(3-t)r_{3}}-\frac{1}{3-t}}{\frac{1}{3-t}-\frac{r_{3}}{(t+(3-t)r_{3})(3-t)}}$

and

$\frac{1-\frac{r_{3}}{t+(3-t)r_{3}}-\frac{1}{3-t}}{\frac{1}{3-t}-\frac{r_{3}}{(t+(3-t)r_{3})(3-t)}}\geq
1-t\Leftrightarrow t\geq(t-1)r_{3},$

where $r_{3}>0$ is any positive number and $0<t<1$. Note that
$t\geq(t-1)r_{3}$ as $0<t<1$ and $r_{3}>0$. Thus we see that we still have

$c^{2}\leq 1-t\Rightarrow\|F_{x}F_{x}^{\dagger}\|\leq 1.$

Subcase 5. $x_{3}=0$ and $x_{i}\not=0$ for $i=1,2$.

Let $r_{1}=|\frac{x_{1}}{x_{2}}|^{2}=\frac{|x_{1}|^{2}}{1-|x_{1}|^{2}}$. By
Eqs.(2.3)-(2.4), one may choose $\beta_{3}=\gamma_{3}=0$,
$\alpha_{2}=\frac{1}{\sqrt{3-t}}$,
$\beta_{1}=\frac{(1-\sqrt{3-t}\alpha_{1})x_{1}}{\sqrt{t}x_{2}}$,
$\delta_{2}=\frac{-c}{\sqrt{3-t}}$ and
$\gamma_{1}=\frac{(c-\sqrt{3-t}\delta_{1})x_{1}}{\sqrt{t}x_{2}}$. Then for
choice

$\begin{array}[]{rl}&(\alpha_{1},\alpha_{2},\alpha_{3},\beta_{1},\beta_{2},\beta_{3})=(\frac{\sqrt{3-t}r_{1}}{t+(3-t)r_{1}},\frac{1}{\sqrt{3-t}},0,\frac{\sqrt{t}\sqrt{r_{1}}}{t+(3-t)r_{1}}e^{i(\theta_{1}-\theta_{2})},0,0)\end{array}$

and

$(\delta_{1},\delta_{2},\delta_{3},\gamma_{1},\gamma_{2},\gamma_{3})=(\frac{\sqrt{3-t}r_{1}c}{t+(3-t)r_{1}},\frac{-c}{\sqrt{3-t}},0,\frac{\sqrt{t}\sqrt{r_{1}}c}{t+(3-t)r_{1}}e^{i(\theta_{1}-\theta_{2})},0,0),$

we get

$f(\alpha_{1},\alpha_{2},\alpha_{3})=\sum_{i=1}^{3}|\alpha_{i}|^{2}+\sum_{i=1}^{3}|\beta_{i}|^{2}=\frac{r_{1}}{t+(3-t)r_{1}}+\frac{1}{3-t},$
$f_{C_{0}}(\delta_{1},\delta_{2},\delta_{3})=\sum_{i=1}^{3}|\delta_{i}|^{2}+\sum_{i=1}^{3}|\gamma_{i}|^{2}=\frac{r_{1}c^{2}}{t+(3-t)r_{1}}+\frac{c^{2}}{3-t}$

and

$\sum_{i=1}^{3}(\alpha_{i}\bar{\delta_{i}}+\beta_{i}\bar{\gamma_{i}})=\frac{r_{1}c}{t+(3-t)r_{1}}-\frac{c}{3-t}.$

So

$F_{x}F_{x}^{\dagger}=\left(\begin{array}[]{cc}\frac{r_{1}}{t+(3-t)r_{1}}+\frac{1}{3-t}&\frac{r_{1}c}{t+(3-t)r_{1}}-\frac{c}{3-t}\\\
\frac{r_{1}c}{t+(3-t)r_{1}}-\frac{c}{3-t}&\frac{r_{1}c^{2}}{t+(3-t)r_{1}}+\frac{c^{2}}{3-t}\end{array}\right).$

It is easily checked that

$None$ $\|F_{x}F_{x}^{\dagger}\|\leq 1\Leftrightarrow
c^{2}\leq\frac{1-\frac{r_{1}}{t+(3-t)r_{1}}-\frac{1}{3-t}}{(1-\frac{r_{1}}{t+(3-t)r_{1}}-\frac{1}{3-t})(\frac{r_{1}}{t+(3-t)r_{1}}+\frac{1}{3-t})+(\frac{r_{1}}{t+(3-t)r_{1}}-\frac{1}{3-t})^{2}},$

where $r_{1}>0$ is any positive number and $0<t<1$. Let

$g(r_{1})=\frac{1-\frac{r_{1}}{t+(3-t)r_{1}}-\frac{1}{3-t}}{(1-\frac{r_{1}}{t+(3-t)r_{1}}-\frac{1}{3-t})(\frac{r_{1}}{t+(3-t)r_{1}}+\frac{1}{3-t})+(\frac{r_{1}}{t+(3-t)r_{1}}-\frac{1}{3-t})^{2}}.$

By a direct calculation, one gets

$g(r_{1})\geq 1-t\Leftrightarrow 1-t^{2}+tr_{1}\geq 0.$

Hence we always have $g(r_{1})\geq 1-t$. This and Eq.(2.8) yield again

$c^{2}\leq 1-t\Rightarrow\|F_{x}F_{x}^{\dagger}\|\leq 1.$

Subcase 6. $x_{1}=x_{2}=0$ and $x_{3}\not=0$.

By Eqs.(2.3)-(2.4), we have $\beta_{2}=\delta_{3}=\gamma_{2}=0$ and
$\alpha_{3}=\frac{1}{\sqrt{3-t}}$. Then take

$(\alpha_{1},\alpha_{2},\alpha_{3},\beta_{1},\beta_{2},\beta_{3})=(0,0,\frac{1}{\sqrt{3-t}},0,0,0)\
{\rm and}\
(\delta_{1},\delta_{2},\delta_{3},\gamma_{1},\gamma_{2},\gamma_{3})=(0,0,0,0,0,0).$

We obtain $F_{x}F_{x}^{\dagger}=\left(\begin{array}[]{cc}\frac{1}{3-t}&0\\\
0&0\end{array}\right),$ which is contractive.

Subcase 7. $x_{1}=x_{3}=0$ and $x_{2}\not=0$.

By Eqs.(2.3)-(2.4), we have $\beta_{1}=\gamma_{1}=0$,
$\alpha_{2}=\frac{1}{\sqrt{3-t}}$ and $\gamma_{2}=\frac{c}{\sqrt{3-t}}$. Then
by taking

$(\alpha_{1},\alpha_{2},\alpha_{3},\beta_{1},\beta_{2},\beta_{3})=(0,\frac{1}{\sqrt{3-t}},0,0,0,0)\
{\rm and}\
(\delta_{1},\delta_{2},\delta_{3},\gamma_{1},\gamma_{2},\gamma_{3})=(0,0,0,0,\frac{c}{\sqrt{3-t}},0),$

we obtain
$F_{x}F_{x}^{\dagger}=\left(\begin{array}[]{cc}\frac{1}{3-t}&\frac{c}{3-t}\\\
\frac{c}{3-t}&\frac{c^{2}}{3-t}\end{array}\right)=\frac{1}{3-t}\left(\begin{array}[]{cc}1&c\\\
c&c^{2}\end{array}\right)$. It is easy to check that

$\|F_{x}F_{x}^{\dagger}\|\leq 1\Leftrightarrow c^{2}\leq(2-t).$

So $c^{2}\leq 1-t$ implies $\|F_{x}F_{x}^{\dagger}\|\leq 1$.

Subcase 8. $x_{2}=x_{3}=0$ and $x_{1}\not=0$.

The case is the same as Case 7.

Thus, by combining Subcases 1-8 and applying Lemma 2.3, we have proved that,
for any matrix $C_{0}={\rm diag}(c,-c,0)$ with $0<c^{2}\leq 1-t$, the map
$A\mapsto\Phi_{t,\pi}(A)-C_{0}AC_{0}^{\dagger}$ is positive. Then, by Theorem
1.1, we see that $W_{\Phi_{t,\pi}}$ is not optimal whenever $l(\pi)=3$ and
$0<t<1$.

The proof is finished. $\Box$

##  3\. Conclusions

Every entangled state can be detected by an optimal entanglement witness. So,
it is important to construct as many as possible optimal EWs. A natural way of
constructing optimal EWs is through NCP positive maps by Choi-Jamiołkowski
isomorphism $\Phi\leftrightarrow W_{\Phi}$. In [14], for $0\leq t\leq n$, a
class of new $D$-type positive maps
$\Phi_{t,\pi}:M_{n}({\mathbb{C}})\rightarrow M_{n}({\mathbb{C}})$ induced by
an arbitrary permutation $\pi$ of $(1,2,\ldots,n)$ was constructed, where
$\Phi_{t,\pi}$ is defined by

$None$
$\Phi_{t,\pi}(A)=(n-t)\sum_{i=1}^{n}E_{ii}AE_{ii}+t\sum_{i=1}^{n}E_{i,\pi(i)}AE_{i,\pi(i)}^{\dagger}-A.$

It was shown in [14] that $\Phi_{t,\pi}$ in NCP positive if and only if
$0<t\leq\frac{n}{l(\pi)}$. In [12], by using Theorem 1.1, we proved that
$W_{\Phi_{1,\pi}}$ is optimal if $l(\pi)=n$ and $\pi^{2}\not={\rm id}$. But it
is not clear that whether or not there exist other optimal
$W_{\Phi_{t,\pi}}$s. We guess there are no.

Conjecture. For $n\geq 3$, $W_{\Phi_{t,\pi}}$ is an optimal entanglement
witness if and only if $t=1$, $l(\pi)=n$ and $\pi^{2}\not={\rm id}$.

The case $n=2$ is simple. It is easily checked that $W_{\Phi_{t,\pi}}$ is
optimal if and only if $t=1$ and $l(\pi)=2$. Note that, $\pi^{2}=$id if $n=2$.

The present note gives an affirmative answer to the above conjecture for the
case $n=3$.

## References

  * [1] D. Bru${\ss}$, J. Math. Phys. 43 (2002) 4237.
  * [2] M.-D. Choi, Lin. Alg. Appl. 10, 285 (1975); ibid 12, 95 (1975).
  * [3] D. Chru$\acute{s}$ci$\acute{n}$ski and A. Kossakowski, Open Systems and Inf. Dynamics 14 (2007) 275.
  * [4] M. Horodecki, P. Horodecki, R. Horodecki, Phys. Lett. A 223 (1996) 1.
  * [5] J. Hou, J. Operator Theory, 39 (1998), 43-58.
  * [6] J. Hou, J. Phys. A: Math. Theor. 43 (2010) 385201; arXiv[quant-ph]: 1007.0560v1.
  * [7] J. Hou, X. Qi, Phys. Rev. A 81 (2010) 062351.
  * [8] M. A. Jafarizadeh, N. Behzadi, Y. Akbari, Eur. Phys. J. D 55 (2009) 197.
  * [9] A. Jamiołkowski, Rep. Math. Phys. 3, 275 (1972).
  * [10] M. Lewensetein, B. Kraus, J.I. Cirac, P. Horodecki, Phys. Rev. A 62 (2001) 052310.
  * [11] M. A. Nielsen, I. L. Chuang, Cambridge University Press, Cambridge, 2000.
  * [12] X. Qi, J. Hou, Phys. Rev. A 85 (2012) 022334.
  * [13] X. Qi, J. Hou, J. Phys. A: Math. Theor. 43 (2011) 385201.
  * [14] J. C. Hou, Chi-Kwong Li, Yiu-Tung Poon, X. F. Qi, Nung-Sing Sze, Criteria for $k$-positivity of linear maps, arXiv: 1211.036v1.
  * [15] G. T$\acute{o}$th, O. G$\ddot{u}$hne, Phys. Rev. Lett. 94 (2005) 060501.


# The solution set of fuzzy relation equations with addition-min composition

Meng Li111 _E-mail address_<EMAIL_ADDRESS>Xue-ping Wang222Corresponding
author<EMAIL_ADDRESS>fax: +86-28-84761393
_School of Mathematical Sciences, Sichuan Normal University,_
_Chengdu 610066, Sichuan, People’s Republic of China_

###### Abstract

This paper deals with the resolutions of fuzzy relation equations with
addition-min composition. When the fuzzy relation equations have a solution,
we first propose an algorithm to find all minimal solutions of the fuzzy
relation equations and also supply an algorithm to find all maximal solutions
of the fuzzy relation equations, which will be illustrated, respectively, by
numeral examples. Then we prove that every solution of the fuzzy relation
equations is between a minimal solution and a maximal one, so that we describe
the solution set of the fuzzy relation equations completely.

###### keywords:

Fuzzy relation equation; Addition-min composition; Minimal solution; Maximal
solution; Algorithm

mytitlenotemytitlenotefootnotetext: This work is supported by the National
Natural Science Foundation of China (No. 12071325).

##  1 Introduction

The system of fuzzy relation equations with max-min composition was first
studied by E. Sanchez [8]. The complete solution set of such finite system is
determined by the unique maximal solution and a finite number of minimal
solutions [2]. In recent year, the theory of fuzzy relation inequalities with
addition-min composition has been applied to BitTorrent-like peer-to-peer
(P2P) file sharing system widely [5]. In such file sharing system, let
$A_{1},A_{2},\cdots,A_{n}$ be $n$ users who are downloading some file datas
simultaneously. Suppose that the $jth$ user $A_{j}$ sends the file data with
quality level $x_{j}$ to $A_{i}$, and the bandwidth between $A_{i}$ and
$A_{j}$ is $a_{ij}$. Because of the bandwidth limitation, the network traffic
that $A_{i}$ receives from $A_{j}$ is actually $a_{ij}\wedge x_{j}$, and
$A_{i}$ receiving the file data from other users is $a_{i1}\wedge
x_{1}+\cdots+a_{i{}i-1}\wedge x_{i-1}+a_{i{i+1}}\wedge
x_{i+1}+\cdots+a_{in}\wedge x_{n}$. If the quality requirement of download
traffic of $A_{i}$ is at least $b_{i}$ ($b_{i}>0$), then the data transmission
mechanism in the file sharing systems is reduced to the system of fuzzy
relation inequations with addition-min composition as follows:

$\left\\{\begin{array}[]{ll}a_{11}\wedge x_{1}+a_{12}\wedge
x_{2}+\cdots+a_{1n}\wedge x_{n}\geq b_{1},\\\ a_{21}\wedge x_{1}+a_{22}\wedge
x_{2}+\cdots+a_{2n}\wedge x_{n}\geq b_{2},\\\ \cdots\\\ a_{m1}\wedge
x_{1}+a_{m2}\wedge x_{2}+\cdots+a_{mn}\wedge x_{n}\geq
b_{m},\end{array}\right.$ (1.1)

where $a_{ij},x_{j}\in[0,1]$, $b_{i}>0$ $(i=1,2,\ldots,m;j=1,2,\ldots,n)$,
$a_{ij}\wedge x_{j}=\min\\{a_{ij},x_{j}\\}$, and the operation $``+"$ is the
ordinary addition. The solution set of the system (1.1) and the related
optimization problems have been investigated[12, 1, 3, 4, 9, 10, 13, 11, 6].

In a circumstances of wireless communication, the information is transmitted
by the electromagnetic wave. As we know, a high radiation intensity can ensure
a good communication quality, but it will also damage the health of humans.
Therefore, in the BitTorrent-like P2P file sharing systems, we are usually
facing that the quality requirement of download traffic of every $A_{i}$ is
exactly required to equal $b_{i}$ ($b_{i}>0$) assigned. Then the file sharing
system (1.1) is transformed to fuzzy relation equations with addition-min
composition as follows.

$\left\\{\begin{array}[]{ll}a_{11}\wedge x_{1}+a_{12}\wedge
x_{2}+\cdots+a_{1n}\wedge x_{n}=b_{1},\\\ a_{21}\wedge x_{1}+a_{22}\wedge
x_{2}+\cdots+a_{2n}\wedge x_{n}=b_{2},\\\ \cdots\\\ a_{m1}\wedge
x_{1}+a_{m2}\wedge x_{2}+\cdots+a_{mn}\wedge x_{n}=b_{m}.\end{array}\right.$
(1.2)

In [10], the system (1.2) is called the corresponding equations system of
system (1.1), and Yang gave an equivalent condition for a solution of the
system (1.2) to be a minimal one. This article will focuses on the structure
of the solution set of system (1.2) by characterizing all minimal and maximal
solutions of system (1.2).

The rest of this article is organized as follows. In Section 2, we present
some relevant definitions and basic properties. In Section 3, we first give a
necessary and sufficient condition for a solution of system (1.2) being a
minimal one, then we present an algorithm to find all minimal solutions. In
Section 4, we first show a necessary and sufficient condition for a solution
of system (1.2) being a maximal solution, and then suggest an algorithm to
find all maximal solutions. In Section 5, we first prove that every solution
of system (1.2) is between a minimal solution and a maximal one if system
(1.2) has a solution, then we describe the solution set of system (1.2). A
conclusion is drawn in Section 6.

##  2 Preliminaries

This section presents some basic definitions and results.

Let $I=\\{1,2,\cdots,m\\}$ and $J=\\{1,2,\cdots,n\\}$ be two index sets. For
$x^{1}=(x_{1}^{1},x_{2}^{1},\cdots,x_{n}^{1})$,
$x^{2}=(x_{1}^{2},x_{2}^{2},\cdots,x_{n}^{2})\in[0,1]^{n}$, define
${x^{1}}\leq{x^{2}}$ if and only if ${x_{j}}^{1}\leq{x_{j}}^{2}$ for arbitrary
$j\in J$, and define ${x^{1}}<{x^{2}}$ if and only if
${x_{j}}^{1}\leq{x_{j}}^{2}$ and there is a ${j_{0}}\in J$ such that
$x_{j_{0}}^{1}<x_{j_{0}}^{2}$. Then system (1.2) can be tersely described as
follows:

$\sum_{j\in J}a_{ij}\wedge x_{j}=b_{i},\forall i\in I$

or

$A\odot{x^{T}}={b^{T}},$

where $A=(a_{ij})_{m\times n}$, $x=(x_{1},x_{2},\cdots,x_{n})$,
$b=(b_{1},b_{2},\cdots,b_{m})$ and

$(a_{i1},a_{i2},\cdots,a_{in})\odot(x_{1},x_{2},\cdots,x_{n})^{T}=a_{i1}\wedge
x_{1}+a_{i2}\wedge x_{2}+\cdots+a_{in}\wedge x_{n}.$

System (1.2) is called solvable if there is an $x\in[0,1]^{n}$ such that
$A\odot{x^{T}}={b^{T}}$. We denote the set of all the solutions of system
(1.2) by $\mathscr{X}=\\{x\in[0,1]^{n}|A\odot x^{T}=b^{T}\\}$, and $A\setminus
B=\\{x\in A\mid x\notin B\\}$ where $A$ and $B$ are two sets.

######  Definition 2.1 ([2])

Let $\mathscr{X}\neq\emptyset$. Then $\hat{x}\in\mathscr{X}$ is called a
maximal solution of system (1.2) if and only if $x\geq\hat{x}$ for any
$x\in\mathscr{X}$, implies $x=\hat{x}$, and $\check{x}\in\mathscr{X}$ is
called a minimal solution of system (1.2) if and only if $x\leq\check{x}$ for
any $x\in\mathscr{X}$, implies $x=\check{x}$.

Denote the set of all minimal solutions of system (1.2) by
$\check{\mathscr{X}}$ and the set of all maximal solutions of system (1.2) by
$\hat{\mathscr{X}}$. Then the following two propositions are obvious.

###### Proposition 2.1

Let $x\in\mathscr{X}$. Then we have

  1. (1)

$x>0$.

  2. (2)

For any $i\in I$, $j\in J$, $x_{j}\geq b_{i}-\sum\limits_{k\in
J\setminus\\{j\\}}{a_{ik}\wedge x_{k}}\geq b_{i}-\sum\limits_{k\in
J\setminus\\{j\\}}{a_{ik}}$.

  3. (3)

For any $i\in I$, $j\in J$, $a_{ij}\geq b_{i}-\sum\limits_{k\in
J\setminus\\{j\\}}{a_{ik}\wedge x_{k}}\geq b_{i}-\sum\limits_{k\in
J\setminus\\{j\\}}a_{ik}$.

###### Proposition 2.2

Let $x^{1},x^{2}\in\mathscr{X}$. If $x^{1}\leq x\leq x^{2}$, then
$x\in\mathscr{X}$.

##  3 Minimal solutions of system (1.2)

In this section, we first prove a necessary and sufficient condition for a
solution of system (1.2) being a minimal one if $\mathscr{X}\neq\emptyset$,
then we propose an algorithm to determine $\check{\mathscr{X}}$.

The following lemma is an equivalent description of Lemma 14 in [10].

###### Lemma 3.1

Let $x=(x_{1},x_{2},\cdots,x_{n})\in\mathscr{X}$. Then
$x\in\check{\mathscr{X}}$ if and only if for any $j\in J$, there is an $i\in
I$ such that $x_{j}\leq a_{ij}$.

Let $\hat{\alpha}=(\hat{\alpha}_{1},\hat{\alpha}_{2},\cdots,\hat{\alpha}_{n})$
with

$\hat{\alpha}_{j}=\max\\{a_{ij}|i\in I\\}.$ (3.1)

Then from Lemma 3.1, we have the following remark.

###### Remark 3.1

Let $x=(x_{1},x_{2},\cdots,x_{n})\in\mathscr{X}$. Then
$x\in\check{\mathscr{X}}$ if and only if $x\leq\hat{\alpha}$.

Let
$\check{\alpha}=(\check{\alpha}_{1},\check{\alpha}_{2},\cdots,\check{\alpha}_{n})$
with

$\check{\alpha}_{j}=\max\\{0,b_{i}-\sum\limits_{k\in
J\setminus\\{j\\}}a_{ik}|i\in I\\}.$ (3.2)

Then we have the following proposition.

###### Proposition 3.1

For any $x=(x_{1},x_{2},\cdots,x_{n})\in\mathscr{X}$, we have
$x\geq\check{\alpha}$.

Proof. Let $x=(x_{1},x_{2},\cdots,x_{n})\in\mathscr{X}$. According to
Proposition 2.1, we have $x_{j}\geq 0$ and $x_{j}\geq b_{i}-\sum\limits_{k\in
J\setminus\\{j\\}}{a_{ik}}$ for any $i\in I$, $j\in J$, hence,
$x_{j}\geq\check{\alpha}_{j}$. $\square$

Remark 3.1 and Proposition 3.1 imply the following two remarks.

###### Remark 3.2

For any $x=(x_{1},x_{2},\cdots,x_{n})\in\check{\mathscr{X}}$, we have
$\check{\alpha}\leq x\leq\hat{\alpha}$.

###### Remark 3.3

If
$\check{\alpha}=(\check{\alpha}_{1},\check{\alpha}_{2},\cdots,\check{\alpha}_{n})\in\mathscr{X}$.
Then $\check{\alpha}$ is the unique minimal solution of system (1.2).

###### Definition 3.1

For any $j\in J$, denote $|\\{a_{ij}|\check{\alpha}_{j}<a_{ij},i\in
I\\}|=t_{j}$ and $Q_{j}=\\{q_{0j},q_{1j},q_{2j},\cdots,q_{t_{j}j}\\}$ with
$\check{\alpha}_{j}=q_{0j}<q_{1j}<q_{2j}<\cdots<q_{t_{j}j}=\hat{\alpha}_{j}$,
where $q_{kj}\in\\{a_{ij}|i\in I\\}(k=1,2,\cdots,t_{j})$.

Notice that if $t_{j}=0$ in Definition 3.1 then
$\check{\alpha}_{j}=\hat{\alpha}_{j}$.

Denote

$J^{*}=\\{j\in J|\check{\alpha}_{j}=\hat{\alpha}_{j}\\},$ (3.3)

and $K=\\{(k_{1},k_{2},\cdots,k_{n})|k_{j}\in K_{j}\mbox{ for any }j\in J\\}$
with

$K_{j}=\left\\{\begin{array}[]{ll}\\{0\\},j\in J^{*},\\\ \\\
\\{k|\check{\alpha}_{j}<q_{kj}\leq\hat{\alpha}_{j}\mbox{ and }q_{kj}\in
Q_{j}\\},j\in J\setminus J^{*}.\end{array}\right.$ (3.4)

Then from Lemma 3.1, we have the following corollary.

###### Corollary 3.1

Let $x=(x_{1},x_{2},\cdots,x_{n})\in\mathscr{X}$. Then
$x\in\check{\mathscr{X}}$ if and only if there exists an
$(k_{1},k_{2},\cdots,k_{n})\in K$ such that $x_{j}\leq q_{k_{j}j}$ for any
$j\in J$.

Proof. Let $x=(x_{1},x_{2},\cdots,x_{n})\in\check{\mathscr{X}}$. By Lemma 3.1
and Remark 3.2, for any $j\in J$ there is an $i\in I$ such that
$\check{\alpha}_{j}\leq x_{j}\leq a_{ij}\leq\hat{\alpha}_{j}$, which means
that $\check{\alpha}_{j}=x_{j}=a_{ij}=\hat{\alpha}_{j}$ for any $j\in J^{*}$
and $\check{\alpha}_{j}\leq x_{j}\leq a_{ij}\leq\hat{\alpha}_{j}$ for any
$j\in J\setminus J^{*}$. Then $K_{j}\neq\emptyset$. Therefore, there exists a
$k=(k_{1},k_{2},\cdots,k_{n})\in K$ such that $x_{j}\leq q_{{k_{j}}j}$ for any
$j\in J$.

Conversely, suppose that there is a $k=(k_{1},k_{2},\cdots,k_{n})\in K$ such
that $x_{j}\leq q_{k_{j}j}$ for any $j\in J$. It is obvious that for any $j\in
J$, there is an $i\in I$ such that $x_{j}\leq q_{k_{j}j}=a_{ij}$ and
$x\in\mathscr{X}$, then $x\in\check{\mathscr{X}}$ by Lemma 3.1. $\square$

Furthermore, we have the following theorem.

###### Theorem 3.1

Let $x=(x_{1},x_{2},\cdots,x_{n})$. Then $x\in\check{\mathscr{X}}$ if and only
if there is an $(k_{1},k_{2},\cdots,k_{n})\in K$ such that $x$ satisfies the
following linear equations:

$\left\\{\begin{array}[]{ll}x_{j}=q_{0j},j\in J^{*},\\\ \\\
q_{({k_{j}-1})j}\leq x_{j}\leq q_{k_{j}j},j\in J\setminus J^{*},\\\ \\\
\sum\limits_{j\in J^{*}}a_{ij}\wedge q_{0j}+\sum\limits_{j\in J\setminus
J^{*}}[\delta_{ij}\cdot x_{j}+(1-\delta_{ij})\cdot a_{ij}]=b_{i},i\in
I\end{array}\right.$ (3.5)

where the operation $``\cdot"$ represents the ordinary multiplication and

$\delta_{ij}=\left\\{\begin{array}[]{l}1,q_{k_{j}j}\leq a_{ij},\\\
0,a_{ij}\leq q_{({k_{j}-1})j}\end{array}\right.$

for all $i\in I$, $j\in J\setminus J^{*}$.

Proof. Suppose that $x\in\check{\mathscr{X}}$. By Corollary 3.1 and Formula
(3.4), there is an $(k_{1},k_{2},\cdots,k_{n})\in K$ such that
$q_{({k_{j}-1})j}\leq x_{j}\leq q_{k_{j}j}$ for any $j\in J\setminus J^{*}$
and $x_{j}=q_{0j}$ for any $j\in J^{*}$. Then for any $i\in I$, we have

$\displaystyle b_{i}$ $\displaystyle=$ $\displaystyle\sum\limits_{j\in
J}a_{ij}\wedge x_{j}$ $\displaystyle=$ $\displaystyle\sum\limits_{j\in
J^{*}}a_{ij}\wedge x_{j}+\sum\limits_{j\in J\setminus J^{*}}a_{ij}\wedge
x_{j}$ $\displaystyle=$ $\displaystyle\sum\limits_{j\in J^{*}}a_{ij}\wedge
q_{0j}+\sum\limits_{j\in J\setminus J^{*},q_{k_{j}j}\leq a_{ij}}a_{ij}\wedge
x_{j}+\sum\limits_{j\in J\setminus J^{*},a_{ij}\leq
q_{({k_{j}-1})j}}a_{ij}\wedge x_{j}$ $\displaystyle=$
$\displaystyle\sum\limits_{j\in J^{*}}a_{ij}\wedge q_{0j}+\sum\limits_{j\in
J\setminus J^{*},q_{k_{j}j}\leq a_{ij}}x_{j}+\sum\limits_{j\in J\setminus
J^{*},a_{ij}\leq q_{({k_{j}-1})j}}a_{ij}$ $\displaystyle=$
$\displaystyle\sum\limits_{j\in J^{*}}a_{ij}\wedge q_{0j}+\sum\limits_{j\in
J\setminus J^{*}}\delta_{ij}\cdot x_{j}+\sum\limits_{j\in J\setminus
J^{*}}(1-\delta_{ij})\cdot a_{ij}$ $\displaystyle=$
$\displaystyle\sum\limits_{j\in J^{*}}a_{ij}\wedge q_{0j}+\sum\limits_{j\in
J\setminus J^{*}}[\delta_{ij}\cdot x_{j}+(1-\delta_{ij})\cdot a_{ij}],$

where the operation $``\cdot"$ represents the ordinary multiplication and

$\delta_{ij}=\left\\{\begin{array}[]{l}1,q_{k_{j}j}\leq a_{ij},\\\
0,a_{ij}\leq q_{({k_{j}-1})j}\end{array}\right.$

for all $i\in I$, $j\in J\setminus J^{*}$.

Now, suppose that there is an $(k_{1},k_{2},\cdots,k_{n})\in K$ such that $x$
satisfies the linear equations (3.5). Then for any $i\in I$, we have

$\displaystyle b_{i}$ $\displaystyle=$ $\displaystyle\sum\limits_{j\in
J^{*}}a_{ij}\wedge q_{0j}+\sum\limits_{j\in J\setminus J^{*}}[\delta_{ij}\cdot
x_{j}+(1-\delta_{ij})\cdot a_{ij}]$ $\displaystyle=$
$\displaystyle\sum\limits_{j\in J^{*}}a_{ij}\wedge x_{j}+\sum\limits_{j\in
J\setminus J^{*}}\delta_{ij}\cdot x_{j}+\sum\limits_{j\in J\setminus
J^{*}}(1-\delta_{ij})\cdot a_{ij}$ $\displaystyle=$
$\displaystyle\sum\limits_{j\in J^{*}}a_{ij}\wedge x_{j}+\sum\limits_{j\in
J\setminus J^{*},q_{k_{j}j}\leq a_{ij}}x_{j}+\sum\limits_{j\in J\setminus
J^{*},a_{ij}\leq q_{({k_{j}-1})j}}a_{ij}$ $\displaystyle=$
$\displaystyle\sum\limits_{j\in J^{*}}a_{ij}\wedge x_{j}+\sum\limits_{j\in
J\setminus J^{*},q_{k_{j}j}\leq a_{ij}}a_{ij}\wedge x_{j}+\sum\limits_{j\in
J\setminus J^{*},a_{ij}\leq q_{({k_{j}-1})j}}a_{ij}\wedge x_{j}$
$\displaystyle=$ $\displaystyle\sum\limits_{j\in J^{*}}a_{ij}\wedge
x_{j}+\sum\limits_{j\in J\setminus J^{*},q_{k_{j}j}\leq a_{ij}}a_{ij}\wedge
x_{j}+\sum\limits_{j\in J\setminus J^{*},a_{ij}\leq
q_{({k_{j}-1})j}}a_{ij}\wedge x_{j}$ $\displaystyle=$
$\displaystyle\sum\limits_{j\in J^{*}}a_{ij}\wedge x_{j}+\sum\limits_{j\in
J\setminus J^{*}}a_{ij}\wedge x_{j}$ $\displaystyle=$
$\displaystyle\sum\limits_{j\in J}a_{ij}\wedge x_{j}.$

Hence $x\in\mathscr{X}$. By Corollary 3.1, we get $x\in\check{\mathscr{X}}$.
$\square$

Moreover, the proof of Theorem 3.1 implies the following theorem.

###### Theorem 3.2

For any $(k_{1},k_{2},\cdots,k_{n})\in K$, if $x=(x_{1},x_{2},\cdots,x_{n})$
satisfies the equations (3.5), then $x\in\check{\mathscr{X}}$.

Let the solution set of linear equations (3.5) corresponding to
$k=(k_{1},k_{2},\cdots,k_{n})\in K$ be represented by
$\breve{\mathscr{X}}(k)$. Based on Theorems 3.1 and 3.2, we obtain an
algorithm to find all minimal solutions of system (1.2) as follows.

###### Algorithm 1

Input $A=(a_{ij})_{m\times n}$ and $b=(b_{1},b_{2},\cdots,b_{m})$. Output
$\check{\mathscr{X}}$.
Step 1. Compute
$\check{\alpha}=(\check{\alpha}_{1},\check{\alpha}_{2},\cdots,\check{\alpha}_{n})$
defined by (3.2).
Step 2. If $\check{\alpha}\notin\mathscr{X}$, then compute $\hat{\alpha}_{j}$
defined by (3.1) for any $j\in J$. Otherwise, output
$\check{\mathscr{X}}=\\{\check{\alpha}\\}$, and go to Step 7.
Step 3. Compute $J^{*}$ defined by (3.3).
Step 4. Compute $K_{j}$ defined by (3.4) for any $j\in J$, and
$K=\\{(k_{1},k_{2},\cdots,k_{n})|k_{j}\in K_{j}\\}$.
Step 5. For any $k=(k_{1},k_{2},\cdots,k_{n})\in K$, construct the
corresponding linear equations (3.5).
Step 6. Solve the corresponding linear equations (3.5) and obtain
$\check{\mathscr{X}}(k)$.
Step 7. Output $\check{\mathscr{X}}=\bigcup\limits_{k\in
K}\check{\mathscr{X}}(k)$.
Step 8. End.

The following example will be given to illustrate Algorithm 1.

###### Example 3.1

_Consider the following fuzzy relation equations:_

$\left\\{\begin{array}[]{l}0.4\wedge x_{1}+0.6\wedge x_{2}+0.5\wedge
x_{3}=1.4,\\\ 0.7\wedge x_{1}+0.5\wedge x_{2}+0.8\wedge x_{3}=1.5.\\\
\end{array}\right.$

Step 1. Compute $\check{\alpha}_{1}=0.3$, $\check{\alpha}_{2}=0.5$,
$\check{\alpha}_{3}=0.4$.
Step 2. It is clear that $\check{\alpha}=(0.3,0.5,0.4)\notin\mathscr{X}$, then
compute $\hat{\alpha}_{1}=0.7$, $\hat{\alpha}_{2}=0.6$ and
$\hat{\alpha}_{3}=0.8$.
Step 3. For any $j\in J$, $\check{\alpha}_{j}\neq\hat{\alpha}_{j}$, thus
$J^{*}=\emptyset$.
Step 4. Compute $K_{1}=\\{1,2\\}$, $K_{2}=\\{1\\}$, $K_{3}=\\{1,2\\}$ and

$K=\\{(1,1,1),(1,1,2),(2,1,1),(2,1,2)\\}.$

Step 5. Construct and solve the following linear equations (3.5):

(1) For $k=(1,1,1)$,

$\left\\{\begin{array}[]{l}0.3\leq x_{1}\leq 0.4,\\\ 0.5\leq x_{2}\leq 0.6,\\\
0.4\leq x_{3}\leq 0.5,\\\ x_{1}+x_{2}+x_{3}=1.4,\\\
x_{1}+0.5+x_{3}=1.5.\end{array}\right.$

Hence by

$\left\\{\begin{array}[]{l}x_{1}+x_{2}+x_{3}=1.4,\\\
x_{1}+0.5+x_{3}=1.5,\end{array}\right.$

we have

$\left\\{\begin{array}[]{l}x_{1}+x_{2}+x_{3}=1.4,\\\
x_{1}+x_{3}=1.\end{array}\right.$

Thus $x_{2}=0.4$, a contradiction since $0.5\leq x_{2}\leq 0.6$. Therefore,
$\check{\mathscr{X}}(1,1,1)=\emptyset$.

(2) For $k=(1,1,2)$,

$\left\\{\begin{array}[]{l}0.3\leq x_{1}\leq 0.4,\\\ 0.5\leq x_{2}\leq 0.6,\\\
0.5\leq x_{3}\leq 0.8,\\\ x_{1}+x_{2}+0.5=1.4,\\\
x_{1}+0.5+x_{3}=1.5.\end{array}\right.$

Hence by

$\left\\{\begin{array}[]{l}x_{1}+x_{2}+0.5=1.4,\\\
x_{1}+0.5+x_{3}=1.5,\end{array}\right.$

we have

$\left\\{\begin{array}[]{l}x_{1}+x_{2}=0.9,\\\
x_{1}+x_{3}=1.\end{array}\right.$

Let $x_{1}=t$. Then $x_{2}=0.9-t$ and $x_{3}=1-t$. Since $0.3\leq x_{1}\leq
0.4$, $0.5\leq x_{2}\leq 0.6$ and $0.5\leq x_{3}\leq 0.8$, $t\in[0.3,0.4]$.
Therefore, $\check{\mathscr{X}}(1,1,2)=\\{(t,0.9-t,1-t)|t\in[0.3,0.4]\\}$.

(3) For $k=(2,1,1)$,

$\left\\{\begin{array}[]{l}0.4\leq x_{1}\leq 0.7,\\\ 0.5\leq x_{2}\leq 0.6,\\\
0.4\leq x_{3}\leq 0.5,\\\ 0.4+x_{2}+x_{3}=1.4,\\\
x_{1}+0.5+x_{3}=1.5.\end{array}\right.$

Hence by

$\left\\{\begin{array}[]{l}0.4+x_{2}+x_{3}=1.4,\\\
x_{1}+0.5+x_{3}=1.5,\end{array},\right.$

we have

$\left\\{\begin{array}[]{l}x_{2}+x_{3}=1,\\\ x_{1}+x_{3}=1.\end{array}\right.$

Let $x_{3}=t$. Then $x_{1}=1-t$ and $x_{2}=1-t$. Since $0.4\leq x_{1}\leq
0.7$, $0.5\leq x_{2}\leq 0.6$ and $0.4\leq x_{3}\leq 0.5$, $t\in[0.4,0.5]$.
Therefore, $\check{\mathscr{X}}(2,1,1)=\\{(1-t,1-t,t)|t\in[0.4,0.5]\\}$.

(4) For $k=(2,1,2)$,

$\left\\{\begin{array}[]{l}0.4\leq x_{1}\leq 0.7,\\\ 0.5\leq x_{2}\leq 0.6,\\\
0.5\leq x_{3}\leq 0.8,\\\ 0.4+x_{2}+0.5=1.4,\\\
x_{1}+0.5+x_{3}=1.5.\end{array}\right.$

Hence by

$\left\\{\begin{array}[]{l}0.4+x_{2}+0.5=1.4,\\\
x_{1}+0.5+x_{3}=1.5,\end{array}\right.$

we have

$\left\\{\begin{array}[]{l}x_{2}=0.5,\\\ x_{1}+x_{3}=1.\end{array}\right.$

Let $x_{1}=t$. Then $x_{3}=1-t$. Since $0.4\leq x_{1}\leq 0.7$, $0.5\leq
x_{2}\leq 0.6$ and $0.5\leq x_{3}\leq 0.8$, $t\in[0.4,0.5]$. Therefore,
$\check{\mathscr{X}}(2,1,2)=\\{(t,0.5,1-t)|t\in[0.4,0.5]\\}$.
Step 6.

$\displaystyle\check{\mathscr{X}}$ $\displaystyle=$
$\displaystyle\bigcup\limits_{k\in K}\check{\mathscr{X}}(k)$ $\displaystyle=$
$\displaystyle\\{(t,0.9-t,1-t)|t\in[0.3,0.4]\\}\cup\\{(1-t,1-t,t)|t\in[0.4,0.5]\\}$
$\displaystyle\cup\\{(t,0.5,1-t)|t\in[0.4,0.5]\\}.$

##  4 Maximal solutions of system (1.2)

In this section, we first show a necessary and sufficient condition for a
solution of system (1.2) being a maximal solution, and then suggest an
algorithm to find all elements of $\hat{\mathscr{X}}$.

###### Remark 4.1

If $(1,1,\cdots,1)\in\mathscr{X}$. Then $(1,1,\cdots,1)$ is the unique maximal
solution of system (1.2).

Let $x=(x_{1},x_{2},\cdots,x_{n})$ and denote $J(x)=\\{j\in J|x_{j}=1\\}$.
Then we have:

###### Theorem 4.1

Let $x=(x_{1},x_{2},\cdots,x_{n})\in\mathscr{X}$. Then $x\in\hat{\mathscr{X}}$
if and only if for any $j\in J\setminus J(x)$, there is an $i\in I$ such that
$x_{j}<a_{ij}$.

Proof. Let $x=(x_{1},x_{2},\cdots,x_{n})\in\hat{\mathscr{X}}$. Assume that for
any $i\in I$, there is a $j\in J\setminus J(x)$ such that $a_{ij}\leq
x_{j}<1$. Define $x^{1}=(x^{1}_{1},x^{1}_{2},\cdots,x^{1}_{s})$ with

$x_{k}^{1}=\left\\{\begin{array}[]{l}1,k=j,\\\ x_{k},k\neq
j.\end{array}\right.$

Obviously, $x<x^{1}$. For any $i\in I$, we have

$\displaystyle\sum\limits_{k\in J}a_{ik}\wedge x^{1}_{k}$ $\displaystyle=$
$\displaystyle a_{ij}\wedge
x^{1}_{j}+\sum\limits_{k\in{J\setminus\\{j\\}}}a_{ik}\wedge x_{k}$
$\displaystyle=$ $\displaystyle
a_{ij}+\sum\limits_{k\in{J\setminus\\{j\\}}}a_{ik}\wedge x_{k}$
$\displaystyle=$ $\displaystyle a_{ij}\wedge
x_{j}+\sum\limits_{k\in{J\setminus\\{j\\}}}a_{ik}\wedge x_{k}$
$\displaystyle=$ $\displaystyle b_{i}.$

Hence, $x^{1}\in\mathscr{X}$, contrary to $x$ is a maximal solution of system
(1.2).

Conversely, suppose that there exists a $y\in\mathscr{X}$ such $x<y$. Then
there is a $h\in J\setminus J(x)$ such that $x_{h}<y_{h}$ since $x_{j}=1$ for
$j\in J(x)$. Thus $x_{h}<a_{ih}\wedge y_{h}$ since $x_{h}<a_{ih}$. So that

$\displaystyle\sum\limits_{k\in J}a_{ik}\wedge y_{k}$ $\displaystyle=$
$\displaystyle a_{ih}\wedge
y_{h}+\sum\limits_{k\in{J\setminus\\{h\\}}}a_{ik}\wedge y_{k}$
$\displaystyle>$ $\displaystyle
x_{h}+\sum\limits_{k\in{J\setminus\\{h\\}}}a_{ik}\wedge y_{k}$
$\displaystyle\geq$ $\displaystyle
x_{h}+\sum\limits_{k\in{J\setminus\\{h\\}}}a_{ik}\wedge x_{k}$
$\displaystyle=$ $\displaystyle a_{ih}\wedge
x_{h}+\sum\limits_{k\in{J\setminus\\{h\\}}}a_{ik}\wedge x_{k}$
$\displaystyle=$ $\displaystyle b_{i}.$

Contrary to $y\in\mathscr{X}$. Therefore, $x$ is a maximal solution of system
(1.2). $\square$

Let $M=\\{(m_{1},m_{2},\cdots,m_{n})|m_{j}\in M_{j}\mbox{ for any }j\in J\\}$
with

$M_{j}=(K_{j}\setminus\\{0\\})\bigcup\\{\infty\\}.$ (4.1)

Let $m=(m_{1},m_{2},\cdots,m_{n})\in M$. Denote $J(m)=\\{j\in
J|m_{j}=\infty\\}$. Then we have the following theorem.

###### Theorem 4.2

Let $x=(x_{1},x_{2},\cdots,x_{n})$. Then $x\in\hat{\mathscr{X}}$ if and only
if there is an $m=(m_{1},m_{2},\cdots,m_{n})\in M$ such that $x$ satisfies the
linear equations as below:

$\left\\{\begin{array}[]{ll}x_{j}=1,j\in J(m),\\\ \\\ q_{(m_{j}-1)j}\leq
x_{j}<q_{m_{j}j},j\in J\setminus J(m),\\\ \\\ \sum\limits_{j\in J\setminus
J(m)}\delta_{ij}\cdot x_{j}+\sum\limits_{j\in J\setminus
J(m)}(1-\delta_{ij})\cdot a_{ij}+\sum\limits_{j\in J(m)}a_{ij}=b_{i},~{}i\in
I,\end{array}\right.$ (4.2)

where the operation $``\cdot"$ represents the ordinary multiplication and

$\delta_{ij}=\left\\{\begin{array}[]{l}1,q_{m_{j}j}\leq a_{ij},\\\ \\\
0,a_{ij}\leq q_{(m_{j}-1)j}\end{array}\right.$

for all $i\in I$, $j\in J\setminus J(m)$.

Proof. Suppose that $x\in\hat{\mathscr{X}}$. Then by Theorem 4.1, there is an
$i\in I$ such that $\check{\alpha}_{j}\leq x_{j}<q_{m_{j}j}=a_{ij}$ for any
$j\in J\setminus J(x)$, and by Formula (3.4) it is easy to see that $m_{j}\in
K_{j}\setminus\\{0\\}$. For any $j\in J$, let $m_{j}=\infty$ if $j\in J(x)$.
Thus $J(m)=J(x)$. In this way, we can construct an
$m=(m_{1},m_{2},\cdots,m_{n})$ such that $x_{j}<q_{m_{j}j}$ for any $j\in
J\setminus J(m)$ and $x_{j}=1$ for any $j\in J(m)$. By Formula (4.1),
$m=(m_{1},m_{2},\cdots,m_{n})\in M$. Again by Formula (3.4), we have
$q_{(m_{j}-1)j}\leq x_{j}<q_{m_{j}j}$ for any $j\in J\setminus J(m)$. Then for
any $i\in I$,

$\displaystyle b_{i}$ $\displaystyle=$ $\displaystyle\sum\limits_{j\in
J}a_{ij}\wedge x_{j}$ $\displaystyle=$ $\displaystyle\sum\limits_{j\in
J\setminus J(m)}a_{ij}\wedge x_{j}+\sum\limits_{j\in J(m)}a_{ij}\wedge x_{j}$
$\displaystyle=$ $\displaystyle\sum\limits_{j\in J\setminus
J(m),q_{m_{j}j}\leq a_{ij}}a_{ij}\wedge x_{j}+\sum\limits_{j\in J\setminus
J(m),a_{ij}\leq q_{({m_{j}-1})j}}a_{ij}\wedge x_{j}+\sum\limits_{j\in
J(m)}a_{ij}\wedge x_{j}$ $\displaystyle=$ $\displaystyle\sum\limits_{j\in
J\setminus J(m),q_{m_{j}j}\leq a_{ij}}x_{j}+\sum\limits_{j\in J\setminus
J(m),a_{ij}\leq q_{({m_{j}-1})j}}a_{ij}+\sum\limits_{j\in J(m)}a_{ij}$
$\displaystyle=$ $\displaystyle\sum\limits_{j\in J\setminus
J(m)}\delta_{ij}\cdot x_{j}+\sum\limits_{j\in J\setminus
J(m)}(1-\delta_{ij})\cdot a_{ij}+\sum\limits_{j\in J(m)}a_{ij},$

where the operation $``\cdot"$ represents the ordinary multiplication and

$\delta_{ij}=\left\\{\begin{array}[]{l}1,q_{m_{j}j}\leq a_{ij},\\\
0,a_{ij}\leq q_{({m_{j}-1})j}\end{array}\right.$

for all $i\in I$, $j\in J\setminus J(m)$.

Conversely, suppose that there exists an $(m_{1},m_{2},\cdots,m_{n})\in M$
such that $x$ satisfies the linear equations (4.2). Then for any $i\in I$, we
have

$\displaystyle b_{i}$ $\displaystyle=$ $\displaystyle\sum\limits_{j\in
J\setminus J(m)}\delta_{ij}\cdot x_{j}+\sum\limits_{j\in J\setminus
J(m)}(1-\delta_{ij})\cdot a_{ij}+\sum\limits_{j\in J(m)}a_{ij}$
$\displaystyle=$ $\displaystyle\sum\limits_{j\in J\setminus
J(m),q_{m_{j}j}\leq a_{ij}}x_{j}+\sum\limits_{j\in J\setminus J(m),a_{ij}\leq
q_{(m_{j}-1)j}}a_{ij}+\sum\limits_{j\in J(m)}a_{ij}$ $\displaystyle=$
$\displaystyle\sum\limits_{j\in J\setminus J(m),q_{m_{j}j}\leq
a_{ij}}a_{ij}\wedge x_{j}+\sum\limits_{j\in J\setminus J(m),a_{ij}\leq
q_{(m_{j}-1)j}}a_{ij}\wedge x_{j}+\sum\limits_{j\in J(m)}a_{ij}\wedge x_{j}$
$\displaystyle=$ $\displaystyle\sum\limits_{j\in J\setminus J(m)}a_{ij}\wedge
x_{j}+\sum\limits_{j\in J(m)}a_{ij}\wedge x_{j}$ $\displaystyle=$
$\displaystyle\sum\limits_{j\in J}a_{ij}\wedge x_{j}.$

Hence $x\in\mathscr{X}$. For this $x$, it is easy to see $J(m)=J(x)$. So that
there is an $i$ such that $x_{j}<q_{m_{j}j}=a_{ij}$ for any $j\in J\setminus
J(x)$. Consequently, by Theorem 4.1, we have $x\in\hat{\mathscr{X}}$.
$\square$

Furthermore, the proof of Theorem 4.2 implies the following theorem.

###### Theorem 4.3

For any $m=(m_{1},m_{2},\cdots,m_{n})\in M$, if $x=(x_{1},x_{2},\cdots,x_{n})$
satisfies the equations (4.2), then $x\in\hat{\mathscr{X}}$.

Let the solution set of linear equations (4.2) corresponding to
$m=(m_{1},m_{2},\cdots,m_{n})\in M$ be represented by $\hat{\mathscr{X}}(m)$.
Then according to Theorems 4.2 and 4.3, we obtain an algorithm to find all
maximal solutions of system (1.2) as follows.

###### Algorithm 2

Input $A=(a_{ij})_{m\times n}$ and $b=(b_{1},b_{2},\cdots,b_{m})$. Output
$\hat{\mathscr{X}}$.
Step 1. If $(1,1,\cdots,1)\notin\mathscr{X}$, then compute $\hat{\alpha}_{j}$
and $\check{\alpha}_{j}$ defined by (3.1) and (3.2) for any $j\in J$,
respectively. Otherwise, output $\check{\mathscr{X}}=\\{(1,1,\cdots,1)\\}$,
and go to Step 6.
Step 2. Compute $M_{j}$ defined by (4.1) for any $j\in J$, and
$M=\\{(m_{1},m_{2},\cdots,m_{n})|m_{j}\in M_{j}\\}$.
Step 3. For any $m=(m_{1},m_{2},\cdots,m_{n})\in M$, construct the
corresponding linear equations (4.2).
Step 4. Solve the corresponding linear equations (4.2) and obtain
$\hat{\mathscr{X}}(m)$.
Step 5. Output $\hat{\mathscr{X}}=\bigcup\limits_{m\in
M}\hat{\mathscr{X}}(m)$.
Step 6. End.

Next, an example will be given to verify the effectiveness of Algorithm 2.

###### Example 4.1

_Consider the fuzzy relation equations in Example 3.1 again._

Step 1. It is obvious that $(1,1,1)$ is not a solution of the fuzzy relation
equations, then compute $\hat{\alpha}_{1}=0.7$, $\hat{\alpha}_{2}=0.6$ and
$\hat{\alpha}_{3}=0.8$; $\check{\alpha}_{1}=0.3$, $\check{\alpha}_{2}=0.5$ and
$\check{\alpha}_{3}=0.4$.
Step 2. Compute $M_{1}=\\{1,2,\infty\\}$, $M_{2}=\\{1,\infty\\}$,
$M_{3}=\\{1,2,\infty\\}$, and

$\displaystyle M$ $\displaystyle=$
$\displaystyle\\{(1,1,1),(1,1,2),(1,1,\infty),(1,\infty,1),(1,\infty,2),(1,\infty,\infty),(2,1,1),(2,1,2),(2,1,\infty),$
$\displaystyle(2,\infty,1),(2,\infty,2),(2,\infty,\infty),(\infty,1,1),(\infty,1,2),(\infty,1,\infty),(\infty,\infty,1),(\infty,\infty,2),$
$\displaystyle(\infty,\infty,\infty)\\}.$

Step 3. Construct and solve the following linear equations (4.2):

(1) For $m=(1,1,1)$,

$\left\\{\begin{array}[]{l}0.3\leq x_{1}<0.4,\\\ 0.5\leq x_{2}<0.6,\\\ 0.4\leq
x_{3}<0.5,\\\ x_{1}+x_{2}+x_{3}=1.4,\\\
x_{1}+0.5+x_{3}=1.5.\end{array}\right.$

Hence by

$\left\\{\begin{array}[]{l}x_{1}+x_{2}+x_{3}=1.4,\\\
x_{1}+0.5+x_{3}=1.5,\end{array}\right.$

we have

$\left\\{\begin{array}[]{l}x_{1}+x_{2}+x_{3}=1.4,\\\
x_{1}+x_{3}=1.\end{array}\right.$

$x_{2}=0.4$, contrary to $0.5\leq x_{2}<0.6$. Therefore,
$\check{\mathscr{X}}(1,1,1)=\emptyset$.

(2) For $m=(1,1,2)$,

$\left\\{\begin{array}[]{l}0.3\leq x_{1}<0.4,\\\ 0.5\leq x_{2}<0.6,\\\ 0.5\leq
x_{3}<0.8,\\\ x_{1}+x_{2}+0.5=1.4,\\\ x_{1}+0.5+x_{3}=1.5.\end{array}\right.$

Hence by

$\left\\{\begin{array}[]{l}x_{1}+x_{2}+0.5=1.4,\\\
x_{1}+0.5+x_{3}=1.5,\end{array}\right.$

we have

$\left\\{\begin{array}[]{l}x_{1}+x_{2}=0.9,\\\
x_{1}+x_{3}=1.\end{array}\right.$

Let $x_{1}=t$. Then $x_{2}=0.9-t$ and $x_{3}=1-t$. Since $0.3\leq x_{1}<0.4$,
$0.5\leq x_{2}<0.6$ and $0.5\leq x_{3}<0.8$, $t\in(0.3,0.4)$. Therefore,
$\hat{\mathscr{X}}(1,1,2)=\\{(t,0.9-t,1-t)|t\in(0.3,0.4)\\}$.

(3) For $m=(1,1,\infty)$,

$\left\\{\begin{array}[]{l}0.3\leq x_{1}<0.4,\\\ 0.5\leq x_{2}<0.6,\\\
x_{3}=1,\\\ x_{1}+x_{2}+0.5=1.4,\\\ x_{1}+0.5+0.8=1.5.\end{array}\right.$

Hence by

$\left\\{\begin{array}[]{l}x_{1}+x_{2}+0.5=1.4,\\\
x_{1}+0.5+0.8=1.5,\end{array}\right.$

we have

$\left\\{\begin{array}[]{l}x_{2}=0.7,\\\ x_{1}=0.2,\end{array}\right.$

contrary to $0.3\leq x_{1}<0.4$ and $0.5\leq x_{2}<0.6$. Therefore,
$\check{\mathscr{X}}(1,1,\infty)=\emptyset$.

(4) For $m=(1,\infty,1)$,

$\left\\{\begin{array}[]{l}0.3\leq x_{1}<0.4,\\\ x_{2}=1,\\\ 0.4\leq
x_{3}<0.5,\\\ x_{1}+0.6+x_{3}=1.4,\\\ x_{1}+0.5+x_{3}=1.5.\end{array}\right.$

Hence by

$\left\\{\begin{array}[]{l}x_{1}+0.6+x_{3}=1.4,\\\
x_{1}+0.5+x_{3}=1.5,\end{array}\right.$

we have

$\left\\{\begin{array}[]{l}x_{1}+x_{3}=0.8,\\\
x_{1}+x_{3}=1,\end{array}\right.$

a contradiction. Therefore, $\check{\mathscr{X}}(1,\infty,1)=\emptyset$.

(5) For $m=(1,\infty,2)$,

$\left\\{\begin{array}[]{l}0.3\leq x_{1}<0.4,\\\ x_{2}=1,\\\ 0.5\leq
x_{3}<0.8,\\\ x_{1}+0.6+0.5=1.4,\\\ x_{1}+0.5+x_{3}=1.5.\end{array}\right.$

Hence by

$\left\\{\begin{array}[]{l}x_{1}+0.6+0.5=1.4,\\\
x_{1}+0.5+x_{3}=1.5,\end{array}\right.$

we have

$\left\\{\begin{array}[]{l}x_{1}=0.3,\\\ x_{3}=0.7.\end{array}\right.$

Therefore, $\hat{\mathscr{X}}(1,\infty,2)=\\{(0.3,1,0.7)\\}$.

(6) For $m=(1,\infty,\infty)$,

$\left\\{\begin{array}[]{l}0.3\leq x_{1}<0.4,\\\ x_{2}=1,\\\ x_{3}=1,\\\
x_{1}+0.6+0.5=1.4,\\\ x_{1}+0.5+0.8=1.5.\end{array}\right.$

Hence by

$\left\\{\begin{array}[]{l}x_{1}+0.6+0.5=1.4,\\\
x_{1}+0.5+0.8=1.5,\end{array}\right.$

we have

$\left\\{\begin{array}[]{l}x_{1}=0.3,\\\ x_{1}=0.2,\end{array}\right.$

a contradiction. Therefore, $\check{\mathscr{X}}(1,\infty,\infty)=\emptyset$.

(7) For $m=(2,1,1)$,

$\left\\{\begin{array}[]{l}0.4\leq x_{1}<0.7,\\\ 0.5\leq x_{2}<0.6,\\\ 0.4\leq
x_{3}<0.5,\\\ 0.4+x_{2}+x_{3}=1.4,\\\ x_{1}+0.5+x_{3}=1.5.\end{array}\right.$

Hence by

$\left\\{\begin{array}[]{l}0.4+x_{2}+x_{3}=1.4,\\\
x_{1}+0.5+x_{3}=1.5,\end{array}\right.$

we have

$\left\\{\begin{array}[]{l}x_{2}+x_{3}=1,\\\ x_{1}+x_{3}=1.\end{array}\right.$

Let $x_{3}=t$. Then $x_{1}=1-t$ and $x_{2}=1-t$. Since $0.4\leq x_{1}<0.7$,
$0.5\leq x_{2}<0.6$ and $0.4\leq x_{3}<0.5$, $t\in(0.4,0.5)$. Therefore,
$\hat{\mathscr{X}}(2,1,1)=\\{(1-t,1-t,t)|t\in(0.4,0.5)\\}$.

(8) For $m=(2,1,2)$,

$\left\\{\begin{array}[]{l}0.4\leq x_{1}<0.7,\\\ 0.5\leq x_{2}<0.6,\\\ 0.5\leq
x_{3}<0.8,\\\ 0.4+x_{2}+0.5=1.4,\\\ x_{1}+0.5+x_{3}=1.5.\end{array}\right.$

Hence by

$\left\\{\begin{array}[]{l}0.4+x_{2}+0.5=1.4,\\\
x_{1}+0.5+x_{3}=1.5,\end{array}\right.$

we have

$\left\\{\begin{array}[]{l}x_{2}=0.5,\\\ x_{1}+x_{3}=1.\end{array}\right.$

Let $x_{1}=t$. Then $x_{3}=1-t$. Since $0.4\leq x_{1}<0.7$, $0.5\leq
x_{2}<0.6$ and $0.5\leq x_{3}<0.8$, $t\in[0.4,0.5]$. Therefore,
$\check{\mathscr{X}}(2,1,2)=\\{(t,0.5,1-t)|t\in[0.4,0.5]\\}$.

(9) For $m=(2,1,\infty)$,

$\left\\{\begin{array}[]{l}0.4\leq x_{1}<0.7,\\\ 0.5\leq x_{2}<0.6,\\\
x_{3}=1,\\\ 0.4+x_{2}+0.5=1.4,\\\ x_{1}+0.5+0.8=1.5.\end{array}\right.$

Hence by

$\left\\{\begin{array}[]{l}0.4+x_{2}+0.5=1.4,\\\
x_{1}+0.5+0.8=1.5,\end{array}\right.$

we have

$\left\\{\begin{array}[]{l}x_{2}=0.5,\\\ x_{1}=0.2,\end{array}\right.$

contrary to $0.4\leq x_{1}<0.7$. Therefore,
$\check{\mathscr{X}}(2,1,\infty)=\emptyset$.

(10) For $m=(2,\infty,1)$,

$\left\\{\begin{array}[]{l}0.4\leq x_{1}<0.7,\\\ x_{2}=1,\\\ 0.4\leq
x_{3}<0.5,\\\ 0.4+0.6+x_{3}=1.4,\\\ x_{1}+0.5+x_{3}=1.5.\end{array}\right.$

Hence by

$\left\\{\begin{array}[]{l}0.4+0.6+x_{3}=1.4,\\\
x_{1}+0.5+x_{3}=1.5,\end{array}\right.$

we have

$\left\\{\begin{array}[]{l}x_{1}=0.6,\\\ x_{3}=0.4.\end{array}\right.$

Therefore, $\hat{\mathscr{X}}(2,\infty,1)=\\{(0.6,1,0.4)\\}$.

(11) For $m=(2,\infty,2)$,

$\left\\{\begin{array}[]{l}0.4\leq x_{1}<0.7,\\\ x_{2}=1,\\\ 0.5\leq
x_{3}<0.8,\\\ 0.4+0.6+0.5=1.4,\\\ x_{1}+0.5+x_{3}=1.5.\end{array}\right.$

0.4 + 0.6 + 0.5= 1.4 is impossible. Therefore,
$\check{\mathscr{X}}(2,\infty,2)=\emptyset$.

(12) For $m=(2,\infty,\infty)$,

$\left\\{\begin{array}[]{l}0.4\leq x_{1}<0.7,\\\ x_{2}=1,\\\ x_{3}=1,\\\
0.4+0.6+0.5=1.4,\\\ x_{1}+0.5+0.8=1.5.\end{array}\right.$

0.4 + 0.6 + 0.5= 1.4 is impossible. Therefore,
$\check{\mathscr{X}}(2,\infty,\infty)=\emptyset$.

(13) For $m=(\infty,1,1)$,

$\left\\{\begin{array}[]{l}x_{1}=1,\\\ 0.5\leq x_{2}<0.6,\\\ 0.4\leq
x_{3}<0.5,\\\ 0.4+x_{2}+x_{3}=1.4,\\\ 0.7+0.5+x_{3}=1.5.\end{array}\right.$

Hence by

$\left\\{\begin{array}[]{l}0.4+x_{2}+x_{3}=1.4,\\\
0.7+0.5+x_{3}=1.5,\end{array}\right.$

we have

$\left\\{\begin{array}[]{l}x_{2}=0.7,\\\ x_{3}=0.3,\end{array}\right.$

contrary to $0.5\leq x_{2}<0.6$ and $0.4\leq x_{3}<0.5$. Therefore,
$\check{\mathscr{X}}(\infty,1,1)=\emptyset$.

(14) For $m=(\infty,1,2)$,

$\left\\{\begin{array}[]{l}x_{1}=1,\\\ 0.5\leq x_{2}<0.6,\\\ 0.5\leq
x_{3}<0.8,\\\ 0.4+x_{2}+0.5=1.4,\\\ 0.7+0.5+x_{3}=1.5.\end{array}\right.$

Hence by

$\left\\{\begin{array}[]{l}0.4+x_{2}+0.5=1.4,\\\
0.7+0.5+x_{3}=1.5,\end{array}\right.$

we have

$\left\\{\begin{array}[]{l}x_{2}=0.5,\\\ x_{3}=0.3,\end{array}\right.$

contrary to $0.5\leq x_{3}<0.8$, therefore,
$\check{\mathscr{X}}(\infty,1,2)=\emptyset$.

(15) For $m=(\infty,1,\infty)$,

$\left\\{\begin{array}[]{l}x_{1}=1,\\\ 0.5\leq x_{2}<0.6,\\\ x_{3}=1,\\\
0.4+x_{2}+0.5=1.4,\\\ 0.7+0.5+0.8=1.5.\end{array}\right.$

0.7 + 0.5 + 0.8 = 1.5 is impossible. Therefore,
$\check{\mathscr{X}}(\infty,1,\infty)=\emptyset$.

(16) For $m=(\infty,\infty,1)$,

$\left\\{\begin{array}[]{l}x_{1}=1,\\\ x_{2}=1,\\\ 0.4\leq x_{3}<0.5,\\\
0.4+0.6+x_{3}=1.4,\\\ 0.7+0.5+x_{3}=1.5.\end{array}\right.$

Hence by

$\left\\{\begin{array}[]{l}0.4+0.6+x_{3}=1.4,\\\
0.7+0.5+x_{3}=1.5,\end{array}\right.$

we have

$\left\\{\begin{array}[]{l}x_{3}=0.4,\\\ x_{3}=0.3,\end{array}\right.$

a contradiction. Therefore, $\check{\mathscr{X}}(\infty,\infty,1)=\emptyset$.

(17) For $m=(\infty,\infty,2)$,

$\left\\{\begin{array}[]{l}x_{1}=1,\\\ x_{2}=1,\\\ 0.5\leq x_{3}<0.8,\\\
0.4+0.6+0.5=1.4,\\\ 0.7+0.5+x_{3}=1.5.\end{array}\right.$

0.4 + 0.6 + 0.5= 1.4 is impossible. Therefore,
$\check{\mathscr{X}}(\infty,\infty,2)=\emptyset$.

(18) For $m=(\infty,\infty,\infty)$,

$\left\\{\begin{array}[]{l}x_{1}=1,\\\ x_{2}=1,\\\ x_{3}=1,\\\
0.4+0.6+0.5=1.4,\\\ 0.7+0.5+0.8=1.5.\end{array}\right.$

Both 0.4 + 0.6 + 0.5= 1.4 and 0.7 + 0.5 + 0.8 = 1.5 are impossible. Therefore,
$\check{\mathscr{X}}(\infty,\infty,\infty)=\emptyset$.
Step 4.

$\displaystyle\hat{\mathscr{X}}$ $\displaystyle=$
$\displaystyle\bigcup\limits_{m\in M}\hat{\mathscr{X}}(m)$ $\displaystyle=$
$\displaystyle\\{(t,0.9-t,1-t)|t\in(0.3,0.4)\\}\cup\\{(0.3,1,0.7)\\}\cup\\{(1-t,1-t,t)|t\in(0.4,0.5)\\}$
$\displaystyle\cup\\{(t,0.5,1-t)|t\in[0.4,0.5]\\}\cup\\{(0.6,1,0.4)\\}.$

##  5 The solution set of system (1.2)

In this section, we first prove that every solution of system (1.2) is between
a minimal solution and a maximal one if $\mathscr{X}\neq\emptyset$, then we
completely describe the solution set $\mathscr{X}$.

###### Theorem 5.1

For every $x\in\mathscr{X}$, there is an $\check{x}\in\check{\mathscr{X}}$ and
an $\hat{x}\in\hat{\mathscr{X}}$ such that $\check{x}\leq x\leq\hat{x}$.

Proof. Let $x=(x_{1},x_{2},\cdots,x_{n})\in\mathscr{X}$. If
$x\in\check{\mathscr{X}}$, then obviously, there is an
$\check{x}\in\check{\mathscr{X}}$ such that $\check{x}\leq x$.

If $x\notin\check{\mathscr{X}}$, then according to Lemma 3.1, for any $i\in I$
there is a $j\in J$ such that $x_{j}>a_{ij}$. Thus $J_{1}=\\{j\in
J|x_{j}>\max\\{a_{ij}|i\in I\\}\\}\neq\emptyset$. Define
$x^{1}=(x^{1}_{1},x^{1}_{2},\cdots,x^{1}_{n})$ with

$x_{j}^{1}=\left\\{\begin{array}[]{l}\max\\{a_{ij}|i\in I\\},j\in J_{1},\\\
x_{j},j\in J\setminus J_{1}.\end{array}\right.$

Obviously, $x^{1}<x$. For any $i\in I$, we have

$\displaystyle\sum\limits_{j\in J}a_{ij}\wedge x^{1}_{j}$ $\displaystyle=$
$\displaystyle\sum\limits_{j\in J_{1}}a_{ij}\wedge x^{1}_{j}+\sum\limits_{j\in
J\setminus J_{1}}a_{ij}\wedge x_{j}$ $\displaystyle=$
$\displaystyle\sum\limits_{j\in J_{1}}a_{ij}+\sum\limits_{j\in J\setminus
J_{1}}a_{ij}\wedge x_{j}$ $\displaystyle=$ $\displaystyle\sum\limits_{j\in
J_{1}}a_{ij}\wedge x_{j}+\sum\limits_{j\in{J\setminus J_{1}}}a_{ij}\wedge
x_{j}$ $\displaystyle=$ $\displaystyle b_{i}.$

Hence, $x^{1}\in\mathscr{X}$. From the structurer of $x^{1}$ one can verify
that for any $j\in J$ there is an $i\in I$ such that $x^{1}_{j}\leq a_{ij}$.
By Lemma 3.1, $x^{1}\in\check{\mathscr{X}}$ and $x^{1}<x$.

Consider the $x=(x_{1},x_{2},\cdots,x_{n})\in\mathscr{X}$ again. If
$x\in\hat{\mathscr{X}}$, then obviously, there is an
$\hat{x}\in\hat{\mathscr{X}}$ such that $x\leq\hat{x}$.

If $x\notin\hat{\mathscr{X}}$, then by Remark 4.1 $J(x)\neq J$, and by Theorem
4.1, for any $i\in I$ there is a $j\in J\setminus J(x)$ such that $x_{j}\geq
a_{ij}$. Thus $J_{2}=\\{j\in J\setminus J(x)|x_{j}\geq\max\\{a_{ij}|i\in
I\\}\\}\neq\emptyset$. Define $x^{2}=(x^{2}_{1},x^{2}_{2},\cdots,x^{2}_{n})$
with

$x_{j}^{2}=\left\\{\begin{array}[]{l}1,j\in J_{2},\\\ x_{j},j\in J\setminus
J_{2}.\end{array}\right.$

Obviously, $x<x^{2}$. For any $i\in I$, we have

$\displaystyle\sum\limits_{j\in J}a_{ij}\wedge x^{2}_{j}$ $\displaystyle=$
$\displaystyle\sum\limits_{j\in J_{2}}a_{ij}\wedge
x^{2}_{j}+\sum\limits_{j\in{J\setminus J_{2}}}a_{ij}\wedge x_{j}$
$\displaystyle=$ $\displaystyle\sum\limits_{j\in
J_{2}}a_{ij}+\sum\limits_{j\in{J\setminus J_{2}}}a_{ikj}\wedge x_{j}$
$\displaystyle=$ $\displaystyle\sum\limits_{j\in J_{2}}a_{ij}\wedge
x_{j}+\sum\limits_{j\in{J\setminus J_{2}}}a_{ij}\wedge x_{j}$ $\displaystyle=$
$\displaystyle b_{i}.$

Hence, $x^{2}\in\mathscr{X}$. One can check that
$J(x^{2})=J_{2}\cup(J(x)\cap(J\setminus J_{2}))$, and for any $j\in J\setminus
J(x^{2})$ there is an $i\in I$ such that $x^{2}_{j}<a_{ij}$. From Theorem 4.1,
$x^{2}\in\hat{\mathscr{X}}$ and $x<x^{2}$.

Consequently, there is an $\check{x}\in\check{\mathscr{X}}$ and an
$\hat{x}\in\hat{\mathscr{X}}$ such that $\check{x}\leq x\leq\hat{x}$.
$\square$

From Proposition 2.2 and Theorem 5.1, we have:

###### Theorem 5.2

If $\mathscr{X}\neq\emptyset$, then

$\mathscr{X}=\bigcup\limits_{\check{x}\in\check{\mathscr{X}},\hat{x}\in\hat{\mathscr{X}}}\\{x\in[0,1]^{n}\mid\check{x}\leq
x\leq\hat{x}\\}.$

The solution set of the fuzzy relation equations in Example 3.1 is

$\displaystyle\mathscr{X}$ $\displaystyle=$
$\displaystyle\bigcup\limits_{\check{x}\in\check{\mathscr{X}},\hat{x}\in\hat{\mathscr{X}}}\\{x\in[0,1]^{n}\mid\check{x}\leq
x\leq\hat{x}\\}$ $\displaystyle=$
$\displaystyle\\{(t,0.9-t,1-t)|t\in(0.3,0.4)\\}\cup\\{(1-t,1-t,t)|t\in(0.4,0.5)\\}$
$\displaystyle\cup\\{(t,0.5,1-t)|t\in[0.4,0.5]\\}\cup\\{(0.6,0.6,0.4)\leq
x\leq(0.6,1,0.4)\\}$ $\displaystyle\cup\\{(0.3,0.6,0.7)\leq
x\leq(0.3,1,0.7)\\}.$

##  6 Conclusions

This paper first gave two algorithms to find all minimal and maximal solutions
of system (1.2) if $\mathscr{X}\neq\emptyset$, respectively, and then showed
that the solution set of system (1.2) is completely determined by all minimal
and maximal solutions. Algorithm 1 can determine a lot of minimal solutions of
system (1.1) if $\mathscr{X}\neq\emptyset$ since every minimal solution of
system (1.2) is also a minimal one of system (1.1). In the future, all minimal
solutions found by Algorithm 1 will be used for studying the optimization
problems with system (1.2) as constraints. Also, it is worth pointing out that
we do not know the solvable condition of system (1.2).

## References

  * [1] B. Y. Cao, X. P. Yang, X. G. Zhou, Properties of fuzzy relation inequalities with addition-min composition, in: B. Y. Cao (Ed.), Fuzzy Information and Engineering and Decision, in: Advances in Intelligent Systems and Computing, vol. 646, Springer, 2018, pp. 177-185.
  * [2] A. Di Nola, S. Sessa, W. Pedrycz and E. Sanchez, Fuzzy Relation Equations and Their Applications to Knowledge Engineering, Kluwer Academic Publishers, Dordrecht, Boston/London, 1989.
  * [3] F. F. Guo, J. Shen, A smoothing approach for minimizing a Linear function subject to fuzzy relation inequalities with addition-min composition, Int. J. Fuzzy Syst. 21 (2019) 281-290.
  * [4] S. M. Guu, Y. K. Wu, A linear programming approach for minimizing a linear function subject to fuzzy relational inequalities with addition-min composition, IEEE Transactions on Fuzzy Systems 25 (2017) 985-992.
  * [5] J. X. Li, S. J. Yang, Fuzzy relation inequalities about the data tranmission mechanism in BitTorrent-like Peer-to-Peer file sharing systems, in: Proceedings of the 2012 9th International Conference on Fuzzy systems and Knowledge Discover, FSKD 2012, pp. 452-456.
  * [6] M. Li, X. P. Wang, Remarks on minimal solutions of fuzzy relation inequalities with Addition-min composition, Fuzzy Sets and Systems 410 (2021) 19-26.
  * [7] H. T. Lin, X. P. Yang, Dichotomy algorithm for solving weighted min-max programming problem with addition-min fuzzy relation inequalities constraint, Computers and Industrial Engineering 146 (2020) 106537.
  * [8] E. Sanchez, Resolution of composite fuzzy relation equations, Information and Control 30 (1976) 38-48.
  * [9] S. J. Yang, An algorithm for minizing a linear objective function subject to the fuzzy relation inequalities with addition-min composition, Fuzzy Sets and Systems 255 (2014) 41-51.
  * [10] S. J. Yang, Some results of fuzzy relation inequalities with addition-min composition, IEEE Transactions on Fuzzy Systems 26 (2018) 239-245.
  * [11] X. P. Yang, Optimal-vector-based algorithm for solving min-max programming subject to addition-min fuzzy relation inequality, IEEE Transactions on Fuzzy Systems 25 (2017) 1127-1140.
  * [12] X. P. Yang, Leximax minimum solution of addition-min fuzzy relation inequalities, Information Sciences 524 (2020) 184-198.
  * [13] X. P. Yang, H. T. Lin, X. G. Zhou, B. Y. Cao, Addition-min fuzzy relation inequalities with application in BitTorrent-like Peer-to-Peer file sharing system, Fuzzy Sets and Systems 343 (2018) 126-140.