Sets of solution-set-invariant coefficient matrices of fuzzy relation equations with max-min composition 1

Abstract

This paper describes a set of solution-set-invariant coefficient matrices of the fuzzy relation equation with max-min composition A ⊙ x = b or $⋁_{j \in {1, 2, \dots, n}} (a_{ij} \land x_{j}) = b_{i} for all i \in {1, 2, \dots, m}$ with $1 \geq b_{1} \geq b_{2} \geq \dots \geq b_{m} > 0 .$ An algorithm is given for determining the set scripfontA = {B ∣ {x ∣ B ⊙ x = b} = {x ∣ A ⊙ x = b}} completely.

Keywords

Fuzzy relation equation solution-set invariance coefficient matrix characteristic matrix

1 Introduction

In 1976, Sanchez [1] first introduced the fuzzy relation equation which has the following form $A ⊙ x = b$ (1) or $⋁_{j \in N} (a_{ij} \land x_{j}) = b_{i} for all i \in M .$ where x = (x_j) ^T ∈ [0, 1] ⁿ is unknown and ⊙ denotes the max-min composite operation, T denotes transposition, A = (a_ij) ∈ [0, 1] ^m×n is the coefficient matrix and b = (b_i) ^T ∈ [0, 1] ^m is a constant vector (M = {1, 2, ⋯ , m} and N = {1, 2, ⋯ , n} are index sets). Since then, the theory has been applied in many fields, such as fuzzy control [2], discrete dynamic systems [3], intelligence technology [4], et al.. Many works about solving systems of fuzzy relation equations were published [5 –15]. Among them, Miyakoshi and Shimbo [9] investigated a kind of simple fuzzy relation equations which have the form of (1) with b satisfying $1 \geq b_{1} > b_{2} > \dots > b_{m} > 0 .$

More specifically, set X = {x ∣ A ⊙ x = b} and A = {B ∣ {x ∣ B ⊙ x = b} = X}. Then Masaaki gave a method to represent A. A natural problem is how to completely describe A when the right hand side b of the equation (1) satisfies 1 ≥ b₁ ≥ b₂ ≥ ⋯ ≥ b_m > 0. Clearly this problem is more difficult than that one investigated by Miyakoshi and Shimbo.

Therefore, in what follows, we shall concentrate on completely describing the set A of the fuzzy relation equation (1) with b satisfying $1 \geq b_{1} \geq b_{2} \geq \dots \geq b_{m} > 0 .$ (2)

This paper organizes in six sections. In Section 2, some notions and previous results are shown. In Section 3, the characteristic matrices for the greatest solution and lower solutions are given, respectively. In Section 4, the set A is completely described. A simple algorithm is represented in Section 5. A conclusion is drawn in Section 6.

2 Preliminaries

In this section, we give some definitions and previous results for the sake of convenience.

Definition 2.1. [1] All matrices and vectors are partially ordered elementwise as follows: A = (a_ij) ≤ B = (b_ij) if and only if a_ij ≤ b_ij (i ∈ M, j ∈ N), and b = (b_i) ≤ c = (c_i) if and only if b_i ≤ c_i (i ∈ M). Respectively, the join and the meet of A and B are defined as follows: A ∨ B = (a_ij ∨ b_ij) , A ∧ B = (a_ij ∧ b_ij). The join and the meet of vectors are defined similarly.

The partial ordering ≤ is used tacitly throughout the paper.

