Eigenproblems in addition-min algebra 1

Abstract

In order to guarantee the downloading quality requirements of users and improve the stability of data transmission in a BitTorrent-like peer-to-peer file sharing system, this article deals with eigenproblems of addition-min algebras. First, it provides a sufficient and necessary condition for a vector being an eigenvector of a given matrix, and then presents an algorithm for finding all the eigenvalues and eigenvectors of a given matrix. It further proposes a sufficient and necessary condition for a vector being a constrained eigenvector of a given matrix and supplies an algorithm for computing all the constrained eigenvectors and eigenvalues of a given matrix. This article finally discusses the supereigenproblem of a given matrix and presents an algorithm for obtaining the maximum constrained supereigenvalue and depicting the feasible region of all the constrained supereigenvectors for a given matrix. It also gives some examples for illustrating the algorithms, respectively.

1 Introduction

An eigenproblem is a very classical and important topic in linear algebra. Its main goal is to find the eigenvalues and the eigenvectors of a given matrix A. A scalar λ is called an eigenvalue of A, if there exists a nonzero vector x satisfying ${\mathit{Ax}}^T=\lambda x^T,$(1) where the operations of equation (1) are the common plus (+) and multiplication (×) in the real number set. In some practical applications, the eigenproblem is used to describe the steady states of discrete event systems, for instance, the eigenproblems in fuzzy algebra and max-plus algebra [7, 19]. Now, the eigenproblem in algebra has been studied by many authors, such as max-plus algebra [1, 13], max-min algebra [4, 23], max-prod algebra [2, 21], max-Lukasiewicz and max-drastic algebra [15, 22].

In particular, Cuninghame-Green [8] first studied the eigenproblem in max-plus algebra, and he even gave all the solutions of the eigenproblem with irreducible matrices [9]. Bapat et al. [1] further proved the spectral theorem for the reducible matrices. In [6], Cechlrov defined the universal and possible eigenvectors and proposed an algorithm for judging whether a given vector is a possible eigenvector or not and a universal eigenvector exists or not, respectively. Gavalec et al. [13] investigated the eigenproblem of a given matrix with interval coefficients and supplied polynomial algorithms to identify three types of tolerance interval eigenvectors.

In max-min algebra, an algorithm for calculating the maximum eigenvector of a given matrix is proposed [4, 10]. Gavalec showed that the complete structure of the eigenspace is a union of permutation non-decreasing eigenvector intervals [12]. In max-drastic algebra, Gavalec et al. [15] completely described the structure of the eigenspace of a given matrix. Rashid et al. [22] obtained a similar result for a square matrix in max-Łukasiewicz algebra. Rashid et al. [21] also investigated the eigenspace of a given matrix of order 3 in max-prod algebra.

The theory of fuzzy relation inequalities has been widely used in BitTorrent-like peer-to-peer (P2P) file sharing system. Assume that the P2P file sharing system has n terminals, which are denoted by A₁, A₂, ⋯ , A _n . Each terminal should share its local file resources to any other one. At the same time, the file data can be downloaded from any other terminal. Suppose that the jth terminal A _j sends the file data to another one with quality level x _j and the bandwidth between A _i and A _j is a _ij . For data transmission, the download quality level of A _i from A _j is actually a _ij  ∧ x _j due to the bandwidth limitation, on which the file data of terminal A _i from other ones is a_i1 ∧ x₁ + ⋯ + a_ii-1 ∧ x_i-1 + a_ii+1 ∧ x_i+1 + ⋯ + a _in  ∧ x _n . In order to satisfy the downloading quality requirements of users, total download quality of A _i should be no less than b _i (b _i  > 0). Then the P2P file sharing system is reduced to a system of fuzzy relation inequations with addition-min composition as follows.