Definition 2.2. [1] α-composition. $A α b = ((A α b)_{j})^{T} \in [0, 1]^{n}, j \in N,$ where $(A α b)_{j} = ⋀_{i \in M} (a_{ij} α b_{i}), a_{ij} α b_{i} = {\begin{matrix} b_{i} & if a_{ij} > b_{i}, \\ 1 & otherwise, \end{matrix}$ for all i ∈ M .

The following theorem is cited from [1].

Theorem 2.1. X≠ ∅ if and only if Aαb is the greatest element in X.

Definition 2.3. [5] An element x ∈ X is called a lower element (lower solution of equation (1)) of X, if, for x′ ∈ X, x′ ≤ x implies x′ = x.

The set of all lower elements of X is denoted by X₀. Then we have

Theorem 2.2. [5] If X≠ ∅, then X₀≠ ∅, and x ∈ X if and only if there exists x₀ ∈ X₀ such that x₀ ≤ x ≤ Aαb .

In the following, we always assume that X≠ ∅ and we denote $A α b = \hat{x} = ({\hat{x}}_{j})$ .

Definition 2.4. [7] A matrix H = (h_ij) is called Boolean if h_ij = 0 or h_ij = 1 (i ∈ M, j ∈ N). For a given Boolean matrix H = (c_ij), we define $H_{i} = the i - th row of H, {H_{i}} = {j ∣ h_{ij} = 1} .$ p = (j₁, j₂, ⋯ , j_m) is called a way of H if j_i ∈ {H_i} for every i = 1, 2, ⋯ , m. A way p = (j₁, j₂, ⋯ , j_m) of H is called conservative when for any 2 ≤ k ≤ m, if {j₁, j₂, ⋯ , j_k-1} ∩ {H_k} ≠ ∅ and j_i is the first element encountering {H_k} in (j₁, j₂, ⋯ , j_k-1), then j_k = j_i holds. When m = 1, every way of H is a conservative way (c.w.) of H.

Let K (m, n) (or K for brevity) be the set of all (m, n)-order Boolean matrices and W (H) be the set of all c.w.’s of H where H ∈ K.

Definition 2.5. [7] Let us define a characteristic matrix C (A) = (c_ij) (for brevity C) of the fuzzy relation equation (1) as that for any i ∈ M, j ∈ N, $c_{ij} = {\begin{matrix} 1 & if a_{ij} \geq b_{i} and {\hat{x}}_{j} \geq b_{i}, \\ 0 & otherwise . \end{matrix}$

Definition 2.6. [13] We define a covering matrix $Δ (\hat{x})$ of the equation (1) as follows: for any i ∈ M, j ∈ N, $Δ (\hat{x})_{ij} = {\begin{matrix} b_{i} & if a_{ij} \land {\hat{x}}_{j} = b_{i}, \\ 0 & otherwise, \end{matrix}$ and $Δ (\hat{x}) = (Δ (\hat{x})_{ij}) .$

For brevity, we put $Δ (\hat{x}) = Δ$ . Then we have the corollary below.

Corollary 2.1. For the equation (1), C = Δ′, where $Δ^{'} = (Δ_{ij}^{'})$ with $Δ_{ij}^{'} = {\begin{matrix} 1 & if a_{ij} \land {\hat{x}}_{j} = b_{i}, \\ 0 & otherwise . \end{matrix}$

Proof. It is obvious that $a_{ij} \land {\hat{x}}_{j} \leq b_{i}$ for all i ∈ M, j ∈ N since $\hat{x} = ({\hat{x}}_{j})$ is the greatest solution of the equation (1). We shall prove C = Δ′ from two sides.

(⇒) For all i ∈ M, j ∈ N, if $Δ_{ij}^{'} = 1$ , then $a_{ij} \land {\hat{x}}_{j} = b_{i}$ . This implies that a_ij ≥ b_i and ${\hat{x}}_{j} \geq b_{i}$ . Hence c_ij = 1 by Theorem 2.3. If $Δ_{ij}^{'} = 0$ , then $a_{ij} \land {\hat{x}}_{j} < b_{i}$ . Hence c_ij = 0 by Theorem 2.3.

(⇐) For all i ∈ M, j ∈ N, if c_ij = 1, then a_ij ≥ b_i and ${\hat{x}}_{j} \geq b_{i}$ by Theorem 2.3. Hence $a_{ij} \land {\hat{x}}_{j} \geq b_{i}$ . Further, we can get $a_{ij} \land {\hat{x}}_{j} = b_{i}$ . Thus $Δ_{ij}^{'} = 1$ . If c_ij = 0, then a_ij < b_i or ${\hat{x}}_{j} < b_{i}$ by Theorem 2.3. Hence $a_{ij} \land {\hat{x}}_{j} < b_{i}$ . Thus $Δ_{ij}^{'} = 0$ . □

For a conservative way p = (j₁, j₂, ⋯ , j_m) of C, define $x (p) = (x (p)_{j})^{T} (j \in N)$ with $x (p)_{j} = {\begin{matrix} ⋁ {b_{i} ∣ j_{i} = j} & if {b_{i} ∣ j_{i} = j} \neq \emptyset, \\ 0 & otherwise . \end{matrix}$

Then we have the corollary below.

Corollary 2.2. [7, 9] If the equation (1) satisfies that 1 ≥ b₁ > b₂ > ⋯ > b_m > 0. Then for any x₀ ∈ X₀ there exists exactly one conservative way p of C such that x₀ = x (p) and |X₀| = |W (C) | (where |A| stands for the cardinality of set A).

Following from Definition 2.4, Corollaries 2.1 and 2.2, we can prove the next corollary.

Corollary 2.3. For the equation (1),

x (p) ∈ X, and

for every x₀ ∈ X₀, there exists one conservative way p of C such that x₀ = x (p).

Remark 2.1. For the equation (1), x (p) may be not a lower solution where p ∈ W (C).

Example 2.1. Let A ⊙ x = b where $A = (\begin{matrix} 0.7 & 0.6 & 0.1 \\ 0.6 & 0.6 & 0.4 \\ 0.6 & 0.2 & 0.6 \end{matrix}) and {b = (\begin{matrix} 0.6 \\ 0.6 \\ 0.6 \end{matrix}) .$

It is easy to see that $\hat{x} = (\begin{matrix} 0.6 \\ 1 \\ 1 \end{matrix}), C = (\begin{matrix} 1 & 1 & 0 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{matrix}),$ and $W (C) = {(1, 1, 1), (2, 2, 1), (2, 2, 3)} .$

Set p₁ = (1, 1, 1) , p₂ = (2, 2, 1) and p₃ = (2, 2, 3). Then we have $\begin{matrix} x (p_{1}) = (\begin{matrix} 0.6 \\ 0 \\ 0 \end{matrix}), x (p_{2}) = (\begin{matrix} 0.6 \\ 0.6 \\ 0 \end{matrix}), and \\ x (p_{3}) = (\begin{matrix} 0 \\ 0.6 \\ 0.6 \end{matrix}) . \end{matrix}$

Clearly, x (p₂) > x (p₁) and x (p₂) ∉ X₀. Furthermore, we easily check that $X_{0} = {(\begin{matrix} 0.6 \\ 0 \\ 0 \end{matrix}), (\begin{matrix} 0 \\ 0.6 \\ 0.6 \end{matrix})} .$

Let W₀ (C) = {p ∈ W (C) ∣ x (p) ∈ X₀}. Then W (C) = W₀ (C) whence |W (C) |=1.

3 The characteristic matrices for the greatest solution and lower solutions

In the sequel, we shall only consider the equation (1) with b satisfying $1 \geq b_{1} \geq b_{2} \geq \dots \geq b_{m} > 0 .$

Let C, C′ be the characteristic matrices of the equations A ⊙ x = b and A′ ⊙ x = b, respectively. Let X and X ′ be their solution sets, and X₀ and $X_{0}^{'}$ be their lower solution sets, respectively. The other notations are similarly denoted.

Now, let us define a Boolean matrix D (A) = (d_ij) (D for brevity) as follows: for any i ∈ M, j ∈ N, $d_{ij} = {\begin{matrix} 1 & if a_{ij} > b_{i}, \\ 0 & otherwise . \end{matrix}$

Definition 3.1. [9] Let d_j be the j-th column of D and 0 be a zero vector. The characteristic matrix $\bar{D} (A) = ({\bar{d}}_{ij})$ (for brevity $\bar{D}$ ) of the greatest solution Aαb is defined as that for any j ∈ N,

if d_j = 0, then ${\bar{d}}_{ij} = 0 for any i \in M$ ;

if d_j ≠ 0, then ${\bar{d}}_{ij} = {\begin{matrix} 1 & if i = i (j), \\ 0 & otherwise \end{matrix}$ wherei (j) = max {i ∈ M ∣ d_ij = 1}.

Note that each column of $\bar{D}$ has at most one ‘1’.

Definition 3.2. Let $\bar{D} = ({\bar{d}}_{ij})$ and ${\bar{D}}^{'} = ({\bar{d}}_{ij}^{'})$ be the characteristic matrices of the greatest solutions Aαb and A′αb, respectively. If ${b_{i} | {\bar{d}}_{i j} = 1, i \in M} = {b_{i} | {\bar{d}}_{i j}^{'} = 1, i \in M}$ for all j ∈ N, then we say that $\bar{D}$ is similar to ${\bar{D}}^{'}$ , in symbols $\bar{D} ≃ {\bar{D}}^{'}$ .

Then the following two lemmas are true.

Lemma 3.1. $A α b = D α b = \bar{D} α b$ .

Lemma 3.2. For two matrices A and A′, Aαb = A′αb if and only if $\bar{D} ≃ {\bar{D}}^{'}$ .

Definition 3.3. The characteristic matrix of lower solutions $\hat{C} (A) = ({\hat{c}}_{ij})$ ( $\hat{C}$ for brevity) is defined as follows: for any i ∈ M, j ∈ N, ${\hat{c}}_{ij} = {= 3 pt \begin{matrix} 1 & \exists p = (j_{1}, j_{2}, \dots, j_{m}) \\ \in W_{0} (C) ∋ j_{i} = j, \\ 0 & otherwise . \end{matrix}$

Then the following lemma holds.

Lemma 3.3.

$C \geq \hat{C}$ .

$W_{0} (C) = W (\hat{C})$ .

$\hat{C} = {\hat{C}}^{'}$ if and only if W₀ (C) = W₀ (C′).

Let I = {1, 2, ⋯ , n}, ∮ = I × I × ⋯ × I (m times), {p} = {j₁, j₂, ⋯ , j_m} for p = (j₁, j₂, ⋯ , j_m) ∈ ∮, and I_p (j) = {i ∣ j_i = j} for j ∈ {p}.

Definition 3.4. An equivalence relation ≡ on ∮ is defined as follows: for p₁, p₂∈ ∮, p₁ ≡ p₂ if and only if (i) {p₁} = {p₂}, and (ii) b_i₁(j) = b_i₂(j) for j ∈ {p₁} (= {p₂}) where i₁ (j) = minI_{p
₁} (j) and i₂ (j) = minI_{p
₂} (j).

Obviously W₀ (C) = ∮ ∩ W₀ (C) and the relation ≡ is also an equivalence relation on W₀ (C). Further, we define that W₀ (C) ≡ W₀ (C′) if and only if for any p ∈ W₀ (C) there exists a q ∈ W₀ (C′) such that p ≡ q and for any u ∈ W₀ (C′) there exists a v ∈ W₀ (C) such that u ≡ v. If W₀ (C) ≡ W₀ (C′), then we define $\hat{C} \equiv {\hat{C}}^{'}$ . If $\hat{C} \equiv {\hat{C}}^{'}$ , then we say C ≡ C′ naturally. Denote the equivalence class of K/≡ which contains $\hat{C}$ by $K (\hat{C})$ .

Notice that the matrix $\hat{C}$ may have two distinct c.w.’s p₁, p₂ with p₁ ≡ p₂, and the following two lemmas hold whose proofs are omitted.

Lemma 3.4. x (p₁) = x (p₂) if and only if p₁ ≡ p₂ .

Lemma 3.5. $X_{0} = X_{0}^{'}$ if and only if $\hat{C} \equiv {\hat{C}}^{'}$ , i.e., C ≡ C′.

Note that from Lemma 3.5 we have that |W₀ (C)/≡ | = |X₀|.

Now we conclude this section with the example below.

Example 3.1. Let m = n = 3. Then | ∮ | = mⁿ = 27. Clearly, if b₁ = b₂ = b₃, then ∮/≡ has the following seven equivalence classes. $\begin{matrix} {(1, 1, 1)}, {(2, 2, 2)}, {(3, 3, 3)}, \\ {(1, 1, 2), (1, 2, 1), (2, 1, 1), (2, 2, 1), \\ (2, 1, 2), (1, 2, 2)}, \\ {(1, 1, 3), (1, 3, 1), (3, 1, 1), (3, 3, 1), \\ (3, 1, 3), (1, 3, 3)}, \\ {(2, 2, 3), (2, 3, 2), (3, 2, 2), (3, 3, 2), \\ (3, 2, 3), (2, 3, 3)}, \end{matrix}$ and $\begin{matrix} {(1, 2, 3), (1, 3, 2), (3, 1, 2), (3, 2, 1), \\ (2, 1, 3), (2, 3, 1)} . \end{matrix}$

If b₁ = b₂ > b₃, then {(1, 2, 1) , (2, 1, 1) , (2, 1, 2) , (1, 2, 2)} is one of the equivalence classes. If b₁ > b₂ = b₃, then {(1, 1, 2) , (1, 2, 1) , (1, 2, 2)} is one of the equivalence classes.

4 Set of solution-set-invariant coefficient matrices

By Theorem 2.2, Lemmas 3.2 and 3.5, the following result holds.

Theorem 4.1. X = X ′ if and only if $\bar{D} ≃ {\bar{D}}^{'}$ and $\hat{C} \equiv {\hat{C}}^{'}$ , i.e., C ≡ C′.

Theorem 4.1 states a fact that the solution set of equation (1) is completely determined by the equivalence class of K/≃ which contains the characteristic matrix of the greatest solution and the equivalence class of K/≡ which contains the characteristic matrix of the lower solutions.

Definition 4.1. Let ${\bar{d}}_{j}$ be the j-th column of $\bar{D}$ , and I = {i ∈ M ∣ b_i = b_i(j)}. If H = (h_ij) ∈ K satisfies that there exists k ∈ I such that h_kj = 1 and h_ij = 0 for any i ∈ {i ∈ M ∣ b_i > b_i(j)} whence ${\bar{d}}_{j} \neq 0$ for j ∈ N, then H = (h_ij) ∈ K is called compatibleto $\bar{D}$ .

Set $K (\bar{D}) = {H \in K ∣ H is compatible to \bar{D}}$ . We can observe that ${\bar{D}}^{'} \in K (\bar{D})$ if ${\bar{D}}^{'} ≃ \bar{D}$ and $K (\bar{D}) = K$ if $\bar{D}$ has no ‘1’. Let $K (\bar{D}, \hat{C}) = K (\bar{D}) \cap K (\hat{C})$ .

Now we construct a matrix $(a_{ij}^{*})$ corresponding to a chosen matrix $H = (h_{ij}) \in K (\bar{D}, \hat{C})$ satisfying the following conditions denoted by (C1.1)-(C1.9):

for ${\bar{d}}_{j} = 0$ ,

if h_ij = 0, then $a_{ij}^{*} \in [0, b_{i})$ ,

if h_ij = 1, then $a_{ij}^{*} = b_{i}$ ,

for ${\bar{d}}_{j} \neq 0$ , let I_j = {i ∈ M ∣ h_ij = 1}, minI_j = i₀ (j), $I_{j}^{'} = {i \in I_{j} ∣ b_{i} = b_{i_{0} (j)}}$ . If $| I_{j}^{'} | > 1$ , then we denote $I_{j}^{*} = I_{j}^{'}$ .

if $i = k^{(j)} \in I_{j}^{*}$ , then $a_{ij}^{*} \in (b_{i}, 1]$ ,

if $i \in I_{j}^{*} ∖ {k^{(j)}}$ , then $a_{ij}^{*} \in [b_{i}, 1]$ ,

if $i = i_{0} (j) \notin I_{j}^{*}$ , then $a_{ij}^{*} \in (b_{i}, 1]$ ,

if $i \in I_{j} ∖ I_{j}^{'}$ , then $a_{ij}^{*} = b_{i}$ ,

if i > i₀ (j) ∉ I_j, then $a_{ij}^{*} \in [0, b_{i})$ ,

if i < i₀ (j) and b_i > b_i₀(j), then $a_{ij}^{*} \in [0, 1]$ ,

if i < i₀ (j) and b_i = b_i₀(j), then $a_{ij}^{*} \in [0, b_{i})$ .

Set $J = {j \in N ∣ | I_{j}^{'} | > 1}$ . If |J| = t > 0, then let j_s ∈ J, s = 1, 2, ⋯ , t, where j₁ < j₂ < ⋯ < j_t. Let $K = {k = (k^{(j_{1})}, k^{(j_{2})}, \dots, k^{(j_{t})}) ∣ k^{(j_{s})} \in I_{j_{s}}^{*} with s = 1, 2, \dots, t}$ and denote by A^* (H) the set of all matrices defined by (C1.1)– (C1.9) with respect to $H \in K (\bar{D}, \hat{C})$ . Then the following two results hold.

If J≠ ∅, then $A^{*} (H) = ⋃_{k \in K} A_{k_{H}}^{*}$ where $A_{k_{H}}^{*} = (a_{ij}^{*})$ is defined by (C1.1)– (C1.9);

If J =∅, then $A^{*} (H) = ⋃ A_{0_{H}}^{*}$ where $A_{0_{H}}^{*} = (a_{ij}^{*})$ is defined by (C1.1)– (C1.9).

No ambiguity there, we denote the matrix $A_{H}^{*} = (a_{ij}^{*})$ for $(a_{ij}^{*}) \in A^{*} (H)$ .

Remark 4.1. (1) It is easy to see that $i_{0} (j) \in I_{j}^{'}$ , and there exists i > i₀ (j) such that $i_{0} (j), i \in I_{j}^{*}$ and b_i = b_i₀(j) if $| I_{j}^{'} | > 1$ .

(2) ${\hat{x}}_{j} = (A α b)_{j} = b_{i_{0} (j)} = b_{i (j)}$ follows from the definitions of $\bar{D}$ and $K (\bar{D})$ (in this case ${\bar{d}}_{j} \neq 0$ ).

(3) If i < i₀ (j) and b_i > b_i₀(j), then c_ij = 0 because $b_{i} > {\hat{x}}_{j} = b_{i_{0} (j)}$ by the definition of matrix C.

Now we have the following three lemmas.

Lemma 4.1. Let $a_{i}^{*}$ be the i-th row of $A_{H}^{*}$ . Then each $a_{i}^{*}$ has at least an element such that essentially $a_{ij}^{*} \geq b_{i}$ , where ‘essentially’ means that the case that $a_{ij}^{*} \geq b_{i}$ is caused by $a_{ij}^{*} \in [0, 1]$ is excluded.

Proof. Since $A ⊙ \hat{x} = b$ , for any i ∈ M there exists at least one j ∈ N such that $a_{ij}^{*} \land {\hat{x}}_{j} = b_{i}$ , i.e., c_ij = 1 according to Definition 2.5 and Corollary 2.1. Thus each row of $\hat{C}$ has at least one ‘1’ by Definition 2.4. Since $H \in K (\bar{D}, \hat{C})$ , each row of $\hat{H}$ has at least one ‘1’.

Let us assume that a row $a_{i}^{*}$ has no elements such that essentially $a_{ij}^{*} \geq b_{i}$ . Then from the definition of $A_{H}^{*}$ , we have

if ${\bar{d}}_{j} = 0$ , then h_ij = 0,

if ${\bar{d}}_{j} \neq 0$ , then i ∉ I_j holds. From the assumption we get h_ij = 0 for i > i₀ (j) ∉ I_j, and from Definition 4.1 we have also h_ij = 0 for i < i₀ (j).

Both (1) and (2) show that h_ij = 0 (i ∈ M), and this contradicts the assumption of H. □

Lemma 4.2. For $H \in K (\bar{D}, \hat{C})$ ,

$\bar{D} (A_{H}^{*}) ≃ \bar{D} (A)$ ,

$A_{H}^{*} ⊙ (A_{H}^{*} α b) = b$ .

Proof. (1) Let $D (A_{H}^{*}) = (d_{ij}^{*})$ . Then from the definition of $D (A_{H}^{*})$ we have that for all (i, j) ∈ M × N, $d_{ij}^{*} = {\begin{matrix} 1 & if a_{ij}^{*} > b_{i}, \\ 0 & otherwise . \end{matrix}$

In the concrete, from the definition of $A_{H}^{*}$ we have:

If ${\bar{d}}_{j} = 0$ , then $d_{ij}^{*} = 0$ (i ∈ M). Hence ${\bar{d}}_{j} = 0 = {\bar{d}}_{j}^{*}$ , where ${\bar{d}}_{j}^{*}$ denotes the j-th column of $\bar{D} (A_{H}^{*})$ .

If ${\bar{d}}_{j} \neq 0$ $({\bar{d}}_{i (j) j} = 1)$ , then for any i ∈ M, $d_{ij}^{*} = {\begin{matrix} 1 or 0 & if i \in I_{j}^{*}, \\ 1 & if i = i_{0} (j) \notin I_{j}^{*}, \\ 1 or 0 & if i < i_{0} (j) and b_{i} > b_{i_{0} (j)}, \\ 0 & otherwise . \end{matrix}$

By Remark 4.1 if $| I_{j}^{'} | > 1$ , then we have $i (j), i_{0} (j) \in I_{j}^{*}$ , and b_i(j) = b_i₀(j). Consequently $\bar{D} (A_{H}^{*}) ≃ \bar{D} (A)$ from Definitions 3.1 and 3.2.

Proof of (2). From Lemma 3.1, 3.2 and (1) of this lemma we get $A_{H}^{*} α b = \bar{D} (A_{H}^{*}) α b = \bar{D} (A) α b = \hat{x} = ({\hat{x}}_{j})$ . Next, we shall show the following equations hold: $⋁_{j \in N} (a_{ij}^{*} \land {\hat{x}}_{j}) = b_{i} for all i \in M .$

If ${\bar{d}}_{j} = 0$ , then ${\hat{x}}_{j} = 1$ , and we have $a_{ij}^{*} \land {\hat{x}}_{j} \leq b_{i}$ by (C1.1) and (C1.2).

If ${\bar{d}}_{j} \neq 0$ , then we have ${\hat{x}}_{j} = b_{i (j)} = b_{i_{0} (j)}$ by Remark 4. We distinguish four cases as below.

From (C1.3), (C1.4) and (C1.5), we have $a_{ij}^{*} \geq b_{i} = b_{i_{0} (j)}$ , and hence $a_{ij}^{*} \land {\hat{x}}_{j} = a_{ij}^{*} \land b_{i_{0} (j)} = b_{i}$ .

From (C1.6), we have $a_{ij}^{*} = b_{i}$ , and b_i < b_i₀(j), hence $a_{ij}^{*} \land {\hat{x}}_{j} = a_{ij}^{*} \land b_{i_{0} (j)} = b_{i}$ .

From (C1.7), we have $a_{ij}^{*} < b_{i}$ , hence $a_{ij}^{*} \land {\hat{x}}_{j} \leq a_{ij}^{*} < b_{i}$ .

From (C1.8) and (C1.9), we have b_i ≥ b_i₀(j), hence $a_{ij}^{*} \land {\hat{x}}_{j} = a_{ij}^{*} \land b_{i_{0} (j)} \leq b_{i_{0} (j)} \leq b_{i}$ .

Therefore, the cases (i) and (ii) imply that $⋁_{j \in N} (a_{ij}^{*} \land {\hat{x}}_{j}) \leq b_{i} for all i \in M .$

Further, from the cases (a1), (a2) and Lemma 4.1 we have $⋁_{j \in N} (a_{ij}^{*} \land {\hat{x}}_{j}) = b_{i} for all i \in M . □$

Lemma 4.3.

$\bar{D} \leq C$ .

$\hat{C} \leq \hat{C} \lor \bar{D} \leq C$ .

$C \in K (\bar{D}, \hat{C})$ .

$H = C (A_{H}^{*})$ .

$\hat{C} (A) \equiv \hat{C} (A_{H}^{*})$ .

Proof. Proof of (1): If ${\bar{d}}_{ij} = 1$ , then i = i (j) and a_ij > b_i. So ${\hat{x}}_{j} = b_{i}$ . Further we have c_ij = 1 from the definition of C. Thus $\bar{D} \leq C$ .

Proof of (2): It is obvious that $\hat{C} \leq \hat{C} \lor \bar{D}$ . On the other hand, $\hat{C} \lor \bar{D} \leq C$ by (1) and $\hat{C} \leq C$ .

Proof of (3): Following from (1) and Remark 4.1 (3), we have $C \in K (\bar{D})$ by the definition of $K (\bar{D})$ . On the other hand, $C \equiv \hat{C}$ since $W_{0} (C) = W (\hat{C})$ by Lemma 3.3. Therefore, $C \in K (\bar{D}, \hat{C})$ from the definition of $K (\bar{D}, \hat{C})$ .

Proof of (4): From Lemma 4.2, $\bar{D} (A_{H}^{*}) ≃ \bar{D} (A)$ , and we get $A_{H}^{*} α b = \bar{D} (A_{H}^{*}) α b = \bar{D} (A) α b = \hat{x} = ({\hat{x}}_{j})$ . Let $C (A_{H}^{*}) = (c_{ij}^{*})$ . Then from Definition 2.5, we have that for all (i, j) ∈ M × N, $c_{ij}^{*} = {\begin{matrix} 1 & if a_{ij}^{*} \geq b_{i} and \hat{x_{j}} \geq b_{i}, \\ 0 & otherwise . \end{matrix}$

Concrete speaking, by Remark 4.1 we have:

From (C1.1), $h_{ij} = 0, a_{ij}^{*} < b_{i}$ . Hence $c_{ij}^{*} = h_{ij} = 0$ .

From (C1.2), $h_{ij} = 1, a_{ij}^{*} = b_{i}, {\hat{x}}_{j} = 1 \geq b_{i}$ . Hence $c_{ij}^{*} = h_{ij} = 1$ .

From (C1.3)– (C1.6), i ∈ I_j, h_ij = 1, then we get $a_{ij}^{*} \geq b_{i}, \hat{x_{j}} = b_{i_{0} (j)} \geq b_{i}$ . Hence $c_{ij}^{*} = h_{ij} = 1$ .

From (C1.7) and (C1.9), $a_{ij}^{*} < b_{i}$ , then we have $c_{ij}^{*} = 0$ . Moreover, h_ij = 0 from the definition of $K (\bar{D}, \hat{C})$ . Hence $c_{ij}^{*} = h_{ij} = 0$ .

From (C1.8), $c_{ij}^{*} = 0$ since $b_{i} > b_{i_{0} (j)} = {\hat{x}}_{j}$ , and h_ij = 0 from Definition 4.1. Hence $c_{ij}^{*} = h_{ij} = 0$ .

Consequently, $c_{ij}^{*} = 1$ if and only if h_ij = 1, and $c_{ij}^{*} = 0$ if and only if h_ij = 0. Therefore, $H = C (A_{H}^{*})$ .

Proof of (5): From the definition of $K (\bar{D}, \hat{C})$ and (4) in this lemma, (5) follows immediately. □

Now Theorem 4.1 and Lemmas 4.2 and 4.3 lead us to the following theorem.

Theorem 4.2. ${x ∣ A_{H}^{*} ⊙ x = b} \neq \emptyset$ , and ${x ∣ A_{H}^{*} ⊙ x = b} = X$ for any $A_{H}^{*} \in A^{*} (H)$ .

Let $K_{0} = {H \in K ∣ \hat{H} = H}$ , $K_{0} (H_{0}) = {H \in K ∣ \hat{H} = H_{0}}$ , $K_{0} (\bar{D}, H_{0}) = K (\bar{D}) ⋂ K_{0} (H_{0})$ . Then the following equality holds: $K (\bar{D}, \hat{C}) = ⋃_{\begin{matrix} H_{0} \equiv \hat{C} \\ H_{0} \in K_{0} \end{matrix}} K_{0} (\bar{D}, H_{0}) .$

It is easy to see that H₀ is the least element of K₀ (H₀) and we have the following theorem.

Theorem 4.3. $\begin{matrix} A & = ⋃_{H \in K (\bar{D}, \hat{C})} A^{*} (H) \\ = ⋃_{\begin{matrix} H_{0} \equiv \hat{C} \\ H_{0} \in K_{0} \end{matrix}} (⋃_{H \in K_{0} (\bar{D}, H_{0})} A^{*} (H)) . \end{matrix}$

Proof. Obviously we just need to prove $A = ⋃_{H \in K (\bar{D}, \hat{C})} A^{*} (H) .$

Proof of ⊆: Let us consider two fuzzy relation equations A ⊙ x = b and A′ ⊙ x = b. From Theorem 4.1, if X = X ′, then $\bar{D} ≃ {\bar{D}}^{'}$ and $\hat{C} \equiv {\hat{C}}^{'}$ , i.e.,C ≡ C′.

Since $C^{'} = C^{'} \lor {\bar{D}}^{'} \in K (\bar{D}, \hat{C})$ from Lemma 4.3(1), we get A′ ∈ A^* (C′). Therefore $A^{'} \in ⋃_{H \in K (\bar{D}, \hat{C})} A^{*} (H) .$

Proof of ⊇: Follows immediately from Theorems 4.1 and 4.2. □

Definition 4.2. A pattern denoted by $P (\bar{D}, H) = (p_{ij})$ (or P_H for brevity) for $H \in K (\bar{D}, \hat{C})$ is a matrix that takes one of the five symbols ‘>’, ‘≥’, ‘<’, ‘=’, and ‘*’ as the value of its element defined as follows: $\begin{array}{l} a_{i j}^{*} = b_{i} \Leftrightarrow p_{i j} =' =', \\ a_{i j}^{*} \in (b_{i}, 1] \Leftrightarrow p_{i j} =' >', \\ a_{i j}^{*} \in [b_{i}, 1] \Leftrightarrow p_{i j} =' \geq', \\ a_{i j}^{*} \in [0, b_{i}) \Leftrightarrow p_{i j} =' <', \\ a_{i j}^{*} \in [0, b_{i}] \Leftrightarrow p_{i j} =' \leq', \\ a_{i j}^{*} \in [0, 1] \Leftrightarrow p_{i j} =' *' . \end{array}$

A pattern for $\bar{D}$ and $H \in K (\bar{D}, \hat{C})$ is used to compactly represent the conditions that an X-invariant coefficient matrix should satisfy. Therefore we can identify A^* (H) as a pattern P_H. Consequently, from Theorem 4.3, the A of all X-invariant coefficient matrices for the equation (1) is represented by a set of corresponding patterns.

Definition 4.3. Let A, A′ ∈ [0, 1] ^m×n. We define that A is equivalent to A′, in symbols A ∼ A′, asfollows:

A ∼ A′ ⇔ A = A′ after a series of changing the position of the i-th A_i and the k-th A_k whence b_i = b_k.

For the equation (1), let [A] ^∼ = {A′ ∈ [0, 1] ^m×n ∣ A′ ∼ A}, and [A^* (H)] ^∼ = ⋃ _B∈A^*(H) [B] ^∼.

Notice that from Theorem 4.3 we can describe the set A completely.

The following example will show how to calculate A.

Example 4.1. Let us consider the equation (1) with b = (0.6, 0.6, 0.6) ^T and $A = (\begin{matrix} 0.7 & 0.1 & 0.2 \\ 0.3 & 0.8 & 0.3 \\ 0.9 & 0.3 & 0 \end{matrix})$ .

Then $A α b = \hat{x} = (\begin{matrix} 0.6 \\ 0.6 \\ 1 \end{matrix}), \bar{D} = (\begin{matrix} 0 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{matrix}), \hat{C} = (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{matrix}),$ $X_{0} = {(\begin{matrix} 0.6 \\ 0.6 \\ 0 \end{matrix})}$ and W (C) = W₀ (C) = {(1, 2, 1)}.

Since the equivalence class {(1, 2, 1), (1, 1, 2), (2, 1, 1), (2, 2, 1), (2, 1, 2), (1, 2, 2)} contains (1, 2, 1) from Example 3.1, we exactly have the following eight cases by calculating:

If W₀ (H₀) = {(1, 2, 1)}, i.e., $H_{0} = (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{matrix})$ , then $K_{0} (\bar{D}, H_{0}) =$ $\begin{matrix} {(\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{matrix}), (\begin{matrix} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{matrix}), (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 1 & 0 \end{matrix}), \\ (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 1 \end{matrix}), (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 1 & 1 \end{matrix})} . \end{matrix}$

If W₀ (H₀) = {(1, 1, 2)}, i.e., $H_{0} = (\begin{matrix} 1 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix})$ , then $K_{0} (\bar{D}, H_{0}) =$ $\begin{matrix} {(\begin{matrix} 1 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix}), (\begin{matrix} 1 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix}) (\begin{matrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 0 & 1 & 0 \end{matrix}), \\ (\begin{matrix} 1 & 0 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{matrix}), (\begin{matrix} 1 & 0 & 0 \\ 1 & 1 & 1 \\ 0 & 1 & 0 \end{matrix})} . \end{matrix}$

If W₀ (H₀) = {(2, 1, 1)}, i.e., $H_{0} = (\begin{matrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{matrix})$ , then $K_{0} (\bar{D}, H_{0}) = {(\begin{matrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{matrix}), (\begin{matrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 1 & 0 & 0 \end{matrix}) (\begin{matrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 1 \end{matrix})} .$

If W₀ (H₀) = {(2, 2, 1)}, i.e., $H_{0} = (\begin{matrix} 0 & 1 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{matrix})$ , then $K_{0} (\bar{D}, H_{0}) =$ $\begin{matrix} {(\begin{matrix} 0 & 1 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{matrix}), (\begin{matrix} 0 & 1 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{matrix}) (\begin{matrix} 0 & 1 & 0 \\ 1 & 1 & 0 \\ 1 & 0 & 0 \end{matrix}), \\ (\begin{matrix} 0 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \end{matrix}), (\begin{matrix} 0 & 1 & 0 \\ 1 & 1 & 1 \\ 1 & 0 & 0 \end{matrix})} . \end{matrix}$

If W₀ (H₀) = {(2, 1, 2)}, i.e., $H_{0} = (\begin{matrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix})$ , then $K_{0} (\bar{D}, H_{0}) =$ $\begin{matrix} {(\begin{matrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix}), (\begin{matrix} 0 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix}), (\begin{matrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 0 \end{matrix}), \\ (\begin{matrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 1 \end{matrix}), (\begin{matrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \end{matrix})} . \end{matrix}$

If W₀ (H₀) = {(1, 2, 2)}, i.e., $H_{0} = (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 0 \end{matrix})$ , then $\begin{matrix} K_{0} (\bar{D}, H_{0}) \\ = {(\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 0 \end{matrix}), (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 1 & 0 \end{matrix}), (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 1 \end{matrix})} . \end{matrix}$

If W₀ (H₀) = {(1, 2, 1) , (2, 2, 1)}, i.e., $H_{0} = (\begin{matrix} 1 & 1 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{matrix})$ , then $K_{0} (\bar{D}, H_{0}) = {(\begin{matrix} 1 & 1 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{matrix}), (\begin{matrix} 1 & 1 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{matrix})} .$

If W₀ (H₀) = {(2, 1, 2) , (1, 1, 2)}, i.e., $H_{0} = (\begin{matrix} 1 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix})$ , then $K_{0} (\bar{D}, H_{0}) = {(\begin{matrix} 1 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix}), (\begin{matrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix})} .$

Thus $K (\bar{D}, \hat{C})$ is the join of the eight sets $K_{0} (\bar{D}, H_{0})$ above and $\begin{matrix} K (\bar{D}, \hat{C}) / \sim \\ = {{[(\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{matrix})]}^{\sim}, {[(\begin{matrix} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{matrix})]}^{\sim}, {[(\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 1 & 0 \end{matrix})]}^{\sim}} \\ ⋃ {{[(\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 1 & 1 \end{matrix})]}^{\sim}, {[(\begin{matrix} 0 & 1 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{matrix})]}^{\sim}, {[(\begin{matrix} 0 & 1 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{matrix})]}^{\sim}} . \end{matrix}$

Therefore, from (C1.1)– (C1.9) we have $\begin{matrix} A / \sim \\ = {{[(\begin{matrix} \geq & < & \leq \\ < & > & < \\ > & < & < \end{matrix})]}^{\sim}, {[(\begin{matrix} > & < & \leq \\ < & > & < \\ \geq & < & < \end{matrix})]}^{\sim}, {[(\begin{matrix} \geq & < & < \\ < & \geq & < \\ > & > & \leq \end{matrix})]}^{\sim}} \\ ⋃ {{[(\begin{matrix} > & < & < \\ < & \geq & < \\ \geq & > & \leq \end{matrix})]}^{\sim}, {[(\begin{matrix} > & < & < \\ < & > & < \\ \geq & \geq & \leq \end{matrix})]}^{\sim}, {[(\begin{matrix} \geq & < & < \\ < & > & < \\ > & \geq & \leq \end{matrix})]}^{\sim}} \\ ⋃ {{[(\begin{matrix} < & \geq & \leq \\ < & > & < \\ > & < & < \end{matrix})]}^{\sim}, {[(\begin{matrix} < & > & \leq \\ < & \geq & < \\ > & < & < \end{matrix})]}^{\sim}} . \end{matrix}$

Finally, we have A = ⋃ _{[A^*(H)]^∼∈A/∼} [A^* (H)] ^∼. Note that in the process as above we need to exchange the 1-th row, 2-th and 3-th row of the involved matrices since b₁ = b₂ = b₃.

From Example 4.1, we observe that for $H \in K (\bar{D}, \hat{C})$ ,

H may have c.w.’s p₁, p₂ which satisfy that x (p₂) > x (p₁) with p₁ ∈ W₀ (C) or

H may have two distinct c.w.’s p₁, p₂ ∈ W₀ (C) which satisfy that x (p₁) = x (p₂).

5 Algorithm and examples

This section will give a more simple algorithm to describe A.

Let [p]∈ P/≡ which contains the c.w.’s p where P⊆ ∮.

Algorithm 5.1. Input: A = (a_ij)∈ [0, 1] ^m×n, b = (b_i) ^T ∈ [0, 1] ^mand A : = ∅. Output: A. Step 1. Compute Aαb. If A ⊙ (Aαb) ≠ b, then go to Step 7. Step 2. Compute $D, \bar{D}, C$ and W₀ (C). Step 3. Set P = {p ∈ ∮ ∣ p ≡ p′, p′ ∈ W₀ (C)}. Step 4. Set P/≡ = {[p₁] , [p₂] , ⋯ , [p_r]}.

Step 5. Compute $K^{*} (\bar{D}, \hat{C}) = {H \in K ∣ W (H) = {p_{1}^{'}, p_{2}^{'}, \dots, p_{r}^{'}}, p_{i}^{'} \in [p_{i}], i = 1, 2, \dots, r} \cap K (\bar{D})$ . Step 6. Compute A^* (H) and [A^* (H)] ^∼ for every $H \in K^{*} (\bar{D}, \hat{C})$ . Step 7. $A : = ⋃_{H \in K^{*} (\bar{D}, \hat{C})} [A^{*} (H)]^{\sim}$ .

It is easy to show that $K^{*} (\bar{D}, \hat{C}) \subseteq K (\bar{D}, \hat{C})$ and r = |X₀|. Indeed, the following theorem together with Theorems 4.1 and 4.3 implies Algorithm 5.1.

Theorem 5.1. To depict the set A, we have the following two results for $H \in K (\bar{D}, \hat{C})$ .

We don’t need to consider these matrices H who have two (or more) different c.w.’s p₁, p₂ ∈ W₀ (C) where x (p₁) = x (p₂). We just need to take [A^* (H)] ^∼ into account where $\hat{H}$ just contains one of p₁ and p₂ where p₁, p₂ ∈ W₀ (C) with x (p₁) = x (p₂) instead.

We don’t need to consider these matrices H who have c.w.’s p₂ where x (p₂) > x (p₁) with p₁ ∈ W₀ (C). We just need to take [A^* (H)] ^∼ into account where H contains p₁ and doesn’t contain p₂ where x (p₂) > x (p₁) with p₁ ∈ W₀ (C) instead.

Proof. Clearly if $A_{H}^{*}, A_{H^{'}}^{*} \in A$ and $A_{H^{'}}^{*} \sim A_{H}^{*}$ for $H \in K (\bar{D}, \hat{C})$ and $H^{'} \in K (\bar{D}, \hat{C})$ , then H′ ∼ H.

Let p₁ and p₂ be two distinct c.w.’s of $\hat{H}$ where $\hat{H} = ({\hat{h}}_{ij}) \in K (\bar{D}, \hat{C})$ . Put $p_{β} = (j_{1}^{(β)}, j_{2}^{(β)}, \dots, j_{m}^{(β)}) (β = 1, 2)$ and $i_{0} = \min {i ∣ j_{i}^{(1)} \neq j_{i}^{(2)}}$ . Then 1 ≤ i₀ ≤ m since p₁ ≠ p₂. Hence $j_{i}^{(1)} = j_{i}^{(2)} \notin {j_{i_{0}}^{(1)}, j_{i_{0}}^{(2)}}$ for i < i₀. Note that there may exist another pair ${j_{i}^{(1)}, j_{i}^{(2)}} \neq {j_{i_{0}}^{(1)}, j_{i_{0}}^{(2)}}$ with $j_{i}^{(1)} \neq j_{i}^{(2)}$ , then we set $\begin{matrix} i_{0}^{'} & = & \min {i ∣ j_{i}^{(1)} \neq j_{i}^{(2)} and {j_{i}^{(1)}, j_{i}^{(2)}} \\ \neq & {j_{i_{0}}^{(1)}, j_{i_{0}}^{(2)}}} . \end{matrix}$

It is obvious that $i_{0} \neq i_{0}^{'}$ . In this case, we just do the same for $j_{i_{0}^{'}}^{(1)}, j_{i_{0}^{'}}^{(2)}$ as we do for $j_{i_{0}}^{(1)}, j_{i_{0}}^{(2)}$ as below. Thus, we postulate $j_{i}^{(1)} = j_{i}^{(2)}$ if $j_{i}^{(1)} \notin {j_{i_{0}}^{(1)}, j_{i_{0}}^{(2)}}$ . We define $\begin{matrix} {\hat{H}}_{i} = the i - th row of \hat{H}, \\ {{\hat{H}}_{i}} = {j ∣ {\hat{H}}_{ij} = 1} for any i \in M . \end{matrix}$

Since p₁ and p₂ are c.w.’s of $\hat{H}$ , ${j_{1}^{(β)}, j_{2}^{(β)}, \dots, j_{i_{0} - 1}^{(β)}} \cap {{\hat{H}}_{i_{0}}} = \emptyset$ where β = 1, 2, and ${j_{1}^{(β)}, j_{2}^{(β)}, \dots, j_{i_{0} - 1}^{(β)}} = \emptyset$ for i₀ = 1. Then $j_{i_{0}}^{(β)}$ first appears in $(j_{1}^{(β)}, j_{2}^{(β)}, \dots, j_{i_{0} - 1}^{(β)}),$ i.e., $\begin{matrix} i_{0} = \min {i ∣ j_{i}^{(1)} = j_{i_{0}}^{(1)}} and \\ i_{0} = \min {i ∣ j_{i}^{(2)} = j_{i_{0}}^{(2)}} . \end{matrix}$

Proof of (1): Let $p_{1} \equiv p_{2} \in W_{0} (\hat{C})$ and $\hat{H}$ has p₁, p₂. Then we have x (p₁) = x (p₂) and {p₁} = {p₂}. Put

$\begin{matrix} i_{1} = \min {i ∣ j_{i}^{(1)} = j_{i_{0}}^{(2)}} and \\ i_{2} = \min {i ∣ j_{i}^{(2)} = j_{i_{0}}^{(1)}} . \end{matrix}$ (3)

So we have i₁ > i₀, i₂ > i₀, b_{i
₀} = b_{i
₁} = b_{i
₂}, and $j_{i_{β}}^{(β)}$ first appears in $(j_{1}^{(β)}, j_{2}^{(β)}, \dots, j_{i_{β} - 1}^{(β)}) (β = 1, 2)$ . Because $j_{i_{2}}^{(2)} = j_{i_{0}}^{(1)} \in {{\hat{H}}_{i_{2}}}$ and $j_{i_{0}}^{(1)}$ is the first element encountering ${{\hat{H}}_{i_{2}}}$ in $(j_{1}^{(1)}, j_{2}^{(1)}, \dots, j_{i_{2} - 1}^{(1)}),$ we have $j_{i_{2}}^{(1)} = j_{i_{0}}^{(1)}$ . Similarly we have $j_{i_{1}}^{(2)} = j_{i_{0}}^{(2)}$ . Further, we can get i₁ ≠ i₂ by the definition of c.w. In fact, if i₁ = i₂, then $j_{i_{0}}^{(2)} = j_{i_{1}}^{(1)} = j_{i_{2}}^{(1)} = j_{i_{0}}^{(1)}$ , a contradiction since $j_{i_{0}}^{(1)} \neq j_{i_{0}}^{(2)}$ . Hence, i₁ ≠ i₂. Without loss of generality, let us assume that i₁ < i₂ below.

Then formula (1) together with the definition of c.w.’s implies that ${j_{i_{0}}^{(1)}, j_{i_{0}}^{(2)}} \cap {{\hat{H}}_{i_{1}}} = {j_{i_{1}}^{(1)}} = {j_{i_{0}}^{(2)}},$ and ${j_{i_{0}}^{(1)}, j_{i_{0}}^{(2)}} \cap {{\hat{H}}_{i_{2}}} = {j_{i_{2}}^{(2)}} = {j_{i_{0}}^{(1)}} .$

Now, without loss of generality, we let $p_{1} \in W ({\hat{H}}^{'})$ and $p_{2} \notin W ({\hat{H}}^{'})$ where ${\hat{H}}^{'} = ({\hat{h}}_{ij}^{'})$ . Then ${\hat{h}}_{ij}^{'} = {\begin{matrix} 0 & if j_{i} \in {j_{i}^{(2)} ∣ j_{i}^{(1)} \neq j_{i}^{(2)}}, \\ {\hat{h}}_{ij} & otherwise . \end{matrix}$

If $j_{i} \in {j_{i}^{(2)} ∣ j_{i}^{(1)} \neq j_{i}^{(2)}}$ , then $i \geq i_{0}, j_{i} \in {j_{i_{0}}^{(1)}, j_{i_{0}}^{(2)}}$ . Let us assume $j_{i} = j_{i_{0}}^{(1)}$ . Then $j_{i}^{(1)} = j_{i_{0}}^{(1)}$ since $j_{i_{0}}^{(1)} \in {p_{1}}$ and it is the first element appeared in {p₁}. So $j_{i}^{(1)} = j_{i_{0}}^{(1)} = j_{i}^{(2)}$ , a contradiction. Thus, $j_{i} = j_{i_{0}}^{(2)}$ and we have ${\hat{h}}_{{ij}_{i_{0}}^{(1)}}^{'} = 1$ and ${\hat{h}}_{{ij}_{i_{0}}^{(2)}}^{'} = 0$ . Further, from the definition of ${\hat{H}}^{'}$ we have $h_{{ij}_{i_{0}}^{(1)}}^{'} = 1, h_{{ij}_{i_{0}}^{(2)}}^{'} = 0$ or 1 for $H^{'} = (h_{ij}^{'})$ where $j_{i} \in {j_{i}^{(2)} ∣ j_{i}^{(1)} \neq j_{i}^{(2)}}$ and i ≠ i₀. Hence $h_{i_{0} j_{i_{0}}^{(1)}}^{'} = 1, h_{i_{0} j_{i_{0}}^{(2)}}^{'} = 0$ ; $h_{i_{1} j_{i_{0}}^{(1)}}^{'} = 0, h_{i_{1} j_{i_{0}}^{(2)}}^{'} = 1$ ; $h_{i_{2} j_{i_{0}}^{(1)}}^{'} = 1, h_{i_{2} j_{i_{0}}^{(2)}}^{'} = 0$ or 1 . So we can take $H^{'} = (h_{ij}^{'})$ as follows: $h_{ij}^{'} = {\begin{matrix} 1 & if j_{i} \in {j_{i}^{(2)} ∣ j_{i}^{(1)} \neq j_{i}^{(2)}} and i \neq i_{0}, \\ 0 & if i = i_{0} and j = j_{i_{0}}^{(2)}, \\ 1 & if i = i_{2} and j = j_{i_{0}}^{(2)}, \\ {\hat{h}}_{ij}^{'} & otherwise . \end{matrix}$

It is easily seen that p₁ ∈ W (H′) and p₂ ∉ W (H′). Then we get H^* by exchanging the i₀-th row and i₂-th row of H′ since b_{i
₀} = b_{i
₂}. Thus H^* has c.w.s p₁ and p₂. So we just need to take [A^* (H)] ^∼ into account where $\hat{H}$ just contains one of p₁ and p₂ where p₁, p₂ ∈ W₀ (C) with x (p₁) = x (p₂) instead. This completes the proof of (1).

Proof of (2): Let $x (p_{2}) > x (p_{1}) \in W_{0} (\hat{C})$ and H has p₁, p₂. From the definitions of x (p₁) and x (p₂), we have {p₁} ⊆ {p₂}. Arguing as the proof of (1), we have $j_{i}^{(1)} = j_{i}^{(2)}$ if $j_{i}^{(1)}, j_{i}^{(2)} \notin {j_{i_{0}}^{(1)}, j_{i_{0}}^{(2)}}$ . Since $j_{i_{0}}^{(1)} \in {p_{1}}$ , $j_{i_{0}}^{(1)} \in {p_{2}}$ . Thus we can let $i_{2} = \min {i ∣ j_{i}^{(2)} = j_{i_{0}}^{(1)}}$ . Moreover, from Corollary 2.2 we have $x (p_{1})_{j_{i_{0}}^{(1)}} = b_{i_{0}}, x (p_{2})_{j_{i_{0}}^{(1)}} = b_{i_{2}} .$

Then b_{i
₂} ≥ b_{i
₀} since x (p₂) > x (p₁). On the other hand, b_{i
₂} ≤ b_{i
₀} since i₂ > i₀. So that b_{i
₀} = b_{i
₂}.

Now, let $H^{'} \in K (\bar{D}, \hat{C})$ where p₁ ∈ W (H′) and p₂ ∉ W (H′). Similar to the proof of (1) we have $h_{i_{0} j_{i_{0}}^{(1)}}^{'} = 1, h_{i_{0} j_{i_{0}}^{(2)}}^{'} = 0; h_{i_{2} j_{i_{0}}^{(1)}}^{'} = 1, h_{i_{2} j_{i_{0}}^{(2)}}^{'} = 0 or 1,$ and we can take $H^{'} = (h_{ij}^{'})$ as below: $h_{ij}^{'} = {\begin{matrix} 1 & if j_{i} \in {j_{i}^{(2)} ∣ j_{i}^{(1)} \neq j_{i}^{(2)}} and i \neq i_{0}, \\ 0 & if i = i_{0} and j = j_{i_{0}}^{(2)}, \\ 1 & if i = i_{2} and j = j_{i_{0}}^{(2)}, \\ h_{ij} & otherwise . \end{matrix}$

It is easily seen that p₁ ∈ W (H′), p₂ ∉ W (H′) and $\hat{H^{'}} = \hat{H}$ . Then we get H^* by exchanging the i₀-th row and i₂-th row of H′ since b_{i
₀} = b_{i
₂}. Thus H^* has c.w.s p₁ and p₂. Consequently, we just need to take [A^* (H)] ^∼ into account where H contains p₁ and doesn’t contain p₂ where x (p₂) > x (p₁) with p₁ ∈ W₀ (C) instead. □

Notice that from Theorem 5.1, one can see that in order to describe A Algorithm 5.1 is more simple than Theorem 4.3.

The following example will illustrate Algorithm 5.1. For convenience, let $K_{0}^{*} (H_{0}) = {H \in K ∣ W (H) = W (H_{0}), H_{0} \in K_{0}}$ and $K_{0}^{*} (\bar{D}, H_{0}) = K_{0}^{*} (H_{0}) \cap K (\bar{D})$ .

Example 5.1. Let us consider Example 4.1. First we have P = $\begin{matrix} {(1, 2, 1), (1, 1, 2), (2, 1, 1), (2, 2, 1), \\ (2, 1, 2), (1, 2, 2)}, \end{matrix}$ and P/≡ = {[(1, 2, 1)]}. Therefore, we exactly have the following six cases by Algorithm 5.1:

If W (H₀) = {(1, 2, 1)}, i.e., $H_{0} = (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{matrix})$ , then $K_{0}^{*} (\bar{D}, H_{0}) =$ ${(\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{matrix}), (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 1 & 0 \end{matrix}), (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 1 \end{matrix}), (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 1 & 1 \end{matrix})} .$

If W (H₀) = {(1, 1, 2)}, i.e., $H_{0} = (\begin{matrix} 1 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix})$ , then $K_{0}^{*} (\bar{D}, H_{0}) =$ ${(\begin{matrix} 1 & 0 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix}), (\begin{matrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 0 & 1 & 0 \end{matrix}), (\begin{matrix} 1 & 0 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{matrix}), (\begin{matrix} 1 & 0 & 0 \\ 1 & 1 & 1 \\ 0 & 1 & 0 \end{matrix})} .$

If W (H₀) = {(2, 1, 1)}, i.e., $H_{0} = (\begin{matrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{matrix})$ , then $K_{0}^{*} (\bar{D}, H_{0}) = {(\begin{matrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 0 \end{matrix}), (\begin{matrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 0 & 1 \end{matrix})} .$

If W (H₀) = {(2, 2, 1)}, i.e., $H_{0} = (\begin{matrix} 0 & 1 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{matrix})$ , then $K_{0}^{*} (\bar{D}, H_{0}) =$ ${(\begin{matrix} 0 & 1 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{matrix}), (\begin{matrix} 0 & 1 & 0 \\ 1 & 1 & 0 \\ 1 & 0 & 0 \end{matrix}), (\begin{matrix} 0 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \end{matrix}), (\begin{matrix} 0 & 1 & 0 \\ 1 & 1 & 1 \\ 1 & 0 & 0 \end{matrix})} .$

If W (H₀) = {(2, 1, 2)}, i.e., $H_{0} = (\begin{matrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix})$ , then $K_{0}^{*} (\bar{D}, H_{0}) =$ ${(\begin{matrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix}), (\begin{matrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 0 \end{matrix}), (\begin{matrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 1 \end{matrix}), (\begin{matrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \end{matrix})} .$

If W (H₀) = {(1, 2, 2)}, i.e., $H_{0} = (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 0 \end{matrix})$ , then $K_{0}^{*} (\bar{D}, H_{0}) = {(\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 0 \end{matrix}), (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 1 \end{matrix})} .$

Therefore, by Algorithm 5.1 $K^{*} (\bar{D}, \hat{C})$ is the join of the six sets $K_{0}^{*} (\bar{D}, H_{0})$ above, and from (C1.1)– (C1.9) we have $\begin{matrix} A / \sim \\ = {{[(\begin{matrix} \geq & < & \leq \\ < & > & < \\ > & < & < \end{matrix})]}^{\sim}, {[(\begin{matrix} > & < & \leq \\ < & > & < \\ \geq & < & < \end{matrix})]}^{\sim}, \\ {[(\begin{matrix} \geq & < & < \\ < & \geq & < \\ > & > & \leq \end{matrix})]}^{\sim}} \\ ⋃ {{[(\begin{matrix} > & < & < \\ < & \geq & < \\ \geq & > & \leq \end{matrix})]}^{\sim}, {[(\begin{matrix} > & < & < \\ < & > & < \\ \geq & \geq & \leq \end{matrix})]}^{\sim}, \\ {[(\begin{matrix} \geq & < & < \\ < & > & < \\ > & \geq & \leq \end{matrix})]}^{\sim}} \\ ⋃ {{[(\begin{matrix} < & \geq & \leq \\ < & > & < \\ > & < & < \end{matrix})]}^{\sim}, {[(\begin{matrix} < & > & \leq \\ < & \geq & < \\ > & < & < \end{matrix})]}^{\sim}} . \end{matrix}$

Finally, we have A = ⋃ _{[A^*(H)]^∼∈A/∼} [A^* (H)] ^∼.

6 Conclusions

This contribution gave an algorithm to completely describe the set of coefficient matrices which are invariant to a solution set of a fuzzy relation equation with max-min composition whose right hand side b satisfies 1 ≥ b₁ ≥ b₂ ≥ ⋯ ≥ b_m > 0. Our results generalize the corresponding ones of [9] and they may be used to simplify a fuzzy relation equation with max-min composition when solved.

References

Sanchez

, Resolution of composite fuzzy relation equations, Inform Control 30 (1976), 38–48.

Pavlica

, Petrovacki

, About simple fuzzy control and fuzzy control based on fuzzy relational equations, Fuzzy Sets Syst 101 (1999), 41–47.

Hirota

, Pedrycz

, Data compression with fuzzy relational equations, Fuzzy Sets Syst 126 (2002), 325–335.

Peeva

, Kyosev

, Fuzzy Relational Calculus: Theory, Applications and Software, World Scientific Publishing Company, 2004.

Czogała

, Drewniak

and Pedrycz

, Fuzzy relation equations on a finite set, Fuzzy Sets Syst 7 (1982), 89–101.

Higashi

, Li

, Resolution of finite fuzzy relation equations, Fuzzy Sets and Syst 13 (1984), 65–82.

Di Nola

, Sessa

and Pedrycz

, Wang Pei-zhuang, How many lower solutions does a fuzzy relation equation have, Busefal 18 (1984), 67–74.

Di Nola

, Sessa

, Pedrycz

and Higashi

, Minimal and maximal solutions of a decomposition problem of fuzzy relations, Int J Gen Syst 11 (1985), 103–116.

Miyakoshi

, Shimbo

, Sets of solution-set-invariant coefficient matrices of simple fuzzy relation equations, Fuzzy Sets Syst 21 (1987), 59–83.

10.

Di Nola

, Sessa

, Pedrycz

and Sanchez

, Fuzzy Relation Equations and Their Applications to Knowledge Engineering, Kluwer Academic Publishers, Dordrecht, Boston/London, 1989.

11.

Xiong

Q.Q.

, Wang

X.P.

, The solution set of a fuzzy relational equation with sup-conjunctor composition in a composition in a complete lattice, Fuzzy Sets Syst 153 (2005), 249–260.

12.

X.B.

, Wang

X.P.

, Some properties of infinite fuzzy relational equations on complete Brouwerian lattices, Fuzzy Sets Syst 158 (2007), 1327–1339.

13.

Yeh

C.T.

, On the minimal solutions of max-min fuzzy relation equations, Fuzzy Sets Syst 159 (2008), 23–39.

14.

Drewniak

, Matusiewicz

, Properties of max-* fuzzy relational equations, Soft Comput 14 (2010), 1037–1041.

15.

X.B.

, Feng

, Wang

T.F.

, Matrix elementary transformations in solving systems of fuzzy relation equations, Appl Soft Comput 31 (2015), 25–29.