$\{\begin{array}{cc}{a}_{11}\wedge x_1+\cdots +a_{1n}\wedge x_n\ge b_1,\hfill & \hfill \\ a_{21}\wedge x_1+\cdots +a_{2n}\wedge x_n\ge b_2,\hfill & \hfill \\ \cdots \hfill & \hfill \\ a_{n1}\wedge x_1+\cdots +a_{\mathit{nn}}\wedge x_n\ge b_n,\hfill & \hfill \end{array}$(2) where a _ij , x _j  ∈ [0, 1], b _i  > 0 (i = 1, 2, ⋯ , n ; j = 1, 2, ⋯ , n), a _ij  ∧ x _j  = min {a _ij , x _j }, and the operation ^′ + ′ is the ordinary addition [17]. System (2) can be tersely described as follows $A\odot x^T\ge b^T$ where A = (a _ij ) _n×n, x = (x₁, x₂, ⋯ , x _n ), b = (b₁, b₂, ⋯ , b _n ) and (a_i1, a_i2, ⋯ , a _in ) ⊙ (x₁, x₂, ⋯ , x _n ) = a_i1 ∧ x₁ + a_i2 ∧ x₂ + ⋯ + a _in  ∧ x _n .

In order to avoid network congestion and improve the stability of data transmission, we need to enhance the relevance between the data download quality and the data sending quality of the terminal. Following this idea, a popular method is to give the data download quality a proportional to the data sending quality [25]. This means that the data download quality to the data sending quality will reach a steady state. We say that the system reaches a steady regime. If the proportional coefficient is denoted by λ ≥ 0, then the corresponding steady regime of the P2P file sharing system can be written in mathematics as follows. $\{\begin{array}{cc}{a}_{11}\wedge x_1+\cdots +a_{1n}\wedge x_n=\lambda x_1,\hfill & \hfill \\ a_{21}\wedge x_1+\cdots +a_{2n}\wedge x_n=\lambda x_2,\hfill & \hfill \\ \cdots \hfill & \hfill \\ a_{n1}\wedge x_1+\cdots +a_{\mathit{nn}}\wedge x_n=\lambda x_n.\hfill & \hfill \end{array}$(3) The matrix form of system (3) is $A\odot x^T=\lambda x^T$ where λ ∈ [0, + ∞). Considering the addition-min composition ⊙, λx ^T means that λ multiplies by x _j , j ∈ {1, 2 ⋯ , n}. It is clear that the steady states of the data download quality to the data sending quality are more favorable to the terminal. In other words, a steady value will benefit users. This article aims to obtain the steady value λ and the steady solution x, called an eigenvalue and eigenvector of A, respectively.

The rest of this article is organized as follows. In Section 2, we present some necessary notation and known results for following this article. In Section 3, we introduce an eigenproblem of addition-min algebra, provide a sufficient and necessary condition for a vector being an eigenvector of a given matrix A, and then present an algorithm for finding all the eigenvalues and eigenvectors of a given matrix A for the system (3). In Section 4, we consider the so-called constrained eigenproblem, show a sufficient and necessary condition for a vector being a constrained eigenvector of a given matrix A, and give an algorithm for computing all the constrained eigenvectors and eigenvalues of a given matrix A. In Section 5, we make the algorithms obtained in Sections 3 and 4 be suitable for the supereigenvectors and constrained supereigenvectors of addition-min algebras, respectively. A concluding remark is drawn in Section 6.

2 Preliminaries

This section presents some basic notation and known results.

We call the algebra ([0, 1] , + , ∧) an addition-min algebra and denote the real unit interval by $\mathcal{I}=[0,1]$ . Let N = {1, 2, ⋯ , n}. Further, the notation ${\mathcal{I}}^{\mathcal{n}\times \mathcal{n}}$ denotes the set of n × n matrices over $\mathcal{I}$ , the set of 1 × n vectors over $\mathcal{I}$ is denoted by ${\mathcal{I}}^{\mathcal{n}}$ and θ = (0, 0, ⋯ , 0).

For $x=(x_1,x_2,\cdots ,x_n),y=(y_1,y_2,\cdots ,y_n)\in {\mathcal{I}}^n$ , define x ≤ y if and only if x _i  ≤ y _i for arbitrary i ∈ N, and define x < y if and only if x _i  ≤ y _i for arbitrary i ∈ N and there is a j ∈ N such that x _j  < y _j .

Lemma 2.1 ([17, 24]). System (2) is solvable if and only if (1, 1, ⋯ , 1) is a solution of system (2).

Lemma 2.2 ([17, 24]). Let x = (x₁, x₂, ⋯ , x _n ) be a solution of system (2). Then we have:

x > 0.

For any i ∈ N, j ∈ N, x _j  ≥ b _i  - ∑_k∈N\{j}a _ik  ∧ x _k  ≥ b _i  - ∑_k∈N\{j}a _ik .

For any i ∈ N, j ∈ N, a _ij  ≥ b _i  - ∑_k∈N\{j}a _ik  ∧ x _k  ≥ b _i  - ∑_k∈N\{j}a _ik .

Let $\check{\alpha }=({\check{\alpha }}_1,{\check{\alpha }}_2,\cdots ,{\check{\alpha }}_n)$ with ${\check{\alpha }}_j=max\{0,b_i-\sum _{k\in N\backslash \left\{j\right\}}{a}_{\mathit{ik}}|i\in N\}$ and $\hat{\alpha }=({\hat{\alpha }}_1,{\hat{\alpha }}_2,\cdots ,{\hat{\alpha }}_n)$ with ${\hat{\alpha }}_j=max\left\{a_{\mathit{ij}}\right|i\in N\}.$ Then we have the following lemma.

Lemma 2.3 ([24]). For any solution x of system (2), it holds that $\check{\alpha }\le x$ .

3 Eigenproblems of addition-min algebras

In this section, we first introduce an eigenproblem of addition-min algebra, and then investigate the conditions for a vector being an eigenvector of a given matrix A. We also explore an algorithm for finding all the eigenvalues and eigenvectors of a given matrix A for the system (3).

In addition-min algebra, for a given matrix $A\in {\mathcal{I}}^{n\times n}$ , the task of finding a vector $x\in {\mathcal{I}}^n$ with x ≠ θ and a scalar λ ∈ [0, + ∞) satisfying the system (3) is called an eigenproblem of addition-min algebra. The scalar λ is called an eigenvalue of A, and the corresponding vector x is called an eigenvector of A associated with λ.

The notation V (A, λ) denotes the set consisting of all eigenvectors of A corresponding to λ, and Λ (A) denotes the set consisting of all eigenvalues of A, i.e., $V(A,\lambda )=\{x\in {\mathcal{I}}^n|A\odot x^T=\lambda x^T\mathrm{and}x\ne \theta \}$ and $\Lambda \left(A\right)=\{\lambda \in [0,+\infty \left)\right|V(A,\lambda )\}.$ Let | ∅ |=0 and denote the set of all eigenvectors of A by V (A), i.e., $V\left(A\right)={\bigcup }_{\lambda \in \Lambda \left(A\right)}V(A,\lambda ).$

In what follows, we discuss the eigenproblems of addition-min algebras.

Definition 3.1. For $A=(a_{\mathit{ij}}{)}_{n\times n}\in {\mathcal{I}}^{n\times n}$ and j ∈ N, denote | {a _ij |0 < a _ij  < 1, i ∈ N} | = t _j and Q _j  = {q_0j, q_1j, q_2j, ⋯ , q _{t j j} , q_{(t j +1)j}} with 0 = q_0j < q_1j < q_2j < ⋯ < q _{t j j}  < q_{(t j +1)j} = 1, where q _kj  ∈ {a _ij |i ∈ N} , k = 1, 2, ⋯ , t _j .

Let K = {(k₁, k₂, ⋯ , k _n ) |k _j  ∈ K _j  forany j ∈ N} with $K_j=\left\{k\right|0<q_{\mathit{kj}}\mathrm{and}{q}_{\mathit{kj}}\in Q_j\}.$(4)

Notice that from Definition 3.1, one can check that K _j ≠ ∅ and |Q _j |≥2 for any j ∈ N. In particular, if t _j  = 0 for a j ∈ N then Q _j  = {0, 1}.

Theorem 3.1. Let $x=(x_1,x_2,\cdots ,x_n)\in {\mathcal{I}}^n$ . Then x ∈ V (A, λ) if and only if there exists a k = (k₁, k₂, ⋯ , k _n ) ∈ K such that $\{\begin{array}{cc}{q}_{(k_j-1)j}\le x_j\le q_{k_{j}j}\mathrm{for}\mathrm{all}j\in N,\hfill & \hfill \\ \hfill & \hfill \\ \sum _{j\in N}[{\delta }_{\mathit{ij}}·x_j+(1-{\delta }_{\mathit{ij}})·a_{\mathit{ij}}]=\lambda x_i\hfill & \hfill \\ \mathrm{for}\mathrm{all}i\in N\hfill & \hfill \end{array}$(5) where the operation “ · ″ represents the ordinary multiplication and ${\delta }_{\mathit{ij}}=\{\begin{array}{c}1,q_{k_{j}j}\le a_{\mathit{ij}},\hfill \\ 0,a_{\mathit{ij}}\le q_{(k_j-1)j}.\hfill \end{array}$

Proof. Suppose that x = (x₁, x₂, ⋯ , x _n ) ∈ V (A, λ). According to Definition 3.1 and Formula (4), it is clear that there is a k _j such that q_{(k j -1)j} ≤ x _j  ≤ q _{k j j} for any j ∈ N. Thus, there exists a k = (k₁, k₂, ⋯ , k _n ) ∈ K such that q_{(k j -1)j} ≤ x _j  ≤ q _{k j j} for any j ∈ N. For any i ∈ N, we get $\begin{array}{ccc}\hfill \lambda x_i& \hfill =\hfill & \sum _{j\in N}{a}_{\mathit{ij}}\wedge x_j\hfill \\ \hfill & \hfill =\hfill & \sum _{j\in N,q_{k_{j}j}\le a_{\mathit{ij}}}{a}_{\mathit{ij}}\wedge x_j+\sum _{j\in N,a_{\mathit{ij}}\le q_{(k_j-1)j}}{a}_{\mathit{ij}}\wedge x_j\hfill \\ \hfill & \hfill =\hfill & \sum _{j\in N,q_{k_{j}j}\le a_{\mathit{ij}}}{x}_j+\sum _{j\in N,a_{\mathit{ij}}\le q_{(k_j-1)j}}{a}_{\mathit{ij}}\hfill \\ \hfill & \hfill =\hfill & \sum _{j\in N,q_{k_{j}j}\le a_{\mathit{ij}}}{\delta }_{\mathit{ij}}·x_j+\sum _{j\in N,a_{\mathit{ij}}\le q_{(k_j-1)j}}(1-{\delta }_{\mathit{ij}})·a_{\mathit{ij}}\hfill \\ \hfill & \hfill =\hfill & \sum _{j\in N}[{\delta }_{\mathit{ij}}·x_j+(1-{\delta }_{\mathit{ij}})·a_{\mathit{ij}}],\hfill \end{array}$ where the operation “ · " represents the ordinary multiplication and ${\delta }_{\mathit{ij}}=\{\begin{array}{c}1,q_{k_{j}j}\le a_{\mathit{ij}},\hfill \\ 0,a_{\mathit{ij}}\le q_{(k_j-1)j}.\hfill \end{array}$

Now, suppose that there exists a k = (k₁, k₂, ⋯ , k _n ) ∈ K such that x satisfies the system (5). Then for any i ∈ N, we have $\begin{array}{ccc}\hfill \lambda x_i& \hfill =\hfill & \sum _{j\in N}[{\delta }_{\mathit{ij}}·x_j+(1-{\delta }_{\mathit{ij}})·a_{\mathit{ij}}]\hfill \\ \hfill & \hfill =\hfill & \sum _{j\in N,q_{k_{j}j}\le a_{\mathit{ij}}}{\delta }_{\mathit{ij}}·x_j+\sum _{j\in N,a_{\mathit{ij}}\le q_{(k_j-1)j}}(1-{\delta }_{\mathit{ij}})·a_{\mathit{ij}}\hfill \\ \hfill & \hfill =\hfill & \sum _{j\in N,q_{k_{j}j}\le a_{\mathit{ij}}}{x}_j+\sum _{j\in N,a_{\mathit{ij}}\le q_{(k_j-1)j}}{a}_{\mathit{ij}}\hfill \\ \hfill & \hfill =\hfill & \sum _{j\in N,q_{k_{j}j}\le a_{\mathit{ij}}}{a}_{\mathit{ij}}\wedge x_j+\sum _{j\in N,a_{\mathit{ij}}\le q_{(k_j-1)j}}{a}_{\mathit{ij}}\wedge x_j\hfill \\ \hfill & \hfill =\hfill & \sum _{j\in N}{a}_{\mathit{ij}}\wedge x_j.\hfill \end{array}$ Therefore, x ∈ V (A, λ).□

Note that in Theorem 3.1, λ can be seen as a given constant with λ ∈ [0, + ∞). So that every solution x = (x₁, x₂, ⋯ , x _n ) of system (5) can be represented by λ, and the corresponding λ can be determined by the x = (x₁, x₂, ⋯ , x _n ) since q_{(k j -1)j} ≤ x _j  ≤ q _{k j j}  forall j ∈ N.

Furthermore, Theorem 3.1 implies the following two statements.

Theorem 3.2. If the system (5) is unsolvable for any k = (k₁, k₂, ⋯ , k _n ) ∈ K then V (A, λ) =∅.

Theorem 3.3. For any k = (k₁, k₂, ⋯ , k _n ) ∈ K, if x = (x₁, x₂, ⋯ , x _n ) satisfies the system (5), then x ∈ V (A, λ).

For any k = (k₁, k₂, ⋯ , k _n ) ∈ K, we use V (A, λ, k) denotes the solution set of system (5) corresponding to k = (k₁, k₂, ⋯ , k _n ) ∈ K. Then based on Theorems 3.1 and 3.3, the eigenproblems of addition-min algebras are equivalent to solving the system (5). Therefore, we can summarize an algorithm for finding all the eigenvectors and eigenvalues of a given A as follows.

Algorithm 1

Input: A = (a _ij ) _n×n.

Output: Λ (A) and V (A).

Step 1. Compute K = {(k₁, k₂, ⋯ , k _n ) |k _j  ∈ K _j  forany j ∈ N} defined by (4).

Step 2. For any k = (k₁, k₂, ⋯ , k _n ) ∈ K, construct the corresponding system (5).

Step 3. Compute V (A, λ, k) by the corresponding system (5).

Step 4. Λ (A) = ⋃ _k∈K {λ ∈ [0, + ∞) |V (A, λ, k)} and V (A) = ⋃  _λ∈Λ(A)V (A, λ).

Theorem 3.4. Algorithm 1 terminates after O ((n + 1)  ⁿ ) operations.

Proof. In Step 1, it costs ∑_j∈N (t _j  + 2) operations for computing K, where ∑_j∈N (t _j  + 2) ≤ (n + 2) n. In Steps 2 and 3, for any k ∈ K, it takes 6n² + 3n operations for solving a corresponding system (5). Therefore, it costs (6n² + 3n) |K| operations, where $\left|K\right|=\prod _{j\in N}(t_j+1)\le (n+1{)}^n$ . Step 4 needs 2 (|K|-1) operations for computing Λ (A) and V (A). Therefore, the amount of computation of Algorithm 1 is ∑_j∈N (t _j  + 2) + (6n² + 3n) |K|+2 (|K|-1) = (6n² + 3n + 2) |K| + ∑_j∈N (t _j  + 2) -2. Consequently, the total computational complexity of Algorithm 1 is O ((n + 1)  ⁿ ). □

The following example illustrates Algorithm 1.

Example 3.1. Consider the following system: $\{\begin{array}{c}0.4\wedge x_1+0.6\wedge x_2=\lambda x_1,\hfill \\ 0.2\wedge x_1+0.5\wedge x_2=\lambda x_2.\hfill \\ \hfill \end{array}$

Step 1. Compute K₁ = {1, 2, 3} and K₂ = {1, 2, 3}. Then $\begin{array}{ccc}\hfill K& \hfill =\hfill & \left\{\right(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),\hfill \\ \hfill & \hfill \hfill & (3,2),(3,3)\}.\hfill \end{array}$ Step 2. Construct and solve the corresponding system (5):

For k₁ = (1, 1), $\{\begin{array}{c}{x}_1+x_2=\lambda x_1,\hfill \\ x_1+x_2=\lambda x_2,\hfill \\ 0\le x_1\le 0.2,\hfill \\ 0\le x_2\le 0.5.\hfill \end{array}$ We get x₁ = x₂ and λ = 2. Let x₁ = x₂ = t. Since 0 ≤ x₁ ≤ 0.2 and 0 ≤ x₂ ≤ 0.5, we have t ∈ [0, 0.2]. When t = 0, x = (0, 0) ∉ V (A, λ). Therefore, V (A, λ, k₁) = {(t, t) |t ∈ (0, 0.2] and λ = 2}.

For k₂ = (1, 2), $\{\begin{array}{c}{x}_1+x_2=\lambda x_1,\hfill \\ x_1+0.5=\lambda x_2,\hfill \\ 0\le x_1\le 0.2,\hfill \\ 0.5\le x_2\le 0.6.\hfill \end{array}$ We get $x_1=\frac{0.5}{{\lambda }^2-\lambda -1}$ , $x_2=\frac{0.5(\lambda -1)}{{\lambda }^2-\lambda -1}$ and λ² - λ - 1 >0. Since $0\le \frac{0.5}{{\lambda }^2-\lambda -1}\le 0.2$ and $0.5\le \frac{0.5(\lambda -1)}{{\lambda }^2-\lambda -1}\le 0.6$ , it is impossible. Therefore, V (A, λ, k₂) =∅.

For k₃ = (1, 3), $\{\begin{array}{c}{x}_1+0.6=\lambda x_1,\hfill \\ x_1+0.5=\lambda x_2,\hfill \\ 0\le x_1\le 0.2,\hfill \\ 0.6\le x_2\le 1.\hfill \end{array}$ We get $x_1=\frac{0.6}{\lambda -1}$ , $x_2=\frac{0.5\lambda +0.1}{\lambda (\lambda -1)}$ and λ - 1 >0. Since $0\le \frac{0.6}{\lambda -1}\le 0.2$ and $0.6\le \frac{0.5\lambda +0.1}{\lambda (\lambda -1)}\le 1$ , it is impossible. Therefore, V (A, λ, k₃) =∅.

For k₄ = (2, 1), $\{\begin{array}{c}{x}_1+x_2=\lambda x_1,\hfill \\ 0.2+x_2=\lambda x_2,\hfill \\ 0.2\le x_1\le 0.4,\hfill \\ 0\le x_2\le 0.5.\hfill \end{array}$ We get $x_1=\frac{0.2}{(\lambda -1{)}^2}$ , $x_2=\frac{0.2}{\lambda -1}$ and λ - 1 >0. Since $0.2\le \frac{0.2}{(\lambda -1{)}^2}\le 0.4$ and $0\le \frac{0.2}{\lambda -1}\le 0.5$ , we have $\frac{\sqrt{2}+2}{2}\le \lambda \le 2$ . Therefore, $V(A,\lambda ,k_4)=\left\{\right(\frac{0.2}{(\lambda -1{)}^2},\frac{0.2}{\lambda -1}\left)\right|\frac{\sqrt{2}+2}{2}\le \lambda \le 2\}.$

For k₅ = (2, 2), $\{\begin{array}{c}{x}_1+x_2=\lambda x_1,\hfill \\ 0.2+0.5=\lambda x_2,\hfill \\ 0.2\le x_1\le 0.4,\hfill \\ 0.5\le x_2\le 0.6.\hfill \end{array}$ We get $x_1=\frac{0.7}{\lambda (\lambda -1)}$ , $x_2=\frac{0.7}{\lambda }$ and λ - 1 >0. Since $0.2\le \frac{0.7}{\lambda (\lambda -1)}\le 0.4$ and $0.5\le \frac{0.7}{\lambda }\le 0.6$ , it is impossible. Therefore, V (A, λ, k₅) = ∅ .

For k₆ = (2, 3), $\{\begin{array}{c}{x}_1+0.6=\lambda x_1,\hfill \\ 0.2+0.5=\lambda x_2,\hfill \\ 0.2\le x_1\le 0.4,\hfill \\ 0.6\le x_2\le 1.\hfill \end{array}$ We get $x_1=\frac{0.6}{\lambda -1}$ , $x_2=\frac{0.7}{\lambda }$ and λ - 1 >0. Since $0.2\le \frac{0.6}{\lambda -1}\le 0.4$ and $0.6\le \frac{0.7}{\lambda }\le 1$ , it is impossible. Therefore, V (A, λ, k₆) = ∅ .

For k₇ = (3, 1), $\{\begin{array}{c}0.4+x_2=\lambda x_1,\hfill \\ 0.2+x_2=\lambda x_2,\hfill \\ 0.4\le x_1\le 1,\hfill \\ 0\le x_2\le 0.5.\hfill \end{array}$ We get $x_1=\frac{0.4\lambda -0.2}{\lambda (\lambda -1)}$ , $x_2=\frac{0.2}{\lambda -1}$ and λ - 1 >0. Since $0.4\le \frac{0.4\lambda -0.2}{\lambda (\lambda -1)}\le 1$ and $0\le \frac{0.2}{\lambda -1}\le 0.5$ , we have $\frac{7}{5}\le \lambda \le \frac{\sqrt{2}+2}{2}$ . Therefore, $V(A,\lambda ,k_7)=\left\{\right(\frac{0.4\lambda -0.2}{\lambda (\lambda -1)},\frac{0.2}{\lambda -1}\left)\right|\frac{7}{5}\le \lambda \le \frac{\sqrt{2}+2}{2}\}.$

For k₈ = (3, 2), $\{\begin{array}{c}0.4+x_2=\lambda x_1,\hfill \\ 0.2+0.5=\lambda x_2,\hfill \\ 0.4\le x_1\le 1,\hfill \\ 0.5\le x_2\le 0.6.\hfill \end{array}$ We get $x_1=\frac{0.4\lambda +0.7}{{\lambda }^2}$ , $x_2=\frac{0.7}{\lambda }$ and λ > 0. Since $0.4\le \frac{0.4\lambda +0.7}{{\lambda }^2}\le 1$ and $0.5\le \frac{0.7}{\lambda }\le 0.6$ , we have $\frac{7}{6}\le \lambda \le \frac{7}{5}$ . Therefore, $V(A,\lambda ,k_8)=\left\{\right(\frac{0.4\lambda +0.7}{{\lambda }^2},\frac{0.7}{\lambda }\left)\right|\frac{7}{6}\le \lambda \le \frac{7}{5}\left)\right\}.$

For k₉ = (3, 3), $\{\begin{array}{c}0.4+0.6=\lambda x_1,\hfill \\ 0.2+0.5=\lambda x_2,\hfill \\ 0.4\le x_1\le 1,\hfill \\ 0.6\le x_2\le 1.\hfill \end{array}$ We get $x_1=\frac{1}{\lambda }$ , $x_2=\frac{0.7}{\lambda }$ and λ > 0. Since $0.4\le \frac{1}{\lambda }\le 1$ and $0.6\le \frac{0.7}{\lambda }\le 1$ , we have $1\le \lambda \le \frac{7}{6}$ . Therefore, $V(A,\lambda ,k_9)=\left\{\right(\frac{1}{\lambda },\frac{0.7}{\lambda }\left)\right|1\le \lambda \le \frac{7}{6}\}.$

Step 3. Output $\begin{array}{ccc}\hfill \Lambda \left(A\right)& \hfill =\hfill & {\bigcup }_{k\in K}\{\lambda \in [0,+\infty \left)\right|V(A,\lambda ,k)\}\hfill \\ \hfill & \hfill =\hfill & \{\lambda \in [0,+\infty \left)\right|V(A,\lambda ,k_1)\}\hfill \\ \hfill & \hfill \hfill & \cup \{\lambda \in [0,+\infty \left)\right|V(A,\lambda ,k_4)\}\hfill \\ \hfill & \hfill \hfill & \cup \{\lambda \in [0,+\infty \left)\right|V(A,\lambda ,k_7)\}\hfill \\ \hfill & \hfill \hfill & \cup \{\lambda \in [0,+\infty \left)\right|V(A,\lambda ,k_8)\}\hfill \\ \hfill & \hfill \hfill & \cup \{\lambda \in [0,+\infty \left)\right|V(A,\lambda ,k_9)\}\hfill \\ \hfill & \hfill =\hfill & \left\{\lambda \right|\lambda =2\}\cup \{\lambda |\frac{\sqrt{2}+2}{2}\le \lambda \le 2\}\hfill \\ \hfill & \hfill \hfill & \cup \left\{\lambda \right|\frac{7}{5}\le \lambda \le \frac{\sqrt{2}+2}{2}\}\hfill \\ \hfill & \hfill \hfill & \cup \left\{\lambda \right|\frac{7}{6}\le \lambda \le \frac{7}{5}\}\cup \{\lambda |1\le \lambda \le \frac{7}{6}\}\hfill \\ \hfill & \hfill =\hfill & \left\{\lambda \right|1\le \lambda \le 2\}\hfill \end{array}$ and $\begin{array}{ccc}\hfill V\left(A\right)& \hfill =\hfill & {\bigcup }_{\lambda \in \Lambda \left(A\right)}V(A,\lambda )\hfill \\ \hfill & \hfill =\hfill & \left\{\right(t,t\left)\right|t\in (0,0.2]\mathrm{and}\lambda =2\}\hfill \\ \hfill & \hfill \hfill & \cup \left\{\right(\frac{0.2}{(\lambda -1{)}^2},\frac{0.2}{\lambda -1}\left)\right|\frac{\sqrt{2}+2}{2}\le \lambda \le 2\}\hfill \\ \hfill & \hfill \hfill & \cup \left\{\right(\frac{0.4\lambda -0.2}{\lambda (\lambda -1)},\frac{0.2}{\lambda -1}\left)\right|\frac{7}{5}\le \lambda \le \frac{\sqrt{2}+2}{2}\}\hfill \\ \hfill & \hfill \hfill & \cup \left\{\right(\frac{0.4\lambda +0.7}{{\lambda }^2},\frac{0.7}{\lambda }\left)\right|\frac{7}{6}\le \lambda \le \frac{7}{5}\}\hfill \\ \hfill & \hfill \hfill & \cup \left\{\right(\frac{1}{\lambda },\frac{0.7}{\lambda }\left)\right|1\le \lambda \le \frac{7}{6}\}.\hfill \end{array}$

4 Constrained eigenproblems of addition-min algebras

In order to satisfy the downloading quality requirements of users and improve the stability of data transmission in the P2P file sharing system, it is worth noting the steady states of the data download quality to the data sending quality under the system (2). Based on such a consideration, we investigate the eigenproblem of matrix in addition-min algebra under the system (2) in this section.

For a given $A\in {\mathcal{I}}^{n\times n}$ , the task of finding a vector $x\in {\mathcal{I}}^n$ with x ≠ θ and a scalar λ satisfying both systems (2) and (3) is called a constrained eigenproblem of addition-min algebra. The scalar λ is called a constrained eigenvalue of A, and the corresponding vector x is called a constrained eigenvector of A associated with λ.

Denoted the set consisting of all constrained eigenvectors of A corresponding to λ by V^* (A, λ) and the set consisting of all constrained eigenvalues of A by Λ^* (A), i.e., $V^{*}(A,\lambda )=\{x\in {\mathcal{I}}^n|A\odot x^T\ge b^T,A\odot x^T=\lambda x^T\mathrm{and}x\ne \theta \}$ and ${\Lambda }^{*}\left(A\right)=\{\lambda \in [0,+\infty \left)\right|V^{*}(A,\lambda )\}.$ We also denote by V^* (A) the set consisting of all constrained eigenvectors of A, i.e., $V^{*}\left(A\right)={\bigcup }_{\lambda \in {\Lambda }^{*}\left(A\right)}{V}^{*}(A,\lambda ).$

From Lemma 2.2, we have $\check{\alpha }\le \hat{\alpha }$ . Therefore, for any j ∈ N there exists an i ∈ N such that ${\check{\alpha }}_j\le a_{\mathit{ij}}$ . In this way, we can give the following definition.

Definition 4.1. For $A=(a_{\mathit{ij}}{)}_{n\times n}\in {\mathcal{I}}^{n\times n}$ and j ∈ N, denote D _j  = {d_0j, d_1j, d_2j, ⋯ , d _{l j j} }, where D _j satisfies the following two conditions:

${\check{\alpha }}_j=d_{0j}<d_{1j}<d_{2j}<\cdots <d_{l_{j}j}=1$ , where d _pj  ∈ {a _ij |i ∈ N} , p = 1, 2, ⋯ , l _j  - 1.

For any i ∈ N, if ${\check{\alpha }}_j\le a_{\mathit{ij}}$ then there exists a unique p ∈ {0, 1, 2, ⋯ , l _j } such that a _ij  = d _pj .

Denote $N^{*}=\{j\in N|{\check{\alpha }}_j=1\}$ and P = {(p₁, p₂, ⋯ , p _n ) |p _j  ∈ P _j  forany j ∈ N} with $P_j=\{\begin{array}{cc}\left\{0\right\},j\in N^{*},\hfill & \hfill \\ \hfill & \hfill \\ \left\{p\right|{\check{\alpha }}_j<d_{\mathit{pj}}\mathrm{and}{d}_{\mathit{pj}}\in D_j\},j\in N\backslash N^{*}.\hfill & \hfill \end{array}$(6)

Then we have the following theorem.

Theorem 4.1. Let $x=(x_1,x_2,\cdots ,x_n)\in {\mathcal{I}}^n$ .Then x ∈ V^* (A, λ) if and only if there exists a p = (p₁, p₂, ⋯ , p _n ) ∈ P such that $\{\begin{array}{cc}{x}_j=d_{0j}=1\mathrm{for}\mathrm{all}j\in N^{*},\hfill & \hfill \\ \hfill & \hfill \\ d_{(p_j-1)j}\le x_j\le d_{p_{j}j}\mathrm{for}\mathrm{all}j\in N\backslash N^{*},\hfill & \hfill \\ \hfill & \hfill \\ \sum _{j\in N^{*}}{a}_{\mathit{ij}}+\sum _{j\in N\backslash N^{*}}[{\gamma }_{\mathit{ij}}·x_j+(1-{\gamma }_{\mathit{ij}})·a_{\mathit{ij}}]\hfill & \hfill \\ \ge b_i\mathrm{for}\mathrm{all}i\in N,\hfill & \hfill \\ \hfill & \hfill \\ \sum _{j\in N^{*}}{a}_{\mathit{ij}}+\sum _{j\in N\backslash N^{*}}[{\gamma }_{\mathit{ij}}·x_j+(1-{\gamma }_{\mathit{ij}})·a_{\mathit{ij}}]\hfill & \hfill \\ =\lambda x_i\mathrm{for}\mathrm{all}i\in N\hfill & \hfill \end{array}$(7) where the operation “·” represents the ordinary multiplication and ${\gamma }_{\mathit{ij}}=\{\begin{array}{c}1,d_{p_{j}j}\le a_{\mathit{ij}},\hfill \\ 0,a_{\mathit{ij}}\le d_{(p_j-1)j}.\hfill \end{array}$

Proof. Suppose that x = (x₁, x₂, ⋯ , x _n ) ∈ V^* (A, λ). From Lemma 2.3, ${\check{\alpha }}_j\le x_j\le 1$ for any j ∈ N, then ${\check{\alpha }}_j=1$ or ${\check{\alpha }}_j<1$ . If ${\check{\alpha }}_j=1$ , then x _j  = 1 and j ∈ N^*. According to Definition 4.1 and Formula (6), p _j  = 0 ∈ P _j and ${\check{\alpha }}_j=x_j=d_{0j}=1$ for any j ∈ N^*. If ${\check{\alpha }}_j<1$ then j ∈ N \ N^*. Thus by Definition 4.1 and Formula (6), ${\check{\alpha }}_j\le d_{(p_j-1)j}\le x_j\le d_{p_{j}j}\le 1$ , i.e., there exists a p _j  ∈ P _j such that d_{(p j -1)j} ≤ x _j  ≤ d _{p j j} for any j ∈ N \ N^*. Therefore, P _j ≠ ∅ for any j ∈ N and $\begin{array}{ccc}\hfill \sum _{j\in N}{a}_{\mathit{ij}}\wedge x_j& \hfill =\hfill & \sum _{j\in N^{*}}{a}_{\mathit{ij}}\wedge x_j+\sum _{j\in N\backslash N^{*}}{a}_{\mathit{ij}}\wedge x_j\hfill \\ \hfill & \hfill =\hfill & \sum _{j\in N^{*}}{a}_{\mathit{ij}}\wedge x_j+\sum _{j\in N\backslash N^{*},d_{p_{j}j}\le a_{\mathit{ij}}}{a}_{\mathit{ij}}\wedge x_j\hfill \\ \hfill & \hfill \hfill & +\sum _{j\in N\backslash N^{*},a_{\mathit{ij}}\le d_{(p_j-1)j}}{a}_{\mathit{ij}}\wedge x_j\hfill \\ \hfill & \hfill =\hfill & \sum _{j\in N^{*}}{a}_{\mathit{ij}}+\sum _{j\in N\backslash N^{*},d_{p_{j}j}\le a_{\mathit{ij}}}{x}_j\hfill \\ \hfill & \hfill \hfill & +\sum _{j\in N\backslash N^{*},a_{\mathit{ij}}\le d_{(p_j-1)j}}{a}_{\mathit{ij}}\hfill \\ \hfill & \hfill =\hfill & \sum _{j\in N^{*}}{a}_{\mathit{ij}}+\sum _{j\in N\backslash N^{*},d_{p_{j}j}\le a_{\mathit{ij}}}{\gamma }_{\mathit{ij}}·x_j\hfill \\ \hfill & \hfill \hfill & +\sum _{j\in N\backslash N^{*},a_{\mathit{ij}}\le d_{(p_j-1)j}}(1-{\gamma }_{\mathit{ij}})·a_{\mathit{ij}}\hfill \\ \hfill & \hfill =\hfill & \sum _{j\in N^{*}}{a}_{\mathit{ij}}+\sum _{j\in N\backslash N^{*}}[{\gamma }_{\mathit{ij}}·x_j+(1-{\gamma }_{\mathit{ij}})·a_{\mathit{ij}}]\hfill \end{array}$ where the operation “ · " represents the ordinary multiplication and ${\gamma }_{\mathit{ij}}=\{\begin{array}{c}1,d_{p_{j}j}\le a_{\mathit{ij}},\hfill \\ 0,a_{\mathit{ij}}\le d_{(p_j-1)j}.\hfill \end{array}$

Because of x = (x₁, x₂, ⋯ , x _n ) ∈ V^* (A, λ), we have b _i  ≤ ∑_j∈Na _ij  ∧ x _j  = ∑_j∈N^*a _ij  + ∑_j∈N\N^* [γ _ij  · x _j  + (1 - γ _ij ) · a _ij ] and λx _i  = ∑_j∈Na _ij  ∧ x _j  = ∑_j∈N^*a _ij  + ∑_j∈N\N^* [γ _ij  · x _j  + (1 - γ _ij ) · a _ij ] for any i ∈ N, i.e., ∑_j∈N^*a _ij  + ∑_j∈N\N^* [γ _ij  · x _j  + (1 - γ _ij ) · a _ij ] ≥ b _i and ∑_j∈N^*a _ij  + ∑_j∈N\N^* [γ _ij  · x _j  + (1 - γ _ij ) · a _ij ] = λx _i for all i ∈ N.

Conversely, suppose that there exists a p = (p₁, p₂, ⋯ , p _n ) ∈ P such that x satisfies the system (5). Then $\begin{array}{ccc}\hfill & \hfill \hfill & \sum _{j\in N^{*}}{a}_{\mathit{ij}}+\sum _{j\in N\backslash N^{*}}[{\gamma }_{\mathit{ij}}·x_j+(1-{\gamma }_{\mathit{ij}})·a_{\mathit{ij}}]\hfill \\ \hfill & \hfill =\hfill & \sum _{j\in N^{*}}{a}_{\mathit{ij}}+\sum _{j\in N\backslash N^{*},d_{p_{j}j}\le a_{\mathit{ij}}}{\gamma }_{\mathit{ij}}·x_j\hfill \\ \hfill & \hfill \hfill & +\sum _{j\in N\backslash N^{*},a_{\mathit{ij}}\le d_{(p_j-1)j}}(1-{\gamma }_{\mathit{ij}})·a_{\mathit{ij}}\hfill \\ \hfill & \hfill =\hfill & \sum _{j\in N^{*}}{a}_{\mathit{ij}}+\sum _{j\in N\backslash N^{*},d_{p_{j}j}\le a_{\mathit{ij}}}{x}_j+\sum _{j\in N\backslash N^{*},a_{\mathit{ij}}\le d_{(p_j-1)j}}{a}_{\mathit{ij}}\hfill \\ \hfill & \hfill =\hfill & \sum _{j\in N^{*}}{a}_{\mathit{ij}}\wedge x_j+\sum _{j\in N\backslash N^{*},d_{p_{j}j}\le a_{\mathit{ij}}}{a}_{\mathit{ij}}\wedge x_j\hfill \\ \hfill & \hfill \hfill & +\sum _{j\in N\backslash N^{*},a_{\mathit{ij}}\le d_{(p_j-1)j}}{a}_{\mathit{ij}}\wedge x_j\hfill \\ \hfill & \hfill =\hfill & \sum _{j\in N^{*}}{a}_{\mathit{ij}}\wedge x_j+\sum _{j\in N\backslash N^{*}}{a}_{\mathit{ij}}\wedge x_j\hfill \\ \hfill & \hfill =\hfill & \sum _{j\in N}{a}_{\mathit{ij}}\wedge x_j.\hfill \end{array}$ Since b _i  ≤ ∑_j∈N^*a _ij  + ∑_j∈N\N^* [γ _ij  · x _j  + (1 - γ _ij ) · a _ij ] = ∑_j∈Na _ij  ∧ x _j and λx _i  = ∑_j∈N^*a _ij  + ∑_j∈N\N^* [γ _ij  · x _j  + (1 - γ _ij ) · a _ij ] = ∑_j∈Na _ij  ∧ x _j for any i ∈ N, we have x ∈ V^* (A, λ). □

Noting that in Theorem 4.1, λ can be seen as a given constant with λ ∈ [0, + ∞). So that every solution x = (x₁, x₂, ⋯ , x _n ) of system (5) can be represented by λ, and the corresponding λ can be determined by the x = (x₁, x₂, ⋯ , x _n ) since x _j  = d_0j = 1 forall j ∈ N^* and d_{(p j -1)j} ≤ x _j  ≤ d _{p j j}  forall j ∈ N \ N^*.

The proof of Theorem 4.1 implies the following two theorems.

Theorem 4.2. If the system (5) is unsolvable for any p = (p₁, p₂, ⋯ , p _n ) ∈ P, then V^* (A, λ) =∅.

Theorem 4.3. For any p = (p₁, p₂, ⋯ , p _n ) ∈ P, if x = (x₁, x₂, ⋯ , x _n ) satisfies the system (5), then x ∈ V^* (A, λ).

For any p = (p₁, p₂, ⋯ , p _n ) ∈ P, denote the solution set of system (7) corresponding to p = (p₁, p₂, ⋯ , p _n ) ∈ P by V^* (A, λ, p). Then from Theorems 4.1 and 4.3, the constrained eigenproblems of addition-min algebras are equivalent to solving the system (7). So that we can summarize an algorithm to find all the constrained eigenvectors and eigenvalues of A as follows.

Algorithm 2

Input: A = (a _ij ) _n×n and b.

Output: Λ^* (A) and V^* (A).

Step 1. If (1, 1, ⋯ , 1) isn’t a solution of system (2) then Λ^* (A) =∅, V^* (A) =∅ and stop.

Step 2. Compute P = {(p₁, p₂, ⋯ , p _n ) |p _j  ∈ P _j  forany j ∈ N} defined by (6).

Step 3. For any p = (p₁, p₂, ⋯ , p _n ) ∈ P, construct the corresponding system (5).

Step 4. Compute V^* (A, λ, p) by the corresponding system (5).

Step 5. Λ^* (A) = ⋃ _p∈P {λ ∈ [0, + ∞) |V^* (A, λ, p)} and V^* (A) = ⋃  _λ∈Λ^*(A)V^* (A, λ).

Theorem 4.4. Algorithm 2 terminates after O ((n + 1)  ⁿ ) operations.

Proof. Similar to the proof of Theorem 3.4, one can prove that Algorithm 2 terminates after O ((n + 1)  ⁿ ) operations since Step 3 is the key process of Algorithm 2 and |P| ≤ (n + 1)  ⁿ . □

The following example illustrates Algorithm 2.

Example 4.1. Consider the following system: $\{\begin{array}{c}0.4\wedge x_1+0.6\wedge x_2\ge 0.8,\hfill \\ 0.2\wedge x_1+0.5\wedge x_2\ge 0.5,\hfill \\ 0.4\wedge x_1+0.6\wedge x_2=\lambda x_1,\hfill \\ 0.2\wedge x_1+0.5\wedge x_2=\lambda x_2.\hfill \\ \hfill \end{array}$

Step 1. (1, 1, ⋯ , 1) is a solution of system (2).

Step 2. By ${\check{\alpha }}_1=0.2$ and ${\check{\alpha }}_2=0.4$ . we have P₁ = {1, 2} and P₂ = {1, 2, 3}. $\begin{array}{c}\hfill P=\left\{\right(1,1),(1,2),(1,3),(2,1),(2,2),(2,3\left)\right\}.\end{array}$

Step 3. Construct and solve the corresponding system (5):

For p₁ = (1, 1), $\{\begin{array}{c}{x}_1+x_2\ge 0.8,\hfill \\ 0.2+x_2\ge 0.5,\hfill \\ x_1+x_2=\lambda x_1,\hfill \\ 0.2+x_2=\lambda x_2,\hfill \\ 0.2\le x_1\le 0.4,\hfill \\ 0.4\le x_2\le 0.5.\hfill \end{array}$ We get $x_1=\frac{0.2}{(\lambda -1{)}^2}$ , $x_2=\frac{0.2}{\lambda -1}$ and λ - 1 >0. Since $0.2\le \frac{0.2}{(\lambda -1{)}^2}\le 0.4$ , $0.4\le \frac{0.2}{\lambda -1}\le 0.5$ and $\frac{0.2}{(\lambda -1{)}^2}+\frac{0.2}{\lambda -1}\ge 0.8$ , it is impossible. Therefore, V^* (A, λ, p₁) = ∅ .

For p₂ = (1, 2), $\{\begin{array}{c}{x}_1+x_2\ge 0.8,\hfill \\ 0.2+0.5\ge 0.5,\hfill \\ x_1+x_2=\lambda x_1,\hfill \\ 0.2+0.5=\lambda x_2,\hfill \\ 0.2\le x_1\le 0.4,\hfill \\ 0.5\le x_2\le 0.6.\hfill \end{array}$ We get $x_1=\frac{0.7}{\lambda (\lambda -1)}$ , $x_2=\frac{0.7}{\lambda }$ and λ - 1 >0. Since $0.2\le \frac{0.7}{\lambda (\lambda -1)}\le 0.4$ , $0.5\le \frac{0.7}{\lambda }\le 0.6$ and $\frac{0.7}{\lambda (\lambda -1)}+\frac{0.7}{\lambda }\ge 0.8$ , it is impossible. Therefore, V^* (A, λ, p₂) = ∅ .

For p₃ = (1, 3), $\{\begin{array}{c}{x}_1+0.6\ge 0.8,\hfill \\ 0.2+0.5\ge 0.5,\hfill \\ x_1+0.6=\lambda x_1,\hfill \\ 0.2+0.5=\lambda x_2,\hfill \\ 0.2\le x_1\le 0.4,\hfill \\ 0.6\le x_2\le 1.\hfill \end{array}$ We get $x_1=\frac{0.6}{\lambda -1}$ , $x_2=\frac{0.7}{\lambda }$ and λ - 1 >0. Since $0.2\le \frac{0.6}{\lambda -1}\le 0.4$ and $0.6\le \frac{0.7}{\lambda }\le 1$ , it is impossible. Therefore, V^* (A, λ, p₃) = ∅ .

For p₄ = (2, 1), $\{\begin{array}{c}0.4+x_2\ge 0.8,\hfill \\ 0.2+x_2\ge 0.5,\hfill \\ 0.4+x_2=\lambda x_1,\hfill \\ 0.2+x_2=\lambda x_2,\hfill \\ 0.4\le x_1\le 1,\hfill \\ 0.4\le x_2\le 0.5.\hfill \end{array}$ We get $x_1=\frac{0.4\lambda -0.2}{\lambda (\lambda -1)}$ , $x_2=\frac{0.2}{\lambda -1}$ and λ - 1 >0. Since $0.4\le \frac{0.4\lambda -0.2}{\lambda (\lambda -1)}\le 1$ and $0.4\le \frac{0.2}{\lambda -1}\le 0.5$ , we have $\frac{7}{5}\le \lambda \le \frac{3}{2}$ . Therefore, $V^{*}(A,\lambda ,p_4)=\left\{\right(\frac{0.4\lambda -0.2}{\lambda (\lambda -1)},\frac{0.2}{\lambda -1}\left)\right|\frac{7}{5}\le \lambda \le \frac{3}{2}\}.$

For p₅ = (2, 2), $\{\begin{array}{c}0.4+x_2\ge 0.8,\hfill \\ 0.2+0.5\ge 0.5,\hfill \\ 0.4+x_2=\lambda x_1,\hfill \\ 0.2+0.5=\lambda x_2,\hfill \\ 0.4\le x_1\le 1,\hfill \\ 0.5\le x_2\le 0.6.\hfill \end{array}$ We get $x_1=\frac{0.4\lambda +0.7}{{\lambda }^2}$ , $x_2=\frac{0.7}{\lambda }$ and λ > 0. Since $0.4\le \frac{0.4\lambda +0.7}{{\lambda }^2}\le 1$ and $0.5\le \frac{0.7}{\lambda }\le 0.6$ , we have $\frac{7}{6}\le \lambda \le \frac{7}{5}$ . Therefore, $V^{*}(A,\lambda ,p_5)=\left\{\right(\frac{0.4\lambda +0.7}{{\lambda }^2},\frac{0.7}{\lambda }\left)\right|\frac{7}{6}\le \lambda \le \frac{7}{5}\left)\right\}.$

For p₆ = (2, 3), $\{\begin{array}{c}0.4+0.6\ge 0.8,\hfill \\ 0.2+0.5\ge 0.5,\hfill \\ 0.4+0.6=\lambda x_1,\hfill \\ 0.2+0.5=\lambda x_2,\hfill \\ 0.4\le x_1\le 1,\hfill \\ 0.6\le x_2\le 1.\hfill \end{array}$ We get $x_1=\frac{1}{\lambda }$ , $x_2=\frac{0.7}{\lambda }$ and λ > 0. Since $0.4\le \frac{1}{\lambda }\le 1$ and $0.6\le \frac{0.7}{\lambda }\le 1$ , we have $1\le \lambda \le \frac{7}{6}$ . Therefore, $V^{*}(A,\lambda ,p_6)=\left\{\right(\frac{1}{\lambda },\frac{0.7}{\lambda }\left)\right|1\le \lambda \le \frac{7}{6}\}.$

Step 4. Output $\begin{array}{ccc}\hfill {\Lambda }^{*}\left(A\right)& \hfill =\hfill & {\bigcup }_{p\in P}\{\lambda \in [0,+\infty \left)\right|V^{*}(A,\lambda ,p)\}\hfill \\ \hfill & \hfill =\hfill & \{\lambda \in [0,+\infty \left)\right|V^{*}(A,\lambda ,p_4)\}\hfill \\ \hfill & \hfill \hfill & \cup \{\lambda \in [0,+\infty \left)\right|V^{*}(A,\lambda ,p_5)\}\hfill \\ \hfill & \hfill \hfill & \cup \{\lambda \in [0,+\infty \left)\right|V^{*}(A,\lambda ,p_6)\}\hfill \\ \hfill & \hfill =\hfill & \left\{\lambda \right|\frac{7}{5}\le \lambda \le \frac{3}{2}\}\cup \{\lambda |\frac{7}{6}\le \lambda \le \frac{7}{5})\}\hfill \\ \hfill & \hfill \hfill & \cup \left\{\lambda \right|1\le \lambda \le \frac{7}{6}\}\hfill \\ \hfill & \hfill =\hfill & \left\{\lambda \right|1\le \lambda \le \frac{3}{2}\}\hfill \end{array}$ and $\begin{array}{ccc}\hfill V^{*}\left(A\right)& \hfill =\hfill & {\bigcup }_{\lambda \in {\Lambda }^{*}\left(A\right)}{V}^{*}(A,\lambda )\hfill \\ \hfill & \hfill =\hfill & \left\{\right(\frac{0.4\lambda -0.2}{\lambda (\lambda -1)},\frac{0.2}{\lambda -1}\left)\right|\frac{7}{5}\le \lambda \le \frac{3}{2}\}\hfill \\ \hfill & \hfill \hfill & \cup \left\{\right(\frac{0.4\lambda +0.7}{{\lambda }^2},\frac{0.7}{\lambda }\left)\right|\frac{7}{6}\le \lambda \le \frac{7}{5}\left)\right\}\hfill \\ \hfill & \hfill \hfill & \cup \left\{\right(\frac{1}{\lambda },\frac{0.7}{\lambda }\left)\right|1\le \lambda \le \frac{7}{6}\}.\hfill \end{array}$

5 Supereigenproblems of addition-min algebras

In order to improve the enthusiasm of the terminals, Yang et al. [25] considered the ratio of the data-download quality to the data-sending quality, i.e., they introduced a supereigenproblem of addition-min algebra $A\odot x^T\ge \lambda x^T$(8) where A = (a _ij ) _n×n with a _ii  = 0 for all i ∈ N. They obtained a finite number of the supereigenvectors of system (8) associated with a given supereigenvalue λ ∈ (0, n - 1]. They further investigated a constrained supereigenproblem of addition-min algebra, more specific speaking, they studied the maximum constrained supereigenvalue and the corresponding constrained supereigenvector under the system (2), i.e., $\begin{array}{cc}\hfill & \max \lambda \hfill \\ \hfill & \mathrm{s}.\mathrm{t}.\{\begin{array}{c}A\odot x^T\ge b^T,\hfill \\ A\odot x^T\ge \lambda x^T\hfill \end{array}\hfill \end{array}$(9) where A = (a _ij ) _n×n with a _ii  = 0 for all i ∈ N. They developed a nonlinear programming approach to find the unique maximum constrained supereigenvalue and one corresponding constrained supereigenvector of system (9). In this section, we make Algorithm 1 be suitable for characterizing the feasible region of all the supereigenvectors of system (8) associated with a given supereigenvalue λ ∈ (0, n - 1], and present an algorithm to obtain the maximum constrained supereigenvalue and the feasible region of all the corresponding constrained supereigenvectors of system (9).

Just replacing A ⊙ x ^T  = λx ^T by A ⊙ x ^T  ≥ λx ^T , and ^′ = ′ in the corresponding content of Section 3 by ^′ ≥ ′, one can easily prove that both the corresponding Theorems 3.1 and 3.3 hold, and Algorithm 1 is suitable for describing the feasible region of all the supereigenvectors of system (8) associated with a given supereigenvalue λ ∈ (0, n - 1]. We omit the detail and only use the following example to illustrated it.

Example 5.1. Consider the feasible region of all the supereigenvectors of the following system with λ = 1: $\{\begin{array}{c}0\wedge x_1+0.6\wedge x_2\ge x_1,\hfill \\ 0.4\wedge x_1+0\wedge x_2\ge x_2.\hfill \end{array}$

Step 1. Compute K₁ = {1, 2} and K₂ = {1, 2}. Then $\begin{array}{c}\hfill K=\left\{\right(1,1),(1,2),(2,1),(2,2\left)\right\}.\end{array}$ Step 2. Construct and solve the corresponding system (5) (replacing ^′ = ′ of system (5) by ^′ ≥ ′):

For k₁ = (1, 1), $\{\begin{array}{c}{x}_2\ge x_1,\hfill \\ x_1\ge x_2,\hfill \\ 0\le x_1\le 0.4,\hfill \\ 0\le x_2\le 0.6.\hfill \end{array}$ We get x₁ = x₂. Let x₁ = x₂ = t. Since 0 ≤ x₁ ≤ 0.4 and 0 ≤ x₂ ≤ 0.6, we have t ∈ (0, 0.4]. Therefore, the feasible region in this case is {(t, t) |t ∈ (0, 0.4]}.

For k₂ = (1, 2), $\{\begin{array}{c}0.6\ge x_1,\hfill \\ x_1\ge x_2,\hfill \\ 0\le x_1\le 0.4,\hfill \\ 0.6\le x_2\le 1.\hfill \end{array}$ Obviously, it is impossible.

For k₃ = (2, 1), $\{\begin{array}{c}{x}_2\ge x_1,\hfill \\ 0.4\ge x_2,\hfill \\ 0.4\le x_1\le 1,\hfill \\ 0\le x_2\le 0.6.\hfill \end{array}$ We get x₁ = 0.4, x₂ = 0.4. Then the feasible region in this case is {(0.4, 0.4)}.

For k₄ = (2, 2), $\{\begin{array}{c}0.6\ge x_1,\hfill \\ 0.4\ge x_2,\hfill \\ 0.4\le x_1\le 1,\hfill \\ 0.6\le x_2\le 1.\hfill \end{array}$ Obviously, it is impossible.

Step 3. The feasible region of all the supereigenvectors associated with λ = 1 is {(t, t) |t ∈ (0, 0.4]}.

In what follows, we suggest an algorithm to obtain the maximum constrained supereigenvalue and the feasible region of all the corresponding constrained supereigenvectors of system (9).

From the proof of Theorem 4.1, for any solution x of system (9) there exists a corresponding p = (p₁, p₂, ⋯ , p _n ) ∈ P such that $\begin{array}{cc}\hfill \{\begin{array}{c}{x}_j=d_{0j}=1\mathrm{for}\mathrm{all}j\in N^{*},\hfill \\ d_{(p_j-1)j}\le x_j\le d_{p_{j}j}\mathrm{for}\mathrm{all}j\in N\backslash N^{*},\hfill \\ \sum _{j\in N}{a}_{\mathit{ij}}\wedge x_j=\sum _{j\in N^{*}}{a}_{\mathit{ij}}+\sum _{j\in N\backslash N^{*}}[{\gamma }_{\mathit{ij}}·x_j\hfill \\ +(1-{\gamma }_{\mathit{ij}})·a_{\mathit{ij}}]\mathrm{for}\mathrm{all}i\in N.\hfill \end{array}& \hfill \end{array}$ Thus the system (9) corresponding to p = (p₁, p₂, ⋯ , p _n ) ∈ P can be written as follows.

$\begin{array}{cc}\hfill & max\lambda \hfill \\ \hfill & \mathrm{s}.\mathrm{t}.\{\begin{array}{c}{x}_j=d_{0j}=1\mathrm{for}\mathrm{all}j\in N^{*},\hfill \\ \hfill \\ d_{(p_j-1)j}\le x_j\le d_{p_{j}j}\hfill \\ \mathrm{for}\mathrm{all}j\in N\backslash N^{*},\hfill \\ \hfill \\ \sum _{j\in N^{*}}{a}_{\mathit{ij}}+\sum _{j\in N\backslash N^{*}}[{\gamma }_{\mathit{ij}}·x_j+\hfill \\ (1-{\gamma }_{\mathit{ij}})·a_{\mathit{ij}}]\ge b_i\mathrm{for}\mathrm{all}i\in N,\hfill \\ \hfill \\ \sum _{j\in N^{*}}{a}_{\mathit{ij}}+\sum _{j\in N\backslash N^{*}}[{\gamma }_{\mathit{ij}}·x_j+\hfill \\ (1-{\gamma }_{\mathit{ij}})·a_{\mathit{ij}}]\ge \lambda x_i\mathrm{for}\mathrm{all}i\in N\hfill \end{array}\hfill \end{array}$(10) where the operation “ · " represents the ordinary multiplication and ${\gamma }_{\mathit{ij}}=\{\begin{array}{c}1,d_{p_{j}j}\le a_{\mathit{ij}},\hfill \\ 0,a_{\mathit{ij}}\le d_{(p_j-1)j}.\hfill \end{array}$

For any p = (p₁, p₂, ⋯ , p _n ) ∈ P, denote the local optimal maximum constrained supereigenvalue of system (8) by λ (p) and the corresponding feasible region of the constrained supereigenvectors by V⁰ (A, λ (p) , p). Then the maximum constrained supereigenvalue λ = max {λ (p) |p ∈ P} and the feasible region of all the corresponding constrained supereigenvectors V⁰ (A, λ) = ⋃  _λ=λ(p)V⁰ (A, λ (p) , p) where λ (p) can be computed by using the software LINGO or MATLAB. We can summarize an algorithm to find the maximum constrained supereigenvalue and the feasible region of all the corresponding constrained supereigenvectors of A as follows.

Algorithm 3

Input: A = (a _ij ) _n×n and b.

Output: λ and V⁰ (A, λ).

Step 1. If (1, 1, ⋯ , 1) isn’t a solution of system (2) then λ doesn’t exist, V⁰ (A, λ) =∅ and stop.

Step 2. Compute P = {(p₁, p₂, ⋯ , p _n ) |p _j  ∈ P _j  forany j ∈ N} defined by (6).

Step 3. For any p = (p₁, p₂, ⋯ , p _n ) ∈ P, construct the corresponding system (10).

Step 4. Solve the corresponding system (10), and obtain λ (p) by the software LINGO or MATLAB and V⁰ (A, λ (p) , p).

Step 5. λ = max {λ (p) |p ∈ P} and V⁰ (A, λ) = ⋃  _λ=λ(p)V⁰ (A, λ (p) , p).

Notice that similar to Theorem 4.4, one can see that Algorithm 3 terminates after O ((n + 1)  ⁿ ) operations.

Example 5.2. Consider the following problem: $\begin{array}{cc}\hfill & \mathit{max}\lambda \hfill \\ \hfill & \mathit{s}.\mathit{t}.\{\begin{array}{c}0\wedge x_1+0.6\wedge x_2\ge 0.2,\hfill \\ 0.4\wedge x_1+0\wedge x_2\ge 0.3,\hfill \\ 0\wedge x_1+0.6\wedge x_2\ge \lambda x_1,\hfill \\ 0.4\wedge x_1+0\wedge x_2\ge \lambda x_2.\hfill \end{array}\hfill \end{array}$

Step 1. (1, 1, ⋯ , 1) is a solution of system (2).

Step 2. By ${\check{\alpha }}_1=0$ and ${\check{\alpha }}_2=0$ , we have P₁ = {1, 2} and P₂ = {1, 2}. Then $\begin{array}{c}\hfill P=\left\{\right(1,1),(1,2),(2,1),(2,2\left)\right\}.\end{array}$ Step 3. Construct and solve the corresponding system (10):

For p₁ = (1, 1), $\begin{array}{cc}\hfill & max\lambda \hfill \\ \hfill & \mathrm{s}.\mathrm{t}.\{\begin{array}{c}{x}_2\ge 0.2,\hfill \\ x_1\ge 0.3,\hfill \\ x_2\ge \lambda x_1,\hfill \\ x_1\ge \lambda x_2,\hfill \\ 0\le x_1\le 0.4,\hfill \\ 0\le x_2\le 0.6.\hfill \end{array}\hfill \end{array}$ By MATLAB, λ (p₁) =1. Then x₁ = x₂. Let x₁ = x₂ = t. Since 0.3 ≤ x₁ ≤ 0.4 and 0.2 ≤ x₂ ≤ 0.6, we have 0.3 ≤ t ≤ 0.4. Therefore, V⁰ (A, 1, p₁) = {(t, t) |t ∈ [0.3, 0.4]}.

For p₂ = (1, 2), $\begin{array}{cc}\hfill & \max \lambda \hfill \\ \hfill & \mathrm{s}.\mathrm{t}.\{\begin{array}{c}0.6\ge 0.2,\hfill \\ x_1\ge 0.3,\hfill \\ 0.6\ge \lambda x_1,\hfill \\ x_1\ge \lambda x_2,\hfill \\ 0\le x_1\le 0.4,\hfill \\ 0.6\le x_2\le 1.\hfill \end{array}\hfill \end{array}$ By MATLAB, $\lambda \left(p_2\right)=\frac{2}{3}$ . Then $0.6\ge \frac{2}{3}{x}_1$ and $x_1\ge \frac{2}{3}{x}_2$ . Since 0.3 ≤ x₁ ≤ 0.4 and 0.6 ≤ x₂ ≤ 1, we have x₁ = 0.4 and x₂ = 0.6. Therefore, $V^0(A,\frac{2}{3},p_2)=\left\{\right(0.4,0.6\left)\right\}$ .

For p₃ = (2, 1), $\begin{array}{cc}\hfill & \max \lambda \hfill \\ \hfill & \mathrm{s}.\mathrm{t}.\{\begin{array}{c}{x}_2\ge 0.2,\hfill \\ 0.4\ge 0.3,\hfill \\ x_2\ge \lambda x_1,\hfill \\ 0.4\ge \lambda x_2,\hfill \\ 0.4\le x_1\le 1,\hfill \\ 0\le x_2\le 0.6.\hfill \end{array}\hfill \end{array}$ By MATLAB, λ (p₃) =1. Then x₂ ≥ x₁ and 0.4 ≥ x₂. Since 0.4 ≤ x₁ ≤ 1 and 0 ≤ x₂ ≤ 0.4, we have x₁ = x₂ = 0.4. Therefore, V⁰ (A, 1, p₃) = {(0.4, 0.4)}.

For p₄ = (2, 2), $\begin{array}{cc}\hfill & \max \lambda \hfill \\ \hfill & \mathrm{s}.\mathrm{t}.\{\begin{array}{c}0.6\ge 0.2,\hfill \\ 0.4\ge 0.3,\hfill \\ 0.6\ge \lambda x_1,\hfill \\ 0.4\ge \lambda x_2,\hfill \\ 0.4\le x_1\le 1,\hfill \\ 0.6\le x_2\le 1.\hfill \end{array}\hfill \end{array}$ By MATLAB, $\lambda \left(p_4\right)=\frac{2}{3}$ . Then $0.6\ge \frac{2}{3}{x}_1$ and $0.4\ge \frac{2}{3}{x}_2$ . Since 0.4 ≤ x₁ ≤ 1 and 0.6 ≤ x₂ ≤ 1, we have 0.4 ≤ x₁ ≤ 0.9 and x₂ = 0.6. Let x₁ = t. Then $V^0(A,\frac{2}{3},p_4)=\left\{\right(t,0.6\left)\right|t\in [0.4,0.9]\}$ .

Step 4. Output $\lambda =max\left\{\lambda \right(p\left)\right|p\in P\}=1$ and $\begin{array}{ccc}\hfill V^0(A,1)& \hfill =\hfill & {\bigcup }_{\lambda \left(p\right)=1}{V}^0(A,\lambda (p),p)\hfill \\ \hfill & \hfill =\hfill & V^0(A,1,p_1)\cup V^0(A,1,p_3)\hfill \\ \hfill & \hfill =\hfill & \left\{\right(t,t\left)\right|t\in [0.3,0.4]\}.\hfill \end{array}$

6 Concluding remark

In this article, we first investigated the eigenproblems of addition-min algebras and showed Algorithm 1 for finding all the eigenvalues and eigenvectors for a given matrix. Then, we studied the constrained eigenproblems of addition-min algebras and proposed Algorithm 2 for computing all the constrained eigenvectors and eigenvalues for a given matrix. We finally discussed the supereigenproblems of addition-min algebras and suggested Algorithm 3 for obtaining the maximum constrained supereigenvalue and depicting the feasible region of all the constrained supereigenvectors for a given matrix. Since the computational complexity of our algorithms is O ((n + 1)  ⁿ ), they may involve a heavy and complicated work when n is a larger number. Therefore, finding an efficient method for the eigenproblems (resp. the constrained eigenproblems and the supereigenproblems) of addition-min algebras is an interesting problem in the future.

Acknowledgments

The authors are grateful to the responsible editor and the anonymous referees for their valuable comments and suggestions, which help the authors to improve the earlier version